INTRODUCTION TO QUANTUM ALGORITHMS

摘要: These notes discuss the quantum algorithms we know of that can solve problems significantly faster than corresponding classical algorithms. So far, have only discovered a few techniques which produce speed up versus It is not clear yet whether reason for this do enough intuition to discover more techniques, or there are computers solution. In first section these notes, I try explain why recent results about computing been so surprising. This comes from talk giving several years now, and discusses history its relation mathematical foundations computer science. Sections 2 3, model relationship physics. sections rely heavily on two my papers (SIAM J. Comp. 26 (1997), 1484-1509; Doc. Math. Extra Vol. ICM (1998), 467-486). 4 5 illustrate general technique using Fourier transforms find periodicity. Section contains an algorithm Dan Simon showing likely be exponentially some problems. factoring algorithm, was inspired in part by Simon's paper. final section, Lov Grover's search illustrates different speeding constructing significant ones far.