Evidence of scaling advantage on an NP-complete problem with enhanced quantum solvers

Area of Science:

• Quantum Computing
• Computational Complexity Theory
• Artificial Intelligence

Background:

• Achieving quantum advantage is crucial in the noisy intermediate-scale quantum era.
• Scaling advantage, where quantum resource needs grow slower than classical ones, is a key indicator.
• Direct quantum optimization applications to intractable problems have not yet shown this advantage.

Purpose of the Study:

• To develop enhanced quantum solvers for the NP-complete one-in-three Boolean satisfiability problem.
• To reduce qubit requirements and time complexity for quantum optimization.
• To provide empirical evidence of quantum speedup for NP-complete problems.

Main Methods:

• Developed a restricting space reduction algorithm for optimal search-space dimensionality.
• Utilized enhanced quantum approximate optimization algorithm (QAOA) and quantum adiabatic algorithm (QAA) solvers.
• Conducted numerical studies on instances up to 70 variables and experiments on a 13-qubit superconducting processor.

Main Results:

• Enhanced quantum solvers outperformed state-of-the-art classical solvers for the one-in-three Boolean satisfiability problem.
• The quantum adiabatic algorithm-based solver demonstrated scaling advantage.
• Experimental results on a superconducting processor confirmed predicted improvements.

Conclusions:

• The study provides empirical evidence of quantum speedup for an NP-complete problem.
• The developed methods show potential for reducing quantum resource requirements and time complexity.
• This work advances the pursuit of practical quantum advantage in optimization problems.