Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/3466752.3480072acmconferencesArticle/Chapter ViewAbstractPublication PagesmicroConference Proceedingsconference-collections
research-article
Public Access

AutoBraid: A Framework for Enabling Efficient Surface Code Communication in Quantum Computing

Published: 17 October 2021 Publication History

Abstract

Quantum computers can solve problems that are intractable using the most powerful classical computer. However, qubits are fickle and error prone. It is necessary to actively correct errors in the execution of a quantum circuit. Quantum error correction (QEC) codes are developed to enable fault-tolerant quantum computing. With QEC, one logical circuit is converted into an encoded circuit.
Most studies on quantum circuit compilation focus on NISQ devices which have 10-100 qubits and are not fault-tolerant. In this paper, we focus on the compilation for fault-tolerant quantum hardware. In particular, we focus on optimizing communication parallelism for the surface code based QEC. The execution of surface code circuits involves non-trivial geometric manipulation of a large lattice of entangled physical qubits. A two-qubit gate in surface code is implemented as a virtual “pipe” in space-time called a braiding path. The braiding paths should be carefully routed to avoid congestion. Communication between qubits is considered the major bottleneck as it involves scheduling and searching for simultaneous paths between qubits. We provide a framework for efficiently scheduling braiding paths. We discover that for quantum programs with a local parallelism pattern, our framework guarantees an optimal solution, while the previous greedy-heuristic-based solution cannot. Moreover, we propose an extension to the local parallelism analysis framework to address the communication bottleneck. Our framework achieves orders of magnitude improvement after addressing the communication bottleneck.

References

[1]
[n. d.]. Cirq, a python framework for creating, editing, and invoking Noisy Intermediate Scale Quantum (NISQ) circuits. ([n. d.]). urlhttps://github.com/quantumlib/Cirq.
[2]
Andrew Cross. 2018. The IBM Q experience and QISKit open-source quantum computing software. Bulletin of the American Physical Society 63 (2018).
[3]
Simon J Devitt, William J Munro, and Kae Nemoto. 2013. Quantum error correction for beginners. Reports on Progress in Physics 76, 7 (2013), 076001.
[4]
Simon J Devitt, Ashley M Stephens, William J Munro, and Kae Nemoto. 2013. Requirements for fault-tolerant factoring on an atom-optics quantum computer. Nature communications 4(2013), 2524.
[5]
Yongshan Ding, Adam Holmes, Ali Javadi-Abhari, Diana Franklin, Margaret Martonosi, and Frederic Chong. 2018. Magic-state functional units: Mapping and scheduling multi-level distillation circuits for fault-tolerant quantum architectures. In 2018 51st Annual IEEE/ACM International Symposium on Microarchitecture (MICRO). IEEE, 828–840.
[6]
Austin G Fowler and Simon J Devitt. 2012. A bridge to lower overhead quantum computation. arXiv preprint arXiv:1209.0510(2012).
[7]
Mrityunjay Ghosh, Amlan Chakrabarti, and Niraj K Jha. 2017. Automated quantum circuit synthesis and cost estimation for the binary welded tree oracle. ACM Journal on Emerging Technologies in Computing Systems (JETC) 13, 4(2017), 1–14.
[8]
Daniel Gottesman. 2010. An introduction to quantum error correction and fault-tolerant quantum computation. In Quantum information science and its contributions to mathematics, Proceedings of Symposia in Applied Mathematics, Vol. 68. 13–58.
[9]
Jeff Heckey, Shruti Patil, Ali JavadiAbhari, Adam Holmes, Daniel Kudrow, Kenneth R Brown, Diana Franklin, Frederic T Chong, and Margaret Martonosi. 2015. Compiler management of communication and parallelism for quantum computation. In ACM SIGARCH Computer Architecture News, Vol. 43. ACM, 445–456.
[10]
Ali Javadi-Abhari, Pranav Gokhale, Adam Holmes, Diana Franklin, Kenneth R. Brown, Margaret Martonosi, and Frederic T. Chong. 2017. Optimized surface code communication in superconducting quantum computers. In Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO 2017, Cambridge, MA, USA, October 14-18n.
[11]
Ali JavadiAbhari, Shruti Patil, Daniel Kudrow, Jeff Heckey, Alexey Lvov, Frederic T Chong, and Margaret Martonosi. 2014. ScaffCC: a framework for compilation and analysis of quantum computing programs. In Proceedings of the 11th ACM Conference on Computing Frontiers. 1–10.
[12]
George Karypis and Vipin Kumar. 1995. Metis-unstructured graph partitioning and sparse matrix ordering system, version 2.0. (1995).
[13]
Daniel Kudrow, Kenneth Bier, Zhaoxia Deng, Diana Franklin, Yu Tomita, Kenneth R. Brown, and Frederic T. Chong. 2013. Quantum Rotations: A Case Study in Static and Dynamic Machine-Code Generation for Quantum Computers. In Proceedings of the 40th Annual International Symposium on Computer Architecture(ISCA ’13). Association for Computing Machinery, New York, NY, USA, 166–176. https://doi.org/10.1145/2485922.2485937
[14]
Gushu Li, Yufei Ding, and Yuan Xie. 2019. Tackling the qubit mapping problem for NISQ-era quantum devices. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. ACM, 1001–1014.
[15]
Hongwei Li and Li Yang. 2015. A quantum algorithm for approximating the influences of Boolean functions and its applications. Quantum Information Processing 14, 6 (2015), 1787–1797.
[16]
Austin G. Fowler Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland. 2012. Surface codes: Towards practical large-scale quantum computation. In PHYSICAL REVIEW A covering atomic, molecular, and optical physics and quantum information.
[17]
Dmitri Maslov. 2007. Linear depth stabilizer and quantum Fourier transformation circuits with no auxiliary qubits in finite-neighbor quantum architectures. Physical Review A 76, 5 (Nov 2007). https://doi.org/10.1103/physreva.76.052310
[18]
Prakash Murali, Jonathan M Baker, Ali Javadi-Abhari, Frederic T Chong, and Margaret Martonosi. 2019. Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. 1015–1029.
[19]
P. J. J. O’Malley, J. Kelly, R. Barends, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, A. G. Fowler, I.-C. Hoi, and et al.2015. Qubit Metrology of Ultralow Phase Noise Using Randomized Benchmarking. Physical Review Applied 3, 4 (Apr 2015). https://doi.org/10.1103/physrevapplied.3.044009
[20]
Alexandru Paler. 2019. SurfBraid: A concept tool for preparing and resource estimating quantum circuits protected by the surface code. arxiv:quant-ph/1902.02417
[21]
R Raussendorf, J Harrington, and K Goyal. 2007. Topological fault-tolerance in cluster state quantum computation. New Journal of Physics 9, 6 (Jun 2007), 199–199. https://doi.org/10.1088/1367-2630/9/6/199
[22]
Michael A Riepe and Karem A Sakallah. 2003. Transistor placement for noncomplementary digital VLSI cell synthesis. ACM Transactions on Design Automation of Electronic Systems (TODAES) 8, 1(2003), 81–107.
[23]
Marcos Yukio Siraichi, Vinícius Fernandes dos Santos, Sylvain Collange, and Fernando Magno Quintão Pereira. 2018. Qubit allocation. In Proceedings of the 2018 International Symposium on Code Generation and Optimization. ACM, 113–125.
[24]
Swamit S. Tannu, Zachary A. Myers, Prashant J. Nair, Douglas M. Carmean, and Moinuddin K. Qureshi. 2017. Taming the Instruction Bandwidth of Quantum Computers via Hardware-Managed Error Correction. In Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture(MICRO-50 ’17). Association for Computing Machinery, New York, NY, USA, 679–691. https://doi.org/10.1145/3123939.3123940
[25]
Swamit S. Tannu and Moinuddin Qureshi. 2019. Ensemble of Diverse Mappings: Improving Reliability of Quantum Computers by Orchestrating Dissimilar Mistakes. In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture(MICRO ’52). Association for Computing Machinery, New York, NY, USA, 253–265. https://doi.org/10.1145/3352460.3358257
[26]
Swamit S Tannu and Moinuddin K Qureshi. 2019. Not all qubits are created equal: a case for variability-aware policies for NISQ-era quantum computers. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. ACM, 987–999.
[27]
Robert Wille, Lukas Burgholzer, and Alwin Zulehner. 2019. Mapping quantum circuits to IBM QX architectures using the minimal number of SWAP and H operations. In Proceedings of the 56th Annual Design Automation Conference 2019. ACM, 142.
[28]
R. Wille, D. Große, L. Teuber, G. W. Dueck, and R. Drechsler. 2008. RevLib: An Online Resource for Reversible Functions and Reversible Circuits. In Int’l Symp. on Multi-Valued Logic. 220–225. RevLib is available at http://www.revlib.org.
[29]
Chi Zhang, Ari Hayes, Longfei Qiu, Yuwei Jin, Yanhao Chen, and Edd Z. Zhang. 2021. Time-Optimal Qubit Mapping. In Proceedings of the Twenty-Sixth International Conference on Architectural Support for Programming Languages and Operating Systems(ASPLOS ’21). ACM, Virtual.
[30]
Alwin Zulehner, Alexandru Paler, and Robert Wille. 2018. Efficient mapping of quantum circuits to the IBM QX architectures. In 2018 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, 1135–1138.

Cited By

View all
  • (2024)A High Performance Compiler for Very Large Scale Surface Code ComputationsQuantum10.22331/q-2024-05-22-13548(1354)Online publication date: 22-May-2024
  • (2024)Optimizing Quantum Fourier Transformation (QFT) Kernels for Modern NISQ and FT ArchitecturesProceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis10.1109/SC41406.2024.00074(1-15)Online publication date: 17-Nov-2024
  • (2024)A SAT Scalpel for Lattice Surgery: Representation and Synthesis of Subroutines for Surface-Code Fault-Tolerant Quantum Computing2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA)10.1109/ISCA59077.2024.00032(325-339)Online publication date: 29-Jun-2024
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
MICRO '21: MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture
October 2021
1322 pages
ISBN:9781450385572
DOI:10.1145/3466752
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 October 2021

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Research-article
  • Research
  • Refereed limited

Funding Sources

  • NSF

Conference

MICRO '21
Sponsor:

Acceptance Rates

Overall Acceptance Rate 484 of 2,242 submissions, 22%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)421
  • Downloads (Last 6 weeks)53
Reflects downloads up to 18 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)A High Performance Compiler for Very Large Scale Surface Code ComputationsQuantum10.22331/q-2024-05-22-13548(1354)Online publication date: 22-May-2024
  • (2024)Optimizing Quantum Fourier Transformation (QFT) Kernels for Modern NISQ and FT ArchitecturesProceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis10.1109/SC41406.2024.00074(1-15)Online publication date: 17-Nov-2024
  • (2024)A SAT Scalpel for Lattice Surgery: Representation and Synthesis of Subroutines for Surface-Code Fault-Tolerant Quantum Computing2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA)10.1109/ISCA59077.2024.00032(325-339)Online publication date: 29-Jun-2024
  • (2024)Quantum Network Routing Based on Surface Code Error Correction2024 IEEE 44th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS60910.2024.00117(1236-1247)Online publication date: 23-Jul-2024
  • (2024)Ecmas: Efficient Circuit Mapping and Scheduling for Surface Code2024 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)10.1109/CGO57630.2024.10444874(158-169)Online publication date: 2-Mar-2024
  • (2023)Hardness of Braided Quantum Circuit Optimization in the Surface CodeIEEE Transactions on Quantum Engineering10.1109/TQE.2023.32513584(1-7)Online publication date: 2023
  • (2022)AFS: Accurate, Fast, and Scalable Error-Decoding for Fault-Tolerant Quantum Computers2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA53966.2022.00027(259-273)Online publication date: Apr-2022

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

HTML Format

View this article in HTML Format.

HTML Format

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media