FACTORING IN A DISSIPATIVE QUANTUM COMPUTER

We describe an array of quantum gates implementing Shor's algorithm [i n Proceedings of the 35th Annual Symposium on Foundations of Computer Science, edited by S. Goldwasser (IEEE Computer Society, Los Alamitos, CA, 1994), p. 116; (unpublished); Phys. Rev. A 53, R2493 (1995)] for prime factorization in a quantum computer. The array includes a circui t for modular exponentiation with several subcomponents (such as contr olled multipliers and adders) that are described in terms of elementar y Toffoli gates. We present a simple analysis of the impact of losses and decoherence on the performance of this quantum factoring circuit. For that purpose, we simulate a quantum computer that is running the p rogram to factor N=15 while interacting with a dissipative environment . As a consequence of this interaction, randomly selected quantum bits (qubits) may spontaneously decay. Using the results of our numerical simulations, we analyze the efficiency of some simple error correction techniques.