量子演算法（Quantum algorithm；量子算法）是在量子计算中，于量子计算的现实模型上运行的演算法，最常用的模型是量子线路的计算模型。[1][2]经典（或非量子）演算法是有限的指令序列，或用于解決问题的分步驟过程，其中每个步驟或指令都可以在经典计算机上执行。同样地量子演算法是一个循序渐进的过程，其中每个步驟都可以在量子计算机上执行。儘管所有经典演算法也可以在量子计算机上执行，[3]:126量子演算法一词通常用于那些看起来本质上是量子的演算法，或者使用量子计算的某些基本特征，例如量子疊加、或量子糾纏等。
使用经典计算机对于不可判定问题仍然无法使用量子计算机判定。[4]:127量子演算法的有趣之处在于它们可能比经典演算法更快地解決一些问题，因为量子演算法利用的量子疊加及量子糾纏可能无法解決在经典计算机上进行有效的模擬（参閱量子计算优越性）。
最著名的演算法是用于因式分解的蕭尔演算法以及用于搜索非结构化数据库，或无序列表的格罗弗算法。蕭尔演算法比最著名的经典分解算法（普通数域篩选法）运行得快得多（几乎呈指数级）。[5]对于相同的任务，格罗弗演算法的运行速度比最好的经典演算法快两倍，是一种线性搜索方法。
注释
- ↑ Nielsen, Michael A.; Chuang, Isaac L. Quantum Computation and Quantum Information. Cambridge University Press. 2000. ISBN 978-0-521-63503-5.
- ↑ Mosca, M. Quantum Algorithms. 2008. arXiv:0808.0369
[quant-ph].
- ↑ Lanzagorta, Marco; Uhlmann, Jeffrey K. Quantum Computer Science. Morgan & Claypool Publishers. 2009-01-01. ISBN 9781598297324.
- ↑ Nielsen, Michael A.; Chuang, Isaac L. Quantum Computation and Quantum Information 2nd. Cambridge: Cambridge University Press. 2010. ISBN 978-1-107-00217-3.
- ↑ Shor's algorithm.
参閱
外部链接
- 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.
