From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
arXiv:quant-ph/0504083 · doi:10.1109/SFCS.2005.38
Abstract
We approach the hidden subgroup problem by performing the so-called pretty good measurement on hidden subgroup states. For various groups that can be expressed as the semidirect product of an abelian group and a cyclic group, we show that the pretty good measurement is optimal and that its probability of success and unitary implementation are closely related to an average-case algebraic problem. By solving this problem, we find efficient quantum algorithms for a number of nonabelian hidden subgroup problems, including some for which no efficient algorithm was previously known: certain metacyclic groups as well as all groups of the form (Z_p)^r X| Z_p for fixed r (including the Heisenberg group, r=2). In particular, our results show that entangled measurements across multiple copies of hidden subgroup states can be useful for efficiently solving the nonabelian HSP.
18 pages; v2: updated references on optimal measurement
References in corpus (9)
- Quantum measurements and the Abelian Stabilizer Problem
- The quantum query complexity of the hidden subgroup problem is polynomial
- Efficient Quantum Transforms
- A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
- Polynomial-Time Solution to the Hidden Subgroup Problem for a Class of non-abelian Groups
- A Quantum Observable for the Graph Isomorphism Problem
- Optimal measurements for the dihedral hidden subgroup problem
- For Distinguishing Conjugate Hidden Subgroups, the Pretty Good Measurement is as Good as it Gets
- On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group
Cited by in corpus (48)
- On the impossibility of a quantum sieve algorithm for graph isomorphism: unconditional results
- Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
- Quantum Computation Beyond the Circuit Model
- Computational Indistinguishability between Quantum States and Its Cryptographic Application
- Optimal Measurements for Symmetric Quantum States with Applications to Optical Communication
- Error rates of Belavkin weighted quantum measurements and a converse to Holevo's asymptotic optimality theorem
- For Distinguishing Conjugate Hidden Subgroups, the Pretty Good Measurement is as Good as it Gets
- Quantum algorithms to solve the hidden shift problem for quadratics and for functions of large Gowers norm
- Classical and Quantum Algorithms for Exponential Congruences
- The Hidden Subgroup Problem
- The Optimal Single Copy Measurement for the Hidden Subgroup Problem
- Superpolynomial speedups based on almost any quantum circuit
- Efficient Quantum Algorithms for the Hidden Subgroup Problem over a Class of Semi-direct Product Groups
- Hidden Symmetry Subgroup Problems
- On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems
- Optimal quantum algorithm for polynomial interpolation
- An Efficient Quantum Algorithm for some Instances of the Group Isomorphism Problem
- Limitations of Quantum Coset States for Graph Isomorphism
- Normalizer Circuits and Quantum Computation
- Explicit Multiregister Measurements for Hidden Subgroup Problems
- Deterministic Algorithms for the Hidden Subgroup Problem
- Efficient Quantum Algorithm for Hidden Quadratic and Cubic Polynomial Function Graphs
- Efficient Quantum Algorithm for Identifying Hidden Polynomials
- On solving systems of diagonal polynomial equations over finite fields
- Estimates of non-optimality of quantum measurements and a simple iterative method for computing optimal measurements
- How a Clebsch-Gordan Transform Helps to Solve the Heisenberg Hidden Subgroup Problem
- On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism
- Minimal scheme for certifying three-outcome qubit measurements in the prepare-and-measure scenario
- Certifying optimality for convex quantum channel optimization problems
- Learning With Errors and Extrapolated Dihedral Cosets
- Abelian Hypergroups and Quantum Computation
- Tight Results on Multiregister Fourier Sampling: Quantum Measurements for Graph Isomorphism Require Entanglement
- Polynomial time quantum algorithms for certain bivariate hidden polynomial problems
- Quantum Measurements for Hidden Subgroup Problems with Optimal Sample Complexity
- An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups
- How to hide a secret direction
- Quantum algorithms for highly non-linear Boolean functions
- Finding conjugate stabilizer subgroups in PSL(2; q) and related groups
- Quantum Algorithms Using the Curvelet Transform
- Simon's Algorithm, Clebsch-Gordan Sieves, and Hidden Symmetries of Multiple Squares
- An efficient quantum algorithm for the hidden subgroup problem in extraspecial groups
- An Improved Query for the Hidden Subgroup Problem
- Finding hidden Borel subgroups of the general linear group
- An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group
- On the distinguishability of geometrically uniform quantum states
- Online identification of symmetric pure states
- The Hidden Subgroup Problem for Universal Algebras
- Quantum Property Testing for Solvable Groups