Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Shor, P.W.: Algorithms for Quantum Computation: Discrete Logarithms and Factoring, Proc.35th Annual Symp.on Foundations of Computer Science, pp.124-134 (1994).

孝志 三原

Published Sep 1, 1996• 0 citations
OpenAlex

Related papers

Quantum Factoring, Discrete Logarithms, and the Hidden Subgroup Problem

JozsaRichard

Among the most remarkable successes of quantum computation are Shor's efficient quantum algorithms for the computational tasks of integer factorization and the evaluation of discrete logarithms. In...

IEEE Multimedia•Mar 1, 1996•0 citations

Quantum Computing and the Hunt for Hidden Symmetry.

Gorjan Alagic, Alexander C. Russell

In 1994, Peter Shor gave e cient quantum algorithms for factoring integers and extracting discrete logarithms [20]. If we believe that nature will permit us to faithfully implement our current model of quantum computation, then these algorithms dramatically contradict the Strong Church-Turing thesis. 1

Bulletin of the European Association for Theoretical Computer Science•Jan 1, 2007•1 citation

Shor's discrete logarithm quantum algorithm for elliptic curves

ProosJohn, ZalkaChristof

We show in some detail how to implement Shor's efficient quantum algorithm for discrete logarithms for the particular case of elliptic curve groups. It turns out that for this problem a smaller qua...

Quantum Information and Computation•Jul 1, 2003•26 citations

Strengths and Weaknesses of Quantum Computing

Charles H. Bennett, Ethan Bernstein, Gilles Brassard A +1 more

Recently a great deal of attention has been focused on quantum computation following a sequence of results [Bernstein and Vazirani, in Proc. 25th Annual ACM Symposium Theory Comput., 1993, pp. 11--20, SIAM J. Comput., 26 (1997), pp. 1277--1339], [Simon, in Proc. 35th Annual IEEE Symposium Foundations Comput. Sci., 1994, pp. 116--123, SIAM J. Comput., 26 (1997), pp. 1340--1349], [Shor, in Proc. 35th Annual IEEE Symposium Foundations Comput. Sci., 1994, pp. 124--134] suggesting that quantum computers are more powerful than classical probabilistic computers. Following Shor's result that factoring and the extraction of discrete logarithms are both solvable in quantum polynomial time, it is natural to ask whether all of $\NP$ can be efficiently solved in quantum polynomial time. In this paper, we address this question by proving that relative to an oracle chosen uniformly at random with probability 1 the class $\NP$ cannot be solved on a quantum Turing machine (QTM) in time $o(2^{n/2})$. We also show that relative to a permutation oracle chosen uniformly at random with probability 1 the class $\NP \cap \coNP$ cannot be solved on a QTM in time $o(2^{n/3})$. The former bound is tight since recent work of Grover [in {\it Proc.\ $28$th Annual ACM Symposium Theory Comput.}, 1996] shows how to accept the class $\NP$ relative to any oracle on a quantum computer in time $O(2^{n/2})$.

arXiv:quant-ph/9701001•SIAM Journal on Computing•Oct 1, 1997•1,470 citations

Algorithms for quantum computation: Discrete log and factoring

Peter W. Shor

•Jan 1, 1994•273 citations

Two-boson Hamiltonian for Shor's algorithm

Mario Rasetti, Elena Tagliati, Riccardo Zecchina

A two-boson Hamiltonian is constructed whose induced unitary evolution implements in the corresponding Fock space the algorithm devised by Shor [Algorithms for Quantum Computation: Discrete Logarithms and Factoring, in Proceedings of the 35th Annual Symposium on Foundation of Computer Science, edited by S. Goldwasser (IEEE Computer Society Press, Los Alamitos, CA, 1994), p. 124] to factorize an integer into prime factors.

Physical Review A•Apr 1, 1997•8 citations
Recently a great deal of attention has been focused on quantum computation following a sequence of results [Bernstein and Vazirani, in Proc. 25th Annual ACM Symposium Theory Comput., 1993, pp. 11--20, SIAM J. Comput., 26 (1997), pp. 1277--1339], [Simon, in Proc. 35th Annual IEEE Symposium Foundations Comput. Sci., 1994, pp. 116--123, SIAM J. Comput., 26 (1997), pp. 1340--1349], [Shor, in Proc. 35th Annual IEEE Symposium Foundations Comput. Sci., 1994, pp. 124--134] suggesting that quantum computers are more powerful than classical probabilistic computers. Following Shor's result that factoring and the extraction of discrete logarithms are both solvable in quantum polynomial time, it is natural to ask whether all of $\NP$ can be efficiently solved in quantum polynomial time. In this paper, we address this question by proving that relative to an oracle chosen uniformly at random with probability 1 the class $\NP$ cannot be solved on a quantum Turing machine (QTM) in time o(2n/2)o(2^{n/2})o(2n/2). We also show that relative to a permutation oracle chosen uniformly at random with probability 1 the class $\NP \cap \coNP$ cannot be solved on a QTM in time o(2n/3)o(2^{n/3})o(2n/3). The former bound is tight since recent work of Grover [in {\it Proc.\ 282828th Annual ACM Symposium Theory Comput.}, 1996] shows how to accept the class $\NP$ relative to any oracle on a quantum computer in time O(2n/2)O(2^{n/2})O(2n/2).