Gorjan Alagic Postdoctoral Scholar Annenberg 102 Institute for Quantum Information and Matter California Institute of Technology |
A Marcinkiewicz-Zygmund inequality for compact groups (with Leonard Schulman and Alex Russell), in preparation (2013). In the setting of compact groups, a quadrature rule (or design) is a finite weighted set of group elements which can take the place of Haar measure when integrating functions belonging to a certain Fourier band limit. Quadrature rules are essential ingredients in basic computational tasks such as computing Fourier transforms or extrapolating function values outside a sample set. In this work, we study the size and numerical stability of general quadrature rules on arbitrary compact groups. We provide an upper bound on the minimal number of Haar-random samples necessary to reconstruct functions within a given band. We show that the weights in these random quadrature rules are close to uniform, and provide various error estimates. One consequence of our results is a Marcinkiewicz-Zygmund inequality for random sampling with uniform weights, which holds for any compact group and any band limit. |
|||
Quantum and classical circuit obfuscation with braids. [ arxiv/quant-ph ] (with Stacey Jeffery and Stephen Jordan), preprint (2013). A circuit obfuscator is an algorithm that translates circuits into functionally-equivalent similarly-sized circuits that are hard to understand. The existence of strong obfuscators would have wide-ranging consequences for cryptography, e.g., enabling us to turn private-key encryption into public-key encryption or data encryption into fully homomorphic encryption. In this work, we propose circuit obfuscation algorithms (for both logic circuits and quantum circuits) based on representations of braid groups. We define one obfuscator that satisfies a natural notion of ``partial indistinguishability obfuscation,'' and another obfuscator whose hardness is related to braid conjugator search. We also investigate two potential applications: blind computation on encrypted data, and testing computational devices for quantumness. |
|||
Quantum algorithms for invariants of triangulated manifolds. [ arxiv/quant-ph ] (with undergraduate student Edgar Bering), in Quantum Information and Computation (2012). One of the apparent advantages of quantum computers over their classical counterparts is their ability to efficiently contract tensor networks. In this article, we study some implications of this fact in the case of topological tensor networks. The graph underlying these networks is given by the triangulation of a manifold, and the structure of the tensors ensures that the overall tensor is independent of the choice of internal triangulation. This leads to quantum algorithms for additively approximating certain invariants of triangulated manifolds. We discuss the details of this construction in two specific cases. In the first case, we consider triangulated surfaces, where the triangle tensor is defined by the multiplication operator of a finite group; the resulting invariant has a simple closed-form expression involving the dimensions of the irreducible representations of the group and the Euler characteristic of the surface. In the second case, we consider triangulated 3-manifolds, where the tetrahedral tensor is defined by the so-called Fibonacci anyon model; the resulting invariant is the well-known Turaev-Viro invariant of 3-manifolds. |
|||
Approximating the Turaev-Viro invariant of mapping tori is complete for one clean qubit. [ arxiv/quant-ph ] (with Stephen Jordan), in the Proceedings of TQC (2011). The Turaev-Viro invariants are scalar topological invariants of three-dimensional manifolds. Here we show that the problem of estimating the Fibonacci version of the Turaev-Viro invariant of a mapping torus is a complete problem for the one clean qubit complexity class (DQC1). This complements a previous result showing that estimating the Turaev-Viro invariant for arbitrary manifolds presented as Heegaard splittings is a complete problem for the standard quantum computation model (BQP). We also discuss a beautiful analogy between these results and previously known results on the computational complexity of approximating the Jones polynomial. |
|||
Spectral Concentration of Positive Functions on Compact Groups. [ JFAA ] (with Alexander Russell), in Journal of Fourier Analysis and Applications (2011). The problem of understanding the Fourier-analytic structure of the cone of positive functions on a group has a long history. In this article, we develop the first quantitative spectral concentration results for such functions over arbitrary compact groups. Specifically, we describe a family of finite, positive quadrature rules for the Fourier coefficients of band-limited functions on a compact group. We apply these quadrature rules to prove a spectral concentration result for positive functions: given nested band limits A, B with A a subset of B, we prove a lower bound on the fraction of L^2-mass that any B-band-limited positive function has in A. Our bounds are explicit and depend only on elementary properties of A and B; they are the first such bounds that apply to arbitrary compact groups. These bounds also apply to finite groups, where the quadrature rule is given by the Fourier transform on the smallest quotient whose dual contains the Fourier support of the function. |
|||
Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation. [ arxiv/quant-ph | PRA ] (with Stephen Jordan, Robert Koenig, and Ben Reichardt), in Physical Review A (2010). The Turaev-Viro invariants are scalar topological invariants of compact, orientable 3-manifolds. We give a quantum algorithm for additively approximating Turaev-Viro invariants of a manifold presented by a Heegaard splitting. The algorithm is motivated by the relationship between topological quantum computers and (2+1)-D topological quantum field theories. Its accuracy is shown to be nontrivial, as the same algorithm, after efficient classical preprocessing, can solve any problem efficiently decidable by a quantum computer. Thus approximating certain Turaev-Viro invariants of manifolds presented by Heegaard splittings is a universal problem for quantum computation. This establishes a novel relation between the task of distinguishing non-homeomorphic 3-manifolds and the power of a general quantum computer. |
|||
Quantum Algorithms for Simon's Problem over General Groups.
[ arXiv/quant-ph | TALG ] (with Cristopher Moore and Alexander Russell), in ACM Transactions on Algorithms (2009) and Proceedings of SODA (2007). Daniel Simon's 1994 discovery of an efficient quantum algorithm for solving the hidden subgroup problem (HSP) over Z_2^n provided one of the first algebraic problems for which quantum computers are exponentially faster than their classical counterparts. In this paper, we study the generalization of Simon's problem to arbitrary groups. Fixing a finite group G, this is the problem of recovering an involution m = (m_1, ..., m_n) in G^n from an oracle f with the property that f(x) = f(xy) iff y equals m or the identity. In the current parlance, this is the hidden subgroup problem (HSP) over groups of the form G^n, where G is a nonabelian group of constant size, and where the hidden subgroup is either trivial or has order two. Although groups of the form G^n have a simple product structure, they share important representation-theoretic properties with the symmetric groups S_n, where a solution to the HSP would yield a quantum algorithm for Graph Isomorphism. In particular, solving their HSP with the so-called ``standard method'' requires highly entangled measurements on the tensor product of many coset states. Here we give quantum algorithms with time complexity 2^O(sqrt(n log n)) that recover hidden involutions m = (m_1, ..., m_n) in G^n where, as in Simon's problem, each m_i is either the identity or the conjugate of a known element k, and there is a character X of G for which X(k) = -X(1). Our approach combines the general idea behind Kuperberg's sieve for dihedral groups with the ``missing harmonic'' approach of Moore and Russell. These are the first nontrivial hidden subgroup algorithms for group families that require highly entangled multiregister Fourier sampling. |
|||
Uncertainty Principles for Compact Groups. [ arXiv/math.RT | IJM ] (with Alexander Russell), in Illinois J. Math. (2008). We establish an operator-theoretic uncertainty principle over arbitrary compact groups, generalizing several previous results. As a consequence, we show that if f is in L^2(G), then the product of the measures of the supports of f and its Fourier transform ^f is at least 1; here, the dual measure is given by the sum, over all irreducible representations V, of dim(V) rank(^f(V)). For finite groups, our principle implies the following: if P and R are projection operators on the group algebra C[G] such that P commutes with projection onto each group element, and R commutes with left multiplication, then the squared operator norm of PR is at most rank(P)rank(R)/|G|. |
|||
Quantum Computing and the Hunt for Hidden Symmetry. [ pdf ] (with Alexander Russell), in Bulletin of the European Association for Theoretical Computer Science 93 (2007). In 1994, Peter Shor gave efficient quantum algorithms for factoring integers and extracting discrete logarithms. If we believe that nature will permit us to faithfully implement our current model of quantum computation, then these algorithms dramatically contradict the Strong Church-Turing thesis. The effect is heightened by the fact that these algorithms solve computational problems with long histories of attention by the computational and mathematical communities alike. In this article we discuss the branch of quantum algorithms research arising from attempts to generalize the core quantum algorithmic aspects of Shor's algorithms. Roughly, this can be viewed as the problem of generalizing algorithms of Simon and Shor, which work over abelian groups, to general nonabelian groups. |
|||
Strong Fourier sampling fails over G^n. [ arXiv/quant-ph ] (with Cristopher Moore and Alexander Russell), preprint (2005). We present a negative result regarding the hidden subgroup problem on the powers $G^n$ of a fixed group $G$. Under a condition on the base group $G$, we prove that strong Fourier sampling cannot distinguish some subgroups of $G^n$. Since strong sampling is in fact the optimal measurement on a coset state, this shows that we have no hope of efficiently solving the hidden subgroup problem over these groups with separable measurements on coset states (that is, using any polynomial number of single-register coset state experiments). Groups satisfying our condition include all nonabelian simple groups. We apply our results to show that there exist uniform familes of nilpotent groups whose normal series factors have constant size and yet are immune to strong Fourier sampling. |
|||
Decoherence in quantum walks on the hypercube. [ arXiv/quant-ph | PRA ] (with Alexander Russell), in Physical Review A (2005). We study a natural notion of decoherence on quantum walks over the hypercube. We prove that this model possesses a decoherence threshold beneath which the essential properties of the hypercubic quantum walk, such as linear mixing times, are preserved. Beyond the threshold, we prove that the walks behave like their classical counterparts. |