Divide and Conquer for Combinatorial Optimization and Distributed Quantum Computation

Teague Tomesh, Zain H. Saleem, Michael A. Perlin, Pranav Gokhale, Martin Suchara, Margaret Martonosi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Scaling the size of monolithic quantum computer systems is a difficult task. As the number of qubits within a device increases, a number of factors contribute to decreases in yield and performance. To meet this challenge, distributed architectures composed of many networked quantum computers have been proposed as a viable path to scalability. Such systems will need algorithms and compilers that are tailored to their distributed architectures. In this work we introduce the Quantum Divide and Conquer Algorithm (QDCA), a hybrid variational approach to mapping large combinatorial optimization problems onto distributed quantum architectures. This is achieved through the combined use of graph partitioning and quantum circuit cutting. The QDCA, an example of application-compiler co-design, alters the structure of the variational ansatz to tame the exponential compilation overhead incurred by quantum circuit cutting. The result of this cross-layer co-design is a highly flexible algorithm which can be tuned to the amount of classical or quantum computational resources that are available, and can be applied to both near- and long-term distributed quantum ar-chitectures. We simulate the QDCA on instances of the Maximum Independent Set problem and find that it is able to outperform similar classical algorithms. We also evaluate an 8-qubit QDCA ansatz on a superconducting quantum computer and show that circuit cutting can help to mitigate the effects of noise. Our work demonstrates how many small-scale quantum computers canwork together to solve problems 85 % larger than their own qubit count, motivating the development and potential of large-scale distributed quantum computing.

Original languageEnglish (US)
Title of host publicationProceedings - 2023 IEEE International Conference on Quantum Computing and Engineering, QCE 2023
EditorsHausi Muller, Yuri Alexev, Andrea Delgado, Greg Byrd
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1-12
Number of pages12
ISBN (Electronic)9798350343236
DOIs
StatePublished - 2023
Externally publishedYes
Event4th IEEE International Conference on Quantum Computing and Engineering, QCE 2023 - Bellevue, United States
Duration: Sep 17 2023Sep 22 2023

Publication series

NameProceedings - 2023 IEEE International Conference on Quantum Computing and Engineering, QCE 2023
Volume1

Conference

Conference4th IEEE International Conference on Quantum Computing and Engineering, QCE 2023
Country/TerritoryUnited States
CityBellevue
Period9/17/239/22/23

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Hardware and Architecture
  • Signal Processing
  • Electrical and Electronic Engineering
  • Computational Mathematics
  • Theoretical Computer Science
  • Atomic and Molecular Physics, and Optics
  • Computer Science (miscellaneous)

Keywords

  • Quantum computing
  • circuit cutting
  • combinatorial optimization

Fingerprint

Dive into the research topics of 'Divide and Conquer for Combinatorial Optimization and Distributed Quantum Computation'. Together they form a unique fingerprint.

Cite this