Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

On Optimal Subarchitectures for Quantum Circuit Mapping

On Optimal Subarchitectures for Quantum Circuit Mapping Compiling a high-level quantum circuit down to a low-level description that can be executed on state-of-the-art quantum computers is a crucial part of the software stack for quantum computing. One step in compiling a quantum circuit to some device is quantum circuit mapping, where the circuit is transformed such that it complies with the architecture’s limited qubit connectivity. Because the search space in quantum circuit mapping grows exponentially in the number of qubits, it is desirable to consider as few of the device’s physical qubits as possible in the process. Previous work conjectured that it suffices to consider only subarchitectures of a quantum computer composed of as many qubits as used in the circuit. In this work, we refute this conjecture and establish criteria for judging whether considering larger parts of the architecture might yield better solutions to the mapping problem. We show that determining subarchitectures that are of minimal size, i.e., from which no physical qubit can be removed without losing the optimal mapping solution for some quantum circuit, is a very hard problem. Based on a relaxation of the criteria for optimality, we introduce a relaxed consideration that still maintains optimality for practically relevant quantum circuits. Eventually, this results in two methods for computing near-optimal sets of subarchitectures—providing the basis for efficient quantum circuit mapping solutions. We demonstrate the benefits of this novel method for state-of-the-art quantum computers by IBM, Google and Rigetti. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Quantum Computing Association for Computing Machinery

On Optimal Subarchitectures for Quantum Circuit Mapping

Download PDF
19 pages

Loading next page...
 
/lp/association-for-computing-machinery/on-optimal-subarchitectures-for-quantum-circuit-mapping-aoCEuSXuua
Publisher
Association for Computing Machinery
Copyright
Copyright © 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM.
ISSN
2643-6809
eISSN
2643-6817
DOI
10.1145/3593594
Publisher site
See Article on Publisher Site

Abstract

Compiling a high-level quantum circuit down to a low-level description that can be executed on state-of-the-art quantum computers is a crucial part of the software stack for quantum computing. One step in compiling a quantum circuit to some device is quantum circuit mapping, where the circuit is transformed such that it complies with the architecture’s limited qubit connectivity. Because the search space in quantum circuit mapping grows exponentially in the number of qubits, it is desirable to consider as few of the device’s physical qubits as possible in the process. Previous work conjectured that it suffices to consider only subarchitectures of a quantum computer composed of as many qubits as used in the circuit. In this work, we refute this conjecture and establish criteria for judging whether considering larger parts of the architecture might yield better solutions to the mapping problem. We show that determining subarchitectures that are of minimal size, i.e., from which no physical qubit can be removed without losing the optimal mapping solution for some quantum circuit, is a very hard problem. Based on a relaxation of the criteria for optimality, we introduce a relaxed consideration that still maintains optimality for practically relevant quantum circuits. Eventually, this results in two methods for computing near-optimal sets of subarchitectures—providing the basis for efficient quantum circuit mapping solutions. We demonstrate the benefits of this novel method for state-of-the-art quantum computers by IBM, Google and Rigetti.

Journal

ACM Transactions on Quantum Computing – Association for Computing Machinery

Published: Jan 1, 1

References

  • Quantum Computation and Quantum Information
    Nielsen, Michael A.; Chuang, Isaac L.
  • Superconducting circuits for quantum information: An outlook
    Devoret, M. H.; Schoelkopf, R. J.
  • Synthesis of quantum circuits for linear nearest neighbor architectures
    Saeedi, Mehdi; Wille, Robert; Drechsler, Rolf
  • Qubit allocation
    Siraichi, Marcos Yukio; family=Santos, prefix=dos useprefix=false; given=Vinícius Fernandes, ; Collange, Caroline; Pereira, Fernando Magno Quintao
  • An exact qubit allocation approach for NISQ architectures
    Zhu, Pengcheng; Cheng, Xueyun; Guan, Zhijin
  • On the qubit routing problem
    Cowtan, Alexander; Dilkes, Silas; Duncan, Ross; Krajenbrink, Alexandre; Simmons, Will; Sivarajah, Seyon
  • Automated optimization of large quantum circuits with continuous parameters
    Nam, Yunseong; Ross, Neil J.; Su, Yuan; Childs, Andrew M.; Maslov, Dmitri
  • Reducing T-count with the ZX-calculus
    Kissinger, Aleks; family=Wetering, prefix=van de useprefix=true; given=John,
  • Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers
    Murali, Prakash; Baker, Jonathan M.; Javadi-Abhari, Ali; Chong, Frederic T.; Martonosi, Margaret
  • Limiting the search space in optimal quantum circuit mapping
    Burgholzer, Lukas; Schneider, Sarah; Wille, Robert
  • Mapping quantum circuits to IBM QX architectures using the minimal number of SWAP and H operations
    Wille, Robert; Burgholzer, Lukas; Zulehner, Alwin
  • An efficient methodology for mapping quantum circuits to the IBM QX architectures
    Zulehner, Alwin; Paler, Alexandru; Wille, Robert
  • Compiling SU(4) quantum circuits to IBM QX architectures
    Zulehner, Alwin; Wille, Robert
  • Exploiting Quantum Teleportation in Quantum Circuit Mapping
    Hillmich, Stefan; Zulehner, Alwin; Wille, Robert
  • On the complexity of quantum circuit compilation
    Botea, A.; Kishimoto, A.; Marinescu, Radu
  • IBM’s Roadmap For Scaling Quantum Technology
    Gambetta, Jay
  • Quantum computing in the NISQ era and beyond
    Preskill, John
  • Graph Theory
    Bondy, Adrian; Murty, Uppaluri Siva Ramachandra
  • Quantum circuit placement: Optimizing qubit-to-qubit interactions through mapping quantum circuits into a physical experiment
    Maslov, Dmitri; Falconer, Sean M.; Mosca, Michele
  • Optimality study of existing quantum computing layout synthesis tools
    Tan, B.; Cong, J.
  • Tackling the qubit mapping problem for NISQ-era quantum devices
    Li, Gushu; Ding, Yufei; Xie, Yuan
  • Optimal layout synthesis for quantum computing
    Tan, Bochen; Cong, Jason
  • Qubit routing using graph neural network aided Monte Carlo tree search
    Sinha, Animesh; Azad, Utkarsh; Singh, Harjinder
  • Machine learning optimization of quantum circuit layouts
    Paler, Alexandru; Sasu, Lucian M.; Florea, Adrian-Cătălin; Andonie, Răzvan
  • A novel ant colony optimization strategy for the quantum circuit compilation problem
    Baioletti, Marco; Rasconi, Riccardo; Oddi, Angelo
  • Using reinforcement learning to perform qubit routing in quantum compilers
    Pozzi, Matteo G.; Herbert, Steven J.; Sengupta, Akash; Mullins, Robert D.
  • Exploring the Potential Benefits of Alternative Quantum Computing Architectures
    Deb, Arighna; Dueck, Gerhard W.; Wille, Robert
  • MQT QMAP: Efficient Quantum Circuit Mapping
    Wille, R.; Burgholzer, L.
  • retworkx: A high-performance graph library for python
    Treinish, Matthew; Carvalho, Ivan; Tsilimigkounakis, Georgios; Sá, Nahum
  • A (sub)graph isomorphism algorithm for matching large graphs
    Cordella, Luigi; Foggia, Pasquale; Sansone, Carlo; Vento, Mario
  • The complexity of theorem-proving procedures
    Cook, Stephen A.
  • MQT Bench: Benchmarking software and design automation tools for quantum computing
    Quetschlich, Nils; Burgholzer, Lukas; Wille, Robert
  • mapomatic
    Nation, Paul; Treinish, Matthew