



@article {2530,
	title = {Quantum Computer Systems for Scientific Discovery},
	year = {2019},
	month = {12/16/2019},
	abstract = {<p>The great promise of quantum computers comes with the dual challenges of building them and finding their useful applications. We argue that these two challenges should be considered together, by co-designing full stack quantum computer systems along with their applications in order to hasten their development and potential for scientific discovery. In this context, we identify scientific and community needs, opportunities, and significant challenges for the development of quantum computers for science over the next 2-10 years. This document is written by a community of university, national laboratory, and industrial researchers in the field of Quantum Information Science and Technology, and is based on a summary from a U.S. National Science Foundation workshop on Quantum Computing held on October 21-22, 2019 in Alexandria, VA.</p>},
	url = {https://arxiv.org/abs/1912.07577},
	author = {Yuri Alexeev and Dave Bacon and Kenneth R. Brown and Robert Calderbank and Lincoln D. Carr and Frederic T. Chong and Brian DeMarco and Dirk Englund and Edward Farhi and Bill Fefferman and Alexey V. Gorshkov and Andrew Houck and Jungsang Kim and Shelby Kimmel and Michael Lange and Seth Lloyd and Mikhail D. Lukin and Dmitri Maslov and Peter Maunz and Christopher Monroe and John Preskill and Martin Roetteler and Martin Savage and Jeff Thompson and Umesh Vazirani}
}
@article {1733,
	title = {A Quantum Version of Sch{\"o}ning{\textquoteright}s Algorithm Applied to Quantum 2-SAT},
	journal = {Quantum Information and Computation},
	volume = {16},
	year = {2016},
	month = {2016/03/22},
	abstract = {<p>We study a quantum algorithm that consists of a simple quantum Markov process, and we analyze its behavior on restricted versions of Quantum 2-SAT. We prove that the algorithm solves this decision problem with high probability for n qubits, L clauses, and promise gap c in time O(n^2 L^2 c^{-2}). If the Hamiltonian is additionally polynomially gapped, our algorithm efficiently produces a state that has high overlap with the satisfying subspace. The Markov process we study is a quantum analogue of Sch\&quot;oning\&$\#$39;s probabilistic algorithm for k-SAT.</p>},
	url = {http://arxiv.org/abs/1603.06985},
	author = {Edward Farhi and Shelby Kimmel and Kristan Temme}
}
@article {1516,
	title = {Different Strategies for Optimization Using the Quantum Adiabatic  Algorithm
},
	year = {2014},
	month = {2014/01/28},
	abstract = {  We present the results of a numerical study, with 20 qubits, of the
performance of the Quantum Adiabatic Algorithm on randomly generated instances
of MAX 2-SAT with a unique assignment that maximizes the number of satisfied
clauses. The probability of obtaining this assignment at the end of the quantum
evolution measures the success of the algorithm. Here we report three
strategies which consistently increase the success probability for the hardest
instances in our ensemble: decreasing the overall evolution time, initializing
the system in excited states, and adding a random local Hamiltonian to the
middle of the evolution.
},
	url = {http://arxiv.org/abs/1401.7320v1},
	author = {Elizabeth Crosson and Edward Farhi and Cedric Yen-Yu Lin and Han-Hsuan Lin and Peter Shor}
}
@article {1383,
	title = {Perturbative Gadgets at Arbitrary Orders},
	journal = {Physical Review A},
	volume = {77},
	year = {2008},
	month = {2008/6/19},
	abstract = {  Adiabatic quantum algorithms are often most easily formulated using many-body
interactions. However, experimentally available interactions are generally
two-body. In 2004, Kempe, Kitaev, and Regev introduced perturbative gadgets, by
which arbitrary three-body effective interactions can be obtained using
Hamiltonians consisting only of two-body interactions. These three-body
effective interactions arise from the third order in perturbation theory. Since
their introduction, perturbative gadgets have become a standard tool in the
theory of quantum computation. Here we construct generalized gadgets so that
one can directly obtain arbitrary k-body effective interactions from two-body
Hamiltonians. These effective interactions arise from the kth order in
perturbation theory.
},
	doi = {10.1103/PhysRevA.77.062329},
	url = {http://arxiv.org/abs/0802.1874v4},
	author = {Stephen P. Jordan and Edward Farhi}
}
@article {1394,
	title = {Error correcting codes for adiabatic quantum computation},
	journal = {Physical Review A},
	volume = {74},
	year = {2006},
	month = {2006/11/14},
	abstract = {  Recently, there has been growing interest in using adiabatic quantum
computation as an architecture for experimentally realizable quantum computers.
One of the reasons for this is the idea that the energy gap should provide some
inherent resistance to noise. It is now known that universal quantum
computation can be achieved adiabatically using 2-local Hamiltonians. The
energy gap in these Hamiltonians scales as an inverse polynomial in the problem
size. Here we present stabilizer codes which can be used to produce a constant
energy gap against 1-local and 2-local noise. The corresponding fault-tolerant
universal Hamiltonians are 4-local and 6-local respectively, which is the
optimal result achievable within this framework.
},
	doi = {10.1103/PhysRevA.74.052322},
	url = {http://arxiv.org/abs/quant-ph/0512170v3},
	author = {Stephen P. Jordan and Edward Farhi and Peter W. Shor}
}
@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 {1209,
	title = {Robustness of adiabatic quantum computation},
	journal = {Physical Review A},
	volume = {65},
	year = {2001},
	month = {2001/12/14},
	abstract = {  We study the fault tolerance of quantum computation by adiabatic evolution, a
quantum algorithm for solving various combinatorial search problems. We
describe an inherent robustness of adiabatic computation against two kinds of
errors, unitary control errors and decoherence, and we study this robustness
using numerical simulations of the algorithm.
},
	doi = {10.1103/PhysRevA.65.012322},
	url = {http://arxiv.org/abs/quant-ph/0108048v1},
	author = {Andrew M. Childs and Edward Farhi and John Preskill}
}
@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}
}
