A Multilevel Framework for Partitioning Quantum Circuits

• URL: http://arxiv.org/abs/2503.19082v3
• Date: Fri, 18 Apr 2025 18:14:00 GMT
• Title: A Multilevel Framework for Partitioning Quantum Circuits
• Authors: Felix Burt, Kuan-Cheng Chen, Kin K. Leung,
• Abstract summary: This paper formalises and extends existing constructions for quantum circuit partitioning.<n>We explore multilevel techniques that coarsen hypergraphs and partition at multiple levels of granularity.<n>We find that this reduces runtime and improves solution quality of standard partitioning.
• Score: 2.9078970632232104
• License: http://creativecommons.org/licenses/by/4.0/
• 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 can achieve the lowest entanglement costs in most cases, while always being close to the best performing method. We achieve an average improvement of 33% over the next best performing method across a wide range of circuits. We also find that our techniques can scale to much larger circuit sizes than state-of-the-art methods, provided the number of partitions is not too large.

Related papers

• Spatial and temporal circuit cutting with hypergraphic partitioning [0.0]
  This paper presents a hypergraph-based circuit cutting methodology suitable for both spatial and temporal scenarios. By modeling quantum circuits as high-level hypergraphs, we apply partitionings such as Stoer-Wagner, Fiduccia-Mattheyses, and Kernighan-Lin.
  arXiv  Detail & Related papers  (2025-04-12T20:31:07Z)
• Circuit Folding: Modular and Qubit-Level Workload Management in Quantum-Classical Systems [5.6744988702710835]
  Circuit knitting is a technique that offloads some of the computational burden from quantum circuits.<n>We propose CiFold, a novel graph-based system that identifies and leverages repeated structures within quantum circuits.<n>Our system has been extensively evaluated across various quantum algorithms, achieving up to 799.2% reduction in quantum resource usage.
  arXiv  Detail & Related papers  (2024-12-24T23:34:17Z)
• Quantum Compiling with Reinforcement Learning on a Superconducting Processor [55.135709564322624]
  We develop a reinforcement learning-based quantum compiler for a superconducting processor. We demonstrate its capability of discovering novel and hardware-amenable circuits with short lengths. Our study exemplifies the codesign of the software with hardware for efficient quantum compilation.
  arXiv  Detail & Related papers  (2024-06-18T01:49:48Z)
• Attention-Based Deep Reinforcement Learning for Qubit Allocation in Modular Quantum Architectures [1.8781124875646162]
  This research contributes to the advancement of scalable quantum computing systems by introducing a novel learning-based approach for efficient quantum circuit compilation and mapping. In this work, we propose a novel approach employing Deep Reinforcement Learning (DRL) methods to learn theses for a specific multi-core architecture.
  arXiv  Detail & Related papers  (2024-06-17T12:09:11Z)
• A Genetic Approach to Minimising Gate and Qubit Teleportations for Multi-Processor Quantum Circuit Distribution [6.207327488572861]
  Distributed Quantum Computing (DQC) provides a means for scaling available quantum computation by interconnecting multiple quantum processor units (QPUs) A key challenge in this domain is efficiently allocating logical qubits from quantum circuits to the physical qubits within QPUs, a task known to be NP-hard. Traditional approaches have sought to reduce the number of required Bell pairs for executing non-local CNOT operations, a form of gate teleportation. We introduce a novel meta-heuristic algorithm to minimise the network cost of executing a quantum circuit.
  arXiv  Detail & Related papers  (2024-05-09T16:03:41Z)
• Scaling Up the Quantum Divide and Conquer Algorithm for Combinatorial Optimization [0.8121127831316319]
  We propose a method for constructing quantum circuits which greatly reduces inter-device communication costs. We show that we can construct tractable circuits nearly three times the size of previous QDCA methods while retaining a similar or greater level of quality.
  arXiv  Detail & Related papers  (2024-05-01T20:49:50Z)
• Minimizing the Number of Teleportations in Distributed Quantum Computing Using Alloy [0.0]
  This paper presents a novel approach for minimizing the number of teleportations in Distributed Quantum Computing (DQC) using formal methods. We develop a software tool, called qcAlloy, that takes as input the textual description of a quantum circuit, generates the corresponding Alloy model, and finally solves the problem. We have experimentally evaluated qcAlloy for some of the circuits in the RevLib benchmark with more than 100 qubits and 1200 layers.
  arXiv  Detail & Related papers  (2024-04-24T16:55:29Z)
• QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum Circuits [82.50620782471485]
  QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits. It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness. Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
  arXiv  Detail & Related papers  (2024-01-10T22:33:00Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Near-Term Distributed Quantum Computation using Mean-Field Corrections and Auxiliary Qubits [77.04894470683776]
  We propose near-term distributed quantum computing that involve limited information transfer and conservative entanglement production. We build upon these concepts to produce an approximate circuit-cutting technique for the fragmented pre-training of variational quantum algorithms.
  arXiv  Detail & Related papers  (2023-09-11T18:00:00Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.