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

Area of Science:

• Quantum Computing
• Computational Complexity

Background:

• Boolean satisfiability (B-SAT) is a fundamental problem in computer science.
• Quantum computing offers potential speedups for complex problems like B-SAT.

Purpose of the Study:

• To evaluate the effectiveness of universal gate quantum computers for B-SAT.
• To investigate the impact of different quantum computing configurations on B-SAT problem-solving.

Main Methods:

• Utilized Grover's search algorithm on universal gate quantum computers.
• Experimented with variations in the number of shots, qubit mapping, and quantum processors.
• Conducted a specific experiment on IBM quantum processors to observe unique behaviors.

Main Results:

• Different configurations (shots, qubit mapping, processor choice) affect quantum B-SAT solution effectiveness.
• Observed peculiar performance characteristics of IBM quantum processors at specific shot counts.

Conclusions:

• Configuration tuning is crucial for optimizing quantum B-SAT solvers.
• Further investigation into quantum hardware-specific behaviors is warranted for efficient quantum algorithm implementation.