Student or educator? Sign up with your school email and get 6 months of Pro free.

The DOI matches its Crossref record; 50 of the 56 references it cites were found in a registry or an index; 3 of the 9 sources its claims cite were checked for support.

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

Open access
Lu, Quanfeng, Wei, Shijie, Li, Keren, Gao, Pan, Yan, Bao, Zheng, Muxi, Zhang, Haoran, Zeng, Jinfeng, Long, Gui-Lu · 2026 · Nature Computational Science

Abstract

Achieving quantum advantage remains a milestone in the noisy intermediate-scale quantum era. Without complexity proofs, scaling advantage—where quantum resource requirements grow more slowly than their classical counterparts—is the primary indicator. However, direct applications of quantum optimization algorithms to classically intractable problems have yet to demonstrate this advantage. Here we develop enhanced quantum solvers for the NP-complete one-in-three Boolean satisfiability problem. We propose a restricting space reduction algorithm that achieves optimal search-space dimensionality under mod-2 arithmetic, thereby reducing qubit requirements and time complexity. Numerical studies on instances with up to 70 variables demonstrate that our enhanced quantum approximate optimization algorithm- and quantum adiabatic algorithm-based solvers outperform state-of-the-art classical solvers; the quantum adiabatic algorithm-based solver serves as a lower-bound reference while retaining scaling advantage. Furthermore, experiments on a 13-qubit superconducting processor confirm the predicted improvements. Collectively, our results provide empirical evidence of quantum speedup for an NP-complete problem. This study develops enhanced quantum solvers for an NP-complete Boolean satisfiability problem and reports empirical scaling advantages over leading classical solvers in large-scale simulations, with supporting validation on a superconducting quantum processor.

Overview

CoChat Summary

TL;DR

The paper introduces RSRA-based enhanced quantum solvers for positive one-in-three SAT that restrict the search space and reduce qubit requirements, then reports numerical and experimental evidence of better scaling than classical baselines. It claims empirical quantum speedup on instances up to 70 variables in simulation and confirms improved success probabilities on a 13-qubit superconducting processor.

Key findings

  • RSRA reduces the search-space dimensionality from \(2^n\) to \(2^{n-k}\), with \(k\) the number of mod-2 independent clauses, and in the critical region \(k\) is typically close to \(m\), so the space is approximately \(2^{n-m}\).
  • In scaling analysis on random instances up to \(n=70\), the enhanced QAOA- and QAA-based solvers scale as \(1.0077^n\) and \(1.0070^n\), respectively, compared with \(1.0128^n\) for state-of-the-art classical solvers.
  • The paper reports that on the critical ratio, increasing layers improves scaling to approximately \(1.0032^n\) for the enhanced QAA-based solver and \(1.0076^n\) for the enhanced QAOA-based solver in the layer-sweep study.
  • On a 13-qubit superconducting processor, the enhanced VQE- and QAOA-based solvers achieved final energies of approximately 0.2 and 0.5, with success probabilities of 43.04% and 36.40%, while the RSRA-aware random-sampling baseline reached 25%.

Methods

  • The study targets positive one-in-three SAT instances, mainly around the critical clause-to-variable region near 0.626, and uses RSRA to relax one-in-three clauses to odd-in-three parity constraints, producing a reduced subspace and a 2-SAT restriction inside that subspace.
  • The authors build enhanced VQE-, QAOA-, and QAA-based solvers whose ansätze stay within the relaxed-problem solution space; they evaluate scaling via inverse success probability for quantum solvers and conflict/propagation counts for classical solvers, using linear regression on log-effort versus \(n\).
  • Experiments include classical simulation up to 150 variables for VQE-based solving and hardware tests on a 13-transmon superconducting processor with 8 qubits used in the implementation.

Limitations

  • The paper states that the scaling estimates are based on the largest problem sizes accessible within current computational capability, and that highly specialized classical heuristics could still narrow the gap; this is explicitly acknowledged in the discussion.
  • The experimental hardware demonstration is not presented as a claim of quantum advantage; it is described as a feasibility test, and standard QAOA on larger instances was limited by hardware noise.
  • Evident from the text: some reported results rely on fixed-parameter protocols and classical simulation of the quantum circuits, so the empirical scaling claims are not yet supported by large-scale fault-tolerant hardware execution.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1038/s43588-026-01007-8

Cites

50 of 56 references verified0 citation errors · 6 not checkable

Statistics

Nothing to recompute.

Figures

Fig. 1 Schematic illustration of the RSRA and the enhanced quantum solvers. a , Overview of the RSRA and its application to quantum solvers for the one-inthree SAT problem. The RSRA relaxes one-in-three constraints to odd-in-three parity constraints and reformulates the problem as a 2-SAT problem within the relaxed solution space 𝕊𝕊 , yielding an effective Hamiltonian H RSRA and problemheuristic ansätze. b , Comparison of the original and enhanced quantum solvers. The upper half shows the standard ansätze used in the original solvers, whereas the lower half shows the RSRA-based ansätze used in the enhanced solvers. The
Fig. 1 Schematic illustration of the RSRA and the enhanced quantum solvers. a , Overview of the RSRA and its application to quantum solvers for the one-inthree SAT problem. The RSRA relaxes one-in-three constraints to odd-in-three parity constraints and reformulates the problem as a 2-SAT problem within the relaxed solution space 𝕊𝕊 , yielding an effective Hamiltonian H RSRA and problemheuristic ansätze. b , Comparison of the original and enhanced quantum solvers. The upper half shows the standard ansätze used in the original solvers, whereas the lower half shows the RSRA-based ansätze used in the enhanced solvers. TheCC BY-NC-ND · From the PDF
Fig. 2 Numerical simulation results. a , Average values of k as a function of problem size n for fixed clause-to-variable ratios m n , showing an approximately linear dependence on n . b , Slopes of the average k versus n for different m n ratios, compared with the reference line ė = m n . The inset shows the difference δ between the two quantities, indicating that k ≈ m over a broad range of ratios. c , Representative successful and failed optimization trajectories of the enhanced VQE-based solver for a SAT instance with 150 variables and 94 clauses. d , Energy and success probability of the enhanced QAA-based solver versus the number of layers N QAA , evaluated on a SAT instance with 100 variables and 63 clauses. e , Energy and success probability of the enhanced QAOA-based solver versus the
Fig. 2 Numerical simulation results. a , Average values of k as a function of problem size n for fixed clause-to-variable ratios m n , showing an approximately linear dependence on n . b , Slopes of the average k versus n for different m n ratios, compared with the reference line ė = m n . The inset shows the difference δ between the two quantities, indicating that k ≈ m over a broad range of ratios. c , Representative successful and failed optimization trajectories of the enhanced VQE-based solver for a SAT instance with 150 variables and 94 clauses. d , Energy and success probability of the enhanced QAA-based solver versus the number of layers N QAA , evaluated on a SAT instance with 100 variables and 63 clauses. e , Energy and success probability of the enhanced QAOA-based solver versus theCC BY-NC-ND · From the PDF
Fig. 3 Topological structure of the quantum processor and its compilation method. a , Topological layout of the quantum processor. The colors of the qubits and the connections between pairs of qubits indicate their single-qubit and two-qubit gate fidelities, respectively. In the first experiment, the employed qubits are indicated by dashed red boxes, whereas the second experiment
Fig. 3 Topological structure of the quantum processor and its compilation method. a , Topological layout of the quantum processor. The colors of the qubits and the connections between pairs of qubits indicate their single-qubit and two-qubit gate fidelities, respectively. In the first experiment, the employed qubits are indicated by dashed red boxes, whereas the second experimentCC BY-NC-ND · From the PDF
involves all 13 qubits. b Compilation methods for Rx gates, Ry gates and CNOT gates. c Decomposition of e -iθZZ /2 into two CNOT gates and an Rz gate. d , e , Decomposition of e iθ | šš ᤖᤕ šš |/ Ţ into an Rz gate and a controlledRz gate ( d ), with the latter further decomposed into two CNOT gates and two Rz gates ( e ).
involves all 13 qubits. b Compilation methods for Rx gates, Ry gates and CNOT gates. c Decomposition of e -iθZZ /2 into two CNOT gates and an Rz gate. d , e , Decomposition of e iθ | šš ᤖᤕ šš |/ Ţ into an Rz gate and a controlledRz gate ( d ), with the latter further decomposed into two CNOT gates and two Rz gates ( e ).CC BY-NC-ND · From the PDF
Fig. 5 Experimental results of the enhanced QAOA-based solver with fixed parameters on a quantum processor for instances with up to 22 variables.
Fig. 5 Experimental results of the enhanced QAOA-based solver with fixed parameters on a quantum processor for instances with up to 22 variables.CC BY-NC-ND · From the PDF

Verification

Claims the paper makes

3 Valid · 1 Not valid · 3 Not checked · 101 Own results and interpretations

54 more claims

Create a free account to see all 108 claims and to verify the 1 reference still open.

See all claims — free account
  • Probably not a substantial claim. 23
  • It may state two separate claims as one. 30
  • The quote only partly states this claim. 3

Create a free account to see these claims.

Citations

Cites

Show all 56 references

Cited by

See all 2

Metadata

Authors
Lu, Q., Wei, S., Li, K., Gao, P., Yan, B., Zheng, M., Zhang, H., Zeng, J., & Long, G.-L.
Affiliations
  • Beijing Academy of Quantum Information Sciences (CN)
  • Shenzhen University (CN)
  • State Key Laboratory of Low-Dimensional Quantum Physics (CN)
  • Nanyang Technological University (SG)
Corresponding author
  • Wei, Shijie
  • Zeng, Jinfeng
  • Long, Gui-Lu
Venue
Nature Computational Science
Published
2026-06-19
Volume
6
Issue
8
Pages
882-893
ISSN
2662-8457 (ISSN-L)
OpenAlex
W4416866005
Cited by
1
References
56
Citations by year
2026: 1
FWCI
3.40
Type
journal article
Language
en
Open access
Licence
Locations
  • Nature Computational Science (publishedVersion, cc-by-nc-nd)
  • PubMed (publishedVersion)
  • PubMed Central (publishedVersion, cc-by-nc-nd)
  • arXiv (Cornell University) (submittedVersion)
  • DR-NTU (Nanyang Technological University) (submittedVersion)
  • arXiv (Cornell University) (cc-by)
Funders
  • Beijing Nova Program (20240484609, 20230484345)
  • National Natural Science Foundation of China (62571050, 62571343, 62471046)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
Keywords
quantum advantage, NP-complete problems, quantum approximate optimization algorithm, adiabatic quantum computation, qubit reduction, superconducting quantum processors, noisy intermediate-scale quantum computing

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

A language model drew the claims from the paper on 2026-10-10, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).

A second model labelled each claim on 2026-10-10 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: Evidence of scaling advantage on an NP-complete problem with enhanced quantum solvers. https://app.cochat.ai/papers/10.1038/s43588-026-01007-8
The paper
Lu, Q., Wei, S., Li, K., Gao, P., Yan, B., Zheng, M., Zhang, H., Zeng, J., & Long, G.-L. (2026). Evidence of scaling advantage on an NP-complete problem with enhanced quantum solvers. Nature Computational Science. https://doi.org/10.1038/s43588-026-01007-8

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.