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

• URL: http://arxiv.org/abs/2508.08869v1
• Date: Tue, 12 Aug 2025 11:52:24 GMT
• Title: Evidence of scaling advantage on an NP-Complete problem with enhanced quantum solvers
• Authors: Quanfeng Lu, Shijie Wei, Keren Li, Pan Gao, Bao Yan, Muxi Zheng, Haoran Zhang, Jinfeng Zeng, Gui-Lu Long,
• Abstract summary: We develop enhanced quantum solvers for the NP-complete one-in-three Boolean satisfiability problem.<n>We experimentally implement our enhanced solvers on a superconducting quantum processor with 13 qubits.<n>Our results provide empirical evidence of quantum speedup for an NP-complete problem.
• Score: 17.90947220974444
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Achieving quantum advantage remains a key milestone in the noisy intermediate-scale quantum era. Without rigorous complexity proofs, scaling advantage-where quantum resource requirements grow more slowly than their classical counterparts-serves as the primary indicator. However, direct applications of quantum optimization algorithms to classically intractable problems have yet to demonstrate this advantage. To address this challenge, we develop enhanced quantum solvers for the NP-complete one-in-three Boolean satisfiability problem. We propose a restricting space reduction algorithm (RSRA) that achieves optimal search space dimensionality, thereby reducing both qubits and time complexity for various quantum solvers. Extensive numerical investigations on problem instances with up to 65 variables demonstrate that our enhanced quantum approximate optimization algorithm (QAOA) and quantum adiabatic algorithm (QAA)-based solvers outperform state-of-the-art classical solvers, with the QAA-based solver providing a lower bound for our method while exhibiting scaling advantage. Furthermore, we experimentally implement our enhanced solvers on a superconducting quantum processor with 13 qubits, confirming the predicted performance improvements. Collectively, our results provide empirical evidence of quantum speedup for an NP-complete problem.

Related papers

• Quantum optimisation applied to the Quadratic Assignment Problem [4.483208369550461]
  This paper investigates the performance of the emerging non-variational Quantum Walk-based optimisation algorithm (NV-QWOA) for solving small instances of the Quadratic Assignment Problem (QAP)<n>Performance is evaluated using two metrics: the number of objective function evaluations and the number of algorithm iterations required to consistently reach optimal or near optimal solutions across QAP instances with 5 to 10 facilities.<n>Our findings highlight the practical utility of quantum walks for complex quantum problems and establish a foundation for future quantum optimisation algorithms.
  arXiv  Detail & Related papers  (2026-01-03T07:50:03Z)
• Advancing Quantum State Preparation Using Decision Diagram with Local Invertible Maps [5.328178128965817]
  We propose a family of efficient Quantum State Preparation (QSP) algorithms tailored to different numbers of available ancilla qubits.<n>Our approach exploits the power of Local Invertible Map Decision Diagrams (LimTDDs) to reduce quantum circuit complexity.
  arXiv  Detail & Related papers  (2025-07-23T03:34:44Z)
• Quantum Subroutines in Branch-Price-and-Cut for Vehicle Routing [0.0]
  We demonstrate in this work how quantums with limited resources can be integrated in large-scale exact optimization algorithms for NP-hard problems.<n>A key feature of our algorithm is it not only from the best solution returned by the quantum but from all solutions below a certain cost threshold.
  arXiv  Detail & Related papers  (2024-12-20T08:27:23Z)
• Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
  We call this protocol bias-field digitizeddiabatic quantum optimization (BF-DCQO) Our purely quantum approach eliminates the dependency on classical variational quantum algorithms. It achieves scaling improvements in ground state success probabilities, increasing by up to two orders of magnitude.
  arXiv  Detail & Related papers  (2024-05-22T18:11:42Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Quantum-Enhanced Greedy Combinatorial Optimization Solver [12.454028945013924]
  We introduce an iterative quantum optimization algorithm to solve optimization problems. We implement the quantum algorithm on a programmable superconducting quantum system using up to 72 qubits. We find the quantum algorithm systematically outperforms its classical greedy counterpart, signaling a quantum enhancement.
  arXiv  Detail & Related papers  (2023-03-09T18:59:37Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage [43.3054117987806]
  We introduce a scalable procedure for harnessing classical computing resources to provide pre-optimized initializations for quantum circuits. We show this method significantly improves the trainability and performance of PQCs on a variety of problems. By demonstrating a means of boosting limited quantum resources using classical computers, our approach illustrates the promise of this synergy between quantum and quantum-inspired models in quantum computing.
  arXiv  Detail & Related papers  (2022-08-29T15:24:03Z)
• Squeezing and quantum approximate optimization [0.6562256987706128]
  Variational quantum algorithms offer fascinating prospects for the solution of optimization problems using digital quantum computers. However, the achievable performance in such algorithms and the role of quantum correlations therein remain unclear. We show numerically as well as on an IBM quantum chip how highly squeezed states are generated in a systematic procedure.
  arXiv  Detail & Related papers  (2022-05-20T18:00:06Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
  We propose a resource and runtime efficient scheme termed quantum architecture search (QAS) QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates. We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
  arXiv  Detail & Related papers  (2020-10-20T12:06:27Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.