EFFICIENT NETWORKS FOR QUANTUM FACTORING

We consider how to optimize memory use and computation time in operati ng a quantum computer. In particular, we estimate the number of memory quantum bits (qubits) and the number of operations required to perfor m factorization, using the algorithm suggested by Shot [in Proceedings of the 35th Annual Symposium on Foundations of Computer Science, edit ed by S. Goldwasser (IEEE Computer Society, Los Alamitos, CA, 1994), p . 124]. A K-bit number can be factored in time of order K-3 using a ma chine capable of storing 5K+1 qubits. Evaluation of the modular expone ntial function (the bottleneck of Shor's algorithm) could be achieved with about 72K(3) elementary quantum gates; implementation using a lin ear ion trap would require about 396K(3) laser pulses. A proof-of-prin ciple demonstration of quantum factoring (factorization of 15) could b e performed with only 6 trapped ions and 38 laser pulses. Though the i on trap may never be a useful computer, it will be a powerful device f or exploring experimentally the properties of entangled quantum states .