A Multilevel Framework for Partitioning Quantum Circuits

Abstract

Executing quantum algorithms over distributed quantum systems requires quantum circuits to be divided into sub-circuits which communicate via entanglement-based teleportation. Naively mapping circuits to qubits over multiple quantum processing units (QPUs) results in large communication overhead, increasing both execution time and noise. This can be minimised by optimising the assignment of qubits to QPUs and the methods used for covering non-local operations. Formulations that are general enough to capture the spectrum of teleportation possibilities lead to complex problem instances which can be difficult to solve effectively. This highlights a need to exploit the wide range of heuristic techniques used in the graph partitioning literature. This paper formalises and extends existing constructions for graphical quantum circuit partitioning and designs a new objective function that captures further possibilities for non-local operations via nested state teleportation. We adapt the well-known Fiduccia-Mattheyses heuristic to the constraints and problem objective and explore multilevel techniques that coarsen hypergraphs and partition at multiple levels of granularity. We find that this reduces runtime and improves solution quality of standard partitioning. We place these techniques within a larger framework, through which we can extract full distributed quantum circuits including teleportation instructions. We compare the entanglement requirements and runtimes with state-of-the-art methods, finding that we achieve the lowest entanglement costs in most cases. Averaging over a wide range of circuits, we reduce the entanglement requirements by 35% compared with the next best-performing method. We also find that our techniques can scale to much larger circuit sizes than competing methods, provided the number of partitions is not too large.

47 pages, 33 figures

References in corpus (17)

• A Quantum Approximate Optimization Algorithm
• t$|$ket$⟩$ : A Retargetable Compiler for NISQ Devices
• Quantum computing with Qiskit
• CutQC: Using Small Quantum Computers for Large Quantum Circuit Evaluations
• Time-Sliced Quantum Circuit Partitioning for Modular Architectures
• Hungarian Qubit Assignment for Optimized Mapping of Quantum Circuits on Multi-Core Architectures
• Distributed Quantum Computing in Silicon
• Cutting Quantum Circuits to Run on Quantum and Classical Platforms
• Entanglement-Efficient Distribution of Quantum Circuits over Large-Scale Quantum Networks
• Tour de gross: A modular quantum computer based on bivariate bicycle codes
• Lattice surgery-based logical state teleportation via noisy links
• Optimized noise-resilient surface code teleportation interfaces
• Distributed quantum error correction based on hyperbolic Floquet codes
• Extractors: QLDPC Architectures for Efficient Pauli-Based Computation
• Transversal Fault Tolerant Distributed Quantum Computing Operations
• Lattice surgery with Bell measurements: Modular fault-tolerant quantum computation at low entanglement cost
• Binary integer programming for optimizing ebit cost in distributed quantum circuits with fixed module allocation