鑽石舞台

一個量子可以同時處於兩種狀態的疊加（比如自旋向上和自旋向下），這種疊加態測量的瞬間就會隨機變為一個確定的態（測量得到自旋向上），這個過程叫波函數的坍塌。我們如果將這兩個態表示為0,1，而每種態觀測後出現的概率幅(注意不是概率，概率幅的平方為概率)為,那麼這個量子可以表示為：

這裡叫狄拉克符號，表示量子態，為基態，+表示疊加，兩種態的概率幅平方和為1，即。而我們通常說的量子計算就是通過量子邏輯門來操作處於疊加態的量子。比如Hadamard門，簡稱H門（在量子計算中非常重要），他的一個主要功能就是通過計算基態產生等概率的疊加態。通過H門變換後的單量子疊加態為：

兩種基態的坍塌概率都為 ，兩個量子的H門得到的結果如下：

每個態坍塌的概率 ，對於n個量子的H門變換後：

其他量子門這裡就不做介紹了，本文暫時不會涉及，想更深入了解可以到維基上看。

https://en.wikipedia.org/wiki/Quantum_logic_gate

量子門及其對應的門矩陣如下圖：

還有一個比較重要的複合門是受控U(a,x)門，想深入了解的看這篇文章：一隻冰牙喵：4.2 受控操作。

不過這裡看不懂沒關係，我們只需要知道受控U門可以用於計算以a為基底的冪，其一般用於生成指數函數值。

量子並行運算（Quantum Parallelism）是基於量子疊加態（Quantum Superposition）和幺正變換實現的。量子計算正是有了數據的可疊加性和幺正變換，從而決定了一次操作即可改變全部數據。比如有量子寄存器，存了10個處於疊加態的量子，在通過運算時只需要一次性操作這10個量子，但是由於可疊加性，這10個量子疊加態可以表示2^10個基矢，一次操作10個量子，相當於一次對2^10個基矢進行了操作，這就大大提高了運算的速度。

在經典計算中，並行性的核心思想是將一個計算任務分配給多個處理器同時運行，要快於使用一個處理器來運行。在理想的情況下，將工作分配給K 個處理器就應該使計算時間縮短為原來的1/K。但是現實肯定不是這樣的，真實的任務往往具有串聯性，只有部分具有並聯性的子任務才能夠做並行運算。由於量子計算的特點是數據的可疊加性質和操作的幺正變換本質，從而就決定了量子計算的語義特徵是完全意義上的通過一次操作即可改變全部數據的並行計算。將一個N 位量子寄存器中的 個數據同時通過一次幺正變換（即進行一次運算）所需的時間定義為 ，而經典計算中對一個數據進行運算的時間為 ，因為一次量子計算就對所有的數據做了並行處理，所以量子計算加速能力可以表示為

如果 ,那麼加速能力 ,也就是說對量子計算機做一次運算，相當於對經典計算機做 次運算。

量子計算機是嚴重依賴於優秀的量子算法的實現，雖然通用量子計算機能做經典計算機的所有事情，但是只有在處理特定問題上量子計算才具有決定性的優勢，目前已經有很多優秀的量子算法，其中對大數因子分解，離散對數問題以及更一般的隱含子群問題的解決有着開創性和重大影響的量子算法便是本文要詳細分析的Shor算法。

本文將非常詳細的分析Shor算法來讓各位明白量子計算在解決特定問題上的巨大優勢。

二、Shor算法分析

在費曼提出量子計算機概念不到15年的時間，shor通過研究出的量子算法給世人了一劑強心針，自從shor算法出來後，人類開始加速了量子計算機的研製，各大頭部企業也紛紛加入了量子計算機的量子競賽行列。

shor算法最令人振奮的是直接將質因子分解以及離散對數問題以指數級速度提升，這給人們的啟示是可以利用同樣算法思想來解決更為廣泛的隱含子群問題。

我們知道RSA是基於經典計算機大數質因式分解的指數複雜度的困難而設計的一種非對稱加密算法，目前最優的因子分解算法為指數複雜度 。而通過shor量子算法可以以多項式複雜度完成大數因式分解，從而可以快速破解RSA算法。那麼Shor算法是如何發揮如此威力的，簡單來說，Shor算法的核心依賴於三個變換即H變換,U變換,QFT(量子傅立葉)，接下來我們一步一步的分析。

Shor算法量子實現線路簡圖：

我們設RSA的公鑰為 (e,N) ，私鑰為 (d,N) ,那麼生成公私鑰的過程如下：

首先我們需要將大數因子分解問題轉化為以求待分解的合數N為模的函數 的周期問題。

設周期函數 的周期為r（這裡a為小於N，且與N互質的整數），則有：f(x)=f(x+r) , 那麼：

設整數 ，則

例如：設 N=15，a=7 ,則：

設量子比特長度為 L, 則總共可以表示的 個基態, 設N為要分解的合數，為了確保 長度內有足夠的周期數，我們需要滿足

兩個寄存器展開形式如下：

由於 f(x) 為周期函數，設周期為r，A為總長中存在的周期數，則

設l為小於一個周期內的x的值, x=l+Ar, 則整個系統的態實際為：

因此，x可以表示為

然後對reg2進行計算基上的測量，設測量結果設為 Z ，測量Z在reg1中的投影變化為：

參考文章：

Shor, P.W. (1994). "Algorithms for quantum computation: discrete logarithms and factoring". Proceedings 35th Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc. Press: 124–134

https://authors.library.caltech.edu/2179/1/BECpra96.pdf

https://en.wikipedia.org/wiki/Quantum_logic_gate

https://en.wikipedia.org/wiki/Shor%27s_algorithm

https://en.wikipedia.org/wiki/Discrete_logarithm

https://zhuanlan.zhihu.com/p/106923175