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.

VL - 16 UR - http://arxiv.org/abs/1603.06985 CP - 13-14 ER - TY - JOUR T1 - Different Strategies for Optimization Using the Quantum Adiabatic Algorithm Y1 - 2014 A1 - Elizabeth Crosson A1 - Edward Farhi A1 - Cedric Yen-Yu Lin A1 - Han-Hsuan Lin A1 - Peter Shor AB - 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. UR - http://arxiv.org/abs/1401.7320v1 ER - TY - JOUR T1 - Perturbative Gadgets at Arbitrary Orders JF - Physical Review A Y1 - 2008 A1 - Stephen P. Jordan A1 - Edward Farhi AB - 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. VL - 77 UR - http://arxiv.org/abs/0802.1874v4 CP - 6 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.77.062329 ER - TY - JOUR T1 - Error correcting codes for adiabatic quantum computation JF - Physical Review A Y1 - 2006 A1 - Stephen P. Jordan A1 - Edward Farhi A1 - Peter W. Shor AB - 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. VL - 74 UR - http://arxiv.org/abs/quant-ph/0512170v3 CP - 5 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.74.052322 ER - TY - JOUR T1 - Exponential algorithmic speedup by quantum walk Y1 - 2002 A1 - Andrew M. Childs A1 - Richard Cleve A1 - Enrico Deotto A1 - Edward Farhi A1 - Sam Gutmann A1 - Daniel A. Spielman AB - 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. UR - http://arxiv.org/abs/quant-ph/0209131v2 J1 - Proc. 35th ACM Symposium on Theory of Computing (STOC 2003) U5 - 10.1145/780542.780552 ER - TY - JOUR T1 - Quantum search by measurement JF - Physical Review A Y1 - 2002 A1 - Andrew M. Childs A1 - Enrico Deotto A1 - Edward Farhi A1 - Jeffrey Goldstone A1 - Sam Gutmann A1 - Andrew J. Landahl AB - 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. VL - 66 UR - http://arxiv.org/abs/quant-ph/0204013v1 CP - 3 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.66.032314 ER - TY - JOUR T1 - An example of the difference between quantum and classical random walks JF - Quantum Information Processing Y1 - 2001 A1 - Andrew M. Childs A1 - Edward Farhi A1 - Sam Gutmann AB - 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. VL - 1 U4 - 35 - 43 UR - http://arxiv.org/abs/quant-ph/0103020v1 CP - 1/2 J1 - Quantum Information Processing 1 U5 - 10.1023/A:1019609420309 ER - TY - JOUR T1 - Robustness of adiabatic quantum computation JF - Physical Review A Y1 - 2001 A1 - Andrew M. Childs A1 - Edward Farhi A1 - John Preskill AB - 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. VL - 65 UR - http://arxiv.org/abs/quant-ph/0108048v1 CP - 1 J1 - Phys. Rev. A U5 - 10.1103/PhysRevA.65.012322 ER - TY - JOUR T1 - Finding cliques by quantum adiabatic evolution Y1 - 2000 A1 - Andrew M. Childs A1 - Edward Farhi A1 - Jeffrey Goldstone A1 - Sam Gutmann AB - 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. UR - http://arxiv.org/abs/quant-ph/0012104v1 J1 - Quantum Information and Computation 2 ER -