



@article {1213,
	title = {Spatial search and the Dirac equation},
	journal = {Physical Review A},
	volume = {70},
	year = {2004},
	month = {2004/10/19},
	abstract = {  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.
},
	doi = {10.1103/PhysRevA.70.042312},
	url = {http://arxiv.org/abs/quant-ph/0405120v1},
	author = {Andrew M. Childs and Jeffrey Goldstone}
}
@article {1211,
	title = {Spatial search by quantum walk},
	journal = {Physical Review A},
	volume = {70},
	year = {2004},
	month = {2004/8/23},
	abstract = {  Grover{\textquoteright}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.
},
	doi = {10.1103/PhysRevA.70.022314},
	url = {http://arxiv.org/abs/quant-ph/0306054v2},
	author = {Andrew M. Childs and Jeffrey Goldstone}
}
@article {1262,
	title = {Quantum search by measurement},
	journal = {Physical Review A},
	volume = {66},
	year = {2002},
	month = {2002/9/23},
	abstract = {  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{\textquoteright}s unstructured search problem with
only two measurements. Finally, we discuss some similarities and differences
between the adiabatic and measurement algorithms.
},
	doi = {10.1103/PhysRevA.66.032314},
	url = {http://arxiv.org/abs/quant-ph/0204013v1},
	author = {Andrew M. Childs and Enrico Deotto and Edward Farhi and Jeffrey Goldstone and Sam Gutmann and Andrew J. Landahl}
}
@article {1237,
	title = {Finding cliques by quantum adiabatic evolution},
	year = {2000},
	month = {2000/12/19},
	abstract = {  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.
},
	url = {http://arxiv.org/abs/quant-ph/0012104v1},
	author = {Andrew M. Childs and Edward Farhi and Jeffrey Goldstone and Sam Gutmann}
}
