@article {2530, title = {Quantum Computer Systems for Scientific Discovery}, year = {2019}, month = {12/16/2019}, abstract = {

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.

}, 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 = {

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\"oning\&$\#$39;s probabilistic algorithm for k-SAT.

}, 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} }