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.

1 aFarhi, Edward1 aKimmel, Shelby1 aTemme, Kristan uhttp://arxiv.org/abs/1603.0698501142nas a2200157 4500008004100000245008300041210006900124260001500193520063900208100002300847700001800870700002400888700001900912700001600931856003700947 2014 eng d00aDifferent Strategies for Optimization Using the Quantum Adiabatic Algorithm 0 aDifferent Strategies for Optimization Using the Quantum Adiabati c2014/01/283 a 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. 1 aCrosson, Elizabeth1 aFarhi, Edward1 aLin, Cedric, Yen-Yu1 aLin, Han-Hsuan1 aShor, Peter uhttp://arxiv.org/abs/1401.7320v101152nas a2200133 4500008004100000245004500041210004500086260001400131490000700145520078700152100002400939700001800963856003700981 2008 eng d00aPerturbative Gadgets at Arbitrary Orders0 aPerturbative Gadgets at Arbitrary Orders c2008/6/190 v773 a 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. 1 aJordan, Stephen, P.1 aFarhi, Edward uhttp://arxiv.org/abs/0802.1874v401177nas a2200145 4500008004100000245006100041210006100102260001500163490000700178520074000185100002400925700001800949700002000967856004400987 2006 eng d00aError correcting codes for adiabatic quantum computation0 aError correcting codes for adiabatic quantum computation c2006/11/140 v743 a 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. 1 aJordan, Stephen, P.1 aFarhi, Edward1 aShor, Peter, W. uhttp://arxiv.org/abs/quant-ph/0512170v301113nas a2200169 4500008004100000245005200041210005200093260001500145520061800160100002300778700001900801700001900820700001800839700001700857700002500874856004400899 2002 eng d00aExponential algorithmic speedup by quantum walk0 aExponential algorithmic speedup by quantum walk c2002/09/243 a 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. 1 aChilds, Andrew, M.1 aCleve, Richard1 aDeotto, Enrico1 aFarhi, Edward1 aGutmann, Sam1 aSpielman, Daniel, A. uhttp://arxiv.org/abs/quant-ph/0209131v201071nas a2200181 4500008004100000245003400041210003400075260001400109490000700123520059100130100002300721700001900744700001800763700002300781700001700804700002400821856004400845 2002 eng d00aQuantum search by measurement0 aQuantum search by measurement c2002/9/230 v663 a 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. 1 aChilds, Andrew, M.1 aDeotto, Enrico1 aFarhi, Edward1 aGoldstone, Jeffrey1 aGutmann, Sam1 aLandahl, Andrew, J. uhttp://arxiv.org/abs/quant-ph/0204013v100814nas a2200157 4500008004100000245007600041210006900117260001500186300001200201490000600213520033500219100002300554700001800577700001700595856004400612 2001 eng d00aAn example of the difference between quantum and classical random walks0 aexample of the difference between quantum and classical random w c2002/04/01 a35 - 430 v13 a 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. 1 aChilds, Andrew, M.1 aFarhi, Edward1 aGutmann, Sam uhttp://arxiv.org/abs/quant-ph/0103020v100767nas a2200145 4500008004100000245004800041210004800089260001500137490000700152520035800159100002300517700001800540700001900558856004400577 2001 eng d00aRobustness of adiabatic quantum computation0 aRobustness of adiabatic quantum computation c2001/12/140 v653 a 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. 1 aChilds, Andrew, M.1 aFarhi, Edward1 aPreskill, John uhttp://arxiv.org/abs/quant-ph/0108048v101120nas a2200145 4500008004100000245005100041210005100092260001500143520069100158100002300849700001800872700002300890700001700913856004400930 2000 eng d00aFinding cliques by quantum adiabatic evolution0 aFinding cliques by quantum adiabatic evolution c2000/12/193 a 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. 1 aChilds, Andrew, M.1 aFarhi, Edward1 aGoldstone, Jeffrey1 aGutmann, Sam uhttp://arxiv.org/abs/quant-ph/0012104v1