量子演算法
量子演算法（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. [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.