TY - JOUR
T1 - Spatial search and the Dirac equation
JF - Physical Review A
Y1 - 2004
A1 - Andrew M. Childs
A1 - Jeffrey Goldstone
AB - 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.
VL - 70
UR - http://arxiv.org/abs/quant-ph/0405120v1
CP - 4
J1 - Phys. Rev. A
U5 - 10.1103/PhysRevA.70.042312
ER -
TY - JOUR
T1 - Spatial search by quantum walk
JF - Physical Review A
Y1 - 2004
A1 - Andrew M. Childs
A1 - Jeffrey Goldstone
AB - 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.
VL - 70
UR - http://arxiv.org/abs/quant-ph/0306054v2
CP - 2
J1 - Phys. Rev. A
U5 - 10.1103/PhysRevA.70.022314
ER -
TY - JOUR
T1 - Quantum search by measurement
JF - Physical Review A
Y1 - 2002
A1 - Andrew M. Childs
A1 - Enrico Deotto
A1 - Edward Farhi
A1 - Jeffrey Goldstone
A1 - Sam Gutmann
A1 - Andrew J. Landahl
AB - 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.
VL - 66
UR - http://arxiv.org/abs/quant-ph/0204013v1
CP - 3
J1 - Phys. Rev. A
U5 - 10.1103/PhysRevA.66.032314
ER -
TY - JOUR
T1 - Finding cliques by quantum adiabatic evolution
Y1 - 2000
A1 - Andrew M. Childs
A1 - Edward Farhi
A1 - Jeffrey Goldstone
A1 - Sam Gutmann
AB - 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.
UR - http://arxiv.org/abs/quant-ph/0012104v1
J1 - Quantum Information and Computation 2
ER -