【論文筆記】Shor 1994

【論文筆記】Shor 1994

2021/10/11

-----

https://pixabay.com/zh/photos/tree-snow-winter-landscape-1056598/

-----

標題：Algorithms for Quantum Computation: Discrete Logarithms and Factoring

說明：有兩個演算法，Discrete Logarithms 與 Factoring Integers（factoring integers 在摘要中會出現）。2021/10/11。

-----

摘要：

David Deutsch：提出 Quantum Turing Machine。2021/10/11。

Las Vegas algorithms：永遠給出正確解的隨機算法（給出正確解或失敗）。2021/10/11。

-----

介紹：

Feynman：「1982 Simulating physics with computers [13]」、「1985 Quantum mechanical computers [14]」。2011/10/11。

Benioff：「1982 Quantum mechanical Hamiltonian models of Turing machines [1]」、「1982 Quantum mechanical Hamiltonian models of Turing machines that dissipate no energy [2]」。2011/10/11。

Deutsch：「1989 Quantum computational networks [9]」、「1992 Rapid solution of problems by quantum computation [10]」。

P：指的是在多項式時間內有解的問題。

PSPACE：指的是在多項式空間內有解的問題。「There are also other computational complexity classes discussed in this paper. One of these is PSPACE, which are those problems which can be solved with an amount of memory polynomial in the input size.」本文還討論了其他計算複雜度類。 其中之一是 PSPACE，這些問題可以通過多項式空間的內存來解決。2021/10/20。

NP：

BPP：

P^(#P)：

BQP：

-----

n ≦ q < 2n

2021/11/01

「Lemma 3.2 Given n, there is a polynomial-time algorithm to find a number q with n ≦ q < 2n such that no prime power larger than c log q divides q, for some constant c independent of n.」

「There is always a prime between m and 2m [17, Theorem 418].」

「[17] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth Edition, Oxford University Press, New York (1979).」。# Shor 1994。

-----

求證 n > 2,（n, 2n）區間必有一個質數。

2021/11/01

「伯特蘭-切比雪夫定理。另一個稍弱說法是：對於所有大於 1 的整數 n，存在一個質數 p，符合 n < p < 2n。1845 年約瑟·伯特蘭提出這個猜想。伯特蘭檢查了 2 至 3×10^6 之間的所有數。1850 年切比雪夫證明了這個猜想。拉馬努金給出較簡單的證明，而保羅·艾狄胥則藉二項式係數給出了另一個簡單的證明。」。

https://zhidao.baidu.com/question/296484699.html

https://zh.wikipedia.org/wiki/%E4%BC%AF%E7%89%B9%E8%98%AD-%E5%88%87%E6%AF%94%E9%9B%AA%E5%A4%AB%E5%AE%9A%E7%90%86

-----

References

◎ 論文

# Shor's Algorithm

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

-----