Source-linked AI summary
An Analog Analogue of a Digital Quantum Computation
Edward Farhi, Sam Gutmann
TL;DR
The paper considers finding a marked input w in an unsorted set of N possibilities. It describes Grover’s procedure as repeated applications of UsUf in a two-dimensional subspace, achieving a search cost that grows as N^1/2.
Problem
The problem is to find the unique w for which f(w)=1 among N inputs, a task requiring N/2 evaluations on average classically.
Source: Appendix · p. 5Method
The method repeatedly applies UsUf to |s⟩ and analyzes the evolution in the two-dimensional subspace spanned by |s⟩ and |w⟩.
Source: Appendix · p. 6Results
O(N^1/2) evaluations of f and two-bit operations suffice to find w.
Source: Appendix · p. 6Takeaways & Limitations
The algorithm’s cost grows as N^1/2 because each application rotates the state by approximately 2N^-1/2.
Source: Appendix · p. 6
Abstract
from arXiv · showhide
We solve a problem, which while not fitting into the usual paradigm, can be viewed as a quantum computation. Suppose we are given a quantum system described by an N dimensional Hilbert space with a Hamiltonian of the form $E |w >< w|$ where $| w>$ is an unknown (normalized) state. We show how to discover $| w >$ by adding a Hamiltonian (independent of $| w >$) and evolving for a time proportional to $N^{1/2}/E$. We show that this time is optimally short. This process is an analog analogue to Grover's algorithm, a computation on a conventional (!) quantum computer which locates a marked item from an unsorted list of N items in a number of steps proportional to $N^{1/2}$.
Appendix
The appendix explains Grover’s algorithm as repeated applications of two unitary operators in a two-dimensional subspace, requiring O(N^1/2) evaluations and quantum operations.
Appendix
- The problem is to find the unique w for which f(w)=1 among N inputs, whereas classical search requires N/2 evaluations on average.Source: Appendix · p. 5
- The oracle Uf requires two evaluations of f because ancillary work bits must be erased, while the evaluation code is assumed not to grow polynomially with N.Source: Appendix · p. 5
- The operator Us can be implemented with a number of two-bit operations growing more slowly than any positive power of N.Source: Appendix · p. 5
- Grover’s algorithm repeatedly applies UsUf to |s⟩ while restricting the dynamics to the subspace spanned by |s⟩ and |w⟩.Source: Appendix · p. 6
- For large N, each UsUf application rotates the state by an angle approximately 2N^-1/2.Source: Appendix · p. 6
- O(N^1/2) evaluations of f and two-bit operations suffice to find w after k ∼πN^1/2/4 iterations.Each iteration uses two evaluations of f.Source: Appendix · p. 6