pith. sign in

arxiv: 2605.02057 · v1 · submitted 2026-05-03 · 🪐 quant-ph · cs.CC· cs.IT· math.IT

Exponential speedups in fault-tolerant processing of quantum experiments

Ishaan Kannan , Harald Putterman , Jordan Cotler This is my paper

Pith reviewed 2026-05-08 19:20 UTC · model grok-4.3

classification 🪐 quant-ph cs.CCcs.ITmath.IT
keywords quantum uploadingfault toleranceshadow tomographycubic observablesHeisenberg learning treequantum error correctionlearning lower boundsexponential speedups
0
0 comments X

The pith

Embedding experimental quantum states into high-distance error-correcting codes enables exponential speedups in shadow tomography and cubic observable estimation.

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

This paper establishes that by immediately embedding an unknown quantum system into a high-distance quantum error-correcting code with constant error overhead, fault-tolerant algorithms can extract information exponentially faster than any adaptive strategy that avoids such encoding. The demonstrations focus on classical shadow tomography and the estimation of cubic observables, with the speedups surviving even when the initial encoding step is noisier than direct access to the bare experimental interface. A new Heisenberg learning tree method supplies the matching lower bounds that rule out better performance without immediate uploading. The result shows fault tolerance can turn interface noise from a barrier into an opportunity for reduced experimental repetitions.

Core claim

Quantum uploading embeds the experimental state into an arbitrarily high-distance quantum code with only constant error overhead, after which a fault-tolerant learning algorithm runs on the encoded state. This procedure yields exponential speedups over any adaptive non-uploading strategy for classical shadow tomography and for estimating cubic observables. The separations hold even when the uploading stage is substantially noisier than the bare interface. The Heisenberg learning tree method provides the general tool for proving such lower bounds when the scarce resource is noise tolerance rather than raw quantum copies.

What carries the argument

The quantum uploading procedure, which encodes the unknown experimental system into a high-distance quantum code for subsequent fault-tolerant processing.

If this is right

  • Classical shadow tomography requires exponentially fewer measurements when the state is uploaded and processed fault-tolerantly.
  • Estimation of cubic observables likewise achieves an exponential reduction in experimental shots.
  • The Heisenberg learning tree supplies lower bounds for other noisy quantum learning tasks.
  • Applications such as astronomical imaging locate exoplanets with orders of magnitude fewer photons.
  • Fault-tolerant processors become a practical tool for enhancing data extraction from quantum experiments rather than merely simulating them.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Interfaces for quantum experiments might be redesigned to prioritize rapid encoding over minimizing direct-measurement noise.
  • The approach could extend to other learning tasks such as higher-order observable estimation or quantum metrology.
  • In practice the constant-overhead encoding assumption would need verification on near-term hardware to realize the predicted speedups.
  • Hybrid pipelines that combine classical post-processing with occasional encoded quantum steps might inherit similar advantages.

Load-bearing premise

The unknown system can be embedded into an arbitrarily high-distance quantum code with only constant error overhead even when the uploading stage is noisy.

What would settle it

An experiment or calculation showing that adaptive non-uploading strategies achieve the same sample complexity as the uploaded fault-tolerant method for classical shadow tomography on a noisy interface would falsify the claimed separation.

Figures

Figures reproduced from arXiv: 2605.02057 by Harald Putterman, Ishaan Kannan, Jordan Cotler.

Figure 1
Figure 1. Figure 1: FIG. 1 view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2 view at source ↗
read the original abstract

Quantum information processing has the potential to substantially enhance how we learn from physical experiments, but coupling a quantum processor to an experimental sample introduces noise that can exponentially degrade learning even when the processor itself is fault-tolerant. In this work, we show that fault tolerance can nevertheless be leveraged to recover exponential speedups by embedding the unknown system into an arbitrarily high-distance quantum code with only constant error overhead and running a fault-tolerant learning algorithm. Using this $\textit{quantum uploading}$ procedure, we prove that both classical shadow tomography and the estimation of cubic observables can be performed exponentially faster than by any adaptive strategy that does not immediately upload the state into encoded memory. These separations hold even when the uploading stage is substantially noisier than the bare experimental interface. To prove them, we introduce the Heisenberg learning tree method, a flexible tool for obtaining learning lower bounds when the limited resource is not quantum replicas but an experimentally motivated constraint such as noise. We numerically illustrate the speedups in an astronomical imaging application, where quantum processing of individual uploaded photons locates an exoplanet obscured by a bright star using orders of magnitude fewer shots than unencoded baselines. Our results establish fault-tolerant quantum computation as a valuable tool for learning from quantum experiments.

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.

Referee Report

2 major / 2 minor

Summary. The paper claims that a 'quantum uploading' procedure allows embedding an unknown experimental quantum state into an arbitrarily high-distance quantum error-correcting code with only constant (distance-independent) error overhead, even when the upload channel is noisier than the bare interface. Once encoded, fault-tolerant algorithms for classical shadow tomography and cubic observable estimation achieve exponential speedups over any adaptive strategy that does not upload immediately. The separations are proved via a new 'Heisenberg learning tree' lower-bound method that treats noise as the limited resource; a numerical illustration applies the approach to exoplanet imaging with individual photons.

Significance. If the constant-overhead uploading claim holds, the work would establish fault-tolerant quantum computation as a practical tool for exponentially faster learning from noisy quantum experiments, rather than merely a way to protect computation. The Heisenberg learning tree provides a flexible lower-bound technique for noise-constrained settings that may apply beyond the two examples. The astronomical imaging numerical result supplies a concrete, falsifiable demonstration of orders-of-magnitude shot reduction.

major comments (2)
  1. [Quantum uploading procedure (around the statement of the constant-overhead claim)] The central separation proofs rest on the quantum uploading construction achieving distance-independent logical error with only constant overhead despite a noisier upload channel. The manuscript provides an existence claim and high-level description but does not supply an explicit circuit family, syndrome-extraction scaling analysis, or threshold calculation showing that the total error remains bounded independently of distance (see the paragraph following the definition of the uploading map and the subsequent noise model). Without this, the exponential separation reduces to polynomial when realistic distance-dependent costs are included.
  2. [Heisenberg learning tree method and its application to shadow tomography] The Heisenberg learning tree lower bound is presented as independent of the target result, yet the proof sketch appears to assume that any non-uploading adaptive strategy is limited to bare-interface measurements whose noise cannot be mitigated by encoding. It is unclear whether the tree construction accounts for strategies that interleave partial encoding or use weaker codes; a concrete counter-example or additional lemma showing that such hybrids still incur exponential cost would strengthen the claim.
minor comments (2)
  1. [Notation and definitions] Notation for the upload channel and logical error rate is introduced without a dedicated table or equation summarizing the distance dependence (or lack thereof); adding one would improve readability.
  2. [Numerical illustration] The numerical exoplanet example reports shot counts but does not tabulate the precise code distance, physical error rate, or threshold margin used in the simulation; these parameters should be listed explicitly for reproducibility.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We appreciate the recognition of the significance of the quantum uploading procedure and the Heisenberg learning tree. We address the two major comments below. We agree that both points would benefit from additional detail and clarification in the manuscript and will revise accordingly.

read point-by-point responses

  1. Referee: The central separation proofs rest on the quantum uploading construction achieving distance-independent logical error with only constant overhead despite a noisier upload channel. The manuscript provides an existence claim and high-level description but does not supply an explicit circuit family, syndrome-extraction scaling analysis, or threshold calculation showing that the total error remains bounded independently of distance (see the paragraph following the definition of the uploading map and the subsequent noise model). Without this, the exponential separation reduces to polynomial when realistic distance-dependent costs are included.

    Authors: We acknowledge that the current manuscript presents the uploading procedure at a high level as an existence result. The construction relies on standard fault-tolerance techniques (e.g., concatenated codes or surface-code syndrome extraction) in which, once the physical error rate is below threshold, the logical error can be suppressed to any fixed target with only constant overhead independent of distance. The noise model in the paper treats the upload-channel error rate as fixed and distance-independent, with code distance chosen to meet the target logical error. However, we agree that an explicit circuit sketch and scaling argument would strengthen the claim. In the revision we will add a paragraph detailing the syndrome-extraction overhead (which remains constant for fixed error rate below threshold) together with a reference to standard threshold theorems guaranteeing distance-independent logical error with constant overhead. This addition will make clear that the exponential separation is preserved under realistic costs. revision: yes

  2. Referee: The Heisenberg learning tree lower bound is presented as independent of the target result, yet the proof sketch appears to assume that any non-uploading adaptive strategy is limited to bare-interface measurements whose noise cannot be mitigated by encoding. It is unclear whether the tree construction accounts for strategies that interleave partial encoding or use weaker codes; a concrete counter-example or additional lemma showing that such hybrids still incur exponential cost would strengthen the claim.

    Authors: The Heisenberg learning tree models the cumulative noise budget across adaptive operations; any measurement or gate contributes noise that is only fully suppressed once the state resides in a high-distance code. Partial or weaker encodings leave a residual noise rate comparable to the bare interface, so the effective information gain per shot remains polynomially bounded. While the initial proof focuses on fully unencoded strategies, the tree formalism extends directly to hybrids. In the revision we will insert a short lemma showing that any strategy whose encoding distance remains o(log n) (where n is the number of shots) still incurs an exponential shot overhead, because the uncorrected error probability per logical qubit grows with the number of operations. This lemma will be proved by bounding the total variation distance between the noisy hybrid trajectory and the ideal encoded trajectory, confirming that hybrid approaches cannot evade the exponential cost. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivations rely on independent lower-bound method

full rationale

The paper introduces the Heisenberg learning tree as a new tool for noise-constrained lower bounds and claims exponential separations for shadow tomography and cubic observables via quantum uploading (embedding into high-distance codes with constant overhead). No quoted step reduces the claimed speedups or bounds by construction to fitted parameters, self-definitions, or load-bearing self-citations. The central proofs are presented as independent of the target results, with the uploading procedure treated as an enabling assumption rather than a derived output. This matches the default expectation of self-contained derivations against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 2 invented entities

The central claim rests on the existence of high-distance quantum codes embeddable with constant overhead and on the validity of the new Heisenberg learning tree for proving noise-constrained lower bounds.

axioms (2)
  • domain assumption Quantum error-correcting codes of arbitrarily high distance exist with only constant error overhead for embedding an unknown state.
    Invoked to enable fault-tolerant processing after upload.
  • domain assumption Fault-tolerant quantum computation can be performed on the encoded state to run the learning algorithm.
    Required for the speedups to materialize after uploading.
invented entities (2)
  • Quantum uploading procedure no independent evidence
    purpose: Embed the experimental quantum state into a high-distance code for subsequent fault-tolerant learning.
    Newly defined method that converts noise into a resource for exponential advantage.
  • Heisenberg learning tree method no independent evidence
    purpose: Obtain learning lower bounds when the scarce resource is noise rather than quantum replicas.
    Introduced to prove the exponential separations under the paper's noise model.

pith-pipeline@v0.9.0 · 5518 in / 1482 out tokens · 44595 ms · 2026-05-08T19:20:26.505352+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

37 extracted references · 20 canonical work pages

  1. [1]

    d2 1 T−1X τ=0 ηd1+min(τ,∆) x +d 1 ∆X u=1 T−1X τ=0 ηd1+min(u+τ,∆) x + ∆X x=1 (d1 +x) T−1X τ=0 ηd1+min(x+τ,∆) x + ∆X x=1 ∆X y=x+1 T−1X τ=0 ηd1+min(y+τ,∆) x # , = 1 1−η x

    For every clusterCinVwe have|(e+c)∩C| ≥ |C|/2(instantiating lemma withx→e+c). Necessarily, each clusterCmust contain a vertex ofB. We have that|(e+c)∩C| ≥ |C|/2, and using that the clusters are disjoint, we obtain that |(e+c)∩V|=|(e+c)∩(c 1 ∪ · · · ∪c t)|= X C |(e+c)∩C| ≥ X C∈V |C|/2 =|V|/2.(S55) Sincecis by definition the minimum-weight correction from t...

  2. [2]

    Here, our focus is different: we argue that even given three-copy measurements, any strategy faces an exponential sample complexity lower bound in the presence of noise

    Lower bound without injection In [22] it is demonstrated that any algorithm making joint measurements of at most two copies ofρat a time requiresΩ(2 n/2)measurements, while a protocol with access to three-copy measurements requires only constant measurements. Here, our focus is different: we argue that even given three-copy measurements, any strategy face...

  3. [3]

    To do so, we explicitly compute traces of products of the previously defined operators

    = (1+η 3(A12 +A 13 +A 23)−iη 5B)⊗n 4n .(S139) For notational convenience, define X± =1+η 3(A12 +A 13 +A 23)±iη 5B, Y ij =1+η 3Aij .(S140) Substituting the above formulas into∆3 gives N(∆3) = X ⊗n + +X ⊗n − −2Y ⊗n 12 −2Y ⊗n 13 −2Y ⊗n 23 + 413n 23n(2n + 1)(2n + 2) .(S141) We want to control the square of this object. To do so, we explicitly compute traces o...

  4. [4]

    Here we demonstrate that such a lower bound can also be established for more general observable-estimation tasks of the formtr Oρ3

    Extension of lower bound to cubic observables The previous discussion establishes a noise-dependent lower bound for the particular task of estimatingtr ρ3 . Here we demonstrate that such a lower bound can also be established for more general observable-estimation tasks of the formtr Oρ3 . While this task itself may be useful in certain experimental settin...

  5. [5]

    Third moment estimation upper bound Theorem 11.Letλ ′ ∈[0,1), leta= 1−λ ′, and suppose we are given query access to three noisy copiesD⊗n λ [ρ]⊗3 of an unknownn-qubit stateρ, with no further noise in the circuit. Then there is an algorithm which, using O 1 ϵ2 1−6a −2 + 9a−4 + 12a−6 16 n log 1 δ (S229) experiments, outputs an estimatebm3 satisfying Pr bm3 ...

  6. [6]

    Theorem 12.LetN inj denote the sample complexity of the three-copy cycle test performed on injected copies ofρ subject to depolarizing noise of strengthλ′

    Exponential speedup The following is an immediate corollary upon combining the lower and upper bounds. Theorem 12.LetN inj denote the sample complexity of the three-copy cycle test performed on injected copies ofρ subject to depolarizing noise of strengthλ′. LetN raw denote the sample complexity of any three-copy algorithm for the distinguishing problem w...

  7. [7]

    informative

    Lower bound with noisy brickwork circuits Lemma 18.Consider a classical shadows protocol implemented with a unitary brickwork circuit of depthdand local depolarizing noise of strengthλbetween each circuit layer. Then the number of samplesNrequired to estimatetr(Pkρ) to absolute errorϵ, for arbitrary PauliPk onkcontiguous sites and any quantum stateρ, scal...

  8. [8]

    Lemma 20.LetP k be a Pauli operator supported onkcontiguous qubits

    Upper bound with injection and exponential speedup To compare this lower bound against the injection-enhanced procedure, we prove the following Lemma. Lemma 20.LetP k be a Pauli operator supported onkcontiguous qubits. Consider the protocol that first injects the input stateρinto a logical register via ρlog =U enc D⊗n η (ρ)U † enc,(S284) and then applies ...

  9. [9]

    Dennis, A

    E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Journal of Mathematical Physics43, 4452 (2002). 53

    2002

  10. [10]

    Bombin and M

    H. Bombin and M. A. Martin-Delgado, Physical Review A76, 012305 (2007)

    2007

  11. [11]

    Horsman, A

    D. Horsman, A. G. Fowler, S. Devitt, and R. V. Meter, New Journal of Physics14, 123011 (2012)

    2012

  12. [12]

    A. G. Fowler, A. M. Stephens, and P. Groszkowski, Physical Review A80, 10.1103/physreva.80.052312 (2009)

    work page doi:10.1103/physreva.80.052312 2009

  13. [13]

    A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Physical Review A86, 10.1103/physreva.86.032324 (2012)

    work page doi:10.1103/physreva.86.032324 2012

  14. [14]

    Łodyga, P

    J. Łodyga, P. Mazurek, A. Grudka, and M. Horodecki, Scientific Reports5, 8975 (2015)

    2015

  15. [15]

    Li, New Journal of Physics17, 023037 (2015)

    Y. Li, New Journal of Physics17, 023037 (2015)

    2015

  16. [16]

    Christandl, O

    M. Christandl, O. Fawzi, and A. Goswami, arXiv preprint arXiv:2408.05260 10.48550/arXiv.2408.05260 (2024)

    work page doi:10.48550/arxiv.2408.05260 2024

  17. [17]

    Z. He, Q. T. Nguyen, and C. A. Pattison, arXiv preprint arXiv:2508.08246 10.48550/arXiv.2508.08246 (2025)

    work page doi:10.48550/arxiv.2508.08246 2025

  18. [18]

    Huang, G

    Z. Huang, G. K. Brennen, and Y. Ouyang, Physical Review Letters129, 10.1103/physrevlett.129.210502 (2022)

    work page doi:10.1103/physrevlett.129.210502 2022

  19. [19]

    Khabiboulline, J

    E. Khabiboulline, J. Borregaard, K. De Greve, and M. Lukin, Physical Review Letters123, 10.1103/physrevlett.123.070504 (2019)

    work page doi:10.1103/physrevlett.123.070504 2019

  20. [20]

    Mokeev, B

    A. Mokeev, B. Saif, M. D. Lukin, and J. Borregaard, Enhancing optical imaging via quantum computation (2025), arXiv:2509.09465 [quant-ph]

    work page arXiv 2025

  21. [21]

    Unden, P

    T. Unden, P. Balasubramanian, D. Louzon, Y. Vinkler, M. Plenio, M. Markham, D. Twitchen, A. Stacey, I. Lovchinsky, A. Sushkov, and others, Physical Review Letters116, 10.1103/physrevlett.116.230502 (2016)

    work page doi:10.1103/physrevlett.116.230502 2016

  22. [22]

    X. Wang, C. Liu, X. Lin, Y. Tian, Y. Li, X. Nie, Y. Feng, Y. Zheng, Y. Dong, X. Wang, and others, Noise-resilient quantum metrology with quantum computing (2025), arXiv:2509.00771 [quant-ph]

    work page arXiv 2025

  23. [23]

    C. O. Marrero, R. J. Tang, and N. Wiebe, Encoded quantum signal processing for heisenberg-limited metrology (2026), arXiv:2603.22798 [quant-ph]

    work page arXiv 2026

  24. [24]

    and Danielson D

    J. Cotler, D. L. Danielson, and I. Kannan, Quantum advantage for sensing properties of classical fields (2026), arXiv:2602.17591 [quant-ph]

    work page arXiv 2026

  25. [25]

    Cotler, W

    J. Cotler, W. Gong, and I. Kannan, Noisy quantum learning theory (2026), arXiv:2512.10929 [quant-ph]

    work page arXiv 2026

  26. [26]

    C. Oh, S. Chen, Y. Wong, S. Zhou, H.-Y. Huang, J. A. Nielsen, Z.-H. Liu, J. S. Neergaard-Nielsen, U. L. Andersen, L. Jiang, and others, Physical Review Letters133, 10.1103/physrevlett.133.230604 (2024)

    work page doi:10.1103/physrevlett.133.230604 2024

  27. [27]

    Ansatz-free learning of lindbladian dynamics in situ.arXiv preprint arXiv:2603.05492, 2026

    P. Ivashkov, N. Romanov, W. Gong, A. Gu, H.-Y. Hu, and S. F. Yelin, Ansatz-free learning of lindbladian dynamics in situ (2026), arXiv:2603.05492 [quant-ph]

    work page arXiv 2026

  28. [28]

    S. Chen, J. Cotler, H.-Y. Huang, and J. Li, Exponential separations between learning with and without quantum memory (2021), arXiv:2111.05881 [quant-ph]

    work page arXiv 2021

  29. [29]

    S. Chen, W. Gong, and Q. Ye, Optimal tradeoffs for estimating pauli observables (2024), arXiv:2404.19105 [quant-ph]

    work page arXiv 2024

  30. [30]

    Q. Ye, Z. Liu, and D.-L. Deng, Exponential advantage from one more replica in estimating nonlinear properties of quantum states (2025), arXiv:2509.24000 [quant-ph]

    work page arXiv 2025

  31. [31]

    A. A. Kovalev and L. P. Pryadko, Physical Review A87, 020304(R) (2013)

    2013

  32. [32]

    Huang, M

    H.-Y. Huang, M. Broughton, J. Cotler, S. Chen, J. Li, M. Mohseni, H. Neven, R. Babbush, R. Kueng, J. Preskill, and others, Science376, 1182–1186 (2022)

    2022

  33. [33]

    Z. Liu, W. Gong, Z. Du, and Z. Cai, Exponential separations between quantum learning with and without purification (2025), arXiv:2410.17718 [quant-ph]

    work page arXiv 2025

  34. [34]

    Lloyd, M

    S. Lloyd, M. Mohseni, and P. Rebentrost, Nature Physics10, 631–633 (2014)

    2014

  35. [35]

    W. J. Huggins, S. McArdle, T. E. O’Brien, J. Lee, N. C. Rubin, S. Boixo, K. B. Whaley, R. Babbush, and J. R. McClean, Physical Review X11, 10.1103/physrevx.11.041036 (2021)

    work page doi:10.1103/physrevx.11.041036 2021

  36. [36]

    Huang, R

    H.-Y. Huang, R. Kueng, and J. Preskill, Nature Physics16, 1050–1057 (2020)

    2020

  37. [37]

    H.-Y. Hu, A. Gu, S. Majumder, H. Ren, Y. Zhang, D. S. Wang, Y.-Z. You, Z. Minev, S. F. Yelin, and A. Seif, Nature Communications16, 10.1038/s41467-025-57349-w (2025)

    work page doi:10.1038/s41467-025-57349-w 2025