Toward Classical Algorithms Competing with Shor's Quantum Factorization (IEEE)

Rafael Pereira da Silva

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.

Manisha J. Nene, Gaurav K. Upadhyay

Mikio Nakahara

Shor’s factorization algorithm is one of the prime examples in which a quantum computer demonstrates enormous power surpassing its classical counterpart [1, 2]. Although the factorization algorithm may be carried out with a classical computer, it takes an exponentially longer time (i.e., practically impossible) compared to Shor’s quantum algorithm. Shor’s algorithm is almost identical with the classical one; it consists of a sequence of classical steps with one exception, which is replaced by a quantum algorithm. Our presentation here closely follows [3] and [4].

Xiang-Qun Fu, Wan‐Su Bao, Chun Hua Zhou

David Beckman, Amalavoyal N. Chari, Devabhaktuni Srikrishna +1 more

We consider how to optimize memory use and computation time in operating a quantum computer. In particular, we estimate the number of memory quantum bits (qubits) and the number of operations required to perform factorization, using the algorithm suggested by Shor [in Proceedings of the 35th Annual Symposium on Foundations of Computer Science, edited by S. Goldwasser (IEEE Computer Society, Los Alamitos, CA, 1994), p. 124]. A K-bit number can be factored in time of order ${\mathit{K}}^{3}$ using a machine capable of storing 5K+1 qubits. Evaluation of the modular exponential function (the bottleneck of Shor's algorithm) could be achieved with about 72${\mathit{K}}^{3}$ elementary quantum gates; implementation using a linear ion trap would require about 396${\mathit{K}}^{3}$ laser pulses. A proof-of-principle demonstration of quantum factoring (factorization of 15) could be performed with only 6 trapped ions and 38 laser pulses. Though the ion trap may never be a useful computer, it will be a powerful device for exploring experimentally the properties of entangled quantum states. \textcopyright{} 1996 The American Physical Society.