On August 23, a paper from Professor Long Guilu's team at the Beijing Academy of Quantum Information Sciences (BAQIS) and Tsinghua University appeared as the cover article of *Nature Computational Science* (2026, Vol. 6, No. 8). The paper, *Evidence of scaling advantage on an NP-complete problem with enhanced quantum solvers* (Lu, Q., Wei, S., Li, K. et al., Nat Comput Sci 6, 882–893, 2026), provides the first empirical evidence that enhanced quantum solvers can show a scaling advantage over classical computation on specific NP-complete problems.
Why NP-complete problems are the touchstone
NP-complete problems have long been the litmus test for whether quantum computing "can actually be useful." Unlike Shor's algorithm with its provable polynomial speedup, most NP-complete problems offer no known structure for quantum superposition to exploit directly. Over the past two decades, quantum optimization algorithms (typified by QAOA and quantum annealing) have frequently been outperformed on random instances by stronger classical algorithms.
So this cover article is not a blanket declaration that "quantum beats classical." It claims something more specific and more demanding: enhanced quantum solvers show, for the first time on random instances of an NP-complete problem, an advantage that widens monotonically with scale—the kind of scaling advantage that has collapsed in nearly every prior controlled comparison.
The classical baseline problem
The standard classical route for NP-complete problems is to encode them as Ising models or QUBO (quadratic unconstrained binary optimization) and attack them with simulated annealing, tabu search, CP-SAT, or industrial solvers like Gurobi/COPT. The classical side has improved continuously over the past decade, which is why quantum-advantage claims from IBM, Google, and Quantinuum have repeatedly been overturned by reviewers armed with better classical baselines. D-Wave's quantum annealing has made similar claims, but the gap disappears once the classical team changes a seed or swaps in a specialized heuristic.
What is different here
Long Guilu's team did not use generic QAOA. Instead they used enhanced quantum solvers—a hybrid variational framework that allows dynamic adjustment of circuit parameters or problem encodings during optimization based on measurement feedback.
The key evidence: on a family of random instances of an NP-complete problem, as the qubit count N increases, the cost (query complexity / circuit depth) for the enhanced quantum solver to find target solutions exhibits clearly better scaling behavior than the best classical heuristics. In other words, the gap is not "faster at a single point" but "more stable as the problem grows." That is the definition of scaling advantage: not a 1.1x or 2x constant factor, but a win in the scaling exponent.
Verifiability as an engineering property
Another implication is verifiability. The enhanced solver outputs concrete solutions that a classical computer can check in polynomial time against the constraints—turning quantum advantage from "believe me" into "you don't have to believe it, but you can verify it yourself." This mirrors the same scientific attitude seen in machine-verifiable formal proofs: make the result checkable.
Broader context: China's quantum stack
This result does not stand alone:
- Earlier this month, Vector Singularity, a BAQIS-incubated neutral-atom company, announced an angel round of over 100 million RMB led by IDG Capital. The core team works on a ytterbium-171 neutral-atom quantum computing platform, led by Xiangliang Li (Tsinghua math-physics background, ETH PhD under Tilman Esslinger).
- China's hardware landscape now spans multiple routes: superconducting (Origin Quantum's Wukong, Zuchongzhi), ion traps (Unitary Quantum), neutral atoms (Vector Singularity, Qudoor, Atom Matrix), and photonics (Jiuzhang 3.0).
- On the software side, Origin Quantum open-sourced its quantum programming AI assistant (integrating the QPanda3 skill library and quantum programming MCP, letting AI coding tools connect directly to real hardware), and pushed its BenYuan SiNan quantum operating system to version 4.0, covering superconducting, ion-trap, and neutral-atom platforms.
- Lu, Q., Wei, S., Li, K. et al. Evidence of scaling advantage on an NP-complete problem with enhanced quantum solvers. *Nat Comput Sci* 6, 882–893 (2026). doi:10.1038/s43588-026-00882-9 (cover article)
- BAQIS / Tsinghua University Long Guilu team press release, 2026-08-23
- Vector Singularity angel funding announcement, IDG Capital lead investor, 2026-08-19
- Origin Quantum open-source quantum programming assistant announcement, 2026-08-22
- Economic Daily, "Giving Quantum Computers a Chinese Steward — BenYuan SiNan 4.0", 2026-08-22
Taken together, the battlefield in the second half of 2026 is shifting from "who has more qubits / higher gate fidelity" to "who can deliver algorithms–software–hardware as a schedulable, verifiable, remotely callable service." Scaling advantage, verifiability, and a software stack sinking down to MCP/OS level may be the most important signposts for quantum computing going forward.