【論文筆記】Shor's Algorithm
2021/10/21
步驟五公式說明：
暫存器 1 的值為 a，暫存器 2 的值為 0。
-----
https://pixabay.com/zh/photos/canyon-red-sand-stone-enge-2405833/
-----
一、Shor's Algorithm
-----
Steps to Shor's Algorithm [1]。
Shor's algorithm for factoring a given integer n can be broken into some simple steps.
用於分解給定整數 n 的 Shor 算法可以拆成幾個簡單的步驟。
「1. Determine if the number n is a prime, a even number, or an integer power of a prime number. If it is we will not use Shor's algorithm. There are ecient classical methods for determining if a integer n belongs to one of the above groups, and providing factors for it if it does. This step would be performed on a classical computer.」
一、確定數 n 是否是質數、偶數還是質數的整數次冪。 如果是，我們將不會使用 Shor 算法。 有一些有效的經典方法可以確定整數 n 是否屬於上述組之一，如果屬於，則為其提供因子。 此步驟將在經典計算機上執行。
「2. Pick a integer q that is the power of 2 such that n^2 ≦ q ≦ 2n^2. This step would be done on a classical computer.」
二、選擇一個整數 q，它是 2 的冪，使得 n^2 ≦ q ≦ 2n^2。 這一步將在經典計算機上完成。
「3. Pick a random integer x that is coprime to n. When two numbers are coprime it means that their greatest common divisor is 1. There are efficient classical methods for picking such an x. This step would be done on a classical computer.」
三、選擇一個與 n 互質的隨機整數 x。 當兩個數互質時，這意味著它們的最大公約數是 1。有一些有效的經典方法可以選擇這樣的 x。 這一步將在經典計算機上完成。
「4. Create a quantum register and partition it into two sets, register one and register two. Thus the state of our quantum computer can be given by: left | reg1, reg2 >. Register one must have enough qubits to represent integers as large as q - 1. Register two must have enough qubits to represent integers as large as n - 1.」
四、創建一個量子暫存器並將其劃分為兩組，暫存器一組和暫存器二。 因此，我們的量子計算機的狀態可以由下式給出： left | reg1, reg2 >。 暫存器一必須有足夠的量子位來表示大到 q - 1 的整數。暫存器二必須有足夠的量子位來表示大到 n - 1 的整數。
「5. Load register one with an equally weighted superposition of all integers from 0 to q - 1. Load register two with the 0 state. This operation would be performed by our quantum computer. The total state of the quantum memory register at this point is:」
五、用從 0 到 q - 1 的所有整數的等權疊加加載暫存器 1。用 0 狀態加載占存器 2。 這個操作將由我們的量子計算機執行。 此時量子存儲器佔存器的總狀態為：
「6. Apply the transformation x^a mod n to for each number stored in register one and store the result in register two. Due to quantum parallelism this will take only one step, as the quantum computer will only calculate x^|a> mod n, where |a> is the superposition of states created in step 5. This step is performed on the quantum computer. The state of the quantum memory register at this point is:」
六、對存儲在暫存器 1 中的每個數字應用 x^a mod n 變換，並將結果存儲在暫存器 2 中。 由於量子並行，這將只需要一步，因為量子計算機將只計算 x^|a> mod n，其中 |a> 是在步驟 5 中創建的狀態的疊加。此步驟在量子計算機上執行。 此時量子存儲器暫存器的狀態為：
「7. Measure the second register, and observe some value k. This has the side effect of collapsing register one into a equal superposition of each value a between 0 and q - 1 such that」
七、測量第二個暫存器，並觀察某個值 k。 這具有將暫存器 1 折疊成 0 和 q - 1 之間每個值 a 的相等疊加的副作用，使得
「This operation is performed by the quantum computer. The state of the quantum memory register after this step is:」
該操作由量子計算機執行。 這一步後量子存儲器暫存器的狀態為：
「Where A is the set of a's such that x^a mod n = k, and ||A|| is the number of elements in that set.」
其中 A 是 a 的集合，使得 x^a mod n = k，並且 ||A|| 是該集合中的元素數。
「8. Compute the discrete Fourier transform on register one. The discrete Fourier transform when applied to a state |a> changes it in the following manner:」
八、計算暫存器 1 上的離散傅立葉變換。 應用於狀態 |a> 的離散傅立葉變換以下列方式改變它：
「This step is performed by the quantum computer in one step through quantum parallelism. After the discrete Fourier transform our register is in the state:」
這一步是由量子計算機通過量子並行一步一步完成的。 在離散傅立葉變換之後，我們的暫存器處於以下狀態：
「9. Measure the state of register one, call this value m, this integer m has a very high probability of being a multiple of q/r, where r is the desired period. This step is performed by the quantum computer.」
九、測量暫存器 1 的狀態，稱這個值 m，這個整數 m 很有可能是 q/r 的倍數，其中 r 是想要的周期。 這一步由量子計算機執行。
「10. Take the value m, and on a classical computer do some post processing which calculates r based on knowledge of m and q. There are many ways to do this post processing, they are complex are are omitted for clarity in presentation of the quantum core of Shor's Algorithm. This post processing is done on a classical computer.」
10. 取值 m，並在經典計算機上進行一些後處理，根據 m 和 q 的知識計算 r。 有很多方法可以進行這種後處理，它們很複雜，為了清晰展示 Shor 算法的量子核心，在此省略了它們。 此後處理是在經典計算機上完成的。
「11. Once you have attained r, a factor of n can be determined by taking gcd(x^(r/2)+1, n) and gcd(x^(r/2)-1, n). If you have found a factor of n, then stop, if not go to step 4. This final step is done on a classical computer.」
11. 一旦你達到了 r，n 的因子可以通過 gcd(x^(r/2)+1, n) 和 gcd(x^(r/2)-1, n) 確定。 如果你找到了 n 的因數，則停止，否則轉到步驟 4。這最後一步是在經典計算機上完成的。
Step 11 contains a provision for Shor's algorithm failing to produce the factors of n. Shor's algorithm can fail for multiple reasons, for example the discrete Fourier transform could be measured to be 0 in step 9, making the post processing in step 10 impossible. At other times the algorithm will sometimes find factors of 1 and n, which is correct but not useful. (Williams, Clearwater)
步驟 11 包含對 Shor 算法無法產生 n 因子的規定。 Shor 的算法可能由於多種原因而失敗，例如，離散傅立葉變換在步驟 9 中可能被測量為 0，使得步驟 10 中的後處理無法進行。 在其他時候，算法有時會找到 1 和 n 的因子，這是正確的但沒有用。 （威廉姆斯，克利爾沃特）
-----
References
# Shor’s algorithm
[1] Hayward, Matthew. "Quantum computing and shor’s algorithm." Sydney: Macquarie University Mathematics Department (2008).
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.1509&rep=rep1&type=pdf
# Shor 1994
[2] Shor, Peter W. "Algorithms for quantum computation: discrete logarithms and factoring." Proceedings 35th annual symposium on foundations of computer science. Ieee, 1994.
# Shor 1999
[3] Shor, Peter W. "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer." SIAM review 41.2 (1999): 303-332.
-----
No comments:
Post a Comment