^M

Scientific Progress and Accomplishments:

During this past year, the theory effort in the QUIC group at Caltech has focused primarily on issues relating to quantum error correcting codes and fault-tolerant operation of a quantum computer.  Our major accomplishments are:

1.  The accuracy threshold for quantum computation:  In 1996, we showed that if quantum error correction and fault-tolerant methods are invoked, it is possible in principle to perform a quantum computation of arbitrary length  reliably, if the average probability of error per gate is below a certain critical value. (Similar conclusions were reported by Knill, Laflamme, and Zurek, by Aharonov and Ben-Or, and by Kitaev.)  In our earlier work, we showed that an error probability of  10-5   per quantum gate is acceptable.  In 1997, Daniel Gottesman and John Preskill refined this estimate, showing that an error rate of 10- 4  can be tolerated.  This new analysis made systematic use of a more efficient scheme for computing the error syndrome that had first been suggested by Andrew Steane.  Steane’s method is highly parallelized, and is therefore well optimized for dealing with storage errors (those afflicting  the ``resting’’ qubits that are not necessarily being acted on by quantum gates).

2. Fault tolerance with good codes: The fault-tolerant methods used in the analysis of the accuracy threshold encode only a single qubit in a large code block, and so make inefficient use of  storage space.  But there also exist “good” quantum codes, with many encoded qubits per block, that are far more efficient.  In 1997, Daniel Gottesman (who in 1996 had developed systematic methods for finding good codes), showed how to use good quantum codes for fault-tolerant quantum computation – indeed, Gottesman showed that a universal set of fault-tolerant quantum gates can be designed for any one of the ``stabilizer’’ quantum error-correcting codes. If the reliability of our hardware is close to the accuracy threshold, then good codes provide no improvement.  But as the hardware improves, we can use good codes, and so enhance the reliability of our quantum computer at a smaller cost in storage space.

3. Topological quantum computation:  With the development of fault-tolerant methods, we now know that it is possible in principle for the operator of a quantum computer to actively intervene to stabilize the device against errors in a noisy (but not too noisy) environment. In the long term though, fault tolerance might be achieved in practical quantum computers by a rather different route – with intrinsically fault-tolerant hardware.  Walt Ogburn and John Preskill  have studied a scheme for fault-tolerant hardware envisioned by Alexei Kitaev (who developed his idea while visiting the QUIC group this year), in which the quantum gates exploit non-abelian Aharonov-Bohm interactions among the distantly separated quasiparticles in a suitably constructed spin system.  We have shown that this scheme is amenable to universal quantum computation, and we have explicitly constructed a universal set of quantum gates.

4. Improving capacity with nonorthogonal codewords: In addition to our work directly relating to error correction for quantum computing, the QUIC theory group also addresses problems in quantum communication theory.  In particular, Christopher Fuchs has been systematically studying how efficiently classical information can be transmitted over a noisy quantum channel. In 1997,  Fuchs discovered that there are noisy quantum channels that convey classical information most efficiently if an alphabet of nonorthogonal signal states is chosen.  This claim is surprising, since nonorthogonal states cannot be perfectly distinguished, and illustrates the subtlety of best exploiting quantum resources to carry out classical communication tasks.

Plans for the coming year:

1. Simplified topological computer:  We will continue to pursue schemes for fault-tolerant quantum hardware.  In particular,  in our demonstration that a topological computer is capable of universal computation, the spin model required was quite complicated.  We hope to show that spin systems with much simpler interactions will also work.

2. Topological algorithms:  We expect that the special capabilities of  topological computers may suggest new ideas for efficient quantum algorithms. In particular, we plan to investigate the remarkable suggestion of Michael Freedman, that a topological gauge theory might solve #P-hard problems efficiently.

3. Optical quantum error-correcting codes: With Ignacio Cirac and Peter Zoller, Steven van Enk (now in the QUIC group) proposed new ideas for error correction in optical communication.  We hope to develop these methods more systematically and to generalize them.  By combining those ideas with other known quantum error-correction methods, we suspect that more powerful techniques can be conceived that might soon be implementable in the laboratory.
 

List of Participating Scientific Personnel:

John Preskill, Ph.D., Co-Principal Investigator
Christopher Fuchs: DuBridge Prize Research Fellow
Alexei Kitaev, Debbie Leung, Michael Nielsen, Martin Plenio: Visitors
Daniel Gottesman, David Beckman: GRA's
Srinivas Aji, John Cortese, Sumit Daftuar, Andrew Landahl: Graduate students
Sham Kakade, Eric Dennis, Walt Ogburn: Undergraduate research assistants

List of Manuscripts/Publications:

1. “Reliable Quantum Computers,”J. Preskill, Proceedings of the Royal Society of London A 454 (1998) 385-410.
2. “Quantum Computing: Pro and Con,” J. Preskill, Proceedings of the Royal Society of London A 454 (1998) 469-486.
3. “Fault-Tolerant Quantum Computation” J. Preskill, to appear in Quantum Computation, edited by Hoi-Kwong Lo, Sandu Popescu, and Tim Spiller.
4. “Optimal Universal and State-dependent Quantum Cloning,” D. Bruss, D. P. DiVincenzo, A. Ekert, C.A. Fuchs, C. Macchiavello, and J. A. Smolin, Physical Review A 57 (3), (1998). (Also [quant-ph/9705038]).
5. “Nonorthogonal Quantum States Maximize Classical Information Capacity,” C. A. Fuchs, Physical Review Letters 79 (6), 1162-1165 (1997).
6. “Optimal Eavesdropping in Quantum Cryptography. I. Information Bound and Optimal  Strategy,” C. A. Fuchs, N. Gisin, R. B. Griffiths, C. S. Niu, and A. Peres, Physical Review A 56 (2), 1163-1172 (1997).
7. “Entanglement-Enhanced Classical Communication on a Noisy Quantum Channel,” C. H. Bennett, C. A. Fuchs, and J. A. Smolin, in Quantum Communication, Computing and Measurement, edited by O. Hirota, A. S. Holevo, and C. M. Caves (Plenum Press, NY, 1997), pages 79-88.
8. “Cryptographic Distinguishability Measures for Quantum Mechanical States,” C. A. Fuchs and J. van de Graaf, submitted to IEEE Transactions on Information Theory. (See also [quant-ph/9712042]).
9. “Entanglement of Assistance-A New Measure of Entanglement,” D. P. DiVincenzo, C. A. Fuchs, H. Mabuchi, J. A. Smolin, A. Thapliyal, and A. Uhlmann, submitted to The 1st NASA International Conference on Quantum Computing & Quantum Communications (NASA QCQC'98), (a refereed conference).
10. “A Quantum Analog of Huffman Coding,” S. Braunstein, H.-K. Lo, C. A. Fuchs, and D. Gottesman, submitted to The 1998 IEEE International Symposium on Information Theory, (a refereed conference).
11. “Efficient Computations of Encoding for Quantum Error Correction,” R. Cleve and D. Gottesman, Phys. Rev. A 56 (1997) 76.
12. “A Theory of Fault-Tolerant Quantum Computation,” D. Gottesman, [quant-ph/9702029].
13. “Stabilizer Codes and Quantum Error Correction,” D. Gottesman, [quant-ph/9705052].