# shor演算法與競賽
本周:https://www.youtube.com/watch?v=GITg_-saEeQ
## 1.需要用到多少qubit?
第一暫存器(register)與第二暫存器大約1:2(60個qubit約可以處理$2^{20}$次方的數據)
## 2.如何做shor演算法
### 步驟說明
此例使用3個ancilla qubit(圖D中上方的三種)先做2的1次方mod15(右)，接著是2的2次方mod15(中)，最後2的4次方mod15(左)，在此例中，先將2帶入最右邊的a(N為15)，我們知道2除以15餘數為2
，故輸出應為0010(先後順序為$q_3$到$q_0$)，由於初始狀態為0001，在執行圖E最左邊的SWAP電路後，位元狀態變為0010。接著檢查中間的電路，將2帶入$a^2$mod中，其餘數應為四，執行圖D中間電路，初始狀態在經過兩個X閘之後從
0001變為0100(十進位的4)，4次方亦然，以次類推。
#### 註:
判斷不同數值會有不同的對應電路需由我們自行設計

若只設計1個ancilla qubit會發生甚麼呢?如圖B，在這種情況下，我們需要考慮從$a^1$到$a^k$次方，且每次都要測量(measurement)，因此需要做$2^n$次。
以前述$5^n$mod21為例(左上方圖)，當每次做一個運算子(operater)之後，他會隨著某一個面做旋轉(rotation)，當轉回1時就能知道答案，那為甚麼shor演算法可以拆倒是因為他只要知道狀態(phase)旋轉的週期，而不是轉了幾次。