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

Exponential-to-polynomial scaling of measurement overhead in circuit knitting via quantum tomography

Hiroyuki Harada, Kaito Wada, Naoki Yamamoto, Suguru Endo

quant-phSubmitted Dec 22, 2025• Announced Dec 23, 2025• 0 citations
v1 · Dec 22, 2025v2 · Jun 30, 2026
arXivHTMLPDF

Abstract

Circuit knitting is a family of techniques that enables large quantum computations on limited-size quantum devices by decomposing a target circuit into smaller subcircuits. However, it typically incurs a measurement overhead exponential in the number of cut locations, and it remains open whether this scaling is fundamentally unavoidable. In conventional circuit-cutting approaches based on the quasiprobability decomposition (QPD), for example, rescaling factors lead to an exponential dependence on the number of cuts. In this work, we show that such an exponential scaling is not universal: it can be circumvented for tree-structured quantum circuits via concatenated quantum tomography protocols. We first consider estimating the expectation value of an observable within additive error $ε$ for a tree-structured circuit with tree depth 1 (two layers), maximum branching factor $R$, and bond dimension at most $d$ on each edge. Our approach uses quantum tomography to construct, for each cut edge, a local decomposition that eliminates the rescaling factors in conventional QPD, instead introducing a controllable bias set by the tomography sample size. After cutting $R$ edges, we show that $\mathcal{O}(d^3R^3\ln(dR)/ε^2)$ total measurements suffice, including tomography cost. Next, we extend the tree-depth-1 case to general trees of depth $L\geq2$, and give an algorithm whose total measurement cost $\tilde{\mathcal{O}}(d^3K^{5}/ε^2)$ scales polynomially with the number of cuts for complete $R$-ary trees. Finally, we perform an information-theoretic analysis to show that, in a comparable tree-depth-1 setting, conventional QPD-based wire-cutting methods require at least $Ω((d+1)^R/ε^2)$ measurements. This exponential separation highlights the significance of tomography-based construction for reducing measurement overhead in hybrid quantum-classical computations.

Comments
56 pages, 11 figures

Related papers

Circuit knitting facing exponential sampling-overhead scaling bounded by entanglement cost

Mingrui Jing, Chengkai Zhu, Xin Wang

Circuit knitting, a method for connecting quantum circuits across multiple processors to simulate nonlocal quantum operations, is a promising approach for distributed quantum computing. While various techniques have been developed for circuit knitting, we uncover fundamental limitations to the scalability of this technology. We prove that the sampling overhead of circuit knitting is exponentially lower bounded by the exact entanglement cost of the target bipartite dynamic, even with the asymptotic amount of resources using the parallel cut strategy. Specifically, we prove that the regularized sampling overhead assisted with local operations and classical communication of any bipartite quantum channel is lower bounded by the exponential of its exact entanglement cost under separable preserving operations. Furthermore, we develop the faithful lower bounds for the regularized sampling overhead based on channels' $\ensuremath{\kappa}$ entanglement and max-Rains information, providing efficiently computable benchmarks. Our work reveals a profound connection between virtual quantum information processing via quasiprobability decomposition and quantum Shannon theory, highlighting the critical role of entanglement in distributed quantum computing.

Physical Review A•Jan 22, 2025•9 citations

Circuit Knitting Faces Exponential Sampling Overhead Scaling Bounded by Entanglement Cost

Mingrui Jing, Chengkai Zhu, Xin Wang

Circuit knitting, a method for connecting quantum circuits across multiple processors to simulate nonlocal quantum operations, is a promising approach for distributed quantum computing. While various techniques have been developed for circuit knitting, we uncover fundamental limitations to the scalability of this technology. We prove that the sampling overhead of circuit knitting is exponentially lower bounded by the exact entanglement cost of the target bipartite dynamic, even for asymptotic overhead in the parallel cut regime. Specifically, we prove that the regularized sampling overhead assisted with local operations and classical communication (LOCC), of any bipartite quantum channel is lower bounded by the exponential of its exact entanglement cost under separable preserving operations. Furthermore, we show that the regularized sampling overhead for simulating a general bipartite channel via LOCC is lower bounded by $κ$-entanglement and max-Rains information, providing efficiently computable benchmarks. Our work reveals a profound connection between virtual quantum information processing via quasi-probability decomposition and quantum Shannon theory, highlighting the critical role of entanglement in distributed quantum computing.

arXiv:2404.03619•Apr 4, 2024•0 citations

MOSAIQC: Mixed-topology-aware Optimization for Scalable Approximate noise-Informed Quantum circuit Cutting

Koen Mesman, Yinglu Tang, Matthias Moller +2 more

Current quantum computers do not yet have the required qubit resources to meet the demands of most practical quantum algorithms. To circumvent this constraint, the practice of dividing these algorithms into parts through quantum circuit cutting has been explored. Many of these works either show exponential scaling or are far from optimal solutions. In this paper, MosaiQC is presented as a novel framework to improve upon existing circuit cutting frameworks. A hybrid warmstart with refinement optimization is used to find cutting solutions, allowing the combination of both wire and gate cuts. Additionally, MosaiQC enables hardware partitions of mixed sizes. Furthermore, the refinement stage incorporates a fast approximate quadratic assignment solver to better place hardware partitions, demonstrating a mean local fidelity improvement of $19.56 \% \pm 6.17\%$ over the baseline algorithm. In runtime and sampling overhead costs, improvements of $2.88 \times$ and an average of $16.84\%$ cut reduction (resulting in an average $5.83 \cdot 10^{11} \times$ overhead reduction) are observed. MosaiQC demonstrates a superior trade-off for run speed and solution quality, while adding fundamental features excluded by most competitors. With this, MosaiQC demonstrates that scalable heuristic optimization can substantially reduce the computational overhead of circuit-cut placement for increasingly large quantum circuits.

quant-pharXiv:2607.18888•Jul 22, 2026•0 citations

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•21 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•0 citations

Adaptive Local Measurements For Quantum Learning Can Exponentially Outperform Nonadaptive Global Measurements

Alireza Goldar, Zhen Qin, Zhihui Zhu +2 more

Can measurements chosen adaptively, in response to earlier outcomes, be exponentially more informative than measurements fixed in advance? In many quantum settings, adaptivity helps at most polynomially; known exponential advantages require coherent measurements across copies or restricted measurements. We show an exponential advantage measuring one copy at a time, with no quantum memory kept between state copies, even when the nonadaptive learner may perform arbitrary global measurements on each copy. We construct explicit families of multi-qubit states in which a scalar parameter is encoded in one of exponentially many candidate observables, with an auxiliary marker indicating which one. An adaptive protocol identifies the relevant observable and then measures it using only single-qubit measurements and one round of adaptation. At fixed accuracy, it needs logarithmically many copies as the qubit count grows, whereas every nonadaptive protocol needs exponentially many. The same mechanism yields an exponential gap in local asymptotic minimax mean squared error constants, tight up to the exponential base. The states are separable and classical in label-dependent product bases; no entanglement or other nonclassical correlations are required. The gap comes from measurement incompatibility: the candidate observables cannot be measured jointly, so a fixed measurement must divide its information budget among them, while adaptivity selects the informative one. Accordingly, the separation disappears when the candidate observables commute, and cannot occur with fully observed classical samples. Measurement incompatibility thus emerges as a resource for quantum learning, distinct from entanglement and quantum memory, that classical feedback alone can exploit.

quant-pharXiv:2610.38922•Oct 30, 2026•0 citations
Circuit knitting is a family of techniques that enables large quantum computations on limited-size quantum devices by decomposing a target circuit into smaller subcircuits. However, it typically incurs a measurement overhead exponential in the number of cut locations, and it remains open whether this scaling is fundamentally unavoidable. In conventional circuit-cutting approaches based on the quasiprobability decomposition (QPD), for example, rescaling factors lead to an exponential dependence on the number of cuts. In this work, we show that such an exponential scaling is not universal: it can be circumvented for tree-structured quantum circuits via concatenated quantum tomography protocols. We first consider estimating the expectation value of an observable within additive error εεε for a tree-structured circuit with tree depth 1 (two layers), maximum branching factor RRR, and bond dimension at most ddd on each edge. Our approach uses quantum tomography to construct, for each cut edge, a local decomposition that eliminates the rescaling factors in conventional QPD, instead introducing a controllable bias set by the tomography sample size. After cutting RRR edges, we show that O(d3R3ln⁡(dR)/ε2)\mathcal{O}(d^3R^3\ln(dR)/ε^2)O(d3R3ln(dR)/ε2) total measurements suffice, including tomography cost. Next, we extend the tree-depth-1 case to general trees of depth L≥2L\geq2L≥2, and give an algorithm whose total measurement cost O~(d3K5/ε2)\tilde{\mathcal{O}}(d^3K^{5}/ε^2)O~(d3K5/ε2) scales polynomially with the number of cuts for complete RRR-ary trees. Finally, we perform an information-theoretic analysis to show that, in a comparable tree-depth-1 setting, conventional QPD-based wire-cutting methods require at least Ω((d+1)R/ε2)Ω((d+1)^R/ε^2)Ω((d+1)R/ε2) measurements. This exponential separation highlights the significance of tomography-based construction for reducing measurement overhead in hybrid quantum-classical computations.
Circuit knitting, a method for connecting quantum circuits across multiple processors to simulate nonlocal quantum operations, is a promising approach for distributed quantum computing. While various techniques have been developed for circuit knitting, we uncover fundamental limitations to the scalability of this technology. We prove that the sampling overhead of circuit knitting is exponentially lower bounded by the exact entanglement cost of the target bipartite dynamic, even with the asymptotic amount of resources using the parallel cut strategy. Specifically, we prove that the regularized sampling overhead assisted with local operations and classical communication of any bipartite quantum channel is lower bounded by the exponential of its exact entanglement cost under separable preserving operations. Furthermore, we develop the faithful lower bounds for the regularized sampling overhead based on channels' $\ensuremath{\kappa}$ entanglement and max-Rains information, providing efficiently computable benchmarks. Our work reveals a profound connection between virtual quantum information processing via quasiprobability decomposition and quantum Shannon theory, highlighting the critical role of entanglement in distributed quantum computing.
Circuit knitting, a method for connecting quantum circuits across multiple processors to simulate nonlocal quantum operations, is a promising approach for distributed quantum computing. While various techniques have been developed for circuit knitting, we uncover fundamental limitations to the scalability of this technology. We prove that the sampling overhead of circuit knitting is exponentially lower bounded by the exact entanglement cost of the target bipartite dynamic, even for asymptotic overhead in the parallel cut regime. Specifically, we prove that the regularized sampling overhead assisted with local operations and classical communication (LOCC), of any bipartite quantum channel is lower bounded by the exponential of its exact entanglement cost under separable preserving operations. Furthermore, we show that the regularized sampling overhead for simulating a general bipartite channel via LOCC is lower bounded by κκκ-entanglement and max-Rains information, providing efficiently computable benchmarks. Our work reveals a profound connection between virtual quantum information processing via quasi-probability decomposition and quantum Shannon theory, highlighting the critical role of entanglement in distributed quantum computing.
Current quantum computers do not yet have the required qubit resources to meet the demands of most practical quantum algorithms. To circumvent this constraint, the practice of dividing these algorithms into parts through quantum circuit cutting has been explored. Many of these works either show exponential scaling or are far from optimal solutions. In this paper, MosaiQC is presented as a novel framework to improve upon existing circuit cutting frameworks. A hybrid warmstart with refinement optimization is used to find cutting solutions, allowing the combination of both wire and gate cuts. Additionally, MosaiQC enables hardware partitions of mixed sizes. Furthermore, the refinement stage incorporates a fast approximate quadratic assignment solver to better place hardware partitions, demonstrating a mean local fidelity improvement of 19.56%±6.17%19.56 \% \pm 6.17\%19.56%±6.17% over the baseline algorithm. In runtime and sampling overhead costs, improvements of 2.88×2.88 \times2.88× and an average of 16.84%16.84\%16.84% cut reduction (resulting in an average 5.83⋅1011×5.83 \cdot 10^{11} \times5.83⋅1011× overhead reduction) are observed. MosaiQC demonstrates a superior trade-off for run speed and solution quality, while adding fundamental features excluded by most competitors. With this, MosaiQC demonstrates that scalable heuristic optimization can substantially reduce the computational overhead of circuit-cut placement for increasingly large quantum circuits.
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 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.
Can measurements chosen adaptively, in response to earlier outcomes, be exponentially more informative than measurements fixed in advance? In many quantum settings, adaptivity helps at most polynomially; known exponential advantages require coherent measurements across copies or restricted measurements. We show an exponential advantage measuring one copy at a time, with no quantum memory kept between state copies, even when the nonadaptive learner may perform arbitrary global measurements on each copy. We construct explicit families of multi-qubit states in which a scalar parameter is encoded in one of exponentially many candidate observables, with an auxiliary marker indicating which one. An adaptive protocol identifies the relevant observable and then measures it using only single-qubit measurements and one round of adaptation. At fixed accuracy, it needs logarithmically many copies as the qubit count grows, whereas every nonadaptive protocol needs exponentially many. The same mechanism yields an exponential gap in local asymptotic minimax mean squared error constants, tight up to the exponential base. The states are separable and classical in label-dependent product bases; no entanglement or other nonclassical correlations are required. The gap comes from measurement incompatibility: the candidate observables cannot be measured jointly, so a fixed measurement must divide its information budget among them, while adaptivity selects the informative one. Accordingly, the separation disappears when the candidate observables commute, and cannot occur with fully observed classical samples. Measurement incompatibility thus emerges as a resource for quantum learning, distinct from entanglement and quantum memory, that classical feedback alone can exploit.