. \] As in the algorithm for discrete log, we will not write $x$ and $n$ in the state of our machine, because we never erase these values. Next, we compute $x^a$. We then map $a \rightarrow c$ with amplitude $\frac{1}{q^{1/2}} \exp(2 \pi i ac/q)$. This leaves our machine in state \[ \frac{1}{q} \sum_{a=0}^{q-1} \exp(2 \pi i ac / q) \|c,x^a\>. \] We now compute the probability that our machine ends in this state. Writing $a=br+k$, we obtain that this probability is \[ \left| \frac{1}{q} \sum_{b=0}^{\left\lfloor (q-k)/r \right\rfloor} \exp(2 \pi i (br+k) c / q) \right|^2 . \] Using the same argument as in the algorithm for discrete log, if $\lr{rc}{q}$ is small relative to $q$, all the amplitudes will point in nearly the same direction, giving a big probability. This probability of seeing a state $\| c,x^k\>$ will thus be at least $1/3r^2$ if \[ \frac{-r}{2} \leq \lr{rc}{q} \leq r/2, \] i.e., if there is a $c'$ such that \[ \frac{-r}{2} \leq rc-c'q \leq r/2. \] Dividing by $rq$ and rearranging the terms gives \[ \left| \frac{c}{q} - \frac{c'}{r} \right| \leq \frac{1}{2q}. \] Now, if this holds and $c'$ is relatively prime to $r$, we can obtain $r$ by rounding $c/q$ to the nearest fraction with a denominator of at most $n$. Because $q > 5n^2$, there is at most one such fraction. This fraction can be found in polynomial time by using a continued fraction expansion of $c/q$, which finds all the best approximations of $c/q$ by fractions. There are $r^2$ states $\|c,x^k \>$ with $\left|\frac{c}{q} - \frac{c'}{r} \right| \leq \frac{1}{2q}$ because there are $r$ possible $c'$, each one giving one $c$, and there are $r$ possible $k$. Using similar arguments as in the case of discrete log, we find that with probability at least $\phi(r)/3r$, we obtain $c'/r$ with $c'$ relatively prime to $r$. We can thus find $r$ a polynomial fraction of the time, so by repeating this experiment only polynomially many times, we are assured of a high probability of success. Note that in the algorithm for order, we did not use many of the properties of multiplication $\bmod{n}$. In fact, if we have a permutation $f$ mapping the set $\{0,1,2,\ldots,n-1\}$ into itself such that its $k$th iterate, $f^{(k)}(a)$, is computable in time polynomial in $\log n$ and $\log k$, the same algorithm will be able to find the order of an element $a$ under $f$, i.e., the minimum $r$ such that $f^{(r)}(a)=a$. \section*{Acknowledgements} I would like to thank Jeff Lagarias for finding and fixing a critical bug in an early version of this paper and Andrew Odlyzko for showing me how to factor given an algorithm for the order of an element. I would also like to thank Charles Bennett, Gilles Brassard, Dan Simon, and Umesh Vazirani for productive discussions, for corrections and improvements of early drafts of this paper, and for pointers to the literature. { \small \begin{thebibliography}{BB2} \bibitem[Beni]{Beni} P. Benioff, {\it Quantum mechanical Hamiltonian models of Turing machines}, J. Stat. Phys., Vol. 29, pp. 515--546 (1982). \bibitem[Benn]{Benn} C. H. Bennett, {\it Logical Reversibility of Computation}, IBM J. Res. Develop., Vol 17, pp. 525--532 (1973). \bibitem[BV]{BeVa} E. Bernstein and U. Vazirani, {\it Quantum Complexity Theory}, Proc. 25th ACM Symp. on Theory of Computation, pp. 11--20 (1993). \bibitem[BB1]{BeBr1} A. Berthiaume and G. Brassard, {\it The Quantum Challenge to Structural Complexity Theory}, Proc. 7th IEEE Conference on Structure in Complexity Theory (1992). \bibitem[BB2]{BeBr2} A. Berthiaume and G. Brassard, {\it Oracle Quantum Computing}, Proc. Physics of Computation (1992). \bibitem[Deu1]{Deut85} D. Deutsch, {\it Quantum Theory, the Church--Turing Principle and the Universal Quantum Computer}, Proc. R. Soc. Lond., Vol. A400, pp. 96--117 (1985). \bibitem[Deu2]{Deut89} D. Deutsch, {\it Quantum Computational Networks,} Proc. R. Soc. Lond., Vol. A425, pp. 73--90 (1989). \bibitem[DJ]{DeJo} D. Deutsch and R. Jozsa, {\it Rapid Solution of Problems by Quantum Computation}, Proc. R. Soc. Lond., Vol. A439, pp. 553--558 (1992). \bibitem[Fey]{Feyn} R. Feynman, {\it Simulating Physics with Computers}, International Journal of Theoretical Physics, Vol. 21, nos. 6/7, pp. 467--488 (1982). \bibitem[HW]{HaWr} G. H. Hardy and E. M. Wright, {\it An Introduction to the Theory of Numbers}, Fifth Edition, Oxford University Press, New York, 1979. \bibitem[RSA]{RiShAd} R. L. Rivest, A. Shamir, and L. Adelman {\it A Method of Obtaining Digital Signatures and Public-Key Cryptosystems}, Comm. ACM, Vol. 21, No. 2, pp. 120--126 (1978). \bibitem[Sim]{Simo} D. Simon, {\it On the Power of Quantum Computation}, manuscript. \bibitem[Vaz]{Vazi} U. Vazirani, personal communication. \bibitem[Yao]{Yao} A. Yao, {\it Quantum Circuit Complexity}, Proc. 34th IEEE Symp. on Foundations of Computer Science, 1993. \end{thebibliography} } \end{document}