We construct a set of instances of 3SAT which are not solved efficiently using the simplest quantum adiabatic algorithm. These instances are obtained by picking random clauses all consistent with two disparate planted solutions and then penalizing one of them with a single additional clause. We argue that by randomly modifying the beginning Hamiltonian, one obtains (with substantial probability) an adiabatic path that removes this difficulty. This suggests that the quantum adiabatic algorithm should in general be run on each instance with many different random paths leading to the problem Hamiltonian. We do not know whether this trick will help for a random instance of 3SAT (as opposed to an instance from the particular set we consider), especially if the instance has an exponential number of disparate assignments that violate few clauses. We use a continuous imaginary time Quantum Monte Carlo algorithm in a novel way to numerically investigate the ground state as well as the first excited state of our system. Our arguments are supplemented by Quantum Monte Carlo data from simulations with up to 150 spins.We construct a set of instances of 3SAT which are not solved efficiently using the simplest quantum adiabatic algorithm. These instances are obtained by picking random clauses all consistent with two disparate planted solutions and then penalizing one of them with a single additional clause. We argue that by randomly modifying the beginning Hamiltonian, one obtains (with substantial probability) an adiabatic path that removes this difficulty. This suggests that the quantum adiabatic algorithm should in general be run on each instance with many different random paths leading to the problem Hamiltonian. We do not know whether this trick will help for a random instance of 3SAT (as opposed to an instance from the particular set we consider), especially if the instance has an exponential number of disparate assignments that violate few clauses. We use a continuous imaginary time Quantum Monte Carlo algorithm in a novel way to numerically investigate the ground state as well as the first excited state of our system. Our arguments are supplemented by Quantum Monte Carlo data from simulations with up to 150 spins.

arXiv:0909.4766Sep 25, 20093 citations

Quantum adiabatic algorithms, small gaps, and different paths

Edward Farhi, Jeffrey Goldstone, David Gosset +3 more

Quantum Information and ComputationMar 1, 201157 citations

Different Strategies for Optimization Using the Quantum Adiabatic Algorithm

Elizabeth Crosson, Edward Farhi, Cedric Yen-Yu Lin +2 more

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.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.

arXiv:1401.7320Jan 28, 201466 citations

Algorithmic approach to adiabatic quantum optimization

Neil G. Dickson, M. H. S. Amin

It is believed that the presence of anticrossings with exponentially small gaps between the lowest two energy levels of the system Hamiltonian can render adiabatic quantum optimization inefficient. Here, we present a simple adiabatic quantum algorithm designed to eliminate exponentially small gaps caused by anticrossings between eigenstates that correspond with the local and global minima of the problem Hamiltonian. In each iteration of the algorithm, information is gathered about the local minima that are reached after passing the anticrossing nonadiabatically. This information is then used to penalize pathways to the corresponding local minima by adjusting the initial Hamiltonian. This is repeated for multiple clusters of local minima as needed. We generate 64-qubit random instances of the maximum independent set problem, skewed to be extremely hard, with between ${10}^{5}$ and ${10}^{6}$ highly degenerate local minima. Using quantum Monte Carlo simulations, it is found that the algorithm can trivially solve all of the instances in $\ensuremath{\sim}$10 iterations.It is believed that the presence of anticrossings with exponentially small gaps between the lowest two energy levels of the system Hamiltonian can render adiabatic quantum optimization inefficient. Here, we present a simple adiabatic quantum algorithm designed to eliminate exponentially small gaps caused by anticrossings between eigenstates that correspond with the local and global minima of the problem Hamiltonian. In each iteration of the algorithm, information is gathered about the local minima that are reached after passing the anticrossing nonadiabatically. This information is then used to penalize pathways to the corresponding local minima by adjusting the initial Hamiltonian. This is repeated for multiple clusters of local minima as needed. We generate 64-qubit random instances of the maximum independent set problem, skewed to be extremely hard, with between ${10}^{5}$ and ${10}^{6}$ highly degenerate local minima. Using quantum Monte Carlo simulations, it is found that the algorithm can trivially solve all of the instances in $\ensuremath{\sim}$10 iterations.

arXiv:1108.3303Physical Review AMar 5, 201240 citations

Statistical Analysis for Quantum Adiabatic Computations: Quantum Monte Carlo Annealing

T. Neuhaus

Quantum adiabatic computations are designed to determine the ground state configurations of an classical problem Hamiltonian H3SAT within quantum theory and at imaginary time allow statistical mechanics studies for the computational e_ciency of the ground state search. We mention a recent determination of the quantum complexity, i.e. the mass-gap _mGAP for a specific ensemble of three-satisfiability (3SAT) problems with a unique satisfiability assignment, which shows an exponential increase of the gap correlation length _GAP with _GAP = 1=_mGAP. In 3SAT we present numerical data for the behavior of quantum Monte Carlo annealing cycles in search for the ground state. The findings show, that for the specific set of realizations quantum Monte Carlo searches in 3SAT fail above a sharp cut-o_ Kcut in the complexity K, which exemplifies the intractable nature of 3SAT.Quantum adiabatic computations are designed to determine the ground state configurations of an classical problem Hamiltonian H3SAT within quantum theory and at imaginary time allow statistical mechanics studies for the computational e_ciency of the ground state search. We mention a recent determination of the quantum complexity, i.e. the mass-gap _mGAP for a specific ensemble of three-satisfiability (3SAT) problems with a unique satisfiability assignment, which shows an exponential increase of the gap correlation length _GAP with _GAP = 1=_mGAP. In 3SAT we present numerical data for the behavior of quantum Monte Carlo annealing cycles in search for the ground state. The findings show, that for the specific set of realizations quantum Monte Carlo searches in 3SAT fail above a sharp cut-o_ Kcut in the complexity K, which exemplifies the intractable nature of 3SAT.

Physics ProcediaJan 1, 20110 citations

Eigenlevel statistics of the quantum adiabatic algorithm

Marko Žnidarič

We study the eigenlevel spectrum of quantum adiabatic algorithm for 3-satisfiability problem, focusing on single-solution instances. The properties of the ground state and the associated gap, crucial for determining the running time of the algorithm, are found to be far from the predictions of random matrix theory. The distribution of gaps between the ground and the first excited state shows an abundance of small gaps. Eigenstates from the central part of the spectrum are, on the other hand, well described by random matrix theory.We study the eigenlevel spectrum of quantum adiabatic algorithm for 3-satisfiability problem, focusing on single-solution instances. The properties of the ground state and the associated gap, crucial for determining the running time of the algorithm, are found to be far from the predictions of random matrix theory. The distribution of gaps between the ground and the first excited state shows an abundance of small gaps. Eigenstates from the central part of the spectrum are, on the other hand, well described by random matrix theory.

arXiv:quant-ph/0512018Physical Review ANov 30, 20052 citations

{10}^{5}

and

{10}^{6}

highly degenerate local minima. Using quantum Monte Carlo simulations, it is found that the algorithm can trivially solve all of the instances in $\ensuremath{\sim}$10 iterations.