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

Structural Conditions for Distributed Quantum Advantage

Sabina Drăgoi, María Gragera Garcés, Lirandë Pira

quant-phcs.DCSubmitted Oct 3, 2026• Announced Oct 6, 2026• 0 citations
arXivHTMLPDF

Abstract

Circuit cutting runs a quantum computation on processors smaller than the circuit, at the price of classical knitting whose cost grows exponentially with the number of cut gates. Keeping this cost affordable is necessary but not sufficient for an advantage, since knitting classically easy subcircuits is itself classically easy. We formulate three requirements for distributed quantum advantage under a stated budget: affordable knitting, classical difficulty that survives the cut, and, for variational circuits, resolvable gradients. We prove that under stated assumptions knitting stays affordable when subcircuits grow behind a bounded interface and becomes exponentially expensive when fixed-width subcircuits multiply. We turn the requirements into screening criteria and apply them to eighteen circuit families. We identify finite local-depth circuits with bounded interfaces as a setting in which the requirements can coexist, with hardness established only in the worst case. As a classically verifiable proof of principle, we knit one gate joining two field-perturbed toric-code patches on an IBM Nighthawk processor for up to 142 spins, and confirm that the reconstruction can at least resolve the contact correlation beyond independent execution for up to 98 qubits.

AI Summary

The paper asks when circuit cutting could support distributed quantum advantage, rather than merely extend executable circuit width. It organizes assessment around affordable quasiprobability reconstruction, classical difficulty of the resulting branch tasks, and—for variational circuits—resolvable gradients, and screens eighteen circuit families. For cuts severing $O(\log n)$ gates with bounded-size decompositions, it proves that uniformly efficient classical simulation of all branch tasks implies efficient simulation of bounded-support output observables. Standard cutting constructions have constant or polynomial overhead behind bounded or logarithmic interfaces; connected networks of fixed-width processors instead incur exponential overhead under stated gate-angle assumptions. Using pure-state entanglement robustness, it obtains the exact state-level coefficient norm $\Gamma_{\rm sep}=2\,2^{S_{1/2}}-1$, a lower bound for exact local reconstruction. Finite-local-depth circuits with bounded interfaces can combine affordable cutting, initialization-dependent gradient guarantees, and worst-case-hard branch tasks, but natural hard instances remain unidentified. A hardware benchmark reconstructs one entangling gate between field-perturbed toric-code patches. Its knitting norm is $1+2|\sin\phi|\le3$, independent of patch size. IBM measurements reach 142 spins; connected contact correlations remain distinguishable from zero through 98 spins, recovering about 87% of the target at eight spins and 20% at 80–98 spins. The experiment demonstrates neither quantum advantage nor scalable ground-state optimization. Larger hardware instances use analytically known zero-field angles with Clifford cutting branches. Gradient evidence for the benchmark is numerical at small sizes; its classical hardness remains open. Entanglement-based exclusions concern exact state reconstruction, not arbitrary estimators of individual observables, and device noise progressively suppresses the reconstructed signals.

Little sign of AI-generated textIncrementalStrong assumptions

Error found: The hardware section's maximum of 142 total spins is incompatible with its stated maximum of 6×6 plaquettes per patch and 85 qubits per subcircuit: those dimensions imply 168 total spins, whereas 142 spins corresponds to 5×6 patches and 72-qubit subcircuits including ancillas.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
14 pages of main text + 25 pages of appendices; 18 figures, 7 tables

Related papers

Optimal Wire Cutting With Classical Communication

Lukas Brenner, Christophe Piveteau, David Sutter

Circuit knitting is the process of partitioning large quantum circuits into smaller subcircuits such that the result of the original circuits can be deduced by only running the subcircuits. Such techniques will be crucial for near-term and early fault-tolerant quantum computers, as the limited number of qubits is likely to be a major bottleneck for demonstrating quantum advantage. One typically distinguishes between gate cuts and wire cuts when partitioning a circuit. The cost for any circuit knitting approach scales exponentially in the number of cuts. One possibility to realize a cut is via the quasiprobability simulation technique. In fact, we argue that all existing rigorous circuit knitting techniques can be understood in this framework. Furthermore, we characterize the optimal overhead for wire cuts where the subcircuits can exchange classical information or not. We show that the optimal cost for cuttingnwires without and with classical communication between the subcircuits scales asO(16n) andO(4n), respectively.

arXiv:2302.03366•IEEE Transactions on Information Theory•Aug 20, 2025•73 citations

Automated Cut Finding and Circuit Knitting on Large Quantum Circuits

Ibrahim Shehzad, Edwin Pednault, James R. Garrison +3 more

Circuit knitting (see, e.g., [1]) is a technique that allows circuits that are too large to run on a given quantum processing unit (QPU) to be decomposed into an equivalent series of smaller subcircuits that can run on the QPU, where the resulting measurement outcomes of the subcircuits are then classically combined via post-processing. Circuits are decomposed by cutting gates and/or wires. To obtain results to the same accuracy as those of the original problem, each cut incurs additional sampling overhead (denoted γ2) that grows exponentially with the number of cuts. It is therefore desirable to find optimal sets of cuts that minimize the sampling overhead. To this end, we present the “cut-finder” (Sec. I) module of the Circuit Knitting Toolbox (CKT) [2], which performs an automated search for LO gate and wire cuts that minimize the sampling overhead. Circuit knitting can also be used to engineer gates between distant qubits which would otherwise require a large swap overhead to implement. In Sec II, we show how this capability can be used to calculate certain expectation values on a graph state with a cylindrical topology to a better degree of accuracy than if the experiment were to be performed without circuit knitting.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•2 citations

Entanglement geometry separates circuit cutting, classical hardness, and trainability

Maria Gragera Garces, Sabina Drăgoi, Lirandë Pira

Circuit cutting promises to scale quantum computations beyond current hardware, but variational quantum advantage also requires low cutting overhead, classical hardness, and trainability. We show that these properties are strongly constrained by entanglement geometry. Matrix product state (MPS) and tree tensor network (TTN) circuits with constant seam bond dimension can be cut with \(O(1/\varepsilon^2)\) sampling overhead, but remain efficiently classically simulable, ruling out asymptotic quantum advantage within these families. By independently controlling seam and intra-block entanglement, we construct a two-block circuit family that remains cheaply cuttable while requiring a super-polynomial global MPS bond dimension, as supported numerically up to \(n=100\). However, MPS hardness and trainability require incompatible depth regimes, \(d=ω(\log n)\) and \(d=O(\log n)\), respectively. Using magic rather than entanglement as the hardness resource avoids this conflict: shallow Clifford+\(T\) circuits remain cuttable and trainable while their stabiliser-simulation cost grows exponentially with the \(T\)-count.

quant-pharXiv:2607.17872•Jul 21, 2026•2 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•6 citations

Circuit Knitting With Classical Communication

Christophe Piveteau, David Sutter

The scarcity of qubits is a major obstacle to the practical usage of quantum computers in the near future. To circumvent this problem, various circuit knitting techniques have been developed to partition large quantum circuits into subcircuits that fit on smaller devices, at the cost of a simulation overhead. In this work, we study a particular method of circuit knitting based on quasiprobability simulation of nonlocal gates with operations that act locally on the subcircuits. We investigate whether classical communication between these local quantum computers can help. We provide a positive answer by showing that for circuits containing$n$nonlocal CNOT gates connecting two circuit parts, the simulation overhead can be reduced from$O(9^{n})$to$O(4^{n})$if one allows for classical information exchange. Similar improvements can be obtained for general Clifford gates and, at least in a restricted form, for other gates such as controlled rotation gates.

arXiv:2205.00016•IEEE Transactions on Information Theory•Aug 31, 2023•172 citations

Quantum Advantage with Adaptive Shallow Circuits

Yusen Wu, Yukun Zhang, XIaoming Zhang +2 more

Quantum advantage is widely expected to require sufficiently deep circuits, where correlations and global computational structure can grow beyond the reach of efficient classical simulation. This expectation is especially stark for constant-depth circuits with local readout: the expectation value of any fixed local observable lies within a bounded backward lightcone and is therefore classically tractable. Here we show that measurement feedback changes this picture. We establish a strict hierarchy of computational power: at fixed coherent depth, increasing the number of feedback outcomes strictly enlarges the class of functions accessible through a local expectation value. The two ends of this hierarchy exhibit distinct computational regimes. With logarithmic feedback, local expectation values for product-state inputs are efficiently classically simulable. Polynomial feedback, by contrast, enables an explicit family of adaptive shallow circuits to encode prime-field discrete logarithm problem~(DLP) into a fixed single-qubit expectation. Assuming the standard worst-case classical hardness of DLP, estimating this expectation value is classically hard. These results reveal a feedback-driven complexity transition, with further implications for resource lower bounds on DLP and the complexity of local-observable estimation under area-law entanglement. Our results open a new route to quantum advantage with shallow quantum circuits.

quant-pharXiv:2608.15545•Aug 18, 2026•1 citation
Circuit cutting runs a quantum computation on processors smaller than the circuit, at the price of classical knitting whose cost grows exponentially with the number of cut gates. Keeping this cost affordable is necessary but not sufficient for an advantage, since knitting classically easy subcircuits is itself classically easy. We formulate three requirements for distributed quantum advantage under a stated budget: affordable knitting, classical difficulty that survives the cut, and, for variational circuits, resolvable gradients. We prove that under stated assumptions knitting stays affordable when subcircuits grow behind a bounded interface and becomes exponentially expensive when fixed-width subcircuits multiply. We turn the requirements into screening criteria and apply them to eighteen circuit families. We identify finite local-depth circuits with bounded interfaces as a setting in which the requirements can coexist, with hardness established only in the worst case. As a classically verifiable proof of principle, we knit one gate joining two field-perturbed toric-code patches on an IBM Nighthawk processor for up to 142 spins, and confirm that the reconstruction can at least resolve the contact correlation beyond independent execution for up to 98 qubits.
The paper asks when circuit cutting could support distributed quantum advantage, rather than merely extend executable circuit width. It organizes assessment around affordable quasiprobability reconstruction, classical difficulty of the resulting branch tasks, and—for variational circuits—resolvable gradients, and screens eighteen circuit families.
For cuts severing O(log⁡n)O(\log n)O(logn) gates with bounded-size decompositions, it proves that uniformly efficient classical simulation of all branch tasks implies efficient simulation of bounded-support output observables. Standard cutting constructions have constant or polynomial overhead behind bounded or logarithmic interfaces; connected networks of fixed-width processors instead incur exponential overhead under stated gate-angle assumptions. Using pure-state entanglement robustness, it obtains the exact state-level coefficient norm Γsep=2 2S1/2−1\Gamma_{\rm sep}=2\,2^{S_{1/2}}-1Γsep​=22S1/2​−1, a lower bound for exact local reconstruction. Finite-local-depth circuits with bounded interfaces can combine affordable cutting, initialization-dependent gradient guarantees, and worst-case-hard branch tasks, but natural hard instances remain unidentified.
A hardware benchmark reconstructs one entangling gate between field-perturbed toric-code patches. Its knitting norm is 1+2∣sin⁡ϕ∣≤31+2|\sin\phi|\le31+2∣sinϕ∣≤3, independent of patch size. IBM measurements reach 142 spins; connected contact correlations remain distinguishable from zero through 98 spins, recovering about 87% of the target at eight spins and 20% at 80–98 spins.
The experiment demonstrates neither quantum advantage nor scalable ground-state optimization. Larger hardware instances use analytically known zero-field angles with Clifford cutting branches. Gradient evidence for the benchmark is numerical at small sizes; its classical hardness remains open. Entanglement-based exclusions concern exact state reconstruction, not arbitrary estimators of individual observables, and device noise progressively suppresses the reconstructed signals.
Circuit knitting is the process of partitioning large quantum circuits into smaller subcircuits such that the result of the original circuits can be deduced by only running the subcircuits. Such techniques will be crucial for near-term and early fault-tolerant quantum computers, as the limited number of qubits is likely to be a major bottleneck for demonstrating quantum advantage. One typically distinguishes between gate cuts and wire cuts when partitioning a circuit. The cost for any circuit knitting approach scales exponentially in the number of cuts. One possibility to realize a cut is via the quasiprobability simulation technique. In fact, we argue that all existing rigorous circuit knitting techniques can be understood in this framework. Furthermore, we characterize the optimal overhead for wire cuts where the subcircuits can exchange classical information or not. We show that the optimal cost for cuttingnwires without and with classical communication between the subcircuits scales asO(16n) andO(4n), respectively.
Circuit knitting (see, e.g., [1]) is a technique that allows circuits that are too large to run on a given quantum processing unit (QPU) to be decomposed into an equivalent series of smaller subcircuits that can run on the QPU, where the resulting measurement outcomes of the subcircuits are then classically combined via post-processing. Circuits are decomposed by cutting gates and/or wires. To obtain results to the same accuracy as those of the original problem, each cut incurs additional sampling overhead (denoted γ2) that grows exponentially with the number of cuts. It is therefore desirable to find optimal sets of cuts that minimize the sampling overhead. To this end, we present the “cut-finder” (Sec. I) module of the Circuit Knitting Toolbox (CKT) [2], which performs an automated search for LO gate and wire cuts that minimize the sampling overhead. Circuit knitting can also be used to engineer gates between distant qubits which would otherwise require a large swap overhead to implement. In Sec II, we show how this capability can be used to calculate certain expectation values on a graph state with a cylindrical topology to a better degree of accuracy than if the experiment were to be performed without circuit knitting.
Circuit cutting promises to scale quantum computations beyond current hardware, but variational quantum advantage also requires low cutting overhead, classical hardness, and trainability. We show that these properties are strongly constrained by entanglement geometry. Matrix product state (MPS) and tree tensor network (TTN) circuits with constant seam bond dimension can be cut with O(1/ε2)O(1/\varepsilon^2)O(1/ε2) sampling overhead, but remain efficiently classically simulable, ruling out asymptotic quantum advantage within these families. By independently controlling seam and intra-block entanglement, we construct a two-block circuit family that remains cheaply cuttable while requiring a super-polynomial global MPS bond dimension, as supported numerically up to n=100n=100n=100. However, MPS hardness and trainability require incompatible depth regimes, d=ω(log⁡n)d=ω(\log n)d=ω(logn) and d=O(log⁡n)d=O(\log n)d=O(logn), respectively. Using magic rather than entanglement as the hardness resource avoids this conflict: shallow Clifford+TTT circuits remain cuttable and trainable while their stabiliser-simulation cost grows exponentially with the TTT-count.
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 scarcity of qubits is a major obstacle to the practical usage of quantum computers in the near future. To circumvent this problem, various circuit knitting techniques have been developed to partition large quantum circuits into subcircuits that fit on smaller devices, at the cost of a simulation overhead. In this work, we study a particular method of circuit knitting based on quasiprobability simulation of nonlocal gates with operations that act locally on the subcircuits. We investigate whether classical communication between these local quantum computers can help. We provide a positive answer by showing that for circuits containingnnnnonlocal CNOT gates connecting two circuit parts, the simulation overhead can be reduced fromO(9n)O(9^{n})O(9n)toO(4n)O(4^{n})O(4n)if one allows for classical information exchange. Similar improvements can be obtained for general Clifford gates and, at least in a restricted form, for other gates such as controlled rotation gates.
Quantum advantage is widely expected to require sufficiently deep circuits, where correlations and global computational structure can grow beyond the reach of efficient classical simulation. This expectation is especially stark for constant-depth circuits with local readout: the expectation value of any fixed local observable lies within a bounded backward lightcone and is therefore classically tractable. Here we show that measurement feedback changes this picture. We establish a strict hierarchy of computational power: at fixed coherent depth, increasing the number of feedback outcomes strictly enlarges the class of functions accessible through a local expectation value. The two ends of this hierarchy exhibit distinct computational regimes. With logarithmic feedback, local expectation values for product-state inputs are efficiently classically simulable. Polynomial feedback, by contrast, enables an explicit family of adaptive shallow circuits to encode prime-field discrete logarithm problem~(DLP) into a fixed single-qubit expectation. Assuming the standard worst-case classical hardness of DLP, estimating this expectation value is classically hard. These results reveal a feedback-driven complexity transition, with further implications for resource lower bounds on DLP and the complexity of local-observable estimation under area-law entanglement. Our results open a new route to quantum advantage with shallow quantum circuits.