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:2106.09976 · IEEE Transactions on Quantum Engineering

Finding Solutions to the Integer Case Constraint Satisfiability Problem Using Grover’s Algorithm

Gayathree M. Vinod, Anil Shaji

Published Jan 1, 2021• 14 citations
arXivHTMLPDF

Abstract

Constraint satisfiability problems, crucial to several applications, are solved on a quantum computer using Grover's search algorithm, leading to a quadratic improvement over the classical case. The solutions are obtained with high probability for several cases and are illustrated for the cases involving two variables for both 3- and 4-bit numbers. Methods are defined for inequality comparisons, and these are combined according to the form of the satisfiability formula, to form the oracle for the algorithm. The circuit is constructed using IBM Qiskit and is verified on an IBM simulator. It is further executed on one of the Noisy Intermediate-Scale Quantum (NISQ) processors from IBM on the cloud. Noise levels in the processor at present are found to be too high for successful execution. Running the algorithm on the simulator with a custom noise model lets us identify the noise threshold for successful execution.

DOI
10.1109/tqe.2021.3120449

Related papers

A Benchmarking Study of Grover’s Algorithm for Solving Boolean SAT with Quantum Circuits

Jirapas U. Jipipob, Prabhas Chongstitvatana

This study explores how well Grover's Algorithm performs in solving the Boolean Satisfiability Problem (SAT) using quantum circuits. The algorithm is implemented with IBM's Qiskit framework and compared to classical brute-force methods. Experiments focus on 3-SAT, 4-SAT, and 5-SAT problems, using quantum simulators and IBM quantum hardware. The results show that Grover's Algorithm is more efficient, offering a theoretical quadratic speedup over classical methods. However, practical issues like limited qubit availability, hardware noise, and optimization challenges impact its current performance. The data highlights the potential for quantum computing to scale and solve NP-complete problems. This research shows how quantum computing can improve problem-solving and lays the groundwork for future studies on more complex SAT problems and advanced quantum hardware.

International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON)•May 20, 2025•1 citation

A benchmarking study of grover's algorithm for solving boolean sat with quantum circuits

Jirapas U. Jipipob

This study explores how well Grover's Algorithm performs in solving the Boolean Satisfiability Problem (SAT) using quantum circuits. The algorithm is implemented with IBM's Qiskit framework and compared to classical brute-force methods. Experiments focus on 3-SAT, 4-SAT, and 5-SAT problems, using quantum simulators and IBM quantum hardware. The results show that Grover's Algorithm is more efficient, offering a theoretical quadratic speedup over classical methods. However, practical issues like limited qubit availability, hardware noise, and optimization challenges impact its current performance. The data highlights the potential for quantum computing to scale and solve NP-complete problems. This research shows how quantum computing can improve problem-solving and lays the groundwork for future studies on more complex SAT problems and advanced quantum hardware.

•Jan 1, 2025•0 citations

Classical vs Quantum Search: Experimental Performance Analysis of Grover's Algorithm on Real IBM Quantum Hardware

Kundan Kumar Sahu

Grover's quantum search algorithm provides a proven quadratic speedup over classical linear search for unstructured databases. While its theoretical advantage is well established, experimental validation on real noisy intermediate-scale quantum (NISQ) hardware remains limited by noise, decoherence, and hardware constraints. In this work, we present an experimental comparison between classical linear search and Grover's quantum search algorithm executed on IBM Quantum real superconducting hardware using Qiskit Runtime. A four-qubit implementation corresponding to a 16-element search space is evaluated across multiple experimental runs. The results demonstrate consistent amplitude amplification, achieving an average success probability of 54.25% and an amplification factor of 8.68× over random guessing. Although classical execution remains faster in wall-clock time due to quantum hardware overhead, the experiment empirically validates the algorithmic advantage of Grover's search and quantifies the performance gap between ideal and real quantum processors in the NISQ era.

•Dec 29, 2025•1 citation

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

Solving the B-SAT Problem Using Quantum Computing: Smaller Is Sometimes Better

Ahmad Bennakhi, Gregory T. Byrd, Paul D. Franzon

This paper aims to outline the effectiveness of modern universal gate quantum computers when utilizing different configurations to solve the B-SAT (Boolean satisfiability) problem. The quantum computing experiments were performed using Grover's search algorithm to find a valid solution. The experiments were performed under different variations to demonstrate their effects on the results. Changing the number of shots, qubit mapping, and using a different quantum processor were all among the experimental variables. The study also branched into a dedicated experiment highlighting a peculiar behavior that IBM quantum processors exhibit when running circuits with a certain number of shots.

Entropy•Oct 18, 2024•4 citations

Implementation of Efficient Quantum Computing Algorithm for Searching

Nirhali Atharva, Malwade Rohit, P. Akshay +2 more

The K-SAT problem is a fundamental challenge in computational theory, widely used in artificial intelligence, cryptography, and optimization. Classical algorithms struggle with exponential time complexity, making them inefficient for large-scale instances. In this research, we propose an efficient quantum computing approach based on Grover’s algorithm to enhance the search process for satisfiable solutions in K-SAT problems. Our implementation leverages quantum superposition and amplitude amplification to explore multiple possible solutions simultaneously, reducing the search complexity from O (2ⁿ) in classical methods to O(√2ⁿ) in quantum computing. We design a quantum oracle that encodes the K-SAT clauses and integrates it into Grover’s iterative search framework. The performance is evaluated through Qiskit simulations, demonstrating a significant improvement in search efficiency compared to classical brute-force techniques. The results highlight the potential of quantum algorithms in solving complex combinatorial problems with enhanced speed and accuracy. This study contributes to the development of quantum-accelerated optimization methods, paving the way for real-world applications in machine learning, cryptanalysis, and large-scale data processing.

International Research Journal on Advanced Engineering Hub (IRJAEH)•May 21, 2025•0 citations
Constraint satisfiability problems, crucial to several applications, are solved on a quantum computer using Grover's search algorithm, leading to a quadratic improvement over the classical case. The solutions are obtained with high probability for several cases and are illustrated for the cases involving two variables for both 3- and 4-bit numbers. Methods are defined for inequality comparisons, and these are combined according to the form of the satisfiability formula, to form the oracle for the algorithm. The circuit is constructed using IBM Qiskit and is verified on an IBM simulator. It is further executed on one of the Noisy Intermediate-Scale Quantum (NISQ) processors from IBM on the cloud. Noise levels in the processor at present are found to be too high for successful execution. Running the algorithm on the simulator with a custom noise model lets us identify the noise threshold for successful execution.
This study explores how well Grover's Algorithm performs in solving the Boolean Satisfiability Problem (SAT) using quantum circuits. The algorithm is implemented with IBM's Qiskit framework and compared to classical brute-force methods. Experiments focus on 3-SAT, 4-SAT, and 5-SAT problems, using quantum simulators and IBM quantum hardware. The results show that Grover's Algorithm is more efficient, offering a theoretical quadratic speedup over classical methods. However, practical issues like limited qubit availability, hardware noise, and optimization challenges impact its current performance. The data highlights the potential for quantum computing to scale and solve NP-complete problems. This research shows how quantum computing can improve problem-solving and lays the groundwork for future studies on more complex SAT problems and advanced quantum hardware.
This study explores how well Grover's Algorithm performs in solving the Boolean Satisfiability Problem (SAT) using quantum circuits. The algorithm is implemented with IBM's Qiskit framework and compared to classical brute-force methods. Experiments focus on 3-SAT, 4-SAT, and 5-SAT problems, using quantum simulators and IBM quantum hardware. The results show that Grover's Algorithm is more efficient, offering a theoretical quadratic speedup over classical methods. However, practical issues like limited qubit availability, hardware noise, and optimization challenges impact its current performance. The data highlights the potential for quantum computing to scale and solve NP-complete problems. This research shows how quantum computing can improve problem-solving and lays the groundwork for future studies on more complex SAT problems and advanced quantum hardware.
Grover's quantum search algorithm provides a proven quadratic speedup over classical linear search for unstructured databases. While its theoretical advantage is well established, experimental validation on real noisy intermediate-scale quantum (NISQ) hardware remains limited by noise, decoherence, and hardware constraints. In this work, we present an experimental comparison between classical linear search and Grover's quantum search algorithm executed on IBM Quantum real superconducting hardware using Qiskit Runtime. A four-qubit implementation corresponding to a 16-element search space is evaluated across multiple experimental runs. The results demonstrate consistent amplitude amplification, achieving an average success probability of 54.25% and an amplification factor of 8.68× over random guessing. Although classical execution remains faster in wall-clock time due to quantum hardware overhead, the experiment empirically validates the algorithmic advantage of Grover's search and quantifies the performance gap between ideal and real quantum processors in the NISQ era.
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.
This paper aims to outline the effectiveness of modern universal gate quantum computers when utilizing different configurations to solve the B-SAT (Boolean satisfiability) problem. The quantum computing experiments were performed using Grover's search algorithm to find a valid solution. The experiments were performed under different variations to demonstrate their effects on the results. Changing the number of shots, qubit mapping, and using a different quantum processor were all among the experimental variables. The study also branched into a dedicated experiment highlighting a peculiar behavior that IBM quantum processors exhibit when running circuits with a certain number of shots.
The K-SAT problem is a fundamental challenge in computational theory, widely used in artificial intelligence, cryptography, and optimization. Classical algorithms struggle with exponential time complexity, making them inefficient for large-scale instances. In this research, we propose an efficient quantum computing approach based on Grover’s algorithm to enhance the search process for satisfiable solutions in K-SAT problems. Our implementation leverages quantum superposition and amplitude amplification to explore multiple possible solutions simultaneously, reducing the search complexity from O (2ⁿ) in classical methods to O(√2ⁿ) in quantum computing. We design a quantum oracle that encodes the K-SAT clauses and integrates it into Grover’s iterative search framework. The performance is evaluated through Qiskit simulations, demonstrating a significant improvement in search efficiency compared to classical brute-force techniques. The results highlight the potential of quantum algorithms in solving complex combinatorial problems with enhanced speed and accuracy. This study contributes to the development of quantum-accelerated optimization methods, paving the way for real-world applications in machine learning, cryptanalysis, and large-scale data processing.