The effect of communication costs in solid-state quantum computing architectures

ABSTRACT

Quantum computation has become an intriguing technology with which to attack difficult problems and to enhance system security. Quantum algorithms, however, have been analyzed under idealized assumptions without important physical constraints in mind. In this paper, we analyze two key constraints: the short spatial distance of quantum interactions and the short temporal life of quantum data.In particular, quantum computations must make use of extremely robust error correction techniques to extend the life of quantum data. We present optimized spatial layouts of quantum error correction circuits for quantum bits embedded in silicon. We analyze the complexity of error correction under the constraint that interaction between these bits is near neighbor and data must be propagated via swap operations from one part of the circuit to another.We discover two interesting results from our quantum layouts. First, the recursive nature of quantum error correction circuits requires a additional communication technique more powerful than near-neighbor swaps -- too much error accumulates if we attempt to swap over long distances. We show that quantum teleportation can be used to implement recursive structures. We also show that the reliability of the quantum swap operation is the limiting factor in solid-state quantum computation.

REFERENCES

• 1: D. Aharonov , M. Ben-Or, Fault-tolerant quantum computation with constant error, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.176-188, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258579]
• 2: J. S. Bell. On the Einstein-Podolsy-Rosen paradox. Physics, 1:195--200, 1964. Reprinted in J. S. Bell, Speakable and Unspeakable in Quantum Mechanics, Cambridge University Press, Cambridge, 1987.
• 3: C. H. Bennett and G. Brassard. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing, pages 175--179, 1984.
• 4: D. Bouwmeester, J. W. Pan, K. Mattle, M. Eibl, H. Weinfurter, and A. Zeilinger. Experimental quantum teleportation. Nature, 390(6660):575--579, 1997.
• 5: A. M. Childs, E. Farhi, and J. Preskill. Robustness of adiabatic quantum computation. Phys. Rev. A, (65), 2002.
• 6: I. L. Chuang. Quantum algorithm for clock synchronization. Phys. Rev. Lett., 85:2006, Aug 2000.
• 7: I. L. Chuang, N. Gershenfeld, and M. Kubinec. Experimental implementation of fast quantum searching. Phys. Rev. Lett., 18(15):3408--3411, 1998.
• 8: I. L. Chuang, R. Laflamme, P. Shor, and W. H. Zurek. Quantum computers, factoring, and decoherence. Science, 270:1633, Dec 1995. arXive e-print quant-ph/9503007.
• 9: N. Gershenfeld and I. Chuang. Quantum computing with molecules. Scientific American, June 1998.
• 10: D. Gottesman. Theory of fault-tolerant quantum computation. Phys. Rev. A, 57(1):127--137, 1998. arXive e-print quant-ph/9702029.
• 11: Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.212-219, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237866]
• 12: S. Hallgren. Quantum Information Processing '02 Workshop, 2002.
• 13: P. Hoyer. Banff workshop on quantum algorithms, 2002.
• 14: J. A. Jones, M. Mosca, and R. H. Hansen. Implementation of a quantum search algorithm on a nuclear magnetic resonance quantum computer. Nature, 393(6683):344, 1998. arXive e-print quant-ph/9805069.
• 15: R. Jozsa, D. Abrams, J. Dowling, and C. Williams. Quantum atomic clock synchronization based on shared prior entanglement. Phys. Rev. Lett., pages 2010--2013, August 2000.
• 16: B. Kane. A silicon-based nuclear spin quantum computer. Nature, 393:133--137, 1998.
• 17: D. Kielpinski, C. Monroe, and D. J. Wineland. Architecture for a large-scale ion-trap quantum computer. Nature, 417:709--711, 2002.
• 18: S. Lloyd. Quantum-mechanical computers. Scientific American, 273(4):44, Oct. 1995.
• 19: C. Monroe, D. M. Meekhof, B. E. King, W. M. Itano, and D. J. Wineland. Demonstration of a fundamental quantum logic gate. Phys. Rev. Lett., 75:4714, 1995.
• 20: Y. Nakamura, Y. A. Pashkin, and J. S. Tsai. Coherent control of macroscopic quantum states in a single-cooper-pair box. Nature, 398:786--788, 1999.
• 21: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 22: Mark Oskin , Frederic T. Chong , Isaac L. Chuang , John Kubiatowicz, Building quantum wires: the long and the short of it, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 23: J. Preskill. Reliable quantum computers. Proc. R. Soc. London A, 454(1969):385--410, 1998.
• 24: C. Sackett, D. Kielpinsky, B. King, C. Langer, V. Meyer, C. Myatt, M. Rowe, Q. Turchette, W. Itano, D. Wineland, and C. Monroe. Experimental entanglement of four particles. Nature, 404:256--258, 2000.
• 25: Leonard J. Schulman , Umesh V. Vazirani, Molecular scale heat engines and scalable quantum computation, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.322-329, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301332]
• 26: P. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In Proc. 35th Annual Symposium on Foundations of Computer Science, page 124, Los Alamitos, CA, 1994. IEEE Press.
• 27: P. W. Shor, Fault-tolerant quantum computation, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.56, October 14-16, 1996
• 28: P. W. Shor. Scheme for reducing decoherence in quantum computer memory. Phys. Rev. A, 54:2493, 1995.
• 29: A. Skinner et al. Hydrogenic spin quantum computing in silicon: a digital approach. quant ph/0206159, 2002.
• 30: A. Steane. Error correcting codes in quantum theory. Phys. Rev. Lett., 77, 1996.
• 31: A. Steane. Simple quantum error correcting codes. Phys. Rev. Lett., 77:793--797, 1996.
• 32: Q. A. Turchette, C. J. Hood, W. Lange, H. Mabuchi, and H. J. Kimble. Measurement of conditional phase shifts for quantum logic. Phys. Rev. Lett., 75:4710, 1995.
• 33: W. van Dam and G. Seroussi. Efficient quantum algorithms for estimating gauss sums. quant-ph, page 0207131, 2002.
• 34: L. M. Vandersypen, M. Steffen, G. Breyta, C. S. Yannoni, R. Cleve, and I. L. Chuang. Experimental realization of order-finding with a quantum computer. Phys. Rev. Lett., to appear, 2000.
• 35: L. M. K. Vandersypen, M. Steffen, G. Breyta, C. S. Yannoni, M. H. Sherwood, and I. L. Chuang. Experimental realization of shor's quantum factoring algorithm using nuclear magnetic resonance. Nature, 414:883, 2001.
• 36: D. Vion, A. Aassime, A. Cottet, P. Joyez, H. Pothier, C. Urbina, D. Esteve, and M. H. Devoret. Maniplating the quantum state of an electrical circuit. Science, 296:886, 2002.
• 37: J. von Neuman. Automata Studies. Princeton University Press, Princeton, NJ, 1956.
• 38: R. Vrijen, E. Yablonovitch, K. Wang, H. W. Jiang, A. Balandin, V. Roychowdhury, T. Mor, and D. DiVincenzo. Electron spin resonance transistors for quantum computing in silicon-germanium heterostructures. arXive e-print quant-ph/9905096, 1999.
• 39: S. Winograd and J. D. Cowan. Reliable Computation in the Presence of Noise. MIT Press, Cambridge, Mass., 1963.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.m Miscellaneous

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.m Miscellaneous

  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Error control codes

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
quantum architecture, quantum computing, silicon-based quantum computing