Combinatorial optimization enhanced by shallow quantum circuits with 104 superconducting qubits
Abstract A pivotal task for quantum computing is to speed up solving problems that are both classically intractable and practically valuable. Among these, combinatorial optimization problems have attracted tremendous attention due to their broad applicability and natural fitness to Ising Hamiltonians. Here we propose a quantum sampling strategy, based on which we design an algorithm for accelerating solving the ground states of Ising model, a class of NP-hard problems in combinatorial optimization. The algorithm employs a shallow-circuit quantum sampling subroutine to navigate the energy landscape. Using up to 104 superconducting qubits, we experimentally demonstrate that this algorithm outputs favorable solutions against even a highly-optimized classical simulated annealing algorithm and illustrate the path toward quantum speedup based on the time-to-solution metric against simulated annealing under serial execution. Our results indicate a promising alternative to classical heuristics for combinatorial optimization, where quantum advantage might become possible on near-term superconducting quantum processors.
Authors
- Yiren Zou (ORCID: https://orcid.org/0009-0008-2838-9552)
- Han Wang (ORCID: https://orcid.org/0000-0003-0824-2912)
- Aosai Zhang (ORCID: https://orcid.org/0009-0002-0599-5361)
- P. A. Mosharev (ORCID: https://orcid.org/0000-0001-7065-1974)
- Jianan Yang (ORCID: https://orcid.org/0000-0002-1369-836X)
- Hang Dong (ORCID: https://orcid.org/0000-0003-4762-0023)
- H. Wang
- Hekang Li (ORCID: https://orcid.org/0000-0003-3914-4979)
- Yuyan Han (ORCID: https://orcid.org/0000-0002-6704-8768)
- Jinfeng Deng
- Gongyu Liu
- Yaozu Wu (ORCID: https://orcid.org/0000-0002-1137-4660)
- Qiujiang Guo (ORCID: https://orcid.org/0000-0003-1093-3405)
- Zehang Bao (ORCID: https://orcid.org/0009-0007-9164-714X)
- Feitong Jin (ORCID: https://orcid.org/0000-0003-0789-8207)
- Fanhao Shen (ORCID: https://orcid.org/0009-0003-5289-419X)
- Maolin Luo (ORCID: https://orcid.org/0000-0003-1941-5727)
- Xuhao Zhu (ORCID: https://orcid.org/0000-0003-1318-8367)
- Jiarun Zhong (ORCID: https://orcid.org/0009-0001-3631-6774)
- Zitian Zhu (ORCID: https://orcid.org/0000-0002-8219-2311)
- Yanzhe Wang (ORCID: https://orcid.org/0000-0001-8016-7633)
- Jiachen Chen (ORCID: https://orcid.org/0009-0006-6444-2416)
- Zhengyi Cui (ORCID: https://orcid.org/0009-0001-5534-5167)
- Pengfei Zhang (ORCID: https://orcid.org/0000-0002-9991-9310)
- Ning Wang (ORCID: https://orcid.org/0000-0002-4902-5589)
- Chao Song (ORCID: https://orcid.org/0000-0003-2140-0364)
- Yu Gao (ORCID: https://orcid.org/0000-0001-8576-0970)
- Yiyang He (ORCID: https://orcid.org/0000-0002-7655-2878)
- Chuanyu Zhang
- Jiayuan Shen
- Zixuan Song (ORCID: https://orcid.org/0009-0001-5128-9874)
- Man-Hong Yung
- Zuoheng Zou
- Zhen Wang (ORCID: https://orcid.org/0009-0004-5437-1103)
Institutions
- Huawei Technologies (China) (CN)
- Hefei University (CN)
- Zhejiang Lab (CN)
Publication Details
- Journal
- National Science Review
- Published
- 2026-02-27
- DOI
- https://doi.org/10.1093/nsr/nwag124
- Primary Topic
- Quantum Computing Algorithms and Architecture
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- National Natural Science Foundation of China
- Zhejiang University
- Natural Science Foundation of Zhejiang Province