How a Clebsch-Gordan Transform Helps to Solve the Heisenberg Hidden Subgroup Problem

Abstract

It has recently been shown that quantum computers can efficiently solve the Heisenberg hidden subgroup problem, a problem whose classical query complexity is exponential. This quantum algorithm was discovered within the framework of using pretty-good measurements for obtaining optimal measurements in the hidden subgroup problem. Here we show how to solve the Heisenberg hidden subgroup problem using arguments based instead on the symmetry of certain hidden subgroup states. The symmetry we consider leads naturally to a unitary transform known as the Clebsch-Gordan transform over the Heisenberg group. This gives a new representation theoretic explanation for the pretty-good measurement derived algorithm for efficiently solving the Heisenberg hidden subgroup problem and provides evidence that Clebsch-Gordan transforms over finite groups are a new primitive in quantum algorithm design.

30 pages, uses qic.sty

References in corpus (9)

• Exponential algorithmic speedup by quantum walk
• From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
• A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
• 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
• For Distinguishing Conjugate Hidden Subgroups, the Pretty Good Measurement is as Good as it Gets
• Generic Quantum Fourier Transforms
• The central nature of the Hidden Subgroup problem
• Generalized Bell inequality for mixed states with variable constraints

Cited by in corpus (2)

• The Optimal Single Copy Measurement for the Hidden Subgroup Problem
• The Study of Entangled States in Quantum Computation and Quantum Information Science