In quantum circuit optimization, circuit partitioning enables the optimization process to be parallelized across multiple devices. Each device is responsible for either reducing the number of selected gates or simplifying the local circuit structure. Most existing approaches to circuit partitioning are quantum-distribution-oriented and rely on splitting CNOT gates by introducing mid-circuit measurements and qubit resets. Currently, there is no criterion to determine how a circuit can be optimally partitioned without removing the CNOT gates for circuit optimization purposes. To address this challenge, we formalize the partition problem as a cutting path through a maze, where the CNOT gates represent the walls. We show that the existence of such a path separates quantum circuits into two classes through a percolation phase transition. In particular, it distinguishes a partitionable regime from a nonpartitionable one, arising from qubit permutations. Such permutations are generated by simulated annealing. We analyze its effect on the CNOT cluster from the perspective of network science and distribution analysis. Our results show that partitioning into two CNOT clusters is possible when the number of CNOTs is almost equal to the number of qubits. Based on this observation, we provide a scalable and practical criterion for identifying whether such a partition exists. Overall, our framework provides theoretical and numerical insight into circuit partitioning within quantum circuit optimization, forming the basis for algorithmic development.
Comments
Main text: 16 pages, 6 figures. Supplementary material: 16 pages, 10 figures. M. Guatto and F. Preti contributed equally to this work
In quantum circuit optimization, circuit partitioning enables the optimization process to be parallelized across multiple devices. Each device is responsible for either reducing the number of selected gates or simplifying the local circuit structure. Most existing approaches to circuit partitioning are quantum-distribution-oriented and rely on splitting CNOT gates by introducing mid-circuit measurements and qubit resets. Currently, there is no criterion to determine how a circuit can be optimally partitioned without removing the CNOT gates for circuit optimization purposes. To address this challenge, we formalize the partition problem as a cutting path through a maze, where the CNOT gates represent the walls. We show that the existence of such a path separates quantum circuits into two classes through a percolation phase transition. In particular, it distinguishes a partitionable regime from a nonpartitionable one, arising from qubit permutations. Such permutations are generated by simulated annealing. We analyze its effect on the CNOT cluster from the perspective of network science and distribution analysis. Our results show that partitioning into two CNOT clusters is possible when the number of CNOTs is almost equal to the number of qubits. Based on this observation, we provide a scalable and practical criterion for identifying whether such a partition exists. Overall, our framework provides theoretical and numerical insight into circuit partitioning within quantum circuit optimization, forming the basis for algorithmic development.
The current noisy intermediate-scale quantum (NISQ) era is characterized by substantial errors and noise, which limit the practical feasibility of deep, many-qubit circuits. To address these constraints, quantum circuit cutting has emerged as a promising tool. Recently, there has been significant research on methods for performing such cutting effectively. In this work, the duality between quantum circuits and classical graphs - specifically, directed acyclic graphs (dags) - is leveraged to analyze the complexity of finding an optimal circuit-cutting configuration that minimizes the number of cuts. After developing a rigorous graph-theoretic framework, the complexity of identifying cut locations that partition a given quantum circuit into smaller fragments is characterized. The corresponding graph-combinatorial task is then defined, and the resulting partition problem is shown to be NP-complete. Furthermore, even a simplified version of the problem, restricted to circuits composed only of one- and two-qubit gates, is shown to be NP-complete. Finally, based on these constraints, an algorithm grounded in satisfiability modulo theories (SMT) is proposed to find optimal cuts when the number of qubits per partition is bounded. This work therefore provides a complexity-theoretic characterization of cut placement and a practical solver for bounded-size decompositions.
Quantum circuit cutting enables the execution of large circuits on devices with a limited number of qubits by partitioning circuits into independent subcircuits. However, this introduces a sampling overhead, which grows exponentially with the number of cuts, rendering the choice of cut placements critical for practical circuit cutting. Determining optimal cut placements remains computationally challenging, particularly as circuits grow in size. Additionally, existing circuit cutting approaches typically treat gate and wire cuts independently. Those combining both cutting approaches, however, do not take advantage of joint cutting, i.e., identifying common gate groups and cutting them jointly for a reduced overhead. This work presents a unified framework that combines gate and wire cutting within a single partitioning strategy, enabling more efficient circuit decompositions. Moreover, our approach incorporates joint cutting via a novel gate grouping technique, further reducing sampling overhead. By formulating the cut placement problem as a scalable graph partitioning task, our method efficiently identifies near-optimal cut placements for large circuits, also providing diagnostic feedback on whether circuits are suitable for cutting.
The current phase of quantum computing is in the Noisy Intermediate-Scale Quantum (NISQ) era. On NISQ devices, two-qubit gates such as CNOTs are much noisier than single-qubit gates, so it is essential to minimize their count. Quantum circuit synthesis is a process of decomposing an arbitrary unitary into a sequence of quantum gates, and can be used as an optimization tool to produce shorter circuits to improve overall circuit fidelity. However, the time-to-solution of synthesis grows exponentially with the number of qubits. As a result, synthesis is intractable for circuits on a large qubit scale. In this paper, we propose a hierarchical, block-by-block optimization framework, QGo, for quantum circuit optimization. Our approach allows an exponential cost optimization to scale to large circuits. QGo uses a combination of partitioning and synthesis: 1) partition the circuit into a sequence of independent circuit blocks; 2) re-generate and optimize each block using quantum synthesis; and 3) re-compose the final circuit by stitching all the blocks together. We perform our analysis and show the fidelity improvements in three different regimes: small-size circuits on real devices, medium-size circuits on noise simulations, and large-size circuits on analytical models. Using a set of NISQ benchmarks, we show that QGo can reduce the number of CNOT gates by 29.9% on average and up to 50% when compared with industrial compilers such as t|ket>. When executed on the IBM Athens system, shorter depth leads to higher circuit fidelity. We also demonstrate the scalability of our QGo technique to optimize circuits of 60+ qubits. Our technique is the first demonstration of successfully employing and scaling synthesis in the compilation toolchain for large circuits. Overall, our approach is robust for direct incorporation in production compiler toolchains.
Given the limitations on the number of qubits in current noisy intermediate-scale quantum (NISQ) devices, the implementation of large-scale quantum algorithms on such devices is challenging, prompting research into distributed quantum computing. This article focuses on the issue of excessive communication complexity in distributed quantum computing based on the quantum circuit model. To reduce the number of quantum state transmissions, i.e., the transmission cost, in distributed quantum circuits, a circuit partitioning method based on the quadratic unconstrained binary optimization (QUBO) model is proposed, coupled with the lookahead method for transmission cost optimization. Initially, the problem of distributed quantum circuit partitioning is transformed into a graph minimum cut problem. The QUBO model, which can be accelerated by quantum annealing algorithms, is introduced to minimize the number of quantum gates between quantum processing units (QPUs) and the transmission cost. Subsequently, the dynamic lookahead strategy for the selection of transmission qubits is proposed to optimize the transmission cost in distributed quantum circuits. Finally, through numerical simulations, the impact of different circuit partitioning indicators on the transmission cost is explored, and the proposed method is evaluated on benchmark circuits. Experimental results demonstrate that the proposed circuit partitioning method has a shorter runtime compared with current circuit partitioning methods. Additionally, the transmission cost optimized by the proposed method is significantly lower than that of current transmission cost optimization methods, achieving noticeable improvements across different numbers of partitions.
CNOT optimization plays a significant role in noise reduction for Quantum Circuits. Several heuristic and exact approaches exist for CNOT optimization. In this paper, we investigate more complicated variations of optimal synthesis by allowing qubit permutations and handling layout restrictions. We encode such problems into Planning, SAT, and QBF. We provide optimization for both CNOT gate count and circuit depth. For experimental evaluation, we consider standard T-gate optimized benchmarks and optimize CNOT sub-circuits. We show that allowing qubit permutations can further reduce up to 56% in CNOT count and 46% in circuit depth. In the case of optimally mapped circuits under layout restrictions, we observe a reduction up to 17% CNOT count and 19% CNOT depth.
The current phase of quantum computing is in the Noisy Intermediate-Scale Quantum (NISQ) era. On NISQ devices, two-qubit gates such as CNOTs are much noisier than single-qubit gates, so it is essential to minimize their count. Quantum circuit synthesis is a process of decomposing an arbitrary unitary into a sequence of quantum gates, and can be used as an optimization tool to produce shorter circuits to improve overall circuit fidelity. However, the time-to-solution of synthesis grows exponentially with the number of qubits. As a result, synthesis is intractable for circuits on a large qubit scale.
In this paper, we propose a hierarchical, block-by-block optimization framework, QGo, for quantum circuit optimization. Our approach allows an exponential cost optimization to scale to large circuits. QGo uses a combination of partitioning and synthesis: 1) partition the circuit into a sequence of independent circuit blocks; 2) re-generate and optimize each block using quantum synthesis; and 3) re-compose the final circuit by stitching all the blocks together. We perform our analysis and show the fidelity improvements in three different regimes: small-size circuits on real devices, medium-size circuits on noise simulations, and large-size circuits on analytical models. Using a set of NISQ benchmarks, we show that QGo can reduce the number of CNOT gates by 29.9% on average and up to 50% when compared with industrial compilers such as t|ket>. When executed on the IBM Athens system, shorter depth leads to higher circuit fidelity. We also demonstrate the scalability of our QGo technique to optimize circuits of 60+ qubits. Our technique is the first demonstration of successfully employing and scaling synthesis in the compilation toolchain for large circuits. Overall, our approach is robust for direct incorporation in production compiler toolchains.