More On Grover's Algorithm

Ken Loo

Published 2005-02-22Version 1

The goals of this paper are to show the following. First, Grover's algorithm can be viewed as a digital approximation to the analog quantum algorithm proposed in "An Analog Analogue of a Digital Quantum Computation", by E. Farhi and S. Gutmann, Phys.Rev. A 57, 2403 - 2406 (1998), quant-ph/9612026. We will call the above analog algorithm the Grover-Farhi-Gutmann or GFG algorithm. Second, the propagator of the GFG algorithm can be written as a sum-over-paths formula and given a sum-over-path interpretation, i.e., a Feynman path sum/integral. We will use nonstandard analysis to do this. Third, in the semi-classical limit $\hbar\to 0$, both the Grover and the GFG algorithms (viewed in the setting of the approximation in this paper) must run instantaneously. Finally, we will end the paper with an open question. In "Semiclassical Shor's Algorithm", by P. Giorda, et al, Phys. Rev.A 70, 032303 (2004), quant-ph/0303037, the authors proposed building semi-classical quantum computers to run Shor's algorithm because the success probability of Shor's algorithm does not change much in the semi-classical limit. We ask the open questions: In the semi-classical limit, does Shor's algorithm have to run instantaneously?