Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physical Review A

Increase of degeneracy improves the performance of the quantum adiabatic algorithm

Quntao Zhuang

Published Nov 13, 2014• 15 citations
Publisher

Abstract

We propose a strategy to improve the performance of the quantum adiabatic algorithm (QAA) on an NP-hard (nondeterministic-polynomial-time-hard) problem exact cover, by increasing the ground-state degeneracy of the problem Hamiltonian. Our strategy is based on the empirical finding that for the QAA the difficulty of random instances decreases with the degeneracy of the ground state. We increase the degeneracy by adding extra qubits to form additional clauses. Our numerical results show that on average our strategy can provide an increase in the minimum gap size along the linear interpolation path of Hamiltonian for both easy and difficult instances. The success probability at fixed total evolution time is thus increased.

DOI
10.1103/physreva.90.052317

Related papers

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.

arXiv:1401.7320•Jan 28, 2014•66 citations

Quantum adiabatic algorithms, small gaps, and different paths

Edward Farhi, Jeffrey Goldstone, David Gosset +3 more

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.

Quantum Information and Computation•Mar 1, 2011•57 citations

Quantum Adiabatic Algorithms, Small Gaps, and Different Paths

Edward Farhi, Jeffrey Goldstone, David Gosset +3 more

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.4766•Sep 25, 2009•3 citations

A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem

Edward Farhi, Jeffrey Goldstone, Sam Gutmann +3 more

A quantum system will stay near its instantaneous ground state if the Hamiltonian that governs its evolution varies slowly enough. This quantum adiabatic behavior is the basis of a new class of algorithms for quantum computing. We tested one such algorithm by applying it to randomly generated hard instances of an NP-complete problem. For the small examples that we could simulate, the quantum adiabatic algorithm worked well, providing evidence that quantum computers (if large ones can be built) may be able to outperform ordinary computers on hard sets of instances of NP-complete problems.

arXiv:quant-ph/0104129•Science•Apr 20, 2001•2,055 citations

Schedule path optimization for adiabatic quantum computing and optimization

Lishan Zeng, Jun Zhang, Mohan Sarovar

Abstract Adiabatic quantum computing and optimization have garnered much attention recently as possible models for achieving a quantum advantage over classical approaches to optimization and other special purpose computations. Both techniques are probabilistic in nature and the minimum gap between the ground state and first excited state of the system during evolution is a major factor in determining the success probability. In this work we investigate a strategy for increasing the minimum gap and success probability by introducing intermediate Hamiltonians that modify the evolution path between initial and final Hamiltonians. We focus on an optimization problem relevant to recent hardware implementations and present numerical evidence for the existence of a purely local intermediate Hamiltonian that achieve the optimum performance in terms of pushing the minimum gap to one of the end points of the evolution. As a part of this study we develop a convex optimization formulation of the search for optimal adiabatic schedules that makes this computation more tractable, and which may be of independent interest. We further study the effectiveness of random intermediate Hamiltonians on the minimum gap and success probability, and empirically find that random Hamiltonians have a significant probability of increasing the success probability, but only by a modest amount.

arXiv:1505.00209•Journal of Physics A Mathematical and Theoretical•Mar 14, 2016•31 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.

Quantum Information and Computation•Mar 1, 2011•37 citations
We propose a strategy to improve the performance of the quantum adiabatic algorithm (QAA) on an NP-hard (nondeterministic-polynomial-time-hard) problem exact cover, by increasing the ground-state degeneracy of the problem Hamiltonian. Our strategy is based on the empirical finding that for the QAA the difficulty of random instances decreases with the degeneracy of the ground state. We increase the degeneracy by adding extra qubits to form additional clauses. Our numerical results show that on average our strategy can provide an increase in the minimum gap size along the linear interpolation path of Hamiltonian for both easy and difficult instances. The success probability at fixed total evolution time is thus increased.
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 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.
A quantum system will stay near its instantaneous ground state if the Hamiltonian that governs its evolution varies slowly enough. This quantum adiabatic behavior is the basis of a new class of algorithms for quantum computing. We tested one such algorithm by applying it to randomly generated hard instances of an NP-complete problem. For the small examples that we could simulate, the quantum adiabatic algorithm worked well, providing evidence that quantum computers (if large ones can be built) may be able to outperform ordinary computers on hard sets of instances of NP-complete problems.
Abstract Adiabatic quantum computing and optimization have garnered much attention recently as possible models for achieving a quantum advantage over classical approaches to optimization and other special purpose computations. Both techniques are probabilistic in nature and the minimum gap between the ground state and first excited state of the system during evolution is a major factor in determining the success probability. In this work we investigate a strategy for increasing the minimum gap and success probability by introducing intermediate Hamiltonians that modify the evolution path between initial and final Hamiltonians. We focus on an optimization problem relevant to recent hardware implementations and present numerical evidence for the existence of a purely local intermediate Hamiltonian that achieve the optimum performance in terms of pushing the minimum gap to one of the end points of the evolution. As a part of this study we develop a convex optimization formulation of the search for optimal adiabatic schedules that makes this computation more tractable, and which may be of independent interest. We further study the effectiveness of random intermediate Hamiltonians on the minimum gap and success probability, and empirically find that random Hamiltonians have a significant probability of increasing the success probability, but only by a modest amount.
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.