Hidden Subgroup States are Almost Orthogonal

Abstract

It is well known that quantum computers can efficiently find a hidden subgroup $H$ of a finite Abelian group $G$. This implies that after only a polynomial (in $\log |G|$) number of calls to the oracle function, the states corresponding to different candidate subgroups have exponentially small inner product. We show that this is true for noncommutative groups also. We present a quantum algorithm which identifies a hidden subgroup of an arbitrary finite group $G$ in only a linear (in $\log |G|$) number of calls to the oracle function. This is exponentially better than the best classical algorithm. However our quantum algorithm requires an exponential amount of time, as in the classical case.

5 pages, no figures

Cited by in corpus (16)

• Quantum factoring, discrete logarithms and the hidden subgroup problem
• Applications of coherent classical communication and the Schur transform to quantum information theory
• Quantum algorithms for hidden nonlinear structures
• The Hidden Subgroup Problem - Review and Open Problems
• Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
• Optimal measurements for the dihedral hidden subgroup problem
• A learning graph based quantum query algorithm for finding constant-size subgraphs
• The Hidden Subgroup Problem in Affine Groups: Basis Selection in Fourier Sampling
• Quantum Algorithms for the Triangle Problem
• The Optimal Single Copy Measurement for the Hidden Subgroup Problem
• Quantum Hidden Subgroup Algorithms: The Devil Is in the Details
• Explicit Multiregister Measurements for Hidden Subgroup Problems
• How a Clebsch-Gordan Transform Helps to Solve the Heisenberg Hidden Subgroup Problem
• Quantum algorithms for solvable groups
• Hidden Subhypergroup Problem
• On Statistical Query Sampling and NMR Quantum Computing