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:2207.09984 · Physica A Statistical Mechanics and its Applications

Adiabatic based Algorithm for SAT: A comprehensive algorithmic description

Eric Bourreau, Gérard Fleury, Philippe Lacomme

Published Sep 15, 2023• 0 citations
arXivHTMLPDF
DOI
10.1016/j.physa.2023.129206

Related papers

Study on discrete adiabatic quantum computation in 3-SAT problems

Mohamed El-fiky, Satoshi Ono, Shigeru Nakayama

Artificial Life and Robotics•Jun 1, 2011•3 citations

Adiabatic based Algorithm : a comprehensivealgorithmic description

Gérard Fleury, Philippe Lacomme

•Jul 3, 2022•0 citations

Adiabatic quantum algorithms as quantum phase transitions: First versus second order

Ralf Schützhold, Gernot Schaller

In the continuum limit (large number of qubits), adiabatic quantum algorithms display a remarkable similarity to sweeps through quantum phase transitions. We find that transitions of second or higher order are advantageous in comparison to those of first order. With this insight, we propose an adiabatic quantum algorithm for the solution of 3-satisfiability (3-SAT) problems (exact cover), which is significantly faster than previous proposals according to numerical simulations (up to 20 qubits). These findings suggest that adiabatic quantum algorithms can solve NP-complete problems such as 3-SAT much faster than the Grover search routine (yielding a quadratic enhancement), possibly even with an exponential speedup.

arXiv:quant-ph/0608017•Physical Review A•Dec 28, 2006•79 citations

Quantum hybrid algorithm for solving SAT problem

Charles Varmantchaonala Moudina, Jean Louis Ebongue Kedieng Fendji, J.-P. Tchapet Njafa +1 more

Engineering Applications of Artificial Intelligence•Mar 2, 2023•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

Quantum Hybrid Algorithm for Solving SAT Problem

Charles Varmantchaonala Moudina, Jean Louis Ebongue Kedieng Fendji, J.-P. Tchapet Njafa +1 more

•Jan 1, 2022•1 citation
In the continuum limit (large number of qubits), adiabatic quantum algorithms display a remarkable similarity to sweeps through quantum phase transitions. We find that transitions of second or higher order are advantageous in comparison to those of first order. With this insight, we propose an adiabatic quantum algorithm for the solution of 3-satisfiability (3-SAT) problems (exact cover), which is significantly faster than previous proposals according to numerical simulations (up to 20 qubits). These findings suggest that adiabatic quantum algorithms can solve NP-complete problems such as 3-SAT much faster than the Grover search routine (yielding a quadratic enhancement), possibly even with an exponential speedup.