Abstract

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 K3 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 72K3 elementary quantum gates; implementation using a linear ion trap would require about 396K3 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.

Keywords

Quantum computerFactoringQubitComputer scienceTrapped ion quantum computerBottleneckQuantumFactorizationQuantum mechanicsDiscrete mathematicsPhysicsArithmeticAlgorithmQuantum error correctionMathematicsEmbedded system

Affiliated Institutions

Related Publications

The semiclassical theory of laser cooling

Stig Stenholm

This paper reviews the basic theory of the mechanical action of light in resonant interaction with atoms. At present the main application is laser cooling, but the approach is a...

1986 Reviews of Modern Physics 606 citations

Publication Info

Year
1996
Type
article
Volume
54
Issue
2
Pages
1034-1063
Citations
250
Access
Closed

External Links

Download PDF (Free) View on DOI.org arXiv PubMed Semantic Scholar

Social Impact

Altmetric
PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

250
OpenAlex
15
Influential
172
CrossRef

Cite This

David Beckman, Amalavoyal N. Chari, Devabhaktuni Srikrishna et al. (1996). Efficient networks for quantum factoring. Physical Review A , 54 (2) , 1034-1063. https://doi.org/10.1103/physreva.54.1034

Identifiers

DOI
10.1103/physreva.54.1034
PMID
9913575
arXiv
quant-ph/9602016

Data Quality

Data completeness: 84%