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

arXiv:quant-ph/0206059 · Physical Review A

Adiabatic quantum computing for random satisfiability problems

Tad Hogg

Published Feb 28, 2003• 104 citations
arXivHTMLPDF

Abstract

The discrete formulation of adiabatic quantum computing is compared with other search methods, classical and quantum, for random satisfiability (SAT) problems. With the number of steps growing only as the cube of the number of variables, the adiabatic method gives solution probabilities close to 1 for problem sizes feasible to evaluate via simulation on current computers. However, for these sizes the minimum energy gaps of most instances are fairly large, so the good performance scaling seen for small problems may not reflect asymptotic behavior where costs are dominated by tiny gaps. Moreover, the resulting search costs are much higher than for other methods. Variants of the quantum algorithm that do not match the adiabatic limit give lower costs, on average, and slower growth than the conventional GSAT heuristic method.

DOI
10.1103/physreva.67.022314

Related papers

An evaluation of the performance of the quantum adiabatic algorithm on random instances of k-SAT

James R. McBride

A quantum computational framework has been developed based on the adiabatic theorem. The theorem guarantees that a system with a time dependent Hamiltonian that is placed into its ground state will remain in its ground state provided that the Hamiltonian of the system varies slowly enough with time. This work investigates the performance of the quantum adiabatic algorithm on random instances of k-SAT. The performance of the algorithm is examined on subsets of k-SAT that are classically easy and on subsets that are classically difficult. The evaluation attempts to determine how the typical time required to solve the problems grows with the size of the problems. This evaluation is done by directly determining the required time from numerical integration of the dynamics of the system and by inferring this time using a result from the adiabatic theorem. This evaluation considers quantum systems composed of up to 23 bits and is performed on several large scale Beowulf clusters. As was seen in previous work, the direct integration studies show what appears to be only a quadratic growth rate in the required running time with the number of bits in problems that classically require exponential time. However, further studies show that these effects are caused by polynomial bounded matrix elements and are not indicative of the asymptotic behavior of the performance of the algorithm. The real asymptotic scaling of the performance of the algorithm is controlled by the ground state energy gap. When this is examined directly it is not currently possible to determine whether the growth rate of the running time of the algorithm is exponential or polynomial.

•Jan 1, 2002•1 citation

Solving Random Satisfiability Problems with Quantum Computers

Tad Hogg

Quantum computer algorithms can exploit the structure of random satisfiability problems. This paper extends a previous empirical evaluation of such an algorithm and gives an approximate asymptotic analysis accounting for both the average and variation of amplitudes among search states with the same costs. The analysis predicts good performance, on average, for a variety of problems including those near a phase transition associated with a high concentration of hard cases. Based on empirical evaluation for small problems, modifying the algorithm in light of this analysis improves its performance. The algorithm improves on both GSAT, a commonly used conventional heuristic, and quantum algorithms ignoring problem structure.

arXiv:quant-ph/0104048•Apr 9, 2001•5 citations

Study on discrete quantum adiabatic computation in combinatorial search problems

Mohamed El-fiky

The model of adiabatic quantum computation is a new paradigm for designing quantum algorithms. This model is based on the quantum adiabatic theorem, where a quantum computer evolves the quantum system slowly to switch gradually from an initial Hamiltonian with a ground state which is easy to construct, to a final Hamiltonian whose ground state encodes the solution of the problem to be solved. This dissertation presents an experimental study on the discrete quantum adiabatic computation in combinatorial search problems, we take k-Satisfiability problem as target problem to be examined. For k ? 3, k-SAT is NP-complete, i.e., among the most difficult NP problems in the worst case. Here we proposes a new monotonic variation method for the phase shift and mixing functions in the adiabatic quantum algorithm called the Quadric variation method, in order to speed up the algorithm search and decrease the overall resulting search cost. In addition, we present a better parameter configuration for the algorithm to be used with quadric variation as well as the previously proposed methods. The experiment are carried out in solving random instances of 3-SAT problems. The results indicate that the proposed method of using monotonic quadric variation in the phase functions of the adiabatic algorithm greatly improve the search behavior of the adiabatic algorithm and reduces the resulting search cost, also the results indicate that the better configuration of the algorithm parameters could greatly enhance the search behavior for the proposed method as well as the previously proposed methods.

•Jan 1, 2012•0 citations

A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability

Edward Farhi, Jeffrey Goldstone, Sam Gutmann

Quantum computation by adiabatic evolution, as described in quant-ph/0001106, will solve satisfiability problems if the running time is long enough. In certain special cases (that are classically easy) we know that the quantum algorithm requires a running time that grows as a polynomial in the number of bits. In this paper we present numerical results on randomly generated instances of an NP-complete problem and of a problem that can be solved classically in polynomial time. We simulate a quantum computer (of up to 16 qubits) by integrating the Schrodinger equation on a conventional computer. For both problems considered, for the set of instances studied, the required running time appears to grow slowly as a function of the number of bits.

arXiv:quant-ph/0007071•Jul 19, 2000•74 citations

Discrete adiabatic quantum computation with quadric variation

Mohamed El-fiky, Satoshi Ono, Shigeru Nakayama

Quantum adiabatic algorithm is a method of solving computational problems by evolving the ground state with a slowly varying Hamiltonian to reach the required output state. This paper proposes a new variation method for the phase functions, quadric variation method. The experiments are carried out solving random instances of 3-SAT problems with three variation methods: linear, cubic, and quadric. The experiment's result has revealed that the overall search costs with the quadric variation are less than those for other methods with higher probability of finding the solutions on average.

World Congress on Nature and Biologically Inspired Computing (NaBIC)•Dec 1, 2010•0 citations

Efficiency of structured adiabatic quantum computation

Juan José García‐Ripoll, Mari Carmen Bañuls

We show enough evidence that a structured version of Adiabatic Quantum Computation (AQC) is efficient for most satisfiability problems. More precisely, when the success probability is fixed beforehand, the computational resources grow subexponentially in the number of qubits. Our study focuses on random satisfiability and exact cover problems, developing a multi-step algorithm that solves clauses one by one. Relating the computational cost to classical properties of the problem, we collect significant statistics with up to N=140 qubits, around the phase transitions, which is where the hardest problems appear.

arXiv:0812.1760•Dec 9, 2008•2 citations
The discrete formulation of adiabatic quantum computing is compared with other search methods, classical and quantum, for random satisfiability (SAT) problems. With the number of steps growing only as the cube of the number of variables, the adiabatic method gives solution probabilities close to 1 for problem sizes feasible to evaluate via simulation on current computers. However, for these sizes the minimum energy gaps of most instances are fairly large, so the good performance scaling seen for small problems may not reflect asymptotic behavior where costs are dominated by tiny gaps. Moreover, the resulting search costs are much higher than for other methods. Variants of the quantum algorithm that do not match the adiabatic limit give lower costs, on average, and slower growth than the conventional GSAT heuristic method.
A quantum computational framework has been developed based on the adiabatic theorem. The theorem guarantees that a system with a time dependent Hamiltonian that is placed into its ground state will remain in its ground state provided that the Hamiltonian of the system varies slowly enough with time. This work investigates the performance of the quantum adiabatic algorithm on random instances of k-SAT. The performance of the algorithm is examined on subsets of k-SAT that are classically easy and on subsets that are classically difficult. The evaluation attempts to determine how the typical time required to solve the problems grows with the size of the problems. This evaluation is done by directly determining the required time from numerical integration of the dynamics of the system and by inferring this time using a result from the adiabatic theorem. This evaluation considers quantum systems composed of up to 23 bits and is performed on several large scale Beowulf clusters. As was seen in previous work, the direct integration studies show what appears to be only a quadratic growth rate in the required running time with the number of bits in problems that classically require exponential time. However, further studies show that these effects are caused by polynomial bounded matrix elements and are not indicative of the asymptotic behavior of the performance of the algorithm. The real asymptotic scaling of the performance of the algorithm is controlled by the ground state energy gap. When this is examined directly it is not currently possible to determine whether the growth rate of the running time of the algorithm is exponential or polynomial.
Quantum computer algorithms can exploit the structure of random satisfiability problems. This paper extends a previous empirical evaluation of such an algorithm and gives an approximate asymptotic analysis accounting for both the average and variation of amplitudes among search states with the same costs. The analysis predicts good performance, on average, for a variety of problems including those near a phase transition associated with a high concentration of hard cases. Based on empirical evaluation for small problems, modifying the algorithm in light of this analysis improves its performance. The algorithm improves on both GSAT, a commonly used conventional heuristic, and quantum algorithms ignoring problem structure.
The model of adiabatic quantum computation is a new paradigm for designing quantum algorithms. This model is based on the quantum adiabatic theorem, where a quantum computer evolves the quantum system slowly to switch gradually from an initial Hamiltonian with a ground state which is easy to construct, to a final Hamiltonian whose ground state encodes the solution of the problem to be solved. This dissertation presents an experimental study on the discrete quantum adiabatic computation in combinatorial search problems, we take k-Satisfiability problem as target problem to be examined. For k ? 3, k-SAT is NP-complete, i.e., among the most difficult NP problems in the worst case. Here we proposes a new monotonic variation method for the phase shift and mixing functions in the adiabatic quantum algorithm called the Quadric variation method, in order to speed up the algorithm search and decrease the overall resulting search cost. In addition, we present a better parameter configuration for the algorithm to be used with quadric variation as well as the previously proposed methods. The experiment are carried out in solving random instances of 3-SAT problems. The results indicate that the proposed method of using monotonic quadric variation in the phase functions of the adiabatic algorithm greatly improve the search behavior of the adiabatic algorithm and reduces the resulting search cost, also the results indicate that the better configuration of the algorithm parameters could greatly enhance the search behavior for the proposed method as well as the previously proposed methods.
Quantum computation by adiabatic evolution, as described in quant-ph/0001106, will solve satisfiability problems if the running time is long enough. In certain special cases (that are classically easy) we know that the quantum algorithm requires a running time that grows as a polynomial in the number of bits. In this paper we present numerical results on randomly generated instances of an NP-complete problem and of a problem that can be solved classically in polynomial time. We simulate a quantum computer (of up to 16 qubits) by integrating the Schrodinger equation on a conventional computer. For both problems considered, for the set of instances studied, the required running time appears to grow slowly as a function of the number of bits.
Quantum adiabatic algorithm is a method of solving computational problems by evolving the ground state with a slowly varying Hamiltonian to reach the required output state. This paper proposes a new variation method for the phase functions, quadric variation method. The experiments are carried out solving random instances of 3-SAT problems with three variation methods: linear, cubic, and quadric. The experiment's result has revealed that the overall search costs with the quadric variation are less than those for other methods with higher probability of finding the solutions on average.
We show enough evidence that a structured version of Adiabatic Quantum Computation (AQC) is efficient for most satisfiability problems. More precisely, when the success probability is fixed beforehand, the computational resources grow subexponentially in the number of qubits. Our study focuses on random satisfiability and exact cover problems, developing a multi-step algorithm that solves clauses one by one. Relating the computational cost to classical properties of the problem, we collect significant statistics with up to N=140 qubits, around the phase transitions, which is where the hardest problems appear.