Prime-Numbers
通俗地說，Shor 的算法是如何工作的？
我剛剛閱讀了Shor 的算法，我發現它既迷人又令人費解。我不太了解它，除了它可以在多項式時間內分解半素數。
有人可以用外行的術語解釋它是如何工作的，以及為什麼它依賴於量子計算嗎？
請記住，雖然我了解量子計算的基礎知識（即，它使用光子而不是電子，並且比特被替換為可以是 0、1 或兩者疊加的量子比特），但我並不深入了解它。我知道與經典電腦制相比，它應該是超快的。
要回答的問題是“N 是 P*Q 的乘積嗎？” 我相信理解 Shor 最簡單的方法是想像兩個正弦波，一個長度為 P，一個長度為 Q。假設 P 和 Q 互質，那麼上面的問題也可以回答“ P 與 Q 重複？” 並且可以根據簡單的觀察快速確定答案，即我們可以計算出每個波在數軸上任何給定點的相位。（請記住，相位是“這一點沿圖案有多遠？”通常以度為單位；90 度 = 1/4 旋轉）
如果我們看點 N，那麼如果 P 和 Q 是 N 的因數，則它們的相位必須為 0（否則將有除法 N/Q 或 N/P 的餘數）。Shor 只是在 N 點測試 P 的相位是否 == Q 的相位 == 0。事實證明，相位估計對於量子電腦來說非常容易，因此它是建構因式分解機的好工具。有關更多資訊，請參閱http://www.wikipedia.org/wiki/Quantum_phase_estimation_algorithm。