前瞻科技 ›› 2025, Vol. 4 ›› Issue (4): 46-63.DOI: 10.3981/j.issn.2097-0781.2025.04.004
龙桂鲁1,2,†(
), 魏世杰1, 高攀1, 李行1, 邢同昊1, 曾进峰1, 张江1
收稿日期:2025-08-13
修回日期:2025-10-15
出版日期:2025-12-20
发布日期:2025-12-30
通讯作者:
†
作者简介:龙桂鲁,教授。国家杰出青年科学基金获得者,国务院政府特殊津贴专家,全国优秀科技工作者,美国物理学会、英国物理学会会士。中国通信学会量子通信委员会主任委员,中国密码学会理事、量子密码专业委员会副主任,国际纯粹与应用物理联合会(IUPAP)量子科技组委员、国际电联(ITU)新兴技术学术顾问委员会委员。原创性提出量子直接通信技术,构造量子精确搜索算法,并提出LCU量子计算范式。荣获国家自然科学奖二等奖、IBM全球杰出学者奖、中国电子学会科技奖、中国通信学会科技奖一等奖等荣誉。发表学术论文500余篇,出版专著4部;申请及授权中国专利60余件、美国专利2件。电子信箱:gllong@tsinghua.edu.cn
LONG Guilu1,2,†(
), WEI Shijie1, GAO Pan1, LI Hang1, XING Tonghao1, ZENG Jinfeng1, ZHANG Jiang1
Received:2025-08-13
Revised:2025-10-15
Online:2025-12-20
Published:2025-12-30
Contact:
†
摘要:
量子算法作为量子计算的核心驱动要素,具有突破经典计算瓶颈、实现指数级加速的显著潜力。自20世纪末彼得·肖尔、洛夫·格罗弗等先驱奠定理论根基以来,量子算法在物理模拟、机器学习、密码分析及组合优化等领域快速发展,逐步构建起从理论范式到含噪中等规模量子(Noisy Intermediate-Scale Quantum, NISQ)时代实用算法探索的完备体系。文章系统回顾了量子算法的发展历程,深入剖析了当前量子算法的主要研究方向及技术局限,涉及量子线性系统求解、量子多体与化学模拟、对称与非对称密码的量子攻击、后量子密码分析,以及量子近似优化算法、量子退火等优化类方法。对超越现有范式的新型算法框架、容错与分布式量子算法的演进路径进行了展望,并从国家、学术界及产业界层面提出了量子算法领域的战略性发展建议,旨在为推动量子计算的理论创新与产业应用提供重要参考,助力构建具备国际竞争力的量子算法体系。
龙桂鲁, 魏世杰, 高攀, 李行, 邢同昊, 曾进峰, 张江. 量子算法研究现状及战略发展路线图[J]. 前瞻科技, 2025, 4(4): 46-63.
LONG Guilu, WEI Shijie, GAO Pan, LI Hang, XING Tonghao, ZENG Jinfeng, ZHANG Jiang. Current Status of Quantum Algorithm Research and Strategic Development Roadmap[J]. Science and Technology Foresight, 2025, 4(4): 46-63.
| [1] |
Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Journal on Computing, 1997, 26(5): 1484-1509.
DOI URL |
| [2] | Grover L K. A fast quantum mechanical algorithm for database search[C]// Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing-STOC '96. New York:ACM, 1996: 212-219. |
| [3] | Long G L. Grover algorithm with zero theoretical failure rate[J]. Physical Review A, 2001, 64(2): 022307, doi:10.1103/PhysRevA.64.022307. |
| [4] |
Toyama F M, Van Dijk W, Nogami Y. Quantum search with certainty based on modified Grover algorithms: Optimum choice of parameters[J]. Quantum Information Processing, 2013, 12(5): 1897-1914.
DOI URL |
| [5] | 眭晗, 吴文玲. 后量子对称密码的研究现状与发展趋势[J]. 电子与信息学报, 2020, 42(2): 287-294. |
| Sui H, Wu W L. Research status and development trend of post-quantum symmetric cryptography[J]. Journal of Electronics & Information Technology, 2020, 42(2): 287-294. (in Chinese) | |
| [6] |
Shor P W. Why haven’t more quantum algorithms been found?[J]. Journal of the ACM, 2003, 50(1): 87-90.
DOI URL |
| [7] | Long G L. General quantum interference principle and duality[J]. Communications in Theoretical Physics, 2006, 45(5): 825, doi: 10.1088/0253-6102/45/5/013. |
| [8] | Long G L, Liu Y. Duality computing in quantum computers[J]. Communications in Theoretical Physics, 2008, 50(6): 1303, doi: 10.1088/0253-6102/50/6/11. |
| [9] | Long G L, Liu Y, Wang C. Allowable generalized quantum gates[J]. Communications in Theoretical Physics, 2009, 51(1): 65, doi: 10.1088/0253-6102/51/1/13. |
| [10] |
Gudder S. Mathematical theory of duality quantum computers[J]. Quantum Information Processing, 2007, 6(1): 37-48.
DOI URL |
| [11] |
Zhang Y, Cao H X, Li L. Realization of allowable qeneralized quantum gates[J]. Science China Physics, Mechanics and Astronomy, 2010, 53(10): 1878-1883.
DOI URL |
| [12] | Harrow A W, Hassidim A, Lloyd S. Quantum algorithm for linear systems of equations[J]. Physical Review Letters, 2009, 103(15): 150502, doi: 10.1103/PhysRevLett.103.150502. |
| [13] | Wei S J, Zou Z R, Ruan D, et al. Realization of the algorithm for system of linear equations in duality quantum computing[C]// 2017 IEEE 85th Vehicular Technology Conference (VTC Spring). Piscataway: IEEE Press, 2017, doi: 10.1109/VTCSpring.2017.8108698. |
| [14] | Childs A M, Wiebe N. Hamiltonian simulation using linear combinations of unitary operations[J]. Quantum Information & Computation, 2012, 12(11-12): 901-924. |
| [15] |
Wei S J, Long G L. Duality quantum computer and the efficient quantum simulations[J]. Quantum Information Processing, 2016, 15(3): 1189-1212.
DOI URL |
| [16] | Wei S J, Ruan D, Long G L. Duality quantum algorithm efficiently simulates open quantum systems[J]. Scientific Reports, 2016, 6: 30727, doi: 10.1038/srep30727. |
| [17] | Zheng C, Hao L, Long G L. Observation of a fast evolution in a parity-time-symmetric system[J]. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2013, 371(1989): 20120053, doi: 10.1098/rsta.2012.0053. |
| [18] |
Shao C P, Li Y, Li H B. Quantum algorithm design: Techniques and applications[J]. Journal of Systems Science and Complexity, 2019, 32(1): 375-452.
DOI |
| [19] | Kak S C. Quantum neural computing[M]//Advances in Imaging and Electron Physics. Amsterdam: Elsevier, 1995: 259-313. |
| [20] | Chrisley R. New directions in cognitive science: Proceedings of the international symposium[J]. Saariselka, 1995, 4: 77. |
| [21] |
Lloyd S, Mohseni M, Rebentrost P. Quantum principal component analysis[J]. Nature Physics, 2014, 10(9): 631-633.
DOI |
| [22] | Rebentrost P, Mohseni M, Lloyd S. Quantum support vector machine for big data classification[J]. Physical Review Letters, 2014, 113(13): 130503, doi: 10.1103/PhysRevLett.113.130503. |
| [23] | Wiebe N, Kapoor A, Svore K. Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning[DB/OL]. arXiv preprint:1401.2142, 2014. |
| [24] |
Dong D Y, Chen C, Li H, et al. Quantum reinforcement learning[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2008, 38(5): 1207-1220.
DOI URL |
| [25] | Amin M H, Andriyash E, Rolfe J, et al. Quantum Boltzmann machine[J]. Physical Review X, 2018, 8(2): 021050, doi: 10.1103/PhysRevX.8.021050. |
| [26] |
Cong I, Choi S, Lukin M D. Quantum convolutional neural networks[J]. Nature Physics, 2019, 15(12): 1273-1278.
DOI |
| [27] | Lloyd S, Weedbrook C. Quantum generative adversarial learning[J]. Physical Review Letters, 2018, 121(4): 040502, doi: 10.1103/PhysRevLett.121.040502. |
| [28] | Dallaire-Demers P L, Killoran N. Quantum generative adversarial networks[J]. Physical Review A, 2018, 98: 012324, doi: 10.1103/PhysRevA.98.012324. |
| [29] | Hu L, Wu S H, Cai W Z, et al. Quantum generative adversarial learning in a superconducting quantum circuit[J]. Science Advances, 2019, 5: eaav2761, doi: 10.1126/sciadv.aav2761. |
| [30] | Wei S J, Chen Y H, Zhou Z R, et al. A quantum convolutional neural network on NISQ devices[J]. AAPPS Bulletin, 2022, 32(1): 2, doi: 10.1007/s43673-021-00030-3. |
| [31] |
Zhou Z R, Li H, Long G L. Variational quantum algorithm for node embedding[J]. Fundamental Research, 2024, 4(4): 845-850.
DOI URL |
| [32] | Albash T, Lidar D A. Adiabatic quantum computation[J]. Reviews of Modern Physics, 2018, 90: 015002, doi: 10.1103/RevModPhys.90.015002. |
| [33] |
Zhang J, Kyaw T H, Fillipp S, et al. Geometric and holonomic quantum computation[J]. Physics Reports, 2023, 1027: 1-53.
DOI URL |
| [34] | Du J F, Xu N Y, Peng X H, et al. NMR implementation of a molecular hydrogen quantum simulation with adiabatic state preparation[J]. Physical Review Letters, 2010, 104(3): 030502, doi:10.1103/PhysRevLett.104.030502. |
| [35] |
Abrams D S, Lloyd S. Simulation of many-body Fermi systems on a universal quantum computer[J]. Physical Review Letters, 1997, 79(13): 2586-2589.
DOI URL |
| [36] |
Aspuru-Guzik A, Dutoi A D, Love P J, et al. Simulated quantum computation of molecular energies[J]. Science, 2005, 309(5741): 1704-1707.
PMID |
| [37] |
Peruzzo A, McClean J, Shadbolt P, et al. A variational eigenvalue solver on a photonic quantum processor[J]. Nature Communications, 2014, 5: 4213, doi: 10.1038/ncomms5213.
PMID |
| [38] |
Kandala A, Mezzacapo A, Temme K, et al. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets[J]. Nature, 2017, 549(7671): 242-246.
DOI URL |
| [39] |
Li W T, Huang Z G, Cao C S, et al. Toward practical quantum embedding simulation of realistic chemical systems on near-term quantum computers[J]. Chemical Science, 2022, 13(31): 8953-8962.
DOI PMID |
| [40] | Wei S J, Li H, Long G L. A full quantum eigensolver for quantum chemistry simulations[J]. Research, 2020, 2020: 1486935, doi: 10.34133/2020/1486935. |
| [41] | Wang B Z, Wen J W, Wu J W, et al. Improving the full quantum eigensolver with exponentiated operators[J]. Physical Review B, 2024, 109(24): 245117, doi: 10.34133/2020/1486935. |
| [42] | Wen J W, Wang Z G, Chen C T, et al. A full circuit-based quantum algorithm for excited-states in quantum chemistry[J]. Quantum, 2024, 8: 1219, doi: 10.22331/q-2024-01-04-1219. |
| [43] | Liu T, Liu J G, Fan H. Probabilistic nonunitary gate in imaginary time evolution[J]. Quantum Information Processing, 2021, 20(6): 204, doi: 10.1007/s11128-021-03145-6. |
| [44] | Huo M X, Li Y. Error-resilient Monte Carlo quantum simulation of imaginary time[J]. Quantum, 2023, 7: 916, doi: 10.22331/q-2023-02-09-916. |
| [45] |
Coppersmith D, Holloway C, Matyas S M, et al. The data encryption standard[J]. Information Security Technical Report, 1997, 2(2): 22-24.
DOI URL |
| [46] | Daemen J, Rijmen V. The design of Rijndael: The advanced encryption standard (AES)[M]. 2nd ed. Berlin-Heidelberg: Springer, 2020. |
| [47] | Yamamura A, Ishizuka H. Quantum cryptanalysis of block ciphers (algebraic systems, formal languages and computations)[J]. RIMS Kokyuroku, 2000, 1166: 235-243. |
| [48] | Grassl M, Langenberg B, Roettele M, et al. Applying grover’s algorithm to AES: Quantum resource estimates[M]// Post-Quantum Cryptography. Cham: Springer International Publishing, 2016: 29-43. |
| [49] | Kim P, Han D, Jeong K C. Time-space complexity of quantum search algorithms in symmetric cryptanalysis: Applying to AES and SHA-2[J]. Quantum Information Processing, 2018, 17(12): 339, doi: 10.1007/s11128-018-2107-3. |
| [50] | Langenberg B, Pham H, Steinwandt R. Reducing the cost of implementing the advanced encryption standard as a quantum circuit[J]. IEEE Transactions on Quantum Engineering, 2020, 1: 2500112, doi: 10.1109/TQE.2020.2965697. |
| [51] | Almazrooie M, Samsudin A, Abdullah R, et al. Quantum exhaustive key search with simplified-DES as a case study[J]. SpringerPlus, 2016, 5(1): 1494, doi: 10.1186/s40064-016-3159-4. |
| [52] |
Ambainis A. Quantum walk algorithm for element distinctness[J]. SIAM Journal on Computing, 2007, 37(1): 210-239.
DOI URL |
| [53] |
Li R J, Jin C H. Meet-in-the-middle attacks on 10-round AES-256[J]. Designs, Codes and Cryptography, 2016, 80(3): 459-471.
DOI URL |
| [54] |
Chen Y A, Gao X S. Quantum algorithm for Boolean equation solving and quantum algebraic attack on cryptosystems[J]. Journal of Systems Science and Complexity, 2022, 35(1): 373-412.
DOI |
| [55] | Wang Z G, Wei S J, Long G L, et al. Variational quantum attacks threaten advanced encryption standard based symmetric cryptography[J]. Science China Information Sciences, 2022, 65(10): 200503, doi: 10.1007/s11432-022-3511-5. |
| [56] | Wang Z G, Wei S J, Long G L. A quantum circuit design of AES requiring fewer quantum qubits and gate operations[J]. Frontiers of Physics, 2022, 17(4): 41501, doi: 10.1007/s11467-021-1141-2. |
| [57] | Regev O. An efficient quantum factoring algorithm[J]. Journal of the ACM, 2025, 72(1): 1-13. |
| [58] | Yan B, Tan Z Q, Wei S J, et al. Factoring integers with sublinear resources on a superconducting quantum processor[DB/OL]. arXiv preprint:2212.12372, 2022. |
| [59] | Zalivako I V, Chernyavskiy A Y, Nikolaeva A S, et al. Experimental factoring integers using fixed-point-QAOA with a trapped-ion quantum processor[DB/OL]. arXiv preprint:2503.10588, 2025. |
| [60] | Tesoro M, Siloi I, Jaschke D, et al. Quantum inspired factorization up to 100-bit RSA number in polynomial time[DB/OL]. arXiv preprint:2410.16355, 2024. |
| [61] | 闫宝, 魏世杰, 龙桂鲁. 量子经典融合整数分解算法的发展现状与展望[J]. 中国科学(信息科学), 2025, doi: 10.1360/SSI-2025-0105. |
| Yan B, Wei S J, Long G L. The status and prospect of quantum-classical combination integer factorization algorithm[J]. Science China Information Sciences, 2025, doi: 10.1360/SSI-2025-0105. (in Chinese) | |
| [62] | Grilo A B, Kerenidis I, Zijlstra T. Learning-with-errors problem is easy with quantum samples[J]. Physical Review A, 2019, 99(3): 032314, doi: 10.1103/PhysRevA.99.032314. |
| [63] | Song W, Lim Y, Jeong K, et al. Polynomial T-depth quantum solvability of noisy binary linear problem: from quantum-sample preparation to main computation[J]. New Journal of Physics, 2022, 24(10): 103014, doi: 10.1088/1367-2630/ac94ef. |
| [64] | Song W, Lim Y, Jeong K, et al. Quantum solvability of noisy linear problems by divide-and-conquer strategy[J]. Quantum Science and Technology, 2022, 7(2): 025009, doi: 10.1088/2058-9565/ac51b0. |
| [65] | Zeng J F, Zheng M X, LI H, et al. Analysis of learning with errors problems with variational quantum algorithms[J]. Europhysics Letters, 2025, 150(5): 58001, doi: 10.1209/0295-5075/add959. |
| [66] | Zheng M X, Zeng J F, Yang W T, et al. Quantum-classical hybrid algorithm for solving the learning-with-errors problem on NISQ devices[J]. Communications Physics, 2025, 8: 208, doi: 10.1038/s42005-025-02126-w. |
| [67] | Priestley B, Wallden P. A practically scalable approach to the closest vector problem for sieving via qaoa with fixed angles[DB/OL]. arXiv preprint:2503.08403, 2025. |
| [68] | Apolloni B, Cesa-Bianchi N, De Falco D. A numerical implementation of “quantum annealing”[C]// Stochastic Processes, Physics and Geometry:Proceedings of The Ascona-Locarno Conference. Singapore: World Scientific Publishing Company, 1990: 97-111. |
| [69] |
Kadowaki T, Nishimori H. Quantum annealing in the transverse Ising model[J]. Physical Review E, 1998, 58(5): 5355-5363.
DOI URL |
| [70] | Lucas A. Ising formulations of many NP problems[J]. Frontiers in Physics, 2014, 2: 5, doi: 10.3389/fphy.2014.00005. |
| [71] |
Johnson M W, Amin M H S, Gildert S, et al. Quantum annealing with manufactured spins[J]. Nature, 2011, 473(7346): 194-198.
DOI |
| [72] | Zhang H, Boothby K, Kamenev A. Cyclic quantum annealing: searching for deep low-energy states in 5000-qubit spin glass[J]. Scientific Reports, 2024, 14: 30784, doi: 10.1038/s41598-024-80761-z. |
| [73] | Lanting T, Przybysz A J, Smirnov A Y, et al. Entanglement in a quantum annealing processor[J]. Physical Review X, 2014, 4(2): 021041, doi: 10.1103/PhysRevX.4.021041. |
| [74] | Farhi E, Goldstone J, Gutmann S, et al. Quantum computation by adiabatic evolution[DB/OL]. arXiv preprint::quant-ph/0001106, 2000. |
| [75] |
Farhi E, Goldstone J, Gutmann S, et al. A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem[J]. Science, 2001, 292(5516): 472-476.
PMID |
| [76] | Aharonov D, Van Dam W, Kempe J, et al. Adiabatic quantum computation is equivalent to standard quantum computation[J]. SIAM Review, 2008, 50(4): 755-787. |
| [77] | Amin M H. Searching for quantum speedup in quasistatic quantum annealers[J]. Physical Review A, 2015, 92(5): 052323, doi: 10.1103/PhysRevA.92.052323. |
| [78] | Hauke P, Katzgraber H G, Lechner W, et al. Perspectives of quantum annealing: Methods and implementations[J]. Reports on Progress in Physics, 2020, 83(5): 054401, doi: 10.1088/1361-6633/ab85b8. |
| [79] | Farhi E, Goldstone J, Gutmann S. A quantum approximate optimization algorithm[DB/OL]. arXiv preprint:1411.4028, 2014. |
| [80] | Zhou L, Wang S T, Choi S, et al. Quantum approximate optimization algorithm: performance, mechanism, and implementation on near-term devices[J]. Physical Review X, 2020, 10(2): 021067, doi: 10.1103/PhysRevX.10.021067. |
| [81] | Harrigan M P, Sung K J, Neeley M, et al. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor[J]. Nature Physics, 2021, 17(3): 332-336. |
| [82] | Li H, Xing T H, Wei S J, et al. BQ-bank: A quantum software for finance and banking[J]. Quantum Engineering, 2023, 2023(1): 7810974, doi: 10.1155/2023/7810974. |
| [83] | Ding Q M, Huang Y M, Yuan X. Molecular docking via quantum approximate optimization algorithm[J]. Physical Review Applied, 2024, 21(3): 034036, doi: 10.1103/PhysRevApplied.21.034036. |
| [84] | Aboumrad W, Widdows D, Kaushik A. Quantum and classical combinatorial optimizations applied to lattice-based factorization[DB/OL]. arXiv preprint:2308.07804, 2023. |
| [85] | Herrman R, Lotshaw P C, Ostrowski J, et al. Multi-angle quantum approximate optimization algorithm[J]. Scientific Reports, 2022, 12: 6781, doi: 10.1038/s41598-022-10555-8. |
| [86] | Chalupnik M, Melo H, Alexeev Y, et al. Augmenting QAOA ansatz with multiparameter problem-independent layer[C]// 2022 IEEE International Conference on Quantum Computing and Engineering (QCE). Piscataway: IEEE Press, 2022: 97-103. |
| [87] | Chandarana P, Hegade N N, Paul K, et al. Digitized-counterdiabatic quantum approximate optimization algorithm[J]. Physical Review Research, 2022, 4: 013141, doi: 10.1103/PhysRevResearch.4.013141. |
| [88] | Wurtz J, Love P J. Counterdiabaticity and the quantum approximate optimization algorithm[J]. Quantum, 2022, 6: 635, doi: 10.22331/q-2022-01-27-635. |
| [89] | Yao J H, Lin L, Bukov M. Reinforcement learning for many-body ground-state preparation inspired by counterdiabatic driving[J]. Physical Review X, 2021, 11(3): 031070, doi: 10.1103/PhysRevX.11.031070. |
| [90] | Yu Y L, Cao C F, Dewey C, et al. Quantum approximate optimization algorithm with adaptive bias fields[J]. Physical Review Research, 2022, 4(2): 023249, doi: 10.1103/PhysRevResearch.4.023249. |
| [91] | Zhu L H, Tang H L, Barron G S, et al. Adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer[J]. Physical Review Research, 2022, 4(3): 033029, doi: 10.1103/PhysRevResearch.4.033029. |
| [92] | Bravyi S, Kliesch A, Koenig R, et al. Obstacles to variational quantum optimization from symmetry protection[J]. Physical Review Letters, 2020, 125(26): 260505, doi: 10.1103/PhysRevLett.125.260505. |
| [93] | Moll N, Barkoutsos P, Bishop L S, et al. Quantum optimization using variational algorithms on near-term quantum devices[J]. Quantum Science and Technology, 2018, 3(3): 030503, doi: 10.1088/2058-9565/aab822. |
| [94] | Skolik A, McClean J R, Mohseni M, et al. Layerwise learning for quantum neural networks[J]. Quantum Machine Intelligence, 2021, 3(1): 5, doi: 10.1007/s42484-020-00036-4. |
| [95] | McClean J R, Boixo S, Smelyanskiy V N, et al. Barren plateaus in quantum neural network training landscapes[J]. Nature Communications, 2018, 9: 4812, doi: 10.1038/s41467-018-07090-4. |
| [96] | Brown B J, Loss D, Pachos J K, et al. Quantum memories at finite temperature[J]. Reviews of Modern Physics, 2016, 88(4): 045005, doi: 10.1103/RevModPhys.88.045005. |
| [97] | Fowler A G, Mariantoni M, Martinis J M, et al. Surface codes: Towards practical large-scale quantum computation[J]. Physical Review A, 2012, 86(3): 032324, doi: 10.1103/PhysRevA.86.032324. |
| [98] | Bravyi S, Cross A W, Gambetta J M J M, et al. High-threshold and low-overhead fault-tolerant quantum memory[J]. Nature, 2024, 627(8005): 778-782. |
| No related articles found! |
| 阅读次数 | ||||||
|
全文 |
|
|||||
|
摘要 |
|
|||||

