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

New Journal of Physics

A quantum differentiation ofk-SAT instances

Boaz Tamir, Gerardo Ortíz

Published Jul 28, 2010• 0 citations
Publisher

Abstract

We present a quantum adiabatic algorithm to differentiate between k -SAT instances, those with no solutions and those that have many solutions. The time complexity of the algorithm is a function of the energy gap between the subspace of all 0-eigenvectors (ground states) and the first excited states manifold, and scales polynomially with the number of resources. The idea of gaps between subspaces suggests a new tool to analyze time complexity in adiabatic quantum machines.

DOI
10.1088/1367-2630/12/7/075028

Related papers

Exponential complexity of an adiabatic algorithm for an NP-complete problem

Marko Žnidarič, Martin Horvat

We prove an analytical expression for the size of the gap between the ground and the first excited state of quantum adiabatic algorithm for the 3-satisfiability, where the initial Hamiltonian is a projector on the subspace complementary to the ground state. For large problem sizes the gap decreases exponentially and as a consequence the required running time is also exponential.

arXiv:quant-ph/0509162•Physical Review A•Feb 17, 2006•66 citations

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

Quantum algorithm for a set of quantum 2SAT problems*

Yanglin Hu, Zhelun Zhang, Biao Wu

We present a quantum adiabatic algorithm for a set of quantum 2-satisfiability (Q2SAT) problem, which is a generalization of 2-satisfiability (2SAT) problem. For a Q2SAT problem, we construct the Hamiltonian which is similar to that of a Heisenberg chain. All the solutions of the given Q2SAT problem span the subspace of the degenerate ground states. The Hamiltonian is adiabatically evolved so that the system stays in the degenerate subspace. Our numerical results suggest that the time complexity of our algorithm is O(n 3.9) for yielding non-trivial solutions for problems with the number of clauses m = dn(n – 1)/2 (d ≲ 0.1). We discuss the advantages of our algorithm over the known quantum and classical algorithms.

arXiv:2009.02600•Chinese Physics B•Dec 30, 2020•7 citations

Scaling of the running time of the quantum adiabatic algorithm for propositional satisfiability

Marko Žnidarič

We numerically study the quantum adiabatic algorithm for propositional satisfiability. A new class of previously unknown hard instances is identified among random problems. We numerically find that the running time for such instances grows exponentially with their size. The worst case complexity of the quantum adiabatic algorithm therefore seems to be exponential.

arXiv:quant-ph/0502077•Physical Review A•Jun 8, 2005•37 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.

arXiv:quant-ph/0512018•Physical Review A•Nov 30, 2005•2 citations

Quantum Computation by Adiabatic Evolution

Edward Farhi, Jeffrey Goldstone, Sam Gutmann +1 more

We give a quantum algorithm for solving instances of the satisfiability problem, based on adiabatic evolution. The evolution of the quantum state is governed by a time-dependent Hamiltonian that interpolates between an initial Hamiltonian, whose ground state is easy to construct, and a final Hamiltonian, whose ground state encodes the satisfying assignment. To ensure that the system evolves to the desired final ground state, the evolution time must be big enough. The time required depends on the minimum energy difference between the two lowest states of the interpolating Hamiltonian. We are unable to estimate this gap in general. We give some special symmetric cases of the satisfiability problem where the symmetry allows us to estimate the gap and we show that, in these cases, our algorithm runs in polynomial time.

arXiv:quant-ph/0001106•Jan 28, 2000•2,419 citations
We present a quantum adiabatic algorithm to differentiate between k -SAT instances, those with no solutions and those that have many solutions. The time complexity of the algorithm is a function of the energy gap between the subspace of all 0-eigenvectors (ground states) and the first excited states manifold, and scales polynomially with the number of resources. The idea of gaps between subspaces suggests a new tool to analyze time complexity in adiabatic quantum machines.
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.
We present a quantum adiabatic algorithm for a set of quantum 2-satisfiability (Q2SAT) problem, which is a generalization of 2-satisfiability (2SAT) problem. For a Q2SAT problem, we construct the Hamiltonian which is similar to that of a Heisenberg chain. All the solutions of the given Q2SAT problem span the subspace of the degenerate ground states. The Hamiltonian is adiabatically evolved so that the system stays in the degenerate subspace. Our numerical results suggest that the time complexity of our algorithm is O(n 3.9) for yielding non-trivial solutions for problems with the number of clauses m = dn(n – 1)/2 (d ≲ 0.1). We discuss the advantages of our algorithm over the known quantum and classical algorithms.
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 give a quantum algorithm for solving instances of the satisfiability problem, based on adiabatic evolution. The evolution of the quantum state is governed by a time-dependent Hamiltonian that interpolates between an initial Hamiltonian, whose ground state is easy to construct, and a final Hamiltonian, whose ground state encodes the satisfying assignment. To ensure that the system evolves to the desired final ground state, the evolution time must be big enough. The time required depends on the minimum energy difference between the two lowest states of the interpolating Hamiltonian. We are unable to estimate this gap in general. We give some special symmetric cases of the satisfiability problem where the symmetry allows us to estimate the gap and we show that, in these cases, our algorithm runs in polynomial time.