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's probabilistic algorithm for k-SAT.

%B Quantum Information and Computation %V 16 %8 2016/03/22 %G eng %U http://arxiv.org/abs/1603.06985 %N 13-14 %0 Journal Article %D 2014 %T Different Strategies for Optimization Using the Quantum Adiabatic Algorithm %A Elizabeth Crosson %A Edward Farhi %A Cedric Yen-Yu Lin %A Han-Hsuan Lin %A Peter Shor %X 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. %8 2014/01/28 %G eng %U http://arxiv.org/abs/1401.7320v1 %0 Journal Article %J Physical Review A %D 2008 %T Perturbative Gadgets at Arbitrary Orders %A Stephen P. Jordan %A Edward Farhi %X 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. %B Physical Review A %V 77 %8 2008/6/19 %G eng %U http://arxiv.org/abs/0802.1874v4 %N 6 %! Phys. Rev. A %R 10.1103/PhysRevA.77.062329 %0 Journal Article %J Physical Review A %D 2006 %T Error correcting codes for adiabatic quantum computation %A Stephen P. Jordan %A Edward Farhi %A Peter W. Shor %X 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. %B Physical Review A %V 74 %8 2006/11/14 %G eng %U http://arxiv.org/abs/quant-ph/0512170v3 %N 5 %! Phys. Rev. A %R 10.1103/PhysRevA.74.052322 %0 Journal Article %D 2002 %T Exponential algorithmic speedup by quantum walk %A Andrew M. Childs %A Richard Cleve %A Enrico Deotto %A Edward Farhi %A Sam Gutmann %A Daniel A. Spielman %X 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. %8 2002/09/24 %G eng %U http://arxiv.org/abs/quant-ph/0209131v2 %! Proc. 35th ACM Symposium on Theory of Computing (STOC 2003) %R 10.1145/780542.780552 %0 Journal Article %J Physical Review A %D 2002 %T Quantum search by measurement %A Andrew M. Childs %A Enrico Deotto %A Edward Farhi %A Jeffrey Goldstone %A Sam Gutmann %A Andrew J. Landahl %X 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. %B Physical Review A %V 66 %8 2002/9/23 %G eng %U http://arxiv.org/abs/quant-ph/0204013v1 %N 3 %! Phys. Rev. A %R 10.1103/PhysRevA.66.032314 %0 Journal Article %J Quantum Information Processing %D 2001 %T An example of the difference between quantum and classical random walks %A Andrew M. Childs %A Edward Farhi %A Sam Gutmann %X 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. %B Quantum Information Processing %V 1 %P 35 - 43 %8 2002/04/01 %G eng %U http://arxiv.org/abs/quant-ph/0103020v1 %N 1/2 %! Quantum Information Processing 1 %R 10.1023/A:1019609420309 %0 Journal Article %J Physical Review A %D 2001 %T Robustness of adiabatic quantum computation %A Andrew M. Childs %A Edward Farhi %A John Preskill %X 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. %B Physical Review A %V 65 %8 2001/12/14 %G eng %U http://arxiv.org/abs/quant-ph/0108048v1 %N 1 %! Phys. Rev. A %R 10.1103/PhysRevA.65.012322 %0 Journal Article %D 2000 %T Finding cliques by quantum adiabatic evolution %A Andrew M. Childs %A Edward Farhi %A Jeffrey Goldstone %A Sam Gutmann %X 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. %8 2000/12/19 %G eng %U http://arxiv.org/abs/quant-ph/0012104v1 %! Quantum Information and Computation 2