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 Goldston, David Gosset +3 more

We construct a set of instances of 3SAT which are not solved efficiently using the simplestquantum adiabatic algorithm. These instances are obtained by picking randomclauses all consistent with two disparate planted solutions and then penalizing one ofthem with a single additional clause. We argue that by randomly modifying the beginningHamiltonian, one obtains (with substantial probability) an adiabatic path thatremoves this difficulty. This suggests that the quantum adiabatic algorithm should ingeneral be run on each instance with many different random paths leading to the problemHamiltonian. We do not know whether this trick will help for a random instance of3SAT (as opposed to an instance from the particular set we consider), especially if theinstance 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 tonumerically 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 withup to 150 spins.We construct a set of instances of 3SAT which are not solved efficiently using the simplestquantum adiabatic algorithm. These instances are obtained by picking randomclauses all consistent with two disparate planted solutions and then penalizing one ofthem with a single additional clause. We argue that by randomly modifying the beginningHamiltonian, one obtains (with substantial probability) an adiabatic path thatremoves this difficulty. This suggests that the quantum adiabatic algorithm should ingeneral be run on each instance with many different random paths leading to the problemHamiltonian. We do not know whether this trick will help for a random instance of3SAT (as opposed to an instance from the particular set we consider), especially if theinstance 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 tonumerically 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 withup to 150 spins.

Quantum Information and ComputationMar 1, 201137 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

Adiabatic Quantum Algorithms for the NP-Complete MIS, Exact Cover and 3SAT Problems

Vicky Choi

The problem Hamiltonian of the adiabatic quantum algorithm for the maximum-weight independent set problem (MIS) that is based on the reduction to the Ising problem (as described in [Choi08]) has flexible parameters. We show that by choosing the parameters appropriately in the problem Hamiltonian (without changing the problem to be solved) for MIS on CK graphs, we can prevent the first order quantum phase transition and significantly change the minimum spectral gap. We raise the basic question about what the appropriate formulation of adiabatic running time should be. We also describe adiabatic quantum algorithms for Exact Cover and 3SAT in which the problem Hamiltonians are based on the reduction to MIS. We point out that the argument in Altshuler et al.(arXiv:0908.2782 [quant-ph]) that their adiabatic quantum algorithm failed with high probability for randomly generated instances of Exact Cover does not carry over to this new algorithm.The problem Hamiltonian of the adiabatic quantum algorithm for the maximum-weight independent set problem (MIS) that is based on the reduction to the Ising problem (as described in [Choi08]) has flexible parameters. We show that by choosing the parameters appropriately in the problem Hamiltonian (without changing the problem to be solved) for MIS on CK graphs, we can prevent the first order quantum phase transition and significantly change the minimum spectral gap. We raise the basic question about what the appropriate formulation of adiabatic running time should be. We also describe adiabatic quantum algorithms for Exact Cover and 3SAT in which the problem Hamiltonians are based on the reduction to MIS. We point out that the argument in Altshuler et al.(arXiv:0908.2782 [quant-ph]) that their adiabatic quantum algorithm failed with high probability for randomly generated instances of Exact Cover does not carry over to this new algorithm.

Jan 1, 20160 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

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