Scholarlink

<p>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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年6月19日

查看全文
  • Quanfeng Lu,
  • Shijie Wei,
  • Keren Li,
  • Pan Gao,
  • Bao Yan,
  • Muxi Zheng,
  • Haoran Zhang,
  • Jinfeng Zeng,
  • Gui-Lu Long

摘要

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.