Shor（一）：Shor's Algorithm

Shor（一）：Shor's Algorithm

2021/09/15

前言：

「秀爾演算法是一個 1994 年發表，以數學家彼得·秀爾為名，針對整數分解題目的的量子演算法。」[2], [7]。「利用受控旋轉閘和哈達瑪閘，秀爾設計了一個量子傅立葉變換的線路。」 [3], [7]。

-----

簡介：

一、Shor's Algorithm

二、Tutorial

--

核心演算法：

三、Fourier Transform

四、Qubit

五、Quantum Fourier Transform

--

基礎數學：

六、Bertrand Postulate

七、Euler's Theorem for Shor's Algorithm

八、Euler's Formula for Fourier Transform

-----

https://pixabay.com/zh/photos/skyscrapers-singapore-city-sky-3184798/

-----

References

[1] QC — Cracking RSA with Shor’s Algorithm | by Jonathan Hui | Medium

https://jonathan-hui.medium.com/qc-cracking-rsa-with-shors-algorithm-bc22cb7b7767

◎ 論文

# 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.

https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=365700&casa_token=wyvp59c0kScAAAAA:WmAXK1q7Iw0hifdUGbdZZvGYfTnmZrR5TTkozakX6wglrra-hbvTXrQgZ7plGchqslpfnT2r

# 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.

https://epubs.siam.org/doi/pdf/10.1137/S0036144598347011?casa_token=egnx6GgIuKkAAAAA:vKQVQcJVnL75Ir1DPfD2B8LLLBUfBFd_C9WZYLGBHK_qSw7u8ioYh_CdYFPdmBNTUERCRYdc_NA

# QFT

[4] Ruiz-Perez, Lidia, and Juan Carlos Garcia-Escartin. "Quantum arithmetic with the quantum Fourier transform." Quantum Information Processing 16.6 (2017): 152.

https://arxiv.org/pdf/1411.5949.pdf

# Quantum Cryptography

[5] Gisin, Nicolas, et al. "Quantum cryptography." Reviews of modern physics 74.1 (2002): 145.

https://journals.aps.org/rmp/pdf/10.1103/RevModPhys.74.145?casa_token=M-D90g5EaiMAAAAA%3ADH23AXFCm_ccYhdJAU_eliouVXZ0ouNsACV6aFR7JCy35fEZKEPeXk7D4gIjTX-P2aNqjayLdaByZA

◎ 英文

[6] Shor's algorithm - Wikipedia

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

◎ 中文

[7] 秀爾演算法 - 維基百科，自由的百科全書

https://zh.wikipedia.org/wiki/%E7%A7%80%E7%88%BE%E6%BC%94%E7%AE%97%E6%B3%95

[8] Shor’s Algorithm. 量子計算初學者的理解 | by Howard Peng | Jul, 2021 | Medium

https://howardpeng911.medium.com/shor-algorithm-2c1abca22da2

◎ 實作

# C/C++

[9] 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

# Qiskit

[10] Shor's Algorithm

https://qiskit.org/textbook/ch-algorithms/shor.html

# Cirq

[11] Shor's algorithm  |  Cirq  |  Google Quantum AI

https://quantumai.google/cirq/tutorials/shor

◎ 影片

[12] How Quantum Computers Break Encryption | Shor's Algorithm Explained - YouTube

https://www.youtube.com/watch?v=lvTqbM5Dq4Q

[13] (43) 7. Shor's Algorithm I: Understanding Quantum Fourier Transform, Quantum Phase Estimation - Part 1 - YouTube

https://www.youtube.com/watch?v=mAHC1dWKNYE&list=RDCMUClBNq7mCMf5xm8baE_VMl3A&index=1

-----