Research Update: December '96 - September '97

Research Update: November '97 - June '98

Overview:

Inspired by the possible realization in optical physics, we have designed the first explicit quantum circuits for implementing Shor’s factorization algorithm [e,f]. We have also developed computer-aided tools to help design efficient quantum circuit modules. This work takes an important step toward bridging the gap between abstract quantum algorithms and actual physical implementations by quantifying the scaling behavior of certain quantum circuits and by clarifying the inevitable trade-off between computation speed and storage capacity.

Basic quantum gates are used to build the network to implement Shor’s factorization algorithm allowing us to simulate at multiple levels of abstraction. Simulating at the gate level allows us to study larger networks. It can be shown that all quantum networks can be constructed from a 2 bit controlled-not gate and a rotate gate, but we define additional instructions for sake of efficiency. The following is a list of the quantum instructions which are used. These instructions are either defined as individual gates or as combinations of elemental gates.

clear(J) - clear the quantum bit J.

set(J) - set the QUBIT J to 1.

x(I,J) - 2 bit Controlled not. Exclusive-Or of bits I and J.

x(I,K,J) - 3 bit Controlled-Controlled-Not gate.

r(angle,J) - rotate J by the given angle.

b(J) - butterfly operation on bit J. Used in the QDFT function of the factorization algorithm.

t(J,K) - twiddle between bits J and K. Used in the QDFT function of the factorization algorithm.

measure(K) - perform a quantum measurement of bit K.

From these instructions we build the larger circuits to implement Shor’s factorization algorithm. The calculation of the function f(a) = X^a mod N comprises the majority of the calculation in the algorithm. The computation takes approximately 80L³ operations (where X and N are L-bit numbers and a is a 2L-bit number). For factoring the number 15, L=4 and the computation requires about 4,000 operations. To maintain the quantum wave function we must maintain the superposition of all possible up/down states for M bits. To simulate a quantum computer, we must explicitly represent all 2^M possible complex amplitudes that correspond to the M QUBITS. Therefore the simulation requires storage for 2^M complex numbers to represent the amplitude and phase of each state. For the Shor experiment, M=23 for which we will potentially perform an update on each of the 2²³ complex numbers for each of the 4,000 operations. Each operation is defined by a unitary matrix transformation. A full matrix multiplication would require 2²³x2²³ elementary operations per step. However these matrices are sparse because they each operate on a limited set of bits, and therefore it is advantageous to perform the operation of a gate directly on the state space. For example, a controlled-not gate, x(I,J) causes the bit J to flip based on the value of the bit I. In the state space representation this corresponds to swapping the amplitude and phase values of the two states identified by bit J which have bit I=1. We define similar operations for the other gates.

The architecture of a quantum computer is comprised of a quantum system connected to and controlled by a classical computer. The classical computer generates the operations to be performed on the quantum bits and receives the measurements of the QUBITS which are then used in further computation. The network which is used in the quantum system for the factorization problem is as follows:

After clearing all the bits we calculate F(A) on the superposition of all values of A. We then perform a measurement of F(A) to fix a particular value of F(A), causing the register of A to contain the superposition of only those values which lead to the measured F(A) (Actually, we include the measurement of F(A) only for pedagogical reasons; it is not really necessary). The DFFT is then performed on A to obtain (R), the rank of the function.

We propose building a simulator that will simulate a quantum computer at the instruction level. The simulator will represent the quantum registers as a state space vector as described above. The simulator will implement each of the instructions described previously, and networks are built as combinations of these instructions. These networks will be built up in a hierarchical fashion with basic modules, such as addition and subtraction being constructed out of the basic instructions. These modules can be combined until we have implemented the F(A) operation in the Shor factorization problem. Building the circuit in this manner allows us to reuse functionality and isolate portions of the circuit for possible optimizations.

Simulating at the instruction level will allow us to determine the feasibility of large scale networks at minimal cost before expensive apparatus is built. Simulations allow us to observe the intermediate states of the network, unlike a real quantum system where the quantum behavior breaks down upon observation. Observation of intermediate states is important because now we can make measurements, such as calculating the level of entanglement, at different points in the simulation. We can also introduce different amounts of error at the gate level and measure how this affects the simulation. These intermediate observations are quantified as probabilities that a QUBIT is 1. The following plot illustrates the type of information which we will be able to extract from our simulator.

We will use the Shor factorization problem as the basis of our experiments. It represents a problem which is both important and whose simulation is realizable. We have performed preliminary studies on the Los Alamos factor-4 problem[10] which is a simplification of the Shor problem. The plot shown above tracks the observed probabilities of one of the 6 bits in the Los Alamos problem. Our preliminary studies have allowed us to develop a preliminary version of our simulator and to better understand the internal states of the network at intermediate time steps.

We will study the Shor factorization problem on a number of different inputs. We will investigate networks to factor 3x5 = 15, 3x7 = 21, and 5x7 = 35. We will simulate with different values for X in the f(a)=X^a mod N function. For example we can choose values of X which are relatively prime to N, so in the factor N=15 problem we can choose values of X from the set {2,4,7,8,11,13,14}. We will investigate to see if any of the values of X affect behaviors in the network such as the accumulation of errors.

We will proceed using the circuits defined in [e,f] to implement a network. We will then investigate other more efficient circuits. We have also developed some specialized circuits which are simpler than the general ones and will allow us to verify the operation of our networks. We will investigate the trade-offs between complexity, speed and size of networks.

As part of our study we want to understand how errors affect the results of the computation. We will first study how errors affect our networks and how different networks with the same functionality behave differently with respect to errors. Different networks may exhibit different error sensitivity because of the different entanglement profiles and because of the nonlinear properties of the quantum gates. We will then use this information to investigate different error correction schemes such as those discussed in Section iv of this proposal. Understanding the sensitivity to errors and the noise level at which the various error correction schemes fail will be a major part of the simulation studies.

Another scheme attempts to ameliorate errors by cooling scratch bits back to the 0 state. The circuits in our networks use scratch space during the course of the calculation. Because the conservation of QUBITS is important, we use additional reversing circuits which return these scratch bits to 0. If there are errors introduced into the calculation some of these scratch bits might not return all the way to zero. This has three implications for our error scheme. First, we reuse the scratch space, so by resetting the intermediate values back to zero we prevent errors from accumulating. Second, the scratch bits are entangled to other bits during the calculation. If the scratch bits are not returned all the way to zero they are still entangled to other bits and cooling the scratch bits uses this entanglement to force the other bits closer to their correct values. Thirdly, we can use this entanglement idea to introduce additional scratch bits into the calculation so that they too can be returned to zero, removing additional ‘noise.’

Because of the exponential nature of quantum calculations, simulation has exponential storage and computation requirements. We have estimated the simulation time of the Shor "factor 15" problem on our HP 755 machines, and found that the time is on the order of days. Because of this we will develop a version of the simulator which can run on larger multicomputer systems. This quantum problem lends itself nicely to parallelization because the individual gate operations are associative. We have access to parallel machines at the University of Southern California, as well as at the San Diego Supercomputing Center. We will investigate which of these machines will be most appropriate for the simulation of our quantum networks.

References

a. Q. A. Turchette, C. J. Hood, W. Lange, H. Mabuchi, and H. J. Kimble, Phys. Rev. Lett. 75, 4710(1995).

b. S. Lloyd, Phys. Rev. Lett. 75, 346(1995).

c. S. Lloyd, "Quantum Analog Computers," submitted to Science (1996).

d. J. Preskill, "Can Quantum Errors Be Corrected?," unpublished notes (November, 1994).

e. A. Despain et al., JASON Report JSR-95-115, Mitre Corporation, McLean, VA.

f. D. Beckman, A. Chari, S. Devabhaktuni, and J. Preskill, Caltech Preprint CALT-68-2021 (1995).

g. H. Mabuchi and P. Zoller, Phys. Rev. Lett.(1996).

h. N. J. Cerf and C. Adami, "Negative Entropy and Information in Quantum Mechanics," Caltech Preprint (1995), quant-phy/9512022.

1. R. P. Feynman, Intl. J. Theoretical Physics 21, 467 (1982); D. Deutsch, Proc. R. Soc. Lond. A400, 97 (1985); P. Benioff, Phys. Rev. Lett. 48, 1581(1982).

2. P. W. Shor, in 35th Annual Symposium on Foundations of Computer Science: Proceedings, ed. S. Goldwasser, IEEE Computer Society Press (1994).

3. C. Monroe, D. M. Meekhof, B. E. King, W. M. Itano, and D. J. Wineland, Phys. Rev. Lett. 75, 4714(1995).

4. T. Pellizzari, S. A. Gardiner, J. I. Cirac, and P. Zoller, "Decoherence, Continuous Observation, and Quantum Computing: A Cavity QED Model," Phys. Rev. Lett. 75, 3788 (1995).

5. J. I. Cirac and P. Zoller, Phys. Rev. Lett. 74, 4091 (1995).

6. A. Barenco, D. Deutsch, A. Ekert, and R. Jozsa, Phys. Rev. Lett. 74, 4083 (1995); T. Sleator and H. Weinfurter, ibid., 4087; J. I. Cirac and P. Zoller, ibid., 4091.

7. C. W. Gardiner, Phys. Rev. Lett 70, 2269 (1993); H. J. Carmichael, ibid., 2273.

8. A. S. Parkins, P. Marte, P. Zoller, O. Carnal, and H. J. Kimble, Phys. Rev. A 51, 1578 (1995).

9. Z. Hu and H. J. Kimble, Optics Lett. 19,1888 (1994).

10. R. Hughes, et. al., "Quantum Computation and Factoring," Presentation from Los Alamos National Laboratory, (1995).

11. R. Landauer, "Is quantum mechanically coherent computation useful?," in Proceedings of the Drexel-4 Symposium on Quantum Nonintegrability -- Quantum-Classical Correspondence, edited by D. H. Feng and B.-L. Hu (International Press, to appear).

12. P. W. Shor, Phys. Rev. A 52, 2493 (1995); A. R. Calderbank and P. W. Shor, "Good quantum error-correcting codes exist," (1995, unpublished), quant-ph/9512032; A. Steane, "Multiple particle interference and quantum error correction," (1995, unpublished), quant-ph/9601029.

13. For an elementary review see C. H. Bennett, G. Brassard, and A. K. Ekert, Sci. Am. Oct. 1992, 50.

14. C. H. Bennett et al., "Purification of noisy entanglement and faithful teleportation via noisy channels," (1995, unpublished); D. Deutsch et al., "Entanglement-based quantum cryptography is unconditionally secure," (1995, unpublished).

15. V. Vedral, A. Barenco, and A. Ekert, "Quantum networks for elementary arithmetic operations," Oxford preprint (1995), quantu-ph/9511018.

16. C. Miquel, J. P. Paz, R. Perazzo, "Factoring in a dissipative quantum computer," Technical report 9601021 from Los Alamos National Laboratory repository, (1996).

17. C. H. Bennett et al., "Purification of noisy entanglement and faithful teleportation via noisy channels," (1995, unpublished).

18. D. Deutsch et al., "Entanglement-based quantum cryptography is unconditionally secure," (1995, unpublished).

19. H.-K. Lo and H. F. Chau, "Quantum cryptography in noisy channels," (1995, unpublished), quant-ph/9511025.