research-article

AutoComm: A Framework for Enabling Efficient Communication in Distributed Quantum Programs

Authors:

Alireza Shabani,

Yufei DingAuthors Info & Claims

MICRO '22: Proceedings of the 55th Annual IEEE/ACM International Symposium on Microarchitecture

Pages 1027 - 1041

https://doi.org/10.1109/MICRO56248.2022.00074

Published: 18 December 2023 Publication History

Abstract

Distributed quantum computing (DQC) is a promising approach to extending the computational power of near-term quantum hardware. However, the non-local quantum communication between quantum nodes is much more expensive and error-prone than the local quantum operation within each quantum device. Previous DQC compilers focus on optimizing the implementation of each non-local gate and adopt similar compilation designs to single-node quantum compilers. The communication patterns in distributed quantum programs remain unexplored, leading to a far-from-optimal communication cost. In this paper, we identify burst communication, a specific qubit-node communication pattern that widely exists in various distributed quantum programs and can be leveraged to guide communication overhead optimization. We then propose AutoComm, an automatic compiler framework to extract burst communication patterns from input programs and then optimize the communication steps of burst communication discovered. Compared to state-of-the-art DQC compilers, experimental results show that our proposed AutoComm can reduce the communication resource consumption and the program latency by 72.9% and 69.2% on average, respectively.

References

[1]

Peter W Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2):303--332, 1999.

Digital Library

[2]

Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212--219, 1996.

Digital Library

[3]

Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002.

Digital Library

[4]

Kenneth R Brown, Jungsang Kim, and Christopher Monroe. Co-designing a scalable quantum computer with trapped atomic ions. npj Quantum Information, 2(1):1--10, 2016.

[5]

Colin D Bruzewicz, John Chiaverini, Robert McConnell, and Jeremy M Sage. Trapped-ion quantum computing: Progress and challenges. Applied Physics Reviews, 6(2):021314, 2019.

[6]

Colin D Bruzewicz, John Chiaverini, Robert McConnell, and Jeremy M Sage. Trapped-ion quantum computing: Progress and challenges. Applied Physics Reviews, 6(2):021314, 2019.

[7]

Markus Brink, Jerry M Chow, Jared Hertzberg, Easwar Magesan, and Sami Rosenblatt. Device challenges for near term superconducting quantum processors: frequency collisions. In 2018 IEEE International Electron Devices Meeting (IEDM), pages 6--1. IEEE, 2018.

[8]

Pablo Andr'es-Mart'inez and Chris Heunen. Automated distribution of quantum circuits via hypergraph partitioning. Physical Review A, 2019.

[9]

Nicholas Laracuente, Kaitlin N. Smith, Poolad Imany, Kevin L. Silverman, and Fred Chong. Short-range microwave networks to scale superconducting quantum computation. ArXiv, abs/2201.08825, 2022.

[10]

Jonathan M. Baker, Casey Duckering, Alexander Hoover, and Frederic T. Chong. Time-sliced quantum circuit partitioning for modular architectures. Proceedings of the 17th ACM International Conference on Computing Frontiers, 2020.

Digital Library

[11]

Christopher Young, Akbar Safari, Preston Huft, J. Zhang, Eun Oh, Ravikumar Chinnarasu, and Mark Saffman. An architecture for quantum networking of neutral atom processors. 2022.

[12]

Anocha Yimsiriwattana and Samuel J Lomonaco Jr. Generalized ghz states and distributed quantum computing. arXiv preprint quant-ph/0402148, 2004.

[13]

Jens Eisert, Kurt Jacobs, Polykarpos Papadopoulos, and Martin B Plenio. Optimal local implementation of nonlocal quantum gates. Physical Review A, 62(5):052317, 2000.

[14]

Davide Ferrari, Angela Sara Cacciapuoti, Michele Amoretti, and Marcello Caleffi. Compiler design for distributed quantum computing. IEEE Transactions on Quantum Engineering, 2:1--20, 2021.

[15]

Gushu Li, Yufei Ding, and Yuan Xie. Tackling the qubit mapping problem for nisq-era quantum devices. Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, 2019.

Digital Library

[16]

MD SAJID ANIS, Héctor Abraham, AduOffei, Rochisha Agarwal, et al. Qiskit: An open-source framework for quantum computing, 2021.

[17]

Matthew Amy and Vlad Gheorghiu. staq---a full-stack quantum processing toolkit. arXiv: Quantum Physics, 2019.

[18]

Nader Khammassi, Imran Ashraf, J. van Someren, Răzvan Nane, A. M. Krol, M. A. Rol, Lingling Lao, Koen Bertels, and Carmen Garcia Almudever. Openql : A portable quantum programming framework for quantum accelerators. ACM J. Emerg. Technol. Comput. Syst., 18:13:1--13:24, 2022.

Digital Library

[19]

Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan. t---ket〉: a retargetable compiler for nisq devices. Quantum Science and Technology, 2020.

[20]

Stephen Diadamo, Marco Ghibaudi, and James R. Cruise. Distributed quantum computing and network control for accelerated vqe. IEEE Transactions on Quantum Engineering, 2:1--21, 2021.

[21]

Maarten Van Steen and A Tanenbaum. Distributed systems principles and paradigms. Network, 2:28, 2002.

[22]

R. Wille, D. Große, L. Teuber, G. W. Dueck, and R. Drechsler. RevLib: An online resource for reversible functions and reversible circuits. In Int'l Symp. on Multi-Valued Logic, pages 220--225, 2008. RevLib is available at http://www.revlib.org.

Digital Library

[23]

Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv: Quantum Physics, 2014.

[24]

Yun Seong Nam, Neil J. Ross, Yuan Su, Andrew M. Childs, and Dmitrii L. Maslov. Automated optimization of large

[25]

Nemanja Isailovic, Yatish Patel, Mark Whitney, and John Kubiatowicz. Interconnection networks for scalable quantum computers. In 33rd International Symposium on Computer Architecture (ISCA'06), pages 366--377. IEEE, 2006.

Digital Library

[26]

Roberto Sanchez Correa and Jean Pierre David. Ultra-low latency communication channels for fpga-based hpc cluster. Integration, 63:41--55, 2018. quantum circuits with continuous parameters. npj Quantum Information, 4:1--12, 2017.

[27]

Philip Krantz, Morten Kjaergaard, Fei Yan, Terry P Orlando, Simon Gustavsson, and William D Oliver. A quantum engineer's guide to superconducting qubits. Applied Physics Reviews, 6(2):021318, 2019.

[28]

Prakash Murali, Jonathan M. Baker, Ali Javadi-Abhari, Frederic T. Chong, and Margaret Martonosi. Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers. Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, 2019.

Digital Library

[29]

Hamza Jnane, Brennan Undseth, Zhenyu Cai, Simon C. Benjamin, and Bálint Koczor. Multicore quantum computing. 2022.

[30]

Ying Li and Simon C. Benjamin. Hierarchical surface code for network quantum computing with modules of arbitrary size. Physical Review A, 94:042303, 2016.

[31]

Wei Tang, Teague Tomesh, Martin Suchara, Jeffrey Larson, and Margaret Martonosi. Cutqc: using small quantum computers for large quantum circuit evaluations. In Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, pages 473--486, 2021.

Digital Library

[32]

Tianyi Peng, Aram Wettroth Harrow, Maris A. Ozols, and Xiaodi Wu. Simulating large quantum circuits on a small quantum computer. Physical review letters, 125 15:150504, 2020.

[33]

Davood Dadkhah, Mariam Zomorodi, Seyed Ebrahim Hosseini, Pawel Plawiak, and Xujuan Zhou. Reordering and partitioning of distributed quantum circuits. IEEE Access, 10:70329--70341, 2022.

[34]

Omid Daei, Keivan Navi, and Mariam Zomorodi-Moghadam. Optimized quantum circuit partitioning. International Journal of Theoretical Physics, 59(12):3804--3820, 2020.

[35]

Mariam Zomorodi Moghadam, Monireh Houshmand, and Mahboobeh Houshmand. Optimizing teleportation cost in distributed quantum circuits. International Journal of Theoretical Physics, 57:848--861, 2016.

[36]

Zohreh Davarzani, Mariam Zomorodi Moghadam, Mahboobeh Houshmand, and Mostafa Nouri. A dynamic programming approach for distributing quantum circuits by bipartite graphs. Quantum Inf. Process., 19:360, 2020.

Digital Library

Cited By

Zhang HYin KWu AShapourian HShabani ADing YTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)MECH: Multi-Entry Communication Highway for Superconducting Quantum ChipletsProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3620665.3640377(699-714)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620665.3640377
Shi YNguyen TStein SStavenger TWarner MRoetteler MHoefler TLi A(2023)A Reference Implementation for a Quantum Message Passing InterfaceProceedings of the SC '23 Workshops of The International Conference on High Performance Computing, Network, Storage, and Analysis10.1145/3624062.3624212(1420-1425)Online publication date: 12-Nov-2023
https://dl.acm.org/doi/10.1145/3624062.3624212

Index Terms

AutoComm: A Framework for Enabling Efficient Communication in Distributed Quantum Programs
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language types
        Distributed programming languages

Index terms have been assigned to the content through auto-classification.

Recommendations

QuComm: Optimizing Collective Communication for Distributed Quantum Computing
MICRO '23: Proceedings of the 56th Annual IEEE/ACM International Symposium on Microarchitecture

Distributed quantum computing (DQC) is a scalable way to build a large-scale quantum computing system. Previous compilers for DQC focus on either qubit-to-qubit inter-node gates or qubit-to-node nonlocal circuit blocks, missing opportunities of ...
OpenQL: A Portable Quantum Programming Framework for Quantum Accelerators
With the potential of quantum algorithms to solve intractable classical problems, quantum computing is rapidly evolving, and more algorithms are being developed and optimized. Expressing these quantum algorithms using a high-level language and making them ...
On the Co-Design of Quantum Software and Hardware
NANOCOM '21: Proceedings of the Eight Annual ACM International Conference on Nanoscale Computing and Communication

A quantum computing system naturally consists of two components, the software system and the hardware system. Quantum applications are programmed using the quantum software and then executed on the quantum hardware. However, the performance of existing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MICRO '22: Proceedings of the 55th Annual IEEE/ACM International Symposium on Microarchitecture

October 2022

1498 pages

ISBN:9781665462723

General Chairs:
Nikos Hardavellas
Northwestern University
,
Simone Campanoni
Northwestern University
,
Program Chairs:
Boris Grot
University of Edinburgh
,
Ulya Karpuzcu
University of Minnesota, Twin Cities

Sponsors

SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing

Publisher

IEEE Press

Publication History

Published: 18 December 2023

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MICRO '22

Sponsor:

SIGMICRO

MICRO '22: 55th Annual IEEE/ACM International Symposium on Microarchitecture

October 1 - 5, 2022

Illinois, Chicago, USA

Acceptance Rates

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

Upcoming Conference

MICRO '24

Sponsor:
sigmicro

57th Annual IEEE/ACM International Symposium on Microarchitecture

November 2 - 6, 2024

Austin , TX , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
27
Total Downloads

Downloads (Last 12 months)27
Downloads (Last 6 weeks)4

Reflects downloads up to 28 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang HYin KWu AShapourian HShabani ADing YTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)MECH: Multi-Entry Communication Highway for Superconducting Quantum ChipletsProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3620665.3640377(699-714)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620665.3640377
Shi YNguyen TStein SStavenger TWarner MRoetteler MHoefler TLi A(2023)A Reference Implementation for a Quantum Message Passing InterfaceProceedings of the SC '23 Workshops of The International Conference on High Performance Computing, Network, Storage, and Analysis10.1145/3624062.3624212(1420-1425)Online publication date: 12-Nov-2023
https://dl.acm.org/doi/10.1145/3624062.3624212

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents