Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2005.11614 · International Journal of Theoretical Physics

Optimized Quantum Circuit Partitioning

Omid Daei, Keivan Navi, Mariam Zomorodi Moghadam

Published Nov 6, 2020• 79 citations
arXivHTMLPDF
DOI
10.1007/s10773-020-04633-8

Related papers

Optimal Partitioning of Quantum Circuits Using Gate Cuts and Wire Cuts

Sebastian Brandhofer, Ilia Polian, Kevin Krsulich

A limited number of qubits, high error rates, and limited qubit connectivity are major challenges for effective near-term quantum computations. Quantum circuit partitioning divides a quantum computation into classical postprocessing steps and a set of smaller-scale quantum computations that individually require fewer qubits, lower qubit connectivity, and typically incur less error. However, as partitioning generally increases the duration of a quantum computation exponentially in the required partitioning effort, it is crucial to select optimal partitioning points, so-called cuts, and to use optimal cut realizations. In this work, we develop the first optimal partitioning method relying on quantum circuit knitting for optimal cut realizations and an optimal selection of wire cuts and gate cuts that trades off ancilla qubit insertions for a decrease in quantum computing time. Using this combination, the developed method demonstrates a reduction in quantum computing runtime by 41% on average compared to previous quantum circuit partitioning methods. Furthermore, the qubit requirement of the evaluated quantum circuits was reduced by 40% on average for a runtime budget of one hour and a sampling frequency of 1 kHz. These results highlight the optimality gap of previous quantum circuit partitioning methods and the possible extension in the computational reach of near-term quantum computers.

arXiv:2308.09567•IEEE Transactions on Quantum Engineering•Dec 26, 2023•30 citations

Optimal Quantum Circuit Mapping

Lukas Burgholzer, Robert Wille

Springer eBooks•Jan 1, 2026•0 citations

Circuit Partitioning and Transmission Cost Optimization in Distributed Quantum Circuits

Xinyu Chen, Zilu Chen, Pengcheng Zhu +2 more

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.

arXiv:2407.05953•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Mar 4, 2025•7 citations

Quantum circuit partition as a maze: emerging percolation transition via path finding

P. Zentilini, M. Guatto, F. Preti +4 more

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.

quant-pharXiv:2606.04070•Jun 3, 2026•0 citations

Quantum Circuits: Design and Optimization

George A. Kevrekidis

•Aug 17, 2018•0 citations

Cost Optimization Technique for Quantum Circuits

Anirban Basak, Arindam Sadhu, Kunal Das +1 more

International Journal of Theoretical Physics•Jul 2, 2019•6 citations
A limited number of qubits, high error rates, and limited qubit connectivity are major challenges for effective near-term quantum computations. Quantum circuit partitioning divides a quantum computation into classical postprocessing steps and a set of smaller-scale quantum computations that individually require fewer qubits, lower qubit connectivity, and typically incur less error. However, as partitioning generally increases the duration of a quantum computation exponentially in the required partitioning effort, it is crucial to select optimal partitioning points, so-called cuts, and to use optimal cut realizations. In this work, we develop the first optimal partitioning method relying on quantum circuit knitting for optimal cut realizations and an optimal selection of wire cuts and gate cuts that trades off ancilla qubit insertions for a decrease in quantum computing time. Using this combination, the developed method demonstrates a reduction in quantum computing runtime by 41% on average compared to previous quantum circuit partitioning methods. Furthermore, the qubit requirement of the evaluated quantum circuits was reduced by 40% on average for a runtime budget of one hour and a sampling frequency of 1 kHz. These results highlight the optimality gap of previous quantum circuit partitioning methods and the possible extension in the computational reach of near-term quantum computers.
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.
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.