秀尔演算法
秀爾演算法(英語:)是一個于1994年發現的,以數學家彼得·秀爾命名,針對整數分解題目的的量子演算法(在量子計算機上面運作的演算法)。不正式地說,它解決的題目是:給定一個整數 ,找出他的質因數。在一個量子計算機上面,要分解整數,秀爾演算法的運作需要多項式時間(時間是 的某個多項式這麼長, 在這裡的意義是輸入的檔案長度)。准确来说,该演算法花費 的時間,展示出質因數分解問題可以使用量子計算機以多項式時間解出,因此在複雜度類BQP裡面。這比傳統上已知的最快的因數分解演算法普通數域篩選法所花費的次指數時間——大約 還要快了一個指數。
秀爾演算法非常重要,它意味着:假如有可用的量子計算機,我們可以破解基于公開密鑰加密的算法(比如RSA加密演算法)。RSA演算法的基礎在於假設了我們不能有效率的分解一個已知的整數。就目前所知,這假設對傳統(即非量子)的電腦為真;沒有已知的傳統演算法可以在多項式時間內解決這個問題。但秀爾演算法展示了因數分解問題在量子計算機上可以很有效率的解決,所以一個足夠大的量子計算機可以破解RSA。這對於建立量子計算機和研究新的量子計算機演算法是一個强大的動力。
2001年,IBM的一個小組展示了秀爾演算法的實例,使用NMR實驗的量子計算機及7個量子位元,將15分解成3×5。不过,对于IBM的實驗是否是量子計算的真實展示,有一些疑慮出現,因為沒有发现纏結現象。IBM的實驗之後,也有其他的團隊以光學量子位元實驗秀爾演算法,並強調可觀察到其纏結現象。
程序
試著解決的問題是:給定一個合成數,找到整數在和之間且不包含和,並且整除於。
秀爾演算法包含兩個部份:
- 一個以傳統電腦運作的簡化演算法,將因數分解簡化成搜尋階問題。
- 一個量子演算法,解決搜尋階問題。
傳統部份
量子部份:週期尋找子程序(Period-finding subroutine)
這個演算法使用的量子線路是為了在給定一個固定常數 以及一個任意常數 之下,找出 所設定的。給定 ,找出 = 2 且合乎(這同時表示)。輸入和輸出量子位元暫存器需要儲存從0到 -1所有值的疊加態,因此分別需要 個量子位元。這裡使用看起來比所需的數量還要更多一倍的量子位元,保證了即使週期 的大小逼近 /2,也至少有 個不同的 會產生相同的 。
程序如下:
- 將暫存器初始化成
- 建立量子函式版本的 ( ),並且應用於上面的疊加態,得到
- .
這裡仍舊是 個狀態的疊加。
- 對輸入暫存器進行量子傅立葉變換。這個變換(操作於二的冪次—— 個疊加態上面)
使用一個 單位根例如將任意給定態的振幅平均分佈在所有 個態上。另一個方法是對於每個不同的 :
- 。
由此得到最終狀態:
- .
這是一個遠多過 個狀態的疊加態,但是遠低過 2個。雖然在和中有 2項,但只要 和 的值相同,態就可被提出來。令
- 為 的一個單位根,
- 為 的週期,
- 0為一個產生相同 ( )的 的集裡面的最小元素(我們已經有 0 < ),以及
- b在0到之間使得。那麼則是復平面的一個單位向量(是一個單位根, 和y是整數),而在最終狀態下的係數則為
- 。這一求和的每一項代表一個獲得相同結果的不同路徑,而量子干涉發生。在單位向量幾乎與復平面指向同一方向(要求指向正實數軸)時,干涉將是相長的。
- 進行測量。我們由輸入寄存器取得結果y,由輸出寄存器取得。而既然 是週期,對某對y和進行測量的概率則由
- 對進行連分數展開來計算其近似值,並生成滿足下列兩個條件的:
- 檢查 ( ) = ( + ′) 。如果成功了,我們就完成了。
- 否則,以接近y左右的數值作為 的候選,或者說多取幾個 .如果任何候選成功了,我們就完成了。
- 否則,回到第一步驟(也就是全部重新做一次)。
傳統部份
量子部份:週期尋找子程序(Period-finding subroutine)
這個演算法使用的量子線路是為了在給定一個固定常數 以及一個任意常數 之下,找出 所設定的。給定 ,找出 = 2 且合乎(這同時表示)。輸入和輸出量子位元暫存器需要儲存從0到 -1所有值的疊加態,因此分別需要 個量子位元。這裡使用看起來比所需的數量還要更多一倍的量子位元,保證了即使週期 的大小逼近 /2,也至少有 個不同的 會產生相同的 。
程序如下:
- 將暫存器初始化成
- 建立量子函式版本的 ( ),並且應用於上面的疊加態,得到
- .
這裡仍舊是 個狀態的疊加。
- 對輸入暫存器進行量子傅立葉變換。這個變換(操作於二的冪次—— 個疊加態上面)
使用一個 單位根例如將任意給定態的振幅平均分佈在所有 個態上。另一個方法是對於每個不同的 :
- 。
由此得到最終狀態:
- .
這是一個遠多過 個狀態的疊加態,但是遠低過 2個。雖然在和中有 2項,但只要 和 的值相同,態就可被提出來。令
- 為 的一個單位根,
- 為 的週期,
- 0為一個產生相同 ( )的 的集裡面的最小元素(我們已經有 0 < ),以及
- b在0到之間使得。那麼則是復平面的一個單位向量(是一個單位根, 和y是整數),而在最終狀態下的係數則為
- 。這一求和的每一項代表一個獲得相同結果的不同路徑,而量子干涉發生。在單位向量幾乎與復平面指向同一方向(要求指向正實數軸)時,干涉將是相長的。
- 進行測量。我們由輸入寄存器取得結果y,由輸出寄存器取得。而既然 是週期,對某對y和進行測量的概率則由
- 對進行連分數展開來計算其近似值,並生成滿足下列兩個條件的:
- 檢查 ( ) = ( + ′) 。如果成功了,我們就完成了。
- 否則,以接近y左右的數值作為 的候選,或者說多取幾個 .如果任何候選成功了,我們就完成了。
- 否則,回到第一步驟(也就是全部重新做一次)。
演算法的解釋
此演算法包含兩個部份。演算法的第一部份是將因數分解問題轉成尋找一個函式的週期,而且這部份可以用傳統方式實作。第二部份則是使用量子傅立葉變換來搜尋這個函式的週期,而且這一部份是量子加速這整個演算法的理由。
I.從週期得到因數
小於N且互質於N的整數組成一個有限大,且對乘法同餘N的群。在步驟3之後,我們有一個屬於這個群的整數a。既然這個群是有限的,a必有一個有限大的階r,也就是最小的正整數令
因此可知,N是a r − 1的因數。先假設我們有能力獲得r,而且r是偶數。則
r是令a r ≡ 1最小的正整數,所以(a r / 2 − 1)必定不能整除於N。若(a r / 2 + 1)也不整除於N的話,則N必定與(a r / 2 − 1)或者(a r / 2 + 1)有一個非顯然的公因數。
證明:為了簡化,我們分別用u和v表示(a r / 2 − 1)和(a r / 2 + 1)。N | uv,故kN = uv(k是某個整數)。假設gcd(v, N) = 1:則必定存在某個整數m和n令mv + nN = 1 (這是最大公因數的一個性質)。兩邊同乘以u,我們得到mkN + nuN = u, 所以 N | u,从而產生矛盾(前文提到(a r / 2 − 1)必定不能整除於N)。故假设不成立,即gcd(v, N) ≠ 1。用類似的方法,可以得知若(a r / 2 + 1)不能整除於N, gcd(u, N) ≠ 1。故得證u和v不同時與N互質。
這給予我們一個N的因數分解。若N是兩個質數的乘積,則這是唯一可能的分解。
II.找尋週期
秀爾的週期尋找演算法非常倚賴量子計算機同時計算許多狀態的能力。物理學家稱呼這個特性為這一些狀態的"疊加"。在計算函數f的週期時,我們會同時估計這個函數的所有點。
不過,量子物理不允許我們直接取得這一些資訊。測量會令觀測結果塌陷到其中一個可能的結果,並摧毀其他可能性的存在。但是根據不可克隆原理,我們可以先測量f(x)而非測量x,再製造幾個結果態的拷貝(將會是多個有著同樣的f(x)的態的疊加)。對這些態上的x的測量將會給出能給出相同f(x)的不同的x,由此推導出週期來。因為我們不能複製完全相同的量子狀態,這個方法行不通。因此在這裡我們需要小心的將疊加態轉變成我們有辦法以很高的正確機率回答答案的狀態。在這裡我們使用量子傅立葉變換來達成。
因此秀爾在這裡必須解決三個"實作"的問題。這一些問題都必須要有很快的實作,或者說他們可以用的多項式個數這麼多量子閘來實作。
- 製造狀態的疊加。 這可以藉著對所有輸入的量子位元使用哈達瑪閘(Hadamard gate)來達成。另一個方法是使用量子傅立葉變換(如下述)。
- 以量子變換實作函數f。 要達成這件事情,秀爾使用了反復平方以完成模的取幂變換。值得注意的是,這一個步驟比起量子傅立葉變換還難以實作,需要更多輔助的量子位元以及大體上更多的閘來完成。
- 進行量子傅立葉變換。 利用受控旋轉閘(controlled rotation gate)和哈達瑪閘,秀爾設計了一個量子傅立葉變換的線路,只有使用了個閘(Q = 2q)。
在這一些變換之後,測量會逼近於週期r的近似值。為簡明起見,假設存在y令yr/Q是整數,則測量到y的機率是1(理論上)。要推導出這個,我們首先注意到對任何整數b,
- 。因此Q/r的平方能告訴我們測量y的概率,因為b大致上取Q/r個值,因此概率為。有r個y使得yr/Q為整數,也有r種可能,所以機率總和為1。
Note:另一種解釋秀爾演算法的方式是將之視為是喬裝過後的量子相位估計演算法。
I.從週期得到因數
小於N且互質於N的整數組成一個有限大,且對乘法同餘N的群。在步驟3之後,我們有一個屬於這個群的整數a。既然這個群是有限的,a必有一個有限大的階r,也就是最小的正整數令
因此可知,N是a r − 1的因數。先假設我們有能力獲得r,而且r是偶數。則
r是令a r ≡ 1最小的正整數,所以(a r / 2 − 1)必定不能整除於N。若(a r / 2 + 1)也不整除於N的話,則N必定與(a r / 2 − 1)或者(a r / 2 + 1)有一個非顯然的公因數。
證明:為了簡化,我們分別用u和v表示(a r / 2 − 1)和(a r / 2 + 1)。N | uv,故kN = uv(k是某個整數)。假設gcd(v, N) = 1:則必定存在某個整數m和n令mv + nN = 1 (這是最大公因數的一個性質)。兩邊同乘以u,我們得到mkN + nuN = u, 所以 N | u,从而產生矛盾(前文提到(a r / 2 − 1)必定不能整除於N)。故假设不成立,即gcd(v, N) ≠ 1。用類似的方法,可以得知若(a r / 2 + 1)不能整除於N, gcd(u, N) ≠ 1。故得證u和v不同時與N互質。
這給予我們一個N的因數分解。若N是兩個質數的乘積,則這是唯一可能的分解。
II.找尋週期
秀爾的週期尋找演算法非常倚賴量子計算機同時計算許多狀態的能力。物理學家稱呼這個特性為這一些狀態的"疊加"。在計算函數f的週期時,我們會同時估計這個函數的所有點。
不過,量子物理不允許我們直接取得這一些資訊。測量會令觀測結果塌陷到其中一個可能的結果,並摧毀其他可能性的存在。但是根據不可克隆原理,我們可以先測量f(x)而非測量x,再製造幾個結果態的拷貝(將會是多個有著同樣的f(x)的態的疊加)。對這些態上的x的測量將會給出能給出相同f(x)的不同的x,由此推導出週期來。因為我們不能複製完全相同的量子狀態,這個方法行不通。因此在這裡我們需要小心的將疊加態轉變成我們有辦法以很高的正確機率回答答案的狀態。在這裡我們使用量子傅立葉變換來達成。
因此秀爾在這裡必須解決三個"實作"的問題。這一些問題都必須要有很快的實作,或者說他們可以用的多項式個數這麼多量子閘來實作。
- 製造狀態的疊加。 這可以藉著對所有輸入的量子位元使用哈達瑪閘(Hadamard gate)來達成。另一個方法是使用量子傅立葉變換(如下述)。
- 以量子變換實作函數f。 要達成這件事情,秀爾使用了反復平方以完成模的取幂變換。值得注意的是,這一個步驟比起量子傅立葉變換還難以實作,需要更多輔助的量子位元以及大體上更多的閘來完成。
- 進行量子傅立葉變換。 利用受控旋轉閘(controlled rotation gate)和哈達瑪閘,秀爾設計了一個量子傅立葉變換的線路,只有使用了個閘(Q = 2q)。
在這一些變換之後,測量會逼近於週期r的近似值。為簡明起見,假設存在y令yr/Q是整數,則測量到y的機率是1(理論上)。要推導出這個,我們首先注意到對任何整數b,
- 。因此Q/r的平方能告訴我們測量y的概率,因為b大致上取Q/r個值,因此概率為。有r個y使得yr/Q為整數,也有r種可能,所以機率總和為1。
Note:另一種解釋秀爾演算法的方式是將之視為是喬裝過後的量子相位估計演算法。
质疑
有反对者认为,秀尔算法的量子部分与传统部分在运行中传递了什么信息无法解释清楚。
參考資料
- Vandersypen, Lieven M. K.; Steffen, Matthias; Breyta, Gregory; Yannoni, Costantino S.; Sherwood, Mark H. & Chuang, Isaac L., , Nature, 2001, 414 (6866): 883–887, doi:10.1038/414883a.
- Braunstein, S. L.; Caves, C. M.; Jozsa, R.; Linden, N.; Popescu, S.; Schack, R., , Phys. Rev. Lett, 1999, 83 (5): 1054–1057, doi:10.1103/PhysRevLett.83.1054
- Lu, Chao-Yang; Browne, Daniel E.; Yang, Tao & Pan, Jian-Wei, , Physical Review Letters, 2007, 99 (25): 250504, doi:10.1103/PhysRevLett.99.250504
- Lanyon, B. P.; Weinhold, T. J.; Langford, N. K.; Barbieri, M.; James, D. F. V.; Gilchrist, A. & White, A. G., , Physical Review Letters, 2007, 99 (25): 250505, doi:10.1103/PhysRevLett.99.250505
- Shor 1999,第14页.
延伸閱讀
- Nielsen, Michael A. & Chuang, Isaac L., , Cambridge University Press, 2000.
- Phillip Kaye, Raymond Laflamme, Michele Mosca, An introduction to quantum computing, Oxford University Press, 2007, ISBN 019857049X
- "Explanation for the man in the street" by Scott Aaronson, "approved" by Peter Shor. (Shor wrote "Great article, Scott! That’s the best job of explaining quantum computing to the man on the street that I’ve seen."). Scott Aaronson suggests the following 12 references as further reading (out of "the 10105000 quantum algorithm tutorials that are already on the web."):
- Shor, Peter W., , SIAM J.Sci.Statist.Comput., 1999, 41 (2): 303–332, doi:10.1137/S0036144598347011, arXiv:quant-ph/9508027v2. Revised version of the original paper by Peter Shor ("28 pages, LaTeX. This is an expanded version of a paper that appeared in the Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, Nov. 20--22, 1994. Minor revisions made January, 1996").
- Quantum Computing and Shor's Algorithm, Matthew Hayward, 2005-02-17, imsa.edu, LaTeX2HTML version of the original 2750 line LaTeX document, also available as a 61 page PDF or postscript document.
- Quantum Computation and Shor's Factoring Algorithm, Ronald de Wolf, CWI and University of Amsterdam, January 12, 1999, 9 page postscript document.
- Shor's Factoring Algorithm, Notes from Lecture 9 of Berkeley CS 294-2, dated 4 Oct 2004, 7 page postscript document.
- Chapter 6 Quantum Computation, 91 page postscript document, Caltech, Preskill, PH229.
- Quantum computation: a tutorial by Samuel L. Braunstein.
- The Quantum States of Shor's Algorithm, by Neal Young, Last modified: Tue May 21 11:47:38 1996.
- A now-circular reference via the Wikipedia copy of this article; clearly Aaronson's link originally reached the 20 Feb 2007 version.
- III. Breaking RSA Encryption with a Quantum Computer: Shor's Factoring Algorithm (页面存档备份,存于), LECTURE NOTES ON QUANTUM COMPUTATION, Cornell University, Physics 481-681, CS 483; Spring, 2006 by N. David Mermin. Last revised 2006-03-28, 30 page PDF document.
- arXiv quant-ph/0303175 Shor's Algorithm for Factoring Large Integers. C. Lavor, L.R.U. Manssur, R. Portugal. Submitted on 29 Mar 2003. This work is a tutorial on Shor's factoring algorithm by means of a worked out example. Some basic concepts of Quantum Mechanics and quantum circuits are reviewed. It is intended for non-specialists which have basic knowledge on undergraduate Linear Algebra. 25 pages, 14 figures, introductory review.
- arXiv quant-ph/0010034 Shor's Quantum Factoring Algorithm, Samuel J. Lomonaco, Jr, Submitted on 9 Oct 2000, This paper is a written version of a one hour lecture given on Peter Shor's quantum factoring algorithm. 22 pages.
- Chapter 20 Quantum Computation, from Computational Complexity: A Modern Approach, Draft of a book: Dated January 2007, Comments welcome!, Sanjeev Arora and Boaz Barak, Princeton University.
本文来源:维基百科:秀爾演算法
本篇内容的全部文字在知识共享 署名-相同方式共享 3.0协议之条款下提供,附加条款亦可能应用。(请参阅使用条款)