



@article {1263,
	title = {Exponential algorithmic speedup by quantum walk},
	year = {2002},
	month = {2002/09/24},
	abstract = {  We construct an oracular (i.e., black box) problem that can be solved
exponentially faster on a quantum computer than on a classical computer. The
quantum algorithm is based on a continuous time quantum walk, and thus employs
a different technique from previous quantum algorithms based on quantum Fourier
transforms. We show how to implement the quantum walk efficiently in our
oracular setting. We then show how this quantum walk can be used to solve our
problem by rapidly traversing a graph. Finally, we prove that no classical
algorithm can solve this problem with high probability in subexponential time.
},
	doi = {10.1145/780542.780552},
	url = {http://arxiv.org/abs/quant-ph/0209131v2},
	author = {Andrew M. Childs and Richard Cleve and Enrico Deotto and Edward Farhi and Sam Gutmann and Daniel A. Spielman}
}
@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 {1208,
	title = {An example of the difference between quantum and classical random walks},
	journal = {Quantum Information Processing},
	volume = {1},
	year = {2001},
	month = {2002/04/01},
	pages = {35 - 43},
	abstract = {  In this note, we discuss a general definition of quantum random walks on
graphs and illustrate with a simple graph the possibility of very different
behavior between a classical random walk and its quantum analogue. In this
graph, propagation between a particular pair of nodes is exponentially faster
in the quantum case.
},
	doi = {10.1023/A:1019609420309},
	url = {http://arxiv.org/abs/quant-ph/0103020v1},
	author = {Andrew M. Childs and Edward Farhi and Sam Gutmann}
}
@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}
}
