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•61 citations

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•38 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•536 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.

•Jan 28, 2000•696 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.
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.
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.