量子演算法:修订间差异
外观
删除的内容 添加的内容
小 修正筆誤,Grover's search 並非線性搜索,也不只有常數的加速。另外 Shor's algorithm 有達到指數加速。 标签:2017版源代码编辑 |
|||
第1行: | 第1行: | ||
'''量子演算法'''(Quantum algorithm;量子算法)是在[[量子計算]]中,於量子計算的現實模型上運行的[[演算法]],最常用的模型是[[量子線路]]的計算模型。<ref>{{cite book|title=Quantum Computation and Quantum Information|last1=Nielsen|first1=Michael A.|last2=Chuang|first2=Isaac L.|publisher=[[Cambridge University Press]]|year=2000|isbn=978-0-521-63503-5|author-link=Michael Nielsen|author-link2=Isaac Chuang|title-link=Quantum Computation and Quantum Information}}</ref><ref>{{cite arXiv|eprint=0808.0369|class=quant-ph|first=M.|last=Mosca|author-link=Michele Mosca|title=Quantum Algorithms|date=2008}}</ref>經典(或非量子)演算法是有限的指令序列,或用於解決問題的分步驟過程,其中每個步驟或指令都可以在經典計算機上執行。同樣地量子演算法是一個循序漸進的過程,其中每個步驟都可以在[[量子計算機]]上執行。儘管所有經典演算法也可以在量子計算機上執行,<ref>{{Cite book|title = Quantum Computer Science|url = https://books.google.com/books?id=-wkJIuw0YRsC&q=quantum%2520computer%2520equivalent%2520classical%2520computer&pg=PA23|publisher = Morgan & Claypool Publishers|date = 2009-01-01|isbn = 9781598297324|first1 = Marco|last1 = Lanzagorta|first2 = Jeffrey K.|last2 = Uhlmann}}</ref>{{rp|126}}量子演算法一詞通常用於那些看起來本質上是量子的演算法,或者使用量子計算的某些 |
'''量子演算法'''(Quantum algorithm;量子算法)是在[[量子計算]]中,於量子計算的現實模型上運行的[[演算法]],最常用的模型是[[量子線路]]的計算模型。<ref>{{cite book|title=Quantum Computation and Quantum Information|last1=Nielsen|first1=Michael A.|last2=Chuang|first2=Isaac L.|publisher=[[Cambridge University Press]]|year=2000|isbn=978-0-521-63503-5|author-link=Michael Nielsen|author-link2=Isaac Chuang|title-link=Quantum Computation and Quantum Information}}</ref><ref>{{cite arXiv|eprint=0808.0369|class=quant-ph|first=M.|last=Mosca|author-link=Michele Mosca|title=Quantum Algorithms|date=2008}}</ref>經典(或非量子)演算法是有限的指令序列,或用於解決問題的分步驟過程,其中每個步驟或指令都可以在經典計算機上執行。同樣地量子演算法是一個循序漸進的過程,其中每個步驟都可以在[[量子計算機]]上執行。儘管所有經典演算法也可以在量子計算機上執行,<ref>{{Cite book|title = Quantum Computer Science|url = https://books.google.com/books?id=-wkJIuw0YRsC&q=quantum%2520computer%2520equivalent%2520classical%2520computer&pg=PA23|publisher = Morgan & Claypool Publishers|date = 2009-01-01|isbn = 9781598297324|first1 = Marco|last1 = Lanzagorta|first2 = Jeffrey K.|last2 = Uhlmann}}</ref>{{rp|126}}量子演算法一詞通常用於那些看起來本質上是量子的演算法,或者使用量子計算的某些特性,例如[[量子疊加]]、或[[量子糾纏]]等。 |
||
使用經典計算機對於[[不可判定問題]]仍然無法使用量子計算機判定。<ref name=nielchuan>{{cite book|title=Quantum Computation and Quantum Information|last1=Nielsen|first1=Michael A.|last2=Chuang|first2=Isaac L.|publisher=Cambridge University Press|year=2010|isbn=978-1-107-00217-3|edition=2nd|location=Cambridge|author-link=Michael A. Nielsen|author-link2=Isaac Chuang|url=https://books.google.com/books?id=-s4DEy7o-a0C}}</ref>{{rp|127}}量子演算法的有趣之處在於它們可能比經典演算法更快地解決一些問題,因為量子演算法利用的量子疊加及量子糾纏可能無法解決在經典計算機上進行有效的模擬(參閱[[量子計算優越性]])。 |
使用經典計算機對於[[不可判定問題]]仍然無法使用量子計算機判定。<ref name=nielchuan>{{cite book|title=Quantum Computation and Quantum Information|last1=Nielsen|first1=Michael A.|last2=Chuang|first2=Isaac L.|publisher=Cambridge University Press|year=2010|isbn=978-1-107-00217-3|edition=2nd|location=Cambridge|author-link=Michael A. Nielsen|author-link2=Isaac Chuang|url=https://books.google.com/books?id=-s4DEy7o-a0C}}</ref>{{rp|127}}量子演算法的有趣之處在於它們可能比經典演算法更快地解決一些問題,因為量子演算法利用的量子疊加及量子糾纏可能無法解決在經典計算機上進行有效的模擬(參閱[[量子計算優越性]])。 |
||
最著名的演算法是用於因式分解的[[蕭爾演算法]]以及用於搜索非結構化數據庫,或無序列表的[[格罗弗算法]]。蕭爾演算法比最著名的經典分解算法([[普通數域篩選法]])運行得快得多( |
最著名的演算法是用於因式分解的[[蕭爾演算法]]以及用於搜索非結構化數據庫,或無序列表的[[格罗弗算法]]。蕭爾演算法比最著名的經典分解算法([[普通數域篩選法]])運行得快得多(呈指數級)。<ref>{{Cite web|url=https://quantum-computing.ibm.com/docs/iqx/guide/shors-algorithm|title = Shor's algorithm}}</ref>對於相同的任務,格羅弗演算法的[[量子複雜性理論|查詢複雜度]]跟經典演算法相比有[[平方]]的加速。 |
||
==註釋== |
==註釋== |
2022年1月29日 (六) 10:05的版本
量子演算法(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.