arxiv: 2604.23700 · v1 · submitted 2026-04-26 · 🪐 quant-ph

Recognition: unknown

Quantum Circuit Cutting: Complexity and Optimization

Yuval Idan , Eitan Zahavi , Elad Mentovich , Eliahu Cohen , Shmuel Zaks

Authors on Pith no claims yet

Pith reviewed 2026-05-08 06:29 UTC · model grok-4.3

classification 🪐 quant-ph

keywords quantum circuit cuttingNP-completenessdirected acyclic graphscircuit partitioningsatisfiability modulo theoriesNISQ computingcomputational complexity

0 comments

The pith

The problem of optimally cutting quantum circuits to minimize cuts is NP-complete.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The authors leverage the duality between quantum circuits and directed acyclic graphs to define the task of partitioning the circuit into smaller pieces while minimizing cuts. They show this combinatorial problem is NP-complete. The result holds for a simplified setting using only one- and two-qubit gates. An SMT solver is proposed for cases where each partition has a bounded number of qubits. This matters because it clarifies the computational limits of using circuit cutting to make NISQ-era devices handle deeper circuits.

Core claim

By establishing a duality between quantum circuits and directed acyclic graphs, the paper defines a graph partition problem whose goal is to divide the graph into subgraphs with bounded size while minimizing the number of edges that are cut. This partition problem is proven to be NP-complete, and the same hardness result holds for the restricted case of circuits consisting solely of one- and two-qubit gates.

What carries the argument

The reduction of the quantum circuit cutting problem to a minimum-cut partition problem on the directed acyclic graph representation of the circuit, which encodes the dependencies and allows combinatorial analysis of cut placements.

Load-bearing premise

The assumption that every aspect of cutting a quantum circuit, including measurements and recombination, is captured exactly by partitioning the corresponding directed acyclic graph.

What would settle it

Demonstrating a quantum circuit where the graph-based minimal cut count does not match the actual minimal cuts needed to execute the circuit correctly on hardware.

Figures

Figures reproduced from arXiv: 2604.23700 by Eitan Zahavi, Elad Mentovich, Eliahu Cohen, Shmuel Zaks, Yuval Idan.

**Figure 1.** Figure 1: Evolution of a quantum state within a tensor network. The initial state tensor is enclosed by view at source ↗

**Figure 2.** Figure 2: (a) Rank-2n unitary, which is not separable, and acting on all the qubits simultaneously. (b) Decompositions of the previous rank-2n tensor Uˆ into lower-rank tensors. (c) Cutting the unitary Uˆ into two sets of unitaries. (d) The contraction from Eq. (12). Because the system is closed and the entire computation is unitary the number of qubits does not change through the algorithm. Therefore, for every ver… view at source ↗

**Figure 3.** Figure 3: An example demonstrating GE′ of Definition 7, for |E′ | = 4. (a) Simple tensor network T, and the connected graph (GE), that represent the tensor network. The desired edges that we wish to delete are E′ = {e1, e2, e3, e4} ⊆ E. (b) Tensor network T ′ and GE′ , obtained from the graph duplication, the set E′ = {e1, e2, e3, e4}, the additional vertices V ′ = {x1, y1, x2, y2, x3, y3, x4, y4} ∈/ V and the addit… view at source ↗

**Figure 4.** Figure 4: The case β = 0. The dag shown is G0 . 7.4 Forest G, β > 0 constant Theorem 4. Problem Graph duplication GD(G, k, α, β) is NP-complete for any constant β > 0, even when G is a forest dag. The proof is an extension of the proof of Theorem 3 (see Appendix A.4). 7.5 Forest G, 2-legal dags, β = 0 Our motivation for the specific proof of the 2-legal dag defined in Condition 3 ′ is that any multi-qubit gate can b… view at source ↗

**Figure 5.** Figure 5: The connected dag G˜ used in the proof of Theorem 7. a solution, the program will end without any partition. The SMT formulation provides an exact optimization framework for the encoded GD problem, suitable for modest instance sizes (and relatively small values of β), although worst-case runtime remains exponential. The exact constraints are: • The set O = { ov,p | v ∈ V, p ∈ P }, with each ov,p ∈ {0, 1} i… view at source ↗

**Figure 6.** Figure 6: (a) Arbitrary quantum algorithm represented in the circuit model, each block is unitary view at source ↗

**Figure 7.** Figure 7: (a) Quantum algorithm with induced entanglement, decomposition necessitates qubit cuts. view at source ↗

**Figure 8.** Figure 8: G′ , G′′, G′′ each contains one component while G′′ ∪ G′′′ contains two view at source ↗

**Figure 9.** Figure 9: The case β > 0. The dag shown is G′ , β copies of which are added to G0 . Since β is constant, this construction is done in polynomial time. We have to show that there is a solution to the given instance I of 3-partition iff there is a solution to the problem GD(Gβ , B, m + 2β, β). If there is a solution to I then by duplicating all the β edges (t1, t2) we get a partition Gβ into exactly m + 2β subgraphs, … view at source ↗

**Figure 10.** Figure 10: Illustration of the proof sketch for Theorem 5. view at source ↗

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper proves NP-completeness for minimizing cut count in circuit partitioning on DAGs, even for 1- and 2-qubit gates, plus an SMT solver for bounded fragments.

read the letter

The main takeaway is that optimal placement of cuts to break a quantum circuit into smaller pieces is NP-complete. The authors establish this by mapping the circuit to a directed acyclic graph and reducing the partition problem to a known combinatorial hard task. The result holds even when the circuit is restricted to one- and two-qubit gates only. They follow up with an SMT solver that finds the cuts when each fragment is limited to a small number of qubits.

Referee Report

2 major / 3 minor

Summary. The paper claims to leverage the duality between quantum circuits and directed acyclic graphs (DAGs) to create a graph-theoretic framework for circuit cutting. It defines a combinatorial partition problem whose goal is to minimize the number of cuts that decompose a circuit into smaller fragments, proves this problem NP-complete, and shows NP-completeness persists even when restricted to circuits using only one- and two-qubit gates. An SMT solver is then proposed to compute optimal cuts for instances where each fragment is bounded in qubit count.

Significance. If the modeling and reductions are faithful, the work supplies a complexity-theoretic foundation for optimal cut placement and a concrete solver for bounded cases, both of which are useful in the NISQ regime where cutting is employed to reduce depth and width. The explicit NP-completeness proof for the one-/two-qubit restriction and the SMT formulation constitute clear technical contributions.

major comments (2)

[§3] §3 (graph-theoretic framework and definition of the partition problem): the objective is stated as minimizing the raw number of cuts (i.e., edges removed from the DAG). In quantum circuit cutting each cut replaces a wire by a measurement whose classical recombination cost scales exponentially with the number of cuts (typically 2^c or 4^c). The manuscript must clarify whether the objective function encodes this multiplicity or basis-choice overhead; if it does not, the NP-completeness result applies to a proxy problem whose optimum can differ from the quantum objective later optimized by the SMT solver.
[§4] §4 (complexity analysis and reductions): the proof that the partition problem remains NP-complete even for one- and two-qubit gates relies on a reduction from a known NP-complete problem. The reduction must be shown to preserve all quantum-specific constraints (gate semantics, wire connectivity, and measurement recombination) so that no modeling gap is introduced; without explicit verification that the constructed instances correspond to valid quantum circuits, the applicability of the hardness result to actual cutting instances is not fully established.

minor comments (3)

Notation for vertices, edges, and cut sets in the DAG representation should be introduced once and used consistently throughout the complexity and algorithm sections.
The introduction would benefit from a short comparison table or paragraph contrasting the present min-cut objective with prior circuit-cutting cost functions that explicitly include sampling overhead.
Figure captions for the DAG examples should state the qubit count and gate set of the corresponding circuit so readers can verify the mapping.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review of our manuscript. We address each major comment in turn below, providing our responses and indicating the revisions we will make.

read point-by-point responses

Referee: [§3] §3 (graph-theoretic framework and definition of the partition problem): the objective is stated as minimizing the raw number of cuts (i.e., edges removed from the DAG). In quantum circuit cutting each cut replaces a wire by a measurement whose classical recombination cost scales exponentially with the number of cuts (typically 2^c or 4^c). The manuscript must clarify whether the objective function encodes this multiplicity or basis-choice overhead; if it does not, the NP-completeness result applies to a proxy problem whose optimum can differ from the quantum objective later optimized by the SMT solver.

Authors: We thank the referee for this observation. Our partition problem is defined to minimize the number of cuts because the dominant classical post-processing cost in circuit cutting grows exponentially with this number (e.g., 2^c or 4^c depending on the scheme). Since this cost function is strictly monotonic in the cut count, the optimum for the combinatorial objective coincides exactly with the optimum for the quantum recombination cost; solutions with fewer cuts are always preferable. The SMT solver is formulated to optimize the identical objective (number of cuts) subject to the per-fragment qubit bound. Basis-choice overhead is handled in the subsequent cutting and recombination procedure rather than in the placement optimization. To eliminate any ambiguity, we will insert a short clarifying paragraph in Section 3 that explicitly states this equivalence and notes that the proxy is faithful for the purpose of locating optimal cut positions. revision: yes
Referee: [§4] §4 (complexity analysis and reductions): the proof that the partition problem remains NP-complete even for one- and two-qubit gates relies on a reduction from a known NP-complete problem. The reduction must be shown to preserve all quantum-specific constraints (gate semantics, wire connectivity, and measurement recombination) so that no modeling gap is introduced; without explicit verification that the constructed instances correspond to valid quantum circuits, the applicability of the hardness result to actual cutting instances is not fully established.

Authors: We agree that the reduction requires explicit confirmation of quantum validity. The construction in Section 4 maps instances of the source NP-complete problem to DAGs whose nodes are restricted to one- and two-qubit gates, with edges representing qubit wires that preserve acyclicity and locality. We will expand the proof with a dedicated verification paragraph that (i) confirms every constructed circuit uses only the allowed gate set, (ii) shows that wire connectivity and measurement points correspond directly to valid qubit lines, and (iii) verifies that the cut semantics align with standard quantum circuit cutting recombination. This addition will close the modeling gap and strengthen the claim that the hardness result applies to realistic quantum instances. revision: yes

Circularity Check

0 steps flagged

No circularity: standard NP-completeness reduction via explicit modeling choice

full rationale

The paper models quantum circuit cutting as a graph partition problem on the circuit-DAG duality, then proves the resulting combinatorial task NP-complete (including the 1-/2-qubit restriction) by reduction from a known NP-complete problem. This is a conventional complexity argument whose validity rests on the correctness of the modeling step and the reduction, not on any equation or parameter that equals its own input by construction. No self-definitional relations, fitted inputs relabeled as predictions, or load-bearing self-citations appear in the derivation chain. The SMT solver is presented as a practical consequence of the complexity result rather than a circular justification of it. The modeling assumption that raw cut count suffices for the objective is a potential completeness issue but does not create circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The framework rests on modeling quantum circuits as DAGs and on the assumption that cut placement corresponds exactly to graph partitioning with bounded fragment size.

axioms (1)

domain assumption Quantum circuits can be represented as directed acyclic graphs such that cut locations correspond to edge removals that partition the graph into independent subcircuits.
Invoked to apply graph-combinatorial complexity results directly to the cutting problem.

pith-pipeline@v0.9.0 · 5523 in / 1215 out tokens · 28946 ms · 2026-05-08T06:29:56.107185+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

22 extracted references · 2 canonical work pages

[1]

Quantum computing in the nisq era and beyond,

J. Preskill, “Quantum computing in the nisq era and beyond,”Quantum, vol. 2, p. 79, 2018

2018
[2]

Building a large-scale quantum computer with continuous- variable optical technologies,

K. Fukui and S. Takeda, “Building a large-scale quantum computer with continuous- variable optical technologies,”Journal of Physics B: Atomic, Molecular and Optical Physics, vol. 55, no. 1, p. 012001, 2022

2022
[3]

Trapped-ion quantum computing: Progress and challenges,

C. D. Bruzewicz, J. Chiaverini, R. McConnell, and J. M. Sage, “Trapped-ion quantum computing: Progress and challenges,”Applied Physics Reviews, vol. 6, no. 2, 2019

2019
[4]

Evidence for the utility of quantum computing before fault tolerance,

Y. Kimet al., “Evidence for the utility of quantum computing before fault tolerance,” Nature, vol. 618, pp. 500–505, 2023

2023
[5]

Noisy intermediate-scale quantum algorithms,

K. Bhartiet al., “Noisy intermediate-scale quantum algorithms,”Reviews of Modern Physics, vol. 94, p. 015004, 2022

2022
[6]

Simulating large quantum circuits on a small quantum computer,

T. Peng, A. W. Harrow, M. Ozols, and X. Wu, “Simulating large quantum circuits on a small quantum computer,”Physical Review Letters, vol. 125, no. 15, p. 150504, 2020. 16

2020
[7]

Trading classical and quantum computational resources,

S. Bravyi, G. Smith, and J. A. Smolin, “Trading classical and quantum computational resources,”Physical Review X, vol. 6, no. 2, p. 021043, 2016

2016
[8]

Optimal quantum circuit cuts with application to clus- tered hamiltonian simulation,

A. W. Harrow and A. Lowe, “Optimal quantum circuit cuts with application to clus- tered hamiltonian simulation,”PRX Quantum, vol. 6, p. 010316, 2025

2025
[9]

Circuit knitting with classical communication,

C. Piveteau and D. Sutter, “Circuit knitting with classical communication,”IEEE Transactions on Information Theory, vol. 70, no. 4, pp. 2734–2745, 2024

2024
[10]

Cutting circuits with multiple two-qubit unitaries,

L. Schmitt, C. Piveteau, and D. Sutter, “Cutting circuits with multiple two-qubit unitaries,”Quantum, vol. 9, p. 1634, 2025

2025
[11]

Circuit cutting with classical side informa- tion,

C. Piveteau, L. Schmitt, and D. Sutter, “Circuit cutting with classical side informa- tion,”Physical Review Research, vol. 7, p. 033063, 2025

2025
[12]

Cutting multi-control quantum gates with zx calculus,

C. Ufrecht, M. Periyasamy, S. Rietsch, D. D. Scherer, A. Plinge, and C. Mutschler, “Cutting multi-control quantum gates with zx calculus,”Quantum, vol. 7, p. 1147, 2023

2023
[13]

Tensor networks in a nutshell,

J. Biamonte and V. Bergholm, “Tensor networks in a nutshell,”arXiv preprint arXiv:1708.00006, 2017

work page arXiv 2017
[14]

Elementary gates for quantum com- putation,

A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, “Elementary gates for quantum com- putation,”Physical Review A, vol. 52, no. 5, p. 3457, 1995

1995
[15]

Optimal partitioning of quantum circuits using gate cuts and wire cuts,

S. Brandhofer, I. Polian, and K. Krsulich, “Optimal partitioning of quantum circuits using gate cuts and wire cuts,”IEEE Transactions on Quantum Engineering, 2023

2023
[16]

J. H. Selby,A process theoretic triptych. PhD thesis, PhD thesis, PhD thesis, Imperial College London, 2017

2017
[17]

Biamonte,Lectures on quantum tensor networks, 2020, arXiv:1912.10049

J. Biamonte, “Lectures on quantum tensor networks,”arXiv preprint arXiv:1912.10049, 2019

work page arXiv 1912
[18]

Hand-waving and interpretive dance: an introduc- tory course on tensor networks,

J. C. Bridgeman and C. T. Chubb, “Hand-waving and interpretive dance: an introduc- tory course on tensor networks,”Journal of physics A: Mathematical and theoretical, vol. 50, no. 22, p. 223001, 2017

2017
[19]

Predicting many properties of a quantum system from very few measurements,

H.-Y. Huang, R. Kueng, and J. Preskill, “Predicting many properties of a quantum system from very few measurements,”Nature Physics, vol. 16, no. 10, pp. 1050–1057, 2020

2020
[20]

Complexity results for multiprocessor scheduling under resource constraints,

M. R. Garey and D. S. Johnson, “Complexity results for multiprocessor scheduling under resource constraints,”SIAM Journal on Computing, vol. 4, no. 4, pp. 397–411, 1975

1975
[21]

Quantum split SMT

E. Zahavi and Y. Idan, “Quantum split SMT.”https://github.com/YuvalIdan9/ circuit_cutting.git, 2024

2024
[22]

M. R. Garey and D. S. Johnson,Computers and Intractability, vol. 29. W.H. Freeman, New York, 2002. 17 A Proof extensions A.1 Proof of Theorem 1 (a) Proof.In any directed graphG= (V,E) ∑ v∈Vdin(v) = ∑ v∈Vdout(v) =|E|.Hence∑ v∈V\(In(G)∪Out(G))din(v)+∑ v∈In(G)din(v)+∑ v∈Out(G)din(v) =∑ v∈V\(In(G)∪Out(G))dout(v)+∑ v∈In(G)dout(v) +∑ v∈Out(G)dout(v) Since the s...

2002