Explicit Multiregister Measurements for Hidden Subgroup Problems

Abstract

We present an explicit measurement in the Fourier basis that solves an important case of the Hidden Subgroup Problem, including the case to which Graph Isomorphism reduces. This entangled measurement uses $k={\log }_2|G|$ registers, and each of the $2^k$ subsets of the registers contributes some information. While this does not, in general, yield an efficient algorithm, it generalizes the relationship between Subset Sum and the HSP in the dihedral group, and sheds some light on how quantum algorithms for Graph Isomorphism might work.

References in corpus (7)

• The quantum query complexity of the hidden subgroup problem is polynomial
• From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
• Quantum factoring, discrete logarithms and the hidden subgroup problem
• Efficient Quantum Transforms
• Polynomial-Time Solution to the Hidden Subgroup Problem for a Class of non-abelian Groups
• Hidden Subgroup States are Almost Orthogonal
• For Distinguishing Conjugate Hidden Subgroups, the Pretty Good Measurement is as Good as it Gets

Cited by in corpus (1)

• On the impossibility of a quantum sieve algorithm for graph isomorphism: unconditional results