High-level interconnect model for the quantum logic array architecture

ABSTRACT

We summarize the main characteristics of the quantum logic array (QLA) architecture with a careful look at the key issues not described in the original conference publications: primarily, the teleportation-based logical interconnect. The design goal of the the quantum logic array architecture is to illustrate a model for a large-scale quantum architecture that solves the primary challenges of system-level reliability and data distribution over large distances. The QLA's logical interconnect design, which employs the quantum repeater protocol, is in principle capable of supporting the communication requirements for applications as large as the factoring of a 2048-bit number using Shor's quantum factoring algorithm. Our physical-level assumptions and architectural component validations are based on the trapped ion technology for implementing quantum computing.

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: Dorit Aharonov , Wim van Dam , Julia Kempe , Zeph Landau , Seth Lloyd , Oded Regev, Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation, SIAM Journal on Computing, v.37 n.1, p.166-194, April 2007 [doi>10.1137/S0097539705447323]
• 3: Aliferis, P., Gottesman, D., and Preskill, J. 2005. Quantum accuracy threshold for distance 3 codes. Eprint: quant-ph/0504218.
• 4: Bahr, F., Boehm, M., Franke, J., and Kleinjung, T. 2005. Rsa-640 is factored! RSA Lab, Bedford, MA.
• 5: Steven Balensiefer , Lucas Kregor-Stickles , Mark Oskin, An Evaluation Framework and Instruction Set Architecture for Ion-Trap Based Quantum Micro-Architectures, Proceedings of the 32nd annual international symposium on Computer Architecture, p.186-196, June 04-08, 2005
• 6: Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D., Margolus, N., Shor, P., Sleator, T., Smolin, J., and Weinfurter, H. 1995. Elementary gates for quantum computation. Phys. Rev. A. 52, 3457.
• 7: Barrett, M., Chiaverini, J., Schaetz, T., Britton, J., Itano, W. M., Jost, J. D., Knill, E., Langer, C., Liebfried, D., Ozeri, R., and Wineland, D. J. 2004. Deterministic quantum teleportation of atomic qubits. Nature 429.
• 8: Bell, J. S. 1964. On the Einstein-Podolsky-Rosen paradox. Phys. 1, 195--200.
• 9: Bennett, C., Brassard, G., Popescu, S., Schumacher B., Smolin, J. A., and Wooters, W. K. 1996. Purification of noisy entanglement and faithful teleportation via, noisy channels. Phys. Rev. Lett. 76, 722.
• 10: Bennett, C. H., Barassard, G., Crépeau, C., Jozsa, R., Peres, A., and Wooters, W. K. 1993. Teleporting an unknown quantum state via dual classical and EPR channels. Phys. Rev. Lett. 70, 1895--1899.
• 11: Briegel, H. and Raussendorf, R. 2001. Persistent entanglement in arrays of interacting particles. Phys. Rev. Lett 86, 910--913.
• 12: Britton, J., Leibfried, D., Beall J., Blakestad, R. B., Bollinger, J. J., Chiaverini, J., Epstein, R. J., Jost, J. D., Kielpinski, D., Langer, C., Ozeri, R., Reichle, R., Seidelin, S., Shiga, N., Wesenberg, J. H., and Wineland, D. J. 2006. A microfabricated surface-electrode ion trap in silicon. http://arxiv.org/abs/quant=ph/0605170.
• 13: Buhler, J., Lenstra, H., and Pomerance, C. 1994. Factoring integers with the number field sieve. In The Development of the Number Field Sieve. Lecture Notes: in Mathematics, vol. 1554. Springer, 50--94.
• 14: Bullock, S. S. and Markov, I. L. 2004. Asymptotically optimal circuits for arbitrary n-qubit diagonal computations. Quantum Inf. Comput. 4, 1, 027--047.
• 15: Cabrillo, C., Cirac, J. I., Garcia Fernandez, P., and Roller, P. 1999. Creation of entangled states of distant atoms by interference. Phys. Rev. A 59, 1025--1033.
• 16: C. Chekuri , R. Johnson , R. Motwani , B. Natarajan , B. R. Rau , M. Schlansker, Profile-driven instruction level parallel scheduling with application to super blocks, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.58-67, December 02-04, 1996, Paris, France
• 17: Childs, A. M., Farhi, E., and Preskill, J. 2002. Robustness of adiabatic quantum computation. Phys. Rev. A 65.
• 18: Cirac, J., Ekert, A., Huelga, S., and Macchiavello, C. 1999. Distributed quantum computation over noisy channels. Phys. Rev. A 59, 4249.
• 19: Cirac, J. I. and Zoller, P. 1995. Quantum computations with cold trapped ions. Phys. Rev. Lett. 74, 4091--4094.
• 20: Brian L. Deitrich , Wen-mei W. Hwu, Speculative hedge: regulating compile-time speculation against profile variations, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.70-79, December 02-04, 1996, Paris, France
• 21: Deutsch, D. 1985. Quantum computational networks. Proc. Royal. Soc. London. A 400, 97--117.
• 22: Deutsch, D., Ekert, A., Jozsa, R., Macchiavello, C., Popescu, S., and Sanpera, A. 1996. Quantum privacy amplification and the security of quantum cryptography over noisy channels. Phys. Rev. Lett. 77, 2818--2821.
• 23: DiVincenzo, D. P. 2000. The physical implementation of quantum computation. Fortschr. Phys. 48, 771--783.
• 24: Draper, T., Kutin, S., Rains, E., and Svore, K. 2004. A logarithmic-depth quantum carry-lookahead adder. E-Print: quant-ph/0406142.
• 25: Duan, L., Blinov, B., Moehring, D., and Monroe, C. 2004. Scalable trapped ion quantum computation with a probabilistic ion-photon mapping. E-Print: quant-ph/0401020.
• 26: Dur, W., Briegel, H. J., Cirac, J. I., and Zoller, P. 1999. Quantum repeaters based on entanglement purification. Phys. Rev. A59, 169.
• 27: Farhi, E., Goldstone, J., Gutmann, S., and Sipser, M. 2000. Quantum computation by adiabatic evolution. arXiv.org=quant-ph/0001106.
• 28: Fowler, A., Thompson, W. F., Yan, Z., Stephens, A. M., Plourde, B., and Wilhelm, F. K. 2007. Long-Range coupling and scalable architecture for superconducting flux qubits. arXiv:cond-mat/0702620.
• 29: Freedman, M., Kitaev, A., Larsen, M., and Wang, Z. 2003. Topological quantum computation. Bull. Amer. Math. Soc. 40, 3138.
• 30: Gottesman, D. 2000. Fault tolerant quantum computation with local gates. J. Modern Optics 47, 333--345.
• 31: Gottesman, D. 1998. Theory of fault-tolerant quantum computation. Phys. Rev. A 57, 127--137.
• 32: Gottesman, D. K. and Chuang, I. L. 1999. Quantum teleportation is a universal computational primitive. Nature 402, 390--392.
• 33: Grover, L. K. 1997. Quantum telecomputation. E-Print: http://arXiv.org/quant-ph/9704012.
• 34: Hensinger, W. K., Olmschenk, S., Stick, D., Hucul, D., Yeo, M., Acton, M., Deslauriers, L., Rabchuk, J., and Monroe, C. 2005. T-Junction ion trap array for two-dimensional ion shuttling, storage and manipulation. E-Arxiv: quant-ph/0508097.
• 35: Hime, T., Reichardt, P., Plourde, B., Robertson, T., Wu, C.-E., Ustinov, A., and Clarke, J. 2007. Solid-State qubits with current-controlled coupling. Sci. 314, 5804, 1427--1429.
• 36: Hollenberg, L. C. L., Dzurak, A. S., Wellard, C., Hamilton, A. R., Reilly, D. J., Milburn, G. J., and Clark, R. 2003. Charge-Based quantum computing using single donors in semiconductors. Phys. Rev. B 69, 113301.
• 37: Nemanja Isailovic , Yatish Patel , Mark Whitney , John Kubiatowicz, Interconnection Networks for Scalable Quantum Computers, Proceedings of the 33rd annual international symposium on Computer Architecture, p.366-377, June 17-21, 2006
• 38: Jones, J., Vedral, V., Ekert, A., and Castagnoli, G. 2000. Geometric quantum computation using nuclear magnetic resonance. Nature 403, 869--871.
• 39: Kane, B. 1998. A silicon-based nuclear spin quantum computer. Nature 393, 133--137.
• 40: Kim, J., Pau, S., Ma, Z., McLellan, H., Gates, J., Kornblit, A., and Slusher, R. 2005. System design for a large-scale ion-trap quantum information processor. Quantum Inf. Comput. 5, 7, 515.
• 41: Kitaev, A. Y. 1997. Quantum error correction with imperfect gates. In Proceedings of the 3rd International Conference on Quantum Communication and Measurement, 181--188.
• 42: Knill, E. and Laflamme, R. 1997. A theory of quantum error-correcting codes. Phys. Rev. A 55, 900--911.
• 43: Knill, E., Laflamme, R., and Milburn, G. 2001. A scheme for efficient quantum computation with linear optics. Nature 409, 4652.
• 44: Langer, C., Ozeri, R., Jost, J. D., Chiaverini, J., DeMarco, B., Ben-Kish, A., Blakestad, R. B., Britton, J., Hume, D. B., Itano, W. M., Liebfried, D., Reichle, R., Rosenband, T., Schaetz, T., Schmidt, P. O., and Wineland, D. J. 2005. Long-Lived qubit memory using atomic ions. E-Print: quant-ph/0504076.
• 45: Lim, Y. L., Barrett, S. D., Beige, A., Kok, P., and Kwek, L. C. 2005. Repeat-Until-Success quantum computing using stationary and flying qubits. E-Print: http://arXiv.org/quant-ph/0508218.
• 46: Makhlin, Y., Schoen, G., and Shnirman, A. 1999. Josephson-Junction qubits with controlled couplings. Nature 398, 305.
• 47: Matsukevich, D. and Kuzmich, A. 2004. Quantum state transfer between matter and light. Sci. 306, 5696, 663--666.
• 48: Tzvetan S. Metodi , Darshan D. Thaker , Andrew W. Cross, A Quantum Logic Array Microarchitecture: Scalable Quantum Data Movement and Computation, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.305-318, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.9]
• 49: Metodi, T. S., Thaker, D. D., Cross, A. W., Chong, F. T., and Chuang, I. L. 2006. Physical operations scheduler in a quantum information processor. In Proceedings of the SPIE Defense and Security Symposium, Orlando, FL.
• 50: Nielsen, M. 2004. Optical quantum computation using cluster states. Phys. Rev. Lett. 93 (040503).
• 51: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 52: Nielsen, M. A. and Dawson, C. M. 2004. Fault-Tolerant quantum computation with cluster states.
• 53: Niskanen, A., Harrabi, K., Yoshihara, F., Nakamura, Y., Lloyd, S., and Tsai, J. 2007. Quantum coherent tunable coupling of superconducting qubits. Sci. 316, 5825, 723--726.
• 54: Mark Oskin , Frederic T. Chong , Isaac L. Chuang, A Practical Architecture for Reliable Quantum Computers, Computer, v.35 n.1, p.79-87, January 2002 [doi>10.1109/2.976922]
• 55: Ozeri, R., Langer, C., Jost, J. D., De Marco, B., Ben-Kish, A., Blakestad, B. R., Britton, J., Chiaverini, J., Itand, W. M., Hume, D. B., Leibfried, D., Rosenband, T., Schmidt, P. O., and Wineland, D. J. 2004. Hyperfine coherence in the presence of spontaneous photon scattering. arXiv:quant-ph/0502063.
• 56: Pearson, C. E., Leibrandt, D. R., Bakr, W. S., Mallard, W. J., Brown, K. R., and Chuang, I. L. 2006. Experimental investigation of planar ion traps. Phys. Rev. A 73, 032307.
• 57: Platzman, P. M. and Dykman, M. I. 1999. Computing with electrons floating on liquid helium. Sci. 284, 1967--1969.
• 58: Reichardt, B. W. 2004. Improved ancilla preparation scheme increases fault-tolearant threshold. E-Print: quant-ph/0406025.
• 59: Reichle R., Leibfried, D., Knill, E., Britton, J., Blakestad, R., Jost, J., Langer, C., Ozeri, R., Seidelin, S., and Wineland, D. 2006. Experimental purification of two-atom entanglement. Nature 443, 19, 838--841.
• 60: Riebe, M., Häffner, H., Roos, C., Hänsel, W., Benheln J., Körber, T. W., Becher, C., Schmid-Kaler, F., and Blatt, R. 2004. Deterministic quantum teleportation with atoms. Nature 429, 6993, 734--737.
• 61: Seidelin, S., Chiaverini, J., Reichle, R., Bollinger, J., Leibfried, D., Britton, J., Wesenberg, J. H., Blakestad, R. B., Epstein, R. J., Hume, D. , Itano, W. M., Jost, J. D., Langer, C., Ozeri, R., Shiga, N., and Wineland, D. J. 2006. A microfabricated surface-electrode ion trap for scalable quantum information processing. ArXiv Quantum Physics e-prints.
• 62: Shende, V., Bullock, S., and Markov, I. 2006. Synthesis of quantum logic circuits. IEEE Trans. Comput.-Aided Des. 25, 6, 1000--1010.
• 63: Shende, V. V., Markov, I. L., and Bullock, S. S. 2003. Minimal universal two-qubit quantum circuits. Phys. Rev. A 69, 062321, 1--7.
• 64: Shende, V. V., Markov, I. L., and Bullock, S. S. 2004. Finding small two-qubit circuits. In Proceedings of the SPIE, vol. 5436, 348--359.
• 65: Ghassan Shobaki , Kent Wilken, Optimal Superblock Scheduling Using Enumeration, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.283-293, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.27]
• 66: Shor, P. W. 1995. Scheme for reducing decoherence in quantum computer memory. Phys. Rev. A 54, 2493.
• 67: Skinner, A., Davenport, M., and Kane, B. 2003. Hydrogenic spin quantum computing in silicon: A digital approach. Phys. Rev. L 90, 087901 (Feb.).
• 68: Spiller, T., Nemoto, K., Braunstein, S., Munro, W., van Loock, P., and Milburn, G. 2005. Quantum computation by communication. http://arxiv.org/abs/quant-ph/0509202.
• 69: Steane, A. 1996. Error correcting codes in quantum theory. Phys. Rev. Lett. 77, 793--797.
• 70: Steane, A. 2004. How to build a 300 bit, 1 GOP quantum computer. arXiv:quant-ph/0412165.
• 71: Svore, K., Terhal, B., and DiVincenzo, D. 2004. Local fault-tolerant quantum computation. E-Print: quant-ph/0410047.
• 72: Svore, K. M., DiVincenzo, D. P., and Terhal, B. M. 2006. Noise threshold for a fault-tolerant two-dimensional lattice architecture. E-Print (Arxiv.org): quant-ph/0604090.
• 73: Darshan D. Thaker , Tzvetan S. Metodi , Andrew W. Cross , Isaac L. Chuang , Frederic T. Chong, Quantum Memory Hierarchies: Efficient Designs to Match Available Parallelism in Quantum Computing, Proceedings of the 33rd annual international symposium on Computer Architecture, p.378-390, June 17-21, 2006
• 74: Rodney Van Meter , Kae Nemoto , W. J. Munro , Kohei M. Itoh, Distributed Arithmetic on a Quantum Multicomputer, Proceedings of the 33rd annual international symposium on Computer Architecture, p.354-365, June 17-21, 2006
• 75: Van Meter, R. and Itoh, K. M. 2004. Fast quantum modular exponentiation. E-Print: quant-ph/0408006.
• 76: Rodney Van Meter , Mark Oskin, Architectural implications of quantum computing technologies, ACM Journal on Emerging Technologies in Computing Systems (JETC), v.2 n.1, p.31-63, January 2006 [doi>10.1145/1126257.1126259]
• 77: Wineland, D., Monroe, C., Itano, W., Leibfried, D., King, B., and Meekhof, D. 1998. Experimental issues in coherent quantum-state manipulation of trapped atomic ions. J. Res. NIST 103, 259--328.
• 78: Wineland, D. and Heinrichs, T. 2004. Ion trap approaches to quantum information processing and quantum computing. A Quantum Information Science and Technology Roadmap. url: http://quist.lanl.gov.
• 79: Wineland, D., Leibfried, D., Barrett, M., Ben-Kish, A., Bergquist, J. C., Blakestad, R. B., Bollinger, J. J., Britton, J., Chaverini, B., DeMarco, B., Hume, D., Itano, W. M., Jensen, M., Jost, J. D., Knill, E., Koelemeij, J., Langer, C., Oskay, W., Ozeri, R., Reichle, R., Roseband, T., Schaetz, T., Schmidt, P. O., and Seideling, S. 2005. Quantum control, quantum information processing, and quantum-limited metrology with trapped ions. In Proceedings of the International Conference on Laser Spectroscopy (ICOLS).
• 80: Wootters, W. and Zurek, W. 1982. A single quantum cannot be cloned. Nature 299, 802--803.
• 81: Yimsiriwattana, A. and Lomonaco, S. J. 2004. Distributed quantum computing: A distributed Shor algorithm. E-Print: arXiv.org:quant-ph/0403146.
• 82: Zeng, B., Zhou, D., Xu, Z., and Sun, C. 2003. Quantum teleportation using cluster states. ArXiv Quantum Physics e-prints.

INDEX TERMS

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

General Terms:
Design, Performance, Reliability

Keywords:
QLA, Quantum computer architecture design, fault tolerance, large scale, quantum, teleportation