Lawrence Ip > Papers > 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