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

• URL: http://arxiv.org/abs/2512.19623v1
• Date: Mon, 22 Dec 2025 17:55:47 GMT
• Title: Exponential-to-polynomial scaling of measurement overhead in circuit knitting via quantum tomography
• Authors: Hiroyuki Harada, Kaito Wada, Naoki Yamamoto, Suguru Endo,
• Abstract summary: Circuit knitting incurs a measurement overhead exponential in the number of cut locations.<n>In conventional circuit-cutting approaches, rescaling factors lead to an exponential dependence on the number of cuts.<n>We use quantum tomography to construct, for each cut edge, a local decomposition that eliminates the rescaling factors in conventional QPD.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Optimal learning of quantum channels in diamond distance [0.0]
  We show that a quantum channel acting on a $d$-dimensional system can be estimated to accuracy $varepsilon$ in diamond distance.<n>We obtain, to the best of our knowledge, the first essentially optimal strategies for operator-norm learning of binary POVMs and isometries.
  arXiv  Detail & Related papers  (2025-12-11T02:04:03Z)
• Bridging wire and gate cutting with ZX-calculus [45.200826131319815]
  We show how decompositions of ideal, global unitaries can be obtained diagrammatically using ZX-calculus expanding.<n>We obtain improved decompositions for multi-qubit controlled-Z (MCZ) gates with $1$-norm equal to $3$ for any number of qubits and any partition.
  arXiv  Detail & Related papers  (2025-03-14T15:20:47Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose $Zotimes n$ exponentials of arbitrary length into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions.<n>We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.<n>Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.<n>We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Even shorter quantum circuit for phase estimation on early fault-tolerant quantum computers with applications to ground-state energy estimation [5.746732081406236]
  We develop a phase estimation method with a distinct feature. The total cost of the algorithm satisfies the Heisenberg-limited scaling $widetildemathcalO(epsilon-1)$. Our algorithm may significantly reduce the circuit depth for performing phase estimation tasks on early fault-tolerant quantum computers.
  arXiv  Detail & Related papers  (2022-11-22T03:15:40Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• K-sparse Pure State Tomography with Phase Estimation [1.2183405753834557]
  Quantum state tomography (QST) for reconstructing pure states requires exponentially increasing resources and measurements with the number of qubits. QST reconstruction for any pure state composed of the superposition of $K$ different computational basis states of $n$bits in a specific measurement set-up is presented.
  arXiv  Detail & Related papers  (2021-11-08T09:43:12Z)
• Halving the cost of quantum multiplexed rotations [0.0]
  We improve the number of $T$ gates needed for a $b$-bit approximation of a multiplexed quantum gate with $c$ controls. Our results roughly halve the cost of state-of-art electronic structure simulations based on qubitization of double-factorized or tensor-hypercontracted representations.
  arXiv  Detail & Related papers  (2021-10-26T06:49:44Z)
• Random quantum circuits anti-concentrate in log depth [118.18170052022323]
  We study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated. Our definition of anti-concentration is that the expected collision probability is only a constant factor larger than if the distribution were uniform. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n log(n)) gates are also sufficient.
  arXiv  Detail & Related papers  (2020-11-24T18:44:57Z)
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates [0.0]
  We prove that $poly(t)cdot n1/D$-depth local random quantum circuits with two qudit nearest-neighbor gates are approximate $t$-designs in various measures. We also prove that anti-concentration is possible in depth O(log(n) loglog(n) using a different model.
  arXiv  Detail & Related papers  (2018-09-18T22:28:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.