Automated generation of layout and control for quantum circuits

ABSTRACT

We present a computer-aided design flow for quantum circuits, complete with automatic layout and control logic extraction. To motivate automated layout for quantum circuits, we investigate grid-based layouts and show a performance variance of four times as we vary grid structure and initial qubit placement. We then propose two polynomial-time design heuristics: a greedy algorithm suitable for small, congestion-free quantum circuits and a dataflow-based analysis approach to placement and routing with implicit initial placement of qubits. Finally, we show that our dataflow-based heuristic generates better layouts than the state-of-the-art automated grid-based layout and scheduling mechanism in terms of latency and potential pipelinability, but at the cost of some area.

REFERENCES

• 1: P. Aliferis, D. Gottesman, and J. Preskill. Quantum accuracy threshold for concatenated distance-3 codes. Arxiv preprint quant-ph/0504218, 2005.
• 2: S. Balensiefer, L. Kreger-Stickles, and M. Oskin. QUALE: quantum architecture layout evaluator. Proceedings of SPIE, 5815:103, 2005.
• 3: 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
• 4: J. I. Cirac and P. Zoller. Quantum computations with cold trapped ions. Phys. Rev. Lett, 74:4091--4094, 1995.
• 5: A. Cross. qasm-tools. http://www.media.mit.edu/quanta/quanta-web/projects/qasm-tools/, 2006.
• 6: 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]
• 7: W. Hensinger, S. Olmschenk, D. Stick, D. Hucul, M. Yeo, M. Acton, L. Deslauriers, C. Monroe, and J. Rabchuk. T-junction ion trap array for two-dimensional ion shuttling, storage, and manipulation. Applied Physics Letters, 88(3):34101, 2006.
• 8: D. Hucul, M. Yeo, W. K. Hensinger, J. Rabchuk, S. Olmschenk, and C. Monroe. On the transport of atomic ions in linear and multidimensional ion trap arrays. quant-ph/0702175, 2007.
• 9: 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
• 10: D. Kielpinski, C. Monroe, and D.J. Wineland. Architecture for a large-scale ion-trap quantum computer. Nature, 417:709--711, 2002.
• 11: J. Kim, S. Pau, Z. Ma, H. McLellan, J. Gages, A. Kornblit, and R. Slusher. System design for large-scale ion trap quantum information processor. Quantum Information and Computation, 5(7):515--537, 2005.
• 12: C. M. Kyung , J. M. Widder , D. A. Mlynski, Adaptive Cluster Growth (ACG): a new algorithm for circuit packing in rectilinear region, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
• 13: M.J. Madsen, W.K. Hensinger, D. Stick, J.A. Rabchuk, and C. Monroe. Planar ion trap geometry for microfabrication. Applied Physics B: Lasers and Optics, 78:639--651, 2004.
• 14: 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]
• 15: T.S. Metodi, D.D. Thaker, A.W. Cross, F.T. Chong, and I.L. Chuang. Scheduling physical operations in a quantum information processor. Proceedings of SPIE, 6244:62440T, 2006.
• 16: C. Monroe, D. M. Meekhof, B. E. King, W. M. Itano, and D. J. Wineland. Demonstration of a universal quantum logic gate. Phys. Rev. Lett., 75:4714--4717, 1995.
• 17: C. Pearson, D. Leibrandt, W. Bakr, W. Mallard, K. Brown, and I. Chuang. Experimental investigation of planar ion traps. Phys. Rev. A, 73(3), 2006.
• 18: P.W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. 35'th Ann. Symp. on Foundations of Comp. Science (FOCS), pages 124--134, 1994.
• 19: A. M. Steane. Simple quantum error correcting codes. Phys. Rev. A, 54:4741--4751, 1996.
• 20: A.M. Steane. Overhead and noise threshold of fault-tolerant quantum error correction. Phys. Rev. A, 68(4):42322, 2003.
• 21: Krysta M. Svore , Alfred V. Aho , Andrew W. Cross , Isaac Chuang , Igor L. Markov, A Layered Software Architecture for Quantum Computing Design Tools, Computer, v.39 n.1, p.74-83, January 2006 [doi>10.1109/MC.2006.4]
• 22: K. Svore, A. Cross, A. Aho, I. Chuang, and I. Markov. Toward a software architecture for quantum computing design tools. Proceedings of the 2nd International Workshop on Quantum Programming Languages (QPL), pages 145--162, 2004.
• 23: 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
• 24: W. Wootters and W. Zurek. A single quantum cannot be cloned. Nature, 299:802--803, 1982.
• 25: C. Zalka. Simulating quantum systems on a quantum computer. Proceedings: Mathematical, Physical and Engineering Sciences, 454(1969):313--322, 1998.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.2 Control Structure Performance Analysis and Design Aids
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Design

Keywords:
CAD, control, ion trap, layout, quantum computing