Scientific Progress and Accomplishments:

Parallel Simulation:
We have developed a parallel quantum computer simulator. For many of the problems that we have considered this simulator achieves near perfect linear speedup. We have used the simulator to study circuits to factor the numbers 15, 21, 35 and 57 as well as the Grover database search problem.

Simulating a quantum computer is a difficult problem because to faithfully model a quantum computer the simulator must allocate an exponential number of states and perform an exponential number of operations. Because of these requirements quantum computer simulation is a natural candidate for parallel processing. The simulator distributes the state space of the quantum computer across multiple processors and each processor performs a portion of the total calculation.

Reducing the Complexity of Simulating a Quantum Computer:
All of our simulation studies are based on the trapped ion model of a quantum computer. This model requires three states for each qubit in the computer. We have defined a two state model which reduces the complexity of simulating the trapped ion quantum computer exponentially. We have performed simulation studies to validate this reduced model.

We have also demonstrated a method for simulating the factor 15 problem whose complexity is lower than the original method by a factor of 64.

We have defined the first circuit implementation of the Grover database algorithm for the trapped ion quantum computer. This circuit uses a sequence of rotations and controlled-not gates.

Simulation of the factor 15 problem for operational errors and decoherence would require about 30,000 years of simulation time if we were to use the most detailed simulation model for the ion trap computer and not use any of our simplification techniques. This assumes that we simulate 25 different combinations of inaccuracies, 8 different levels of decoherence and run four trials to average out the effects of random gaussian errors. Each of these simulations, using the 3-State model would take about 36 years. Performing the simulations at this detail is obviously not feasible, but with our methods we can perform the same set of simulations in only 400 hours without an appreciable loss of accuracy. These methods will also allow us to simulate problems of increased size in the future.

Simulating the Factoring and Database Search Problems: (On going work)
Using our reduced simulation models we are currently studying in more depth quantum circuits to factor the numbers 15, 21, 35, and 57 as well as the Grover database search problem.

Our simulations show that random inaccuracies (noise) are more significant than fixed magnitude inaccuracies for the ion trap quantum computer. Also errors in the duration of the laser pulse are more significant than errors in the phase of the laser. For the problems that we have considered we show that noise or constant magnitude inaccuracies of magnitude p/512 or greater cause a significant impact on the fidelity of the calculation.
 Our simulations also show that a quantum computation can tolerate a decoherence rate as high as 10-5. For the ion trap computer this corresponds roughly to a decoherence lifetime of 50 milliseconds and a switching speed of 500 nanoseconds. We also show that inaccuracies and decoherence are uncorrelated and can be simulated separately.

Our simulations relate the physical quantities of inaccuracies and decoherence to the probability of error per gate. An error rate per gate on the order of 10-6 corresponds to inaccuracies of less than phi/4096 per laser operation and a decoherence rate of 10-6.  To his initial work, it has been shown by our QUIC colleague John Preskill that a quantum computer with this error rate, if it uses quantum error correcting codes, could factor a number more efficiently than a classical computer, with more recent work by Preskill, et al relaxing this limit to 10-4.  We plan to investigate these issues with full simulations.  This assumes that the quantum circuits used to implement factoring with error correction codes behave in the same manner as the factoring circuits that we have considered.

Plans for the coming year:

1. Further simulation studies of the factoring problems.
2. Simulation studies of error correction codes.
3. Enhanced gates for the ion trap quantum computer. Multiple fan out gates and gates which provide functions other than the traditional controlled-not gate.

List of Participating Scientific Personnel:

Alvin M. Despain, Ph.D., Co-Principal Investigator, USC
Kevin M. Obenland (GRA)
Joong-Seok Moon (GRA)
Stelian Alupoaei (GRA)
 

List of Manuscripts/Publications:

1. “A Parallel Quantum Computer Simulator,” To appear in the proceedings of High Performance Computing 1998.
2. “Models to Reduce the Complexity of Simulating a Quantum Computer” (Unpublished)