量子算法

量子算法（Quantum algorithm；量子算法）是在量子计算中，于量子计算的现实模型上运行的算法，最常用的模型是量子线路的计算模型。^[1][2]经典（或非量子）算法是有限的指令序列，或用于解决问题的分步骤过程，其中每个步骤或指令都可以在经典计算机上执行。同样地量子算法是一个循序渐进的过程，其中每个步骤都可以在量子计算机上执行。尽管所有经典算法也可以在量子计算机上执行，^[3]:126量子算法一词通常用于那些看起来本质上是量子的算法，或者使用量子计算的某些特性，例如量子叠加、或量子纠缠等。

使用经典计算机对于不可判定问题仍然无法使用量子计算机判定。^[4]:127量子算法的有趣之处在于它们可能比经典算法更快地解决一些问题，因为量子算法利用的量子叠加及量子纠缠可能无法解决在经典计算机上进行有效的模拟（参阅量子计算优越性）。

最著名的算法是用于因式分解的萧尔算法以及用于搜索非结构化数据库，或无序列表的格罗弗算法。萧尔算法比最著名的经典分解算法（普通数域筛选法）运行得快得多（呈指数级）。^[5]对于相同的任务，格罗弗算法的查询复杂度跟经典算法相比有平方的加速。

参见

• 量子计算
• 量子编程
• 量子图灵机
• 秀尔算法
• 量子比特
• 量子信息科学
• 量子计算优越性

注释

1. Nielsen, Michael A.; Chuang, Isaac L. Quantum Computation and Quantum Information. Cambridge University Press. 2000. ISBN 978-0-521-63503-5.
2. Mosca, M. Quantum Algorithms. 2008. arXiv:0808.0369  [quant-ph].
3. Lanzagorta, Marco; Uhlmann, Jeffrey K. Quantum Computer Science. Morgan & Claypool Publishers. 2009-01-01. ISBN 9781598297324.
4. Nielsen, Michael A.; Chuang, Isaac L. Quantum Computation and Quantum Information 2nd. Cambridge: Cambridge University Press. 2010. ISBN 978-1-107-00217-3.
5. Shor's algorithm. [2021-09-21]. （原始内容存档于2021-01-25）.

外部链接

• The Quantum Algorithm Zoo: A comprehensive list of quantum algorithms that provide a speedup over the fastest known classical algorithms.
• Andrew Childs' lecture notes on quantum algorithms （页面存档备份，存于互联网档案馆）
• The Quantum search algorithm - brute force （页面存档备份，存于互联网档案馆）.

调查

• Smith, J.; Mosca, M. Algorithms for Quantum Computers. Handbook of Natural Computing. 2012: 1451. ISBN 978-3-540-92909-3. S2CID 16565723. doi:10.1007/978-3-540-92910-9_43.
• Childs, A. M.; Van Dam, W. Quantum algorithms for algebraic problems. Reviews of Modern Physics. 2010, 82 (1): 1–52. Bibcode:2010RvMP...82....1C. S2CID 119261679. arXiv:0812.0380 . doi:10.1103/RevModPhys.82.1.