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

Theoretical Computer Science

Three “quantum” algorithms to solve 3-SAT

Alberto Leporati, Sara Felloni

Published Dec 1, 2006• 18 citations
Publisher
DOI
10.1016/j.tcs.2006.11.026

Related papers

A quantum algorithm for solving the 3-SAT problem

Lily Chen

The method in this paper is wrong.

arXiv:1210.4321•Oct 16, 2012•0 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•Jan 1, 2022•8 citations

Quantum Solution for the 3-SAT Problem Based on IBM Q

Ying Zhang, Yuxiang Bian, Qiang Fan +1 more

Lecture notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering•Jan 1, 2020•4 citations

Quantum mechanical NMR implementation of DNA algorithm for satisfiability problem

Ren, T. T., Mang Feng, Weng-Long Chang +2 more

DNA computation could in principle solve the satisfiability (SAT) problem due to the operations in parallel on extremely large numbers of strands. We demonstrate some quantum gates corresponding to the DNA ones, based on which an implementation of DNA algorithm for SAT problem is available by quantum mechanical way. Since quantum computation owns the favorable feature of operations in parallel on 2$^{n}$ states by using only n qubits, instead of 2$^{n}$ strands in DNA computation, computational complexity is much reduced in treating the SAT problem quantum mechanically. We take a three-clause SAT problem with two variables as an example, and carry out a NMR experiment for solving a one-variable SAT problem.

arXiv:0802.0232•Feb 2, 2008•0 citations

Quantum Computing Approach for Solving Exactly-1 3-SAT Using Grover's Algorithm

E. Afreen Banu, Amol Atmaram Dhumal, Lukesh Kadu +3 more

This study investigates the application of quantum computing to the Boolean satisfaction problem (SAT), with a special focus on the special case of the Exactly-1 3-SAT problem. Quantum computing has shown significant advantages in solving various computational problems and achieving exponential accelerations. This study designs and implements a quantum algorithm to identify assignments that prove Boolean formulas of bound form using the Grover search algorithm. We tested the implementation of three quantum circuits using as many quantum techniques as possible using the IBM quantum simulator. Only the second implementation showed consistent results due to the number of qubits, decoherence time, and circuit complexity. This study demonstrates that the design of algorithms meets hardware constraints and lays the foundation for future research as quantum devices improve.

International Conference for Advancement in Technology (ICONAT)•Sep 19, 2025•0 citations

Efficient Quantum Circuit Synthesis for SAT-Oracle With Limited Ancillary Qubit

Shuai Yang, Wei Zi, Bujiao Wu +3 more

One of the main concerns in the era of noisy intermediate-scale quantum (NISQ) computing and fault-tolerant quantum computing is the optimization of circuit implementation for quantum oracles, particularly with limited resources. Synthesizing a satisfiability (SAT) oracle, a crucial component in solving SAT problems, presents a significant challenge. The current state-of-the-art implementation of an$m$-clause SAT-oracle necessitates$2m-1$ancillary qubits and a linear number of elementary gates. We develop two efficient and ancilla-adjustable synthesis algorithms to reduce the overall quantum resource usage. Our first quantum oracle algorithm achieves quadratic optimization in the number of ancillary qubits with merely eight times increased circuit size. We also show that using only three ancillary qubits with quadratic circuit size expansion is enough. Our second algorithm optimizes the circuit depth of the SAT oracle to$\tilde {O}(\log m)$using$m$ancillary qubits. By running our algorithms on classical intractable SAT instances featured in SAT competitions, the experiment results show that our required quantum resources align well with our theoretical analysis. Our algorithms highlight the scalability of SAT-oracle-based algorithms in near-term quantum devices, such as Grover’s algorithm.

arXiv:2101.05430•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Oct 19, 2023•5 citations
DNA computation could in principle solve the satisfiability (SAT) problem due to the operations in parallel on extremely large numbers of strands. We demonstrate some quantum gates corresponding to the DNA ones, based on which an implementation of DNA algorithm for SAT problem is available by quantum mechanical way. Since quantum computation owns the favorable feature of operations in parallel on 2n^{n}n states by using only n qubits, instead of 2n^{n}n strands in DNA computation, computational complexity is much reduced in treating the SAT problem quantum mechanically. We take a three-clause SAT problem with two variables as an example, and carry out a NMR experiment for solving a one-variable SAT problem.
This study investigates the application of quantum computing to the Boolean satisfaction problem (SAT), with a special focus on the special case of the Exactly-1 3-SAT problem. Quantum computing has shown significant advantages in solving various computational problems and achieving exponential accelerations. This study designs and implements a quantum algorithm to identify assignments that prove Boolean formulas of bound form using the Grover search algorithm. We tested the implementation of three quantum circuits using as many quantum techniques as possible using the IBM quantum simulator. Only the second implementation showed consistent results due to the number of qubits, decoherence time, and circuit complexity. This study demonstrates that the design of algorithms meets hardware constraints and lays the foundation for future research as quantum devices improve.
One of the main concerns in the era of noisy intermediate-scale quantum (NISQ) computing and fault-tolerant quantum computing is the optimization of circuit implementation for quantum oracles, particularly with limited resources. Synthesizing a satisfiability (SAT) oracle, a crucial component in solving SAT problems, presents a significant challenge. The current state-of-the-art implementation of anmmm-clause SAT-oracle necessitates2m−12m-12m−1ancillary qubits and a linear number of elementary gates. We develop two efficient and ancilla-adjustable synthesis algorithms to reduce the overall quantum resource usage. Our first quantum oracle algorithm achieves quadratic optimization in the number of ancillary qubits with merely eight times increased circuit size. We also show that using only three ancillary qubits with quadratic circuit size expansion is enough. Our second algorithm optimizes the circuit depth of the SAT oracle toO~(log⁡m)\tilde {O}(\log m)O~(logm)usingmmmancillary qubits. By running our algorithms on classical intractable SAT instances featured in SAT competitions, the experiment results show that our required quantum resources align well with our theoretical analysis. Our algorithms highlight the scalability of SAT-oracle-based algorithms in near-term quantum devices, such as Grover’s algorithm.