00967nas a2200133 4500008004100000245004200041210004200083260001500125490000700140520059600147100002300743700002300766856004400789 2004 eng d00aSpatial search and the Dirac equation0 aSpatial search and the Dirac equation c2004/10/190 v703 a We consider the problem of searching a d-dimensional lattice of N sites for a
single marked location. We present a Hamiltonian that solves this problem in
time of order sqrt(N) for d>2 and of order sqrt(N) log(N) in the critical
dimension d=2. This improves upon the performance of our previous quantum walk
search algorithm (which has a critical dimension of d=4), and matches the
performance of a corresponding discrete-time quantum walk algorithm. The
improvement uses a lattice version of the Dirac Hamiltonian, and thus requires
the introduction of spin (or coin) degrees of freedom.
1 aChilds, Andrew, M.1 aGoldstone, Jeffrey uhttp://arxiv.org/abs/quant-ph/0405120v101263nas a2200133 4500008004100000245003500041210003500076260001400111490000700125520090700132100002301039700002301062856004401085 2004 eng d00aSpatial search by quantum walk0 aSpatial search by quantum walk c2004/8/230 v703 a Grover's quantum search algorithm provides a way to speed up combinatorial
search, but is not directly applicable to searching a physical database.
Nevertheless, Aaronson and Ambainis showed that a database of N items laid out
in d spatial dimensions can be searched in time of order sqrt(N) for d>2, and
in time of order sqrt(N) poly(log N) for d=2. We consider an alternative search
algorithm based on a continuous time quantum walk on a graph. The case of the
complete graph gives the continuous time search algorithm of Farhi and Gutmann,
and other previously known results can be used to show that sqrt(N) speedup can
also be achieved on the hypercube. We show that full sqrt(N) speedup can be
achieved on a d-dimensional periodic lattice for d>4. In d=4, the quantum walk
search algorithm takes time of order sqrt(N) poly(log N), and in d<4, the
algorithm does not provide substantial speedup.
1 aChilds, Andrew, M.1 aGoldstone, Jeffrey uhttp://arxiv.org/abs/quant-ph/0306054v201071nas a2200181 4500008004100000245003400041210003400075260001400109490000700123520059100130100002300721700001900744700001800763700002300781700001700804700002400821856004400845 2002 eng d00aQuantum search by measurement0 aQuantum search by measurement c2002/9/230 v663 a We propose a quantum algorithm for solving combinatorial search problems that
uses only a sequence of measurements. The algorithm is similar in spirit to
quantum computation by adiabatic evolution, in that the goal is to remain in
the ground state of a time-varying Hamiltonian. Indeed, we show that the
running times of the two algorithms are closely related. We also show how to
achieve the quadratic speedup for Grover's unstructured search problem with
only two measurements. Finally, we discuss some similarities and differences
between the adiabatic and measurement algorithms.
1 aChilds, Andrew, M.1 aDeotto, Enrico1 aFarhi, Edward1 aGoldstone, Jeffrey1 aGutmann, Sam1 aLandahl, Andrew, J. uhttp://arxiv.org/abs/quant-ph/0204013v101120nas a2200145 4500008004100000245005100041210005100092260001500143520069100158100002300849700001800872700002300890700001700913856004400930 2000 eng d00aFinding cliques by quantum adiabatic evolution0 aFinding cliques by quantum adiabatic evolution c2000/12/193 a Quantum adiabatic evolution provides a general technique for the solution of
combinatorial search problems on quantum computers. We present the results of a
numerical study of a particular application of quantum adiabatic evolution, the
problem of finding the largest clique in a random graph. An n-vertex random
graph has each edge included with probability 1/2, and a clique is a completely
connected subgraph. There is no known classical algorithm that finds the
largest clique in a random graph with high probability and runs in a time
polynomial in n. For the small graphs we are able to investigate (n <= 18), the
quantum algorithm appears to require only a quadratic run time.
1 aChilds, Andrew, M.1 aFarhi, Edward1 aGoldstone, Jeffrey1 aGutmann, Sam uhttp://arxiv.org/abs/quant-ph/0012104v1