%0 Journal Article
%J Physical Review A
%D 2004
%T Spatial search and the Dirac equation
%A Andrew M. Childs
%A Jeffrey Goldstone
%X 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.
%B Physical Review A
%V 70
%8 2004/10/19
%G eng
%U http://arxiv.org/abs/quant-ph/0405120v1
%N 4
%! Phys. Rev. A
%R 10.1103/PhysRevA.70.042312
%0 Journal Article
%J Physical Review A
%D 2004
%T Spatial search by quantum walk
%A Andrew M. Childs
%A Jeffrey Goldstone
%X 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.
%B Physical Review A
%V 70
%8 2004/8/23
%G eng
%U http://arxiv.org/abs/quant-ph/0306054v2
%N 2
%! Phys. Rev. A
%R 10.1103/PhysRevA.70.022314
%0 Journal Article
%J Physical Review A
%D 2002
%T Quantum search by measurement
%A Andrew M. Childs
%A Enrico Deotto
%A Edward Farhi
%A Jeffrey Goldstone
%A Sam Gutmann
%A Andrew J. Landahl
%X 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.
%B Physical Review A
%V 66
%8 2002/9/23
%G eng
%U http://arxiv.org/abs/quant-ph/0204013v1
%N 3
%! Phys. Rev. A
%R 10.1103/PhysRevA.66.032314
%0 Journal Article
%D 2000
%T Finding cliques by quantum adiabatic evolution
%A Andrew M. Childs
%A Edward Farhi
%A Jeffrey Goldstone
%A Sam Gutmann
%X 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.
%8 2000/12/19
%G eng
%U http://arxiv.org/abs/quant-ph/0012104v1
%! Quantum Information and Computation 2