Shor's Algorithm is Optimal

(submitted), 2003. ps (350kB), ps.gz (161kB) or pdf (196kB)

We show that the standard quantum algorithm for the abelian hidden subgroup problem is not only efficient but is optimal in the information theoretic sense, in that it maximizes the probability of correctly identifying the hidden subgroup. The proof uses semidefinite programming to show that the standard algorithm implements the optimal set of measurements.

The arguments break down for the nonabelian hidden subgroup problem, and for the dihedral group, we give explicit expressions for the optimal measurement to distinguish between the subgroups given one random coset state. The measurement cannot be expressed in terms of the Fourier basis, which suggests that to find a quantum algorithm for the nonabelian hidden subgroup problem we may have to look beyond the Fourier transform.

Last modified November 25, 2003