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 accessAbstract
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
Cites
Statistics
Figures





Verification
Claims the paper makes
3 Valid · 1 Not valid · 3 Not checked · 101 Own results and interpretations
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Experimentally, we demonstrate the feasibility of our approach on a superconducting quantum processor by using 13 qubits to solve instances with 22 variables, achieving meaningful results.”
§ Evidence of scaling advantage on an NP-complete problem with enhanced quantum solvers > Main
boostedstates a causeSingle case- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“For problem sizes up to n = 70 variables at the critical ratio , the enhanced QAOA-based solver with 40 layers and the QAA-based solver with 150 layers scale as 1.0077n and 1.0070n, respectively”
§ Evidence of scaling advantage on an NP-complete problem with enhanced quantum solvers > Main
plainstates an associationn = 70- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“As shown in Fig. 2a,b, the average values of k exhibit linear relationships with problem size n when is fixed, and their slopes are approximately equal to in the range between 0.1 and 0.9.”
§ Evidence of scaling advantage on an NP-complete problem with enhanced quantum solvers > Methods > RSRA
plainstates an association- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Rests on 2 assumptions not shown here.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“First, we randomly generate a one-in-three SAT problem with 150 variables and 94 clauses, in which 131 variables actually occur.”
- Also stated in: § Numerical simulation of SAT problem · plain
“In our experiments, 166 out of 2,000 attempts succeed, yielding a success probability of 8.3%, which is notable considering the problem size.”
§ Evidence of scaling advantage on an NP-complete problem with enhanced quantum solvers > Results > Numerical simulation of SAT problem
plainSingle case- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Also stated in: § Numerical simulation of SAT problem · plain
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Notably, for larger problems (for example, n ≥ 20), the standard QAOA-based solver fails to produce meaningful results owing to the noise of the quantum hardware.”
§ Evidence of scaling advantage on an NP-complete problem with enhanced quantum solvers > Results > Experiment on superconducting quantum processors
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
54 more claims
Create a free account to see all 108 claims and to verify the 1 reference still open.
- Probably not a substantial claim. 23
- It may state two separate claims as one. 30
- The quote only partly states this claim. 3
Citations
Cites
Quantum Computing in the NISQ era and beyond
Preskill, J. (2018) · Quantum · doi:10.22331/q-2018-08-06-79 · Cited by 8,830 · cited 1×
“…algorithm (QAOA) 1 and the variational quantum eigensolver (VQE) 2 , are promising candidates for achieving quantum advantage in the noisy intermediate-scale quantum (NISQ) era 3 , which is characterized by limited qubit counts 4–6 and the absence of effective error correction mechanisms 7–10 .”
Quantum supremacy using a programmable superconducting processor
Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J. C., Barends, R., Biswas, R., Boixo, S., Brandao, F. G. S. L., Buell, D. A., et al. (2019) · Nature · doi:10.1038/s41586-019-1666-5 · Cited by 7,720 · cited 1×
“…algorithm (QAOA) 1 and the variational quantum eigensolver (VQE) 2 , are promising candidates for achieving quantum advantage in the noisy intermediate-scale quantum (NISQ) era 3 , which is characterized by limited qubit counts 4–6 and the absence of effective error correction mechanisms 7–10 .”
The complexity of theorem-proving procedures
Cook, S. A. (1971) · Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 · doi:10.1145/800157.805047 · Cited by 6,385 · cited 1×
“2c. in conjunctive normal form (CNF), as a conjunction of clauses where each clause is a disjunction of three literals, was the first problem proven to be NP-complete by the Cook–Levin theorem 26 .”
A variational eigenvalue solver on a photonic quantum processor
Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H., Zhou, X.-Q., Love, P. J., Aspuru-Guzik, A., & O’Brien, J. L. (2014) · Nature Communications · doi:10.1038/ncomms5213 · Cited by 4,552 · cited 1×
“Quantum optimization algorithms, including the quantum approximate optimization algorithm (QAOA) 1 and the variational quantum eigensolver (VQE) 2 , are promising candidates for achieving quantum advantage in the noisy intermediate-scale quantum (NISQ) era 3 , which is characterized by limited…”
Barren plateaus in quantum neural network training landscapes
McClean, J. R., Boixo, S., Smelyanskiy, V. N., Babbush, R., & Neven, H. (2018) · Nature Communications · doi:10.1038/s41467-018-07090-4 · Cited by 2,329 · cited 1×
“https://doi.org/10.1038/s43588-026-01007-8 Furthermore, research indicates that the presence of barren pla-teaus is closely related to the two-design characteristics of circuits 48 and can be assessed through the gradient variance of the loss function 43 .”
InfluentialA Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., & Preda, D. (2001) · Science · doi:10.1126/science.1057726 · Cited by 2,056
A Quantum Approximate Optimization Algorithm
Farhi, E., Goldstone, J., & Gutmann, S. (2014) · arXiv · doi:10.48550/arxiv.1411.4028 · Cited by 1,789
Quantum amplitude amplification and estimation
Brassard, G., Høyer, P., Mosca, M., & Tapp, A. (2002) · Contemporary Mathematics · doi:10.1090/conm/305/05215 · Cited by 1,680 · cited 1×
“Second, the scaling of our QAA-and QAOA-based solvers could be further reduced through amplitude amplification 40 and better schedule functions, while the performance of our VQE-based solver can be improved via more effective classical optimizers or better ansatz design.”
Mitarai, K., Negoro, M., Kitagawa, M., & Fujii, K. (2018) · Physical Review A · doi:10.1103/physreva.98.032309 · Cited by 1,639 · cited 1×
“To compute the gradients of the Hamiltonian with respect to a parameter, we employ the parameter shift technique 38,39 for the VQE-based solvers and finite differences with a step size of 0.2 for the QAOA-based solvers.”
InfluentialAlbash, T., & Lidar, D. A. (2018) · Reviews of Modern Physics · doi:10.1103/revmodphys.90.015002 · Cited by 1,546
Cited by
Variational and Annealing-Based Approaches to Quantum Combinatorial OptimizationPreprint
Hawashin, H., Nath, D., & Javarone, M. A. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2603.19117 · Cited by 1
“In contrast, gate-based approaches, most notably QAOA, are currently positioned at QTRL 3–5, demonstrating significant experimental validation but not yet achieving full industrial readiness.”
Scaling law of variational quantum algorithmsPreprint
Wang, N., & Liu, Z. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2609.39949
“Recent work [14] has reported numerical evidence of a scal-a ing advantage over classical baselines for enhanced quantum solvers on instances of the NP-complete one-in-three SAT problem with up to 70 variables.”
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)
- PMC
- PMC13489940
- OpenAlex
- W4416866005
- Cited by
- 1
- References
- 56
- Citations by year
- 2026: 1
- FWCI
- 3.40
- Type
- journal article
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- cc-by-nc-nd
- creativecommons.org/licenses/by-nc-nd/4.0 (tdm)
- creativecommons.org/licenses/by-nc-nd/4.0 (vor)
- 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.