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:2609.30141

Optimal Two-Qubit Gate-Cutting Cost and Measures of Nonlocality

Michael Hart

quant-phSubmitted Sep 24, 2026• Announced Sep 25, 2026• 0 citations
arXivHTMLPDF

Abstract

Circuit cutting enables quantum computations to be decomposed into smaller subcircuits at the cost of additional sampling overhead. Gate-cutting provides one such approach by replacing nonlocal gates with quasiprobability decompositions of local operations. Starting from the known optimal two-qubit gate-cutting formula, we derive complete sharp lower and upper envelopes relating the quasiprobability extent $γ$ to five established descriptors: entangling power, gate typicality, operator entanglement, Schmidt strength, and maximum product-input concurrence. We recast $γ$ as a Rényi-$1/2$ functional of the operator-Schmidt spectrum and show how the physical constraints on two-qubit spectra sharpen generic entropy bounds and select a small set of recurring extremal Cartan families. None of the five descriptors generically determines $γ$ alone, but each imposes exact constraints, revealing how substantially the optimal gate-cutting cost can vary between gates with similar nonlocal characteristics.

Comments
38 pages, 10 figures

Related papers

Cutting circuits with multiple two-qubit unitaries

Lukas Schmitt, Christophe Piveteau, David Sutter

Quasiprobabilistic cutting techniques allow us to partition large quantum circuits into smaller subcircuits by replacing non-local gates with probabilistic mixtures of local gates. The cost of this method is a sampling overhead that scales exponentially in the number of cuts. It is crucial to determine the minimal cost for gate cutting and to understand whether allowing for classical communication between subcircuits can improve the sampling overhead. In this work, we derive a closed formula for the optimal sampling overhead for cutting an arbitrary number of two-qubit unitaries and provide the corresponding decomposition. We find that cutting several arbitrary two-qubit unitaries together is cheaper than cutting them individually and classical communication does not give any advantage.

arXiv:2312.11638•Quantum•Feb 18, 2025•12 citations

On the Experimental Determination of Nonlocal Characteristics of Two-Qubit Gates

M. Karthick Selvan, S. Balakrishnan

In this paper, we discuss the experimental determination of the nonlocal characteristics of two-qubit gates. Based on the recently derived expressions for the entangling power and gate typicality of two-qubit gates, we construct two-qubit quantum circuits to measure the entangling power and gate typicality of the two-qubit gates, which are generated by the elements of the su(4) Cartan subalgebra. These elements describe the native interactions in many quantum processors. Hence, these circuits can be used to determine the nonlocal characteristics of native gates of many quantum processors. In each circuit, the native gate is applied twice. In addition, each circuit consists of at least one CNOT gate. A set of six two-qubit circuits is constructed to measure the entangling power. The number of circuits is further reduced to three by increasing the nonlocal resources (the number of CNOT gates). To measure the gate typicality, a set of three two-qubit circuits is constructed. Measurement of gate typicality requires more nonlocal resources than the measurement of entangling power.

quant-pharXiv:2607.11973•Jul 14, 2026•0 citations

Decomposition of Multi-Qubit Gates for Circuit Cutting

Ryota Tamura, Tomoya Kashimata, Yohei Hamakawa +2 more

A large-scale quantum circuit can be partitioned into multiple subcircuits through circuit cutting, where each subcircuit is executed multiple times and the expectation value of the original circuit is reconstructed by classical post-processing from their measurement (sampling) results. In this process, appropriate cut locations are identified after the user-designed quantum circuit, including multi-qubit gates that act on three or more qubits, has been decomposed into single-qubit gates and two-qubit gates such as the CNOT gate. Here, we present a method for reducing the sampling overhead, which refers to the increase in the number of samples required due to the cutting process, by modifying the decomposition strategy of multi-qubit gates. Using MCX and CCCX gates as representatives of multi-qubit gates, we demonstrate that the proposed decomposition method, which introduces a small number of ancilla qubits according to the identified cut locations, effectively decreases the sampling overhead.

quant-pharXiv:2603.26278•Mar 30, 2026•0 citations

Optimal joint cutting of two-qubit rotation gates

Christian Ufrecht, Laura S. Herzog, Daniel D. Scherer +4 more

Circuit cutting, the partitioning of quantum circuits into smaller independent fragments, has become a promising avenue for scaling up current quantum-computing experiments. Here, we introduce a scheme for joint cutting of two-qubit rotation gates based on a virtual gate-teleportation protocol. With that, we significantly lower the previous upper bounds on the sampling overhead and prove the optimality of the scheme. Furthermore, we show that no classical communication between the circuit partitions is required. For parallel two-qubit rotation gates we derive an optimal ancilla-free decomposition, which includes cnot gates as a special case.

arXiv:2312.09679•Physical Review A•May 30, 2024•16 citations

All this for one qubit? Bounds on local circuit cutting schemes

Simon C. Marshall, Tura, Jordi, Vedran Dunjko

Small numbers of qubits are one of the primary constraints on the near-term deployment of advantageous quantum computing. To mitigate this constraint, techniques have been developed to break up a large quantum computation into smaller computations. While this work is sometimes called circuit knitting or divide and quantum we generically refer to it as circuit cutting (CC). Much of the existing work has focused on the development of more efficient circuit cutting schemes, leaving open questions on the limits of what theoretically optimal schemes can achieve. We develop bounds by breaking up possible approaches into two distinct regimes: the first, where the input state and measurement are fixed and known, and the second, which requires a given cutting to work for a complete basis of input states and measurements. For the first case, it is easy to see that bounds addressing the efficiency of any approaches to circuit cutting amount to resolving BPP$\stackrel{?}{=}$BQP. We therefore restrict ourselves to a simpler question, asking what \textit{locally-acting} circuit cutting schemes can achieve, a technical restriction which still includes all existing circuit cutting schemes. In our first case we show that the existence of a locally-acting circuit cutting scheme which could efficiently partition even a single qubit from the rest of a circuit would imply BPP$=$BQP. In our second case, we obtain more general results, showing inefficiency unconditionally. We also show that any (local or otherwise) circuit cutting scheme cannot function by only applying unital channels.

arXiv:2303.13422•Mar 23, 2023•1 citation

Quantum Circuit Cutting: Complexity and Optimization

Yuval Idan, Eitan Zahavi, Elad Mentovich +2 more

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.

quant-pharXiv:2604.23700•Apr 28, 2026•0 citations
Circuit cutting enables quantum computations to be decomposed into smaller subcircuits at the cost of additional sampling overhead. Gate-cutting provides one such approach by replacing nonlocal gates with quasiprobability decompositions of local operations. Starting from the known optimal two-qubit gate-cutting formula, we derive complete sharp lower and upper envelopes relating the quasiprobability extent γγγ to five established descriptors: entangling power, gate typicality, operator entanglement, Schmidt strength, and maximum product-input concurrence. We recast γγγ as a Rényi-1/21/21/2 functional of the operator-Schmidt spectrum and show how the physical constraints on two-qubit spectra sharpen generic entropy bounds and select a small set of recurring extremal Cartan families. None of the five descriptors generically determines γγγ alone, but each imposes exact constraints, revealing how substantially the optimal gate-cutting cost can vary between gates with similar nonlocal characteristics.
Quasiprobabilistic cutting techniques allow us to partition large quantum circuits into smaller subcircuits by replacing non-local gates with probabilistic mixtures of local gates. The cost of this method is a sampling overhead that scales exponentially in the number of cuts. It is crucial to determine the minimal cost for gate cutting and to understand whether allowing for classical communication between subcircuits can improve the sampling overhead. In this work, we derive a closed formula for the optimal sampling overhead for cutting an arbitrary number of two-qubit unitaries and provide the corresponding decomposition. We find that cutting several arbitrary two-qubit unitaries together is cheaper than cutting them individually and classical communication does not give any advantage.
In this paper, we discuss the experimental determination of the nonlocal characteristics of two-qubit gates. Based on the recently derived expressions for the entangling power and gate typicality of two-qubit gates, we construct two-qubit quantum circuits to measure the entangling power and gate typicality of the two-qubit gates, which are generated by the elements of the su(4) Cartan subalgebra. These elements describe the native interactions in many quantum processors. Hence, these circuits can be used to determine the nonlocal characteristics of native gates of many quantum processors. In each circuit, the native gate is applied twice. In addition, each circuit consists of at least one CNOT gate. A set of six two-qubit circuits is constructed to measure the entangling power. The number of circuits is further reduced to three by increasing the nonlocal resources (the number of CNOT gates). To measure the gate typicality, a set of three two-qubit circuits is constructed. Measurement of gate typicality requires more nonlocal resources than the measurement of entangling power.
A large-scale quantum circuit can be partitioned into multiple subcircuits through circuit cutting, where each subcircuit is executed multiple times and the expectation value of the original circuit is reconstructed by classical post-processing from their measurement (sampling) results. In this process, appropriate cut locations are identified after the user-designed quantum circuit, including multi-qubit gates that act on three or more qubits, has been decomposed into single-qubit gates and two-qubit gates such as the CNOT gate. Here, we present a method for reducing the sampling overhead, which refers to the increase in the number of samples required due to the cutting process, by modifying the decomposition strategy of multi-qubit gates. Using MCX and CCCX gates as representatives of multi-qubit gates, we demonstrate that the proposed decomposition method, which introduces a small number of ancilla qubits according to the identified cut locations, effectively decreases the sampling overhead.
Circuit cutting, the partitioning of quantum circuits into smaller independent fragments, has become a promising avenue for scaling up current quantum-computing experiments. Here, we introduce a scheme for joint cutting of two-qubit rotation gates based on a virtual gate-teleportation protocol. With that, we significantly lower the previous upper bounds on the sampling overhead and prove the optimality of the scheme. Furthermore, we show that no classical communication between the circuit partitions is required. For parallel two-qubit rotation gates we derive an optimal ancilla-free decomposition, which includes cnot gates as a special case.
Small numbers of qubits are one of the primary constraints on the near-term deployment of advantageous quantum computing. To mitigate this constraint, techniques have been developed to break up a large quantum computation into smaller computations. While this work is sometimes called circuit knitting or divide and quantum we generically refer to it as circuit cutting (CC). Much of the existing work has focused on the development of more efficient circuit cutting schemes, leaving open questions on the limits of what theoretically optimal schemes can achieve. We develop bounds by breaking up possible approaches into two distinct regimes: the first, where the input state and measurement are fixed and known, and the second, which requires a given cutting to work for a complete basis of input states and measurements. For the first case, it is easy to see that bounds addressing the efficiency of any approaches to circuit cutting amount to resolving BPP=?\stackrel{?}{=}=?BQP. We therefore restrict ourselves to a simpler question, asking what \textit{locally-acting} circuit cutting schemes can achieve, a technical restriction which still includes all existing circuit cutting schemes. In our first case we show that the existence of a locally-acting circuit cutting scheme which could efficiently partition even a single qubit from the rest of a circuit would imply BPP===BQP. In our second case, we obtain more general results, showing inefficiency unconditionally. We also show that any (local or otherwise) circuit cutting scheme cannot function by only applying unital channels.
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.