Pith. sign in

REVIEW 5 minor 1 cited by

Learning an unknown quantum channel to diamond-norm accuracy ε costs Θ(d_in^3 d_out^3/ε^2) queries without quantum memory and Θ(d_in^2 d_out^2/ε^2) with it.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-02 05:04 UTC pith:SJWLMXZC

load-bearing objection This paper settles the open adaptivity question for incoherent process tomography with a tight Θ(D^3/ε^2) bound and a clean matching upper bound; the main tilt lemma holds up under scrutiny.

arxiv 2607.13476 v1 pith:SJWLMXZC submitted 2026-07-15 quant-ph cs.DSmath-phmath.MP

Quantum memory advantage for quantum process tomography

Carlos Bravo-Prieto , Weiyuan Gong , Antonio Anna Mele This is my paper
classification quant-ph cs.DSmath-phmath.MP
keywords quantum process tomographyquantum memory advantagequery complexitydiamond normincoherent protocolsadaptive protocolsChoi representationposterior anti-concentration
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper settles a long-standing question in quantum process tomography: whether the ability to keep quantum information across multiple uses of an unknown channel gives a real query-complexity advantage. The answer is yes, and the paper pins down the exact size of the advantage. It proves that every protocol that measures after each channel use and keeps only a classical record—even one that adapts its next experiment to all previous outcomes and uses fresh ancillas—needs Θ(d_in^3 d_out^3/ε^2) queries to learn an arbitrary channel to diamond-norm error ε. Coherent protocols that can store quantum systems between uses achieve the optimal Θ(d_in^2 d_out^2/ε^2) for the same task, so quantum memory saves a factor of d_in d_out. This generalizes the known single-copy state-tomography gap, recovered when d_in=1.

Core claim

The central result is a matching pair of bounds. Theorem 1 shows that any adaptive incoherent protocol—allowing arbitrary classical adaptivity, arbitrary fresh ancillas per round, and standard Borel outcome spaces—requires at least c d_in^3 d_out^3/ε^2 queries to learn an arbitrary channel in diamond norm with constant success probability. Theorem 2 gives a non-adaptive, ancilla-free protocol that achieves the same scaling up to a constant factor. Together they determine the optimal incoherent query complexity as Θ(d_in^3 d_out^3/ε^2). Since coherent protocols are already known to achieve Θ(d_in^2 d_out^2/ε^2), the paper establishes a strict quantum-memory separation: retaining quantum infor

What carries the argument

The argument centers on the transcript-wise adaptive tester tilt lemma: once an adaptive protocol's full transcript is fixed, its choices become a deterministic tester sequence, and the likelihood ratio against the true channel, averaged over a symmetric Schatten neighborhood around the depolarizing channel, cannot drop below exp(−O(η^2T/D)). The hard family perturbs the Choi operator in off-diagonal blocks, making trace distances in the channel match Schatten distances in the parameter, so posterior anti-concentration becomes a volume comparison in a matrix space of dimension Θ(D^2).

Load-bearing premise

The proof stands on assuming that no adaptive sequence of experiments can make the data likelihood concentrate sharply on a small neighborhood of the true channel below D^3/ε^2 queries; if that assumption fails for some strategy, the claimed lower bound does not follow.

What would settle it

Evaluate Lemma 8's second-moment bound directly: take a tester element T whose off-diagonal block B_t saturates ∥B_t∥_2 = ∥T_t∥_2, and numerically compute E_W |Tr(B_t^† W)|^2 for W uniform on N_{C,η}. If the covariance constant exceeds C^2 L_η^2/(4 r^3), the tilt lemma's uniform estimate fails and the Ω(D^3/ε^2) lower bound would not follow.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Any future incoherent process-tomography protocol must use Ω(d_in^3 d_out^3/ε^2) queries; adaptivity and ancillas cannot improve this.
  • The previously known incoherent upper bound with logarithmic overhead is tight up to constants; a non-adaptive, ancilla-free protocol already matches the lower bound.
  • Coherent protocols remain the optimal option, so the factor d_in d_out is the exact price of discarding quantum memory.
  • Setting d_in=1 reproduces the known Θ(d_out^3/ε^2) optimal sample complexity for single-copy quantum state tomography, confirming the state case as a special instance.

Where Pith is reading between the lines

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

  • The off-diagonal perturbation trick is likely reusable: adapting the hard family to low-Kraus-rank or structured channels (e.g., Pauli or Gaussian) should yield analogous lower bounds, although the paper does not prove these.
  • One would expect a smooth tradeoff: protocols allowed to keep k coherent copies across uses should interpolate between the incoherent D^3/ε^2 and coherent D^2/ε^2 rates; the paper leaves this intermediate regime open.
  • The upper-bound technique—bounding scalar quadratic forms by Bernstein and then covering the sphere with a constant-radius net—is a transferable replacement for matrix concentration that can remove logarithmic factors in other single-copy estimation problems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper resolves the query-complexity question for quantum process tomography by incoherent protocols, i.e. protocols that measure after each channel use and retain only classical data, while allowing arbitrary classical adaptivity and ancilla-assisted inputs within each round. The main results are: (Theorem 1) every adaptive incoherent protocol for learning an arbitrary channel Φ:L(A)→L(B) to diamond-norm accuracy ε requires T≥c d_in^3 d_out^3/ε² queries, even with fresh ancilla per query; and (Theorem 2) a matching non-adaptive, ancilla-free upper bound O(d_in^3 d_out^3/ε²). Together with previously known coherent-protocol bounds Θ(d_in² d_out²/ε²), this gives a strict quantum-memory advantage of order Θ(D), D=d_in d_out. The lower bound is proved by constructing a high-dimensional hard family of channels near the depolarizing channel, representing each round by a one-slot tester, conditioning on transcripts to freeze adaptive choices, and proving a transcript-wise likelihood tilt lemma that drives a Bayesian posterior anti-concentration argument. The upper bound uses an unbiased random-basis Choi estimator and scalar Bernstein concentration over a constant-radius net, removing logarithmic factors from earlier incoherent upper bounds.

Significance. If correct, the result is significant: it closes the open gap between adaptive incoherent and coherent process tomography, establishes the optimal incoherent complexity Θ(D³/ε²), and generalizes the known optimal Θ(d³/ε²) single-copy state-tomography bound to arbitrary channels. The lower bound is robust—it covers arbitrary classical adaptivity, ancilla-assisted inputs, and standard Borel outcome spaces—and the proof is self-contained, with explicit constants and no fitted parameters. The upper bound is likewise explicit and even ancilla-free. I checked the main structural steps: the hard family is a valid set of channels (Lemma 3), the trace-distance conversion is exact (Lemma 4), and the tilt lemma's second-moment and volume estimates are internally consistent. The paper ships a complete proof rather than a sketch, and the technical innovations—the off-diagonal Choi embedding and the transcript-wise tilt estimate—are credible and well matched to the problem.

minor comments (5)
  1. [Appendix D, Eq. (D8)] For complex W, the displayed isotropy condition E[W_ij W_kl]=α δ_ik δ_jl is false as written. It should read E[W_ij \overline{W_kl}]=α δ_ik δ_jl (with α=E||W||₂²/r²). The surrounding derivation of E|Tr(B†W)|²=α||B||₂² uses the conjugated version, so the proof is correct once this typo is fixed.
  2. [Appendix G, Lemma 17] The covering bound is printed as |T|≤92D; this must be |T|≤9^{2D}, as the volume comparison in the proof directly shows. The subsequent union bound correctly uses exp(2D log 9).
  3. [Appendix G, Lemma 15 proof] The sentence 'using P_v^T=P_v' is not correct for a fixed complex vector v; in general P_v^T=P_{\bar v}. The estimator and variance bound still go through because \bar v is Haar-distributed whenever v is Haar-distributed, but the displayed identity should be replaced by the distributional statement. The same applies to the garbled phrase 'Because v is Haar-distributed whenever v is Haar-distributed,' which should refer to \bar v.
  4. [Appendix F] The measure-theoretic extension is terse. The density argument is standard, and the claims are plausible, but a few more details on why the likelihood-ratio factorization and common support hold for POVM densities would improve readability.
  5. [Throughout] The notation 92D in Lemma 17 and a few missing bars on v in Appendix G are likely LaTeX artifacts, but they should be corrected in the final version to avoid confusion.

Circularity Check

0 steps flagged

No significant circularity: all load-bearing bounds are proved in-line from explicit constructions and concentration arguments.

full rationale

The paper's central claims are derived self-contained rather than imported from its inputs. The lower bound (Theorem 1) constructs an explicit hard family near the depolarizing channel, represents each round by a tester, and then proves the key transcript-wise tilt estimate (Lemma 8, Appendix D) from the operator-norm constraint on N_{C,eta}, the off-diagonal structure of E(W), and the unitary invariance of N_{C,eta}. This estimate converts adaptivity into a deterministic sequence of testers and is not assumed. The posterior anti-concentration lemma (Lemma 10) follows from the volume comparison in Lemma 7, the prior density ratio in Lemma 5, and Lemma 8, with explicit constants chosen in the proof. The upper bound (Theorem 2, Appendix G) is also proved in full: the estimator is shown unbiased and its directional variance is bounded by a universal constant, then scalar Bernstein concentration plus a constant-radius net gives O(D^3/epsilon^2) with no logarithmic factor. The coherent Θ(D^2/epsilon^2) bound is cited only as an external benchmark for comparison, not as a load-bearing input; the state-tomography bound [35] is likewise a benchmark and is not used to force the channel results. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported from the authors' prior work, and no ansatz is smuggled in via citation. The only subtlety is that the isotropy statement in Eq. (D8) must be read with a conjugate for complex entries, exactly as used in Eq. (D11); this is a notational slip, not a circular reduction. Because the lower and upper bounds are each established by explicit first-principles proofs against a constructed hard family and independent concentration inequalities, there is no self-definitional or fitted-input circularity. Score 0 is appropriate.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

No empirical data are used; all numerical constants (σ, C, c_ac, κ, K_tilt, 30000) are universal proof constants fixed by inequalities, not fitted degrees of freedom. The hard channel family and the Bayesian prior are mathematical tools for the lower-bound proof, not physical postulates. The axioms listed are standard theorems and protocol-model assumptions, each cited or proved in the paper.

axioms (5)
  • standard math Choi characterization: Φ is a quantum channel iff its normalized Choi operator satisfies JΦ ≥ 0 and Tr_B JΦ = I_A/d_in.
    Used in Eq. (3) and Lemma 3 to construct and validate the hard family; standard Choi-Jamiołkowski theorem.
  • standard math Single-round incoherent measurements can be represented by positive operators {T_y} with PΦ(y)=d_in Tr(T_y JΦ) and ∑ T_y = τ^T ⊗ I_B.
    Lemma 1 plus Appendix A prove this via purification/vectorization; the tester representation is central to freezing adaptive transcripts.
  • domain assumption Conditioning on a fixed transcript makes the adaptive choices deterministic, so the likelihood ratio factors as a product of single-round tester ratios.
    Eq. (22) is the formal mechanism for handling adaptivity; it follows from the protocol model of incoherent measurements.
  • standard math Complex Ginibre operator-norm tail bounds and Schatten-ball volume asymptotics hold with universal constants.
    Used in Lemmas 5 and 7 for prior regularity and local volume comparisons; cited to Refs. [38] and standard random-matrix theory.
  • standard math Bernstein's inequality as stated in Lemma 16 and Haar moment identities for random bases and unitaries hold.
    Used in the upper-bound concentration argument (Appendix G), specifically scalar Bernstein and Haar moments for the random-basis reconstruction.

pith-pipeline@v1.3.0-alltime-deepseek · 24381 in / 17679 out tokens · 182760 ms · 2026-08-02T05:04:20.908671+00:00 · methodology

0 comments
read the original abstract

Quantum process tomography, the task of learning an unknown quantum channel from black-box access, is a central problem in quantum information. In this setting, protocols with quantum memory can coherently store and jointly process quantum information obtained from multiple channel uses, whereas protocols without quantum memory must measure after each use and retain only a classical transcript of the measurement outcomes. A fundamental open question is whether quantum memory provides a query-complexity advantage even when protocols without quantum memory may adapt their experiments based on all previous outcomes with unbounded classical computational power. In this work, we show that it does. We determine the optimal query complexity of quantum process tomography without quantum memory up to a constant factor to be $\Theta(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$, where $d_{\mathrm{in}}$ and $d_{\mathrm{out}}$ are the channel input and output dimensions, respectively, and $\varepsilon$ is the target diamond-norm accuracy. More precisely, we prove that any incoherent protocol for this task, including adaptive protocols, requires $\Omega(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$ queries, even when each channel use may be assisted by arbitrary fresh ancilla, and we present a non-adaptive, ancilla-free incoherent protocol achieving the matching upper bound $O(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$. Our results thereby generalize the optimal sample-complexity bounds for single-copy state tomography, recovered as the special case $d_{\mathrm{in}}=1$. By contrast, coherent protocols with quantum memory achieve query complexity $\Theta(d_{\mathrm{in}}^2 d_{\mathrm{out}}^2/\varepsilon^2)$. Hence, our results establish a rigorous learning separation between quantum process tomography with and without quantum memory.

Figures

Figures reproduced from arXiv: 2607.13476 by Antonio Anna Mele, Carlos Bravo-Prieto, Weiyuan Gong.

Figure 1
Figure 1. Figure 1: Overview of the proof strategy. We first construct a local family of channels near the completely depolarizing channel. Each channel is indexed by a matrix perturbation of the normalized Choi operator. We then represent every round of an adaptive incoherent protocol by a single-round tester. Along any transcript, the adaptivity protocol yields a deterministic sequence of tester elements. The key technical … view at source ↗

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Learning Arbitrary Lindbladians from Time Evolution

    quant-ph 2026-07 accept novelty 7.0

    Arbitrary Lindbladians of strength ≤Λ are learned entrywise to error ε with Õ(Λ²/ε²) ancilla-free, control-free experiments and Õ(Λ/ε²) total evolution time.

Reference graph

Works this paper leans on

56 extracted references · 6 linked inside Pith · cited by 1 Pith paper

  1. [1]

    I. L. Chuang and M. A. Nielsen, Prescription for experimental determination of the dynamics of a quantum black box, Journal of Modern Optics44, 2455 (1997)

    1997

  2. [2]

    Poyatos, J

    J. Poyatos, J. I. Cirac, and P. Zoller, Complete characterization of a quantum process: the two-bit quantum gate, Physical Re- view Letters78, 390 (1997)

    1997

  3. [3]

    Helsen, I

    J. Helsen, I. Roth, E. Onorati, A. H. Werner, and J. Eisert, Gen- eral framework for randomized benchmarking, PRX Quantum 3, 020357 (2022)

    2022

  4. [4]

    Mohseni, A

    M. Mohseni, A. T. Rezakhani, and D. A. Lidar, Quantum- process tomography: Resource analysis of different strategies, Physical Review A77, 032322 (2008)

    2008

  5. [5]

    J. L. O’Brien, G. J. Pryde, A. Gilchrist, D. F. James, N. K. Langford, T. C. Ralph, and A. G. White, Quantum process to- mography of a controlled-not gate, Physical Review Letters93, 080502 (2004)

    2004

  6. [6]

    Riebe, K

    M. Riebe, K. Kim, P. Schindler, T. Monz, P. Schmidt, T. K¨orber, W. H¨ansel, . f. H. H ¨affner, C. F. Roos, and R. Blatt, Process tomography of ion trap quantum gates, Physical Review Letters 97, 220407 (2006)

    2006

  7. [7]

    R. C. Bialczak, M. Ansmann, M. Hofheinz, E. Lucero, M. Nee- ley, A. D. O’Connell, D. Sank, H. Wang, J. Wenner, M. Steffen, et al., Quantum process tomography of a universal entangling gate implemented with josephson phase qubits, Nature Physics 6, 409 (2010)

    2010

  8. [8]

    C. J. Ballance, T. P. Harty, N. M. Linke, M. A. Sepiol, and D. M. Lucas, High-fidelity quantum logic gates using trapped-ion hy- perfine qubits, Physical Review Letters117, 060504 (2016)

    2016

  9. [9]

    Bouchard, F

    F. Bouchard, F. Hufnagel, D. Koutn`y, A. Abbas, A. Sit, K. Hes- hami, R. Fickler, and E. Karimi, Quantum process tomography of a high-dimensional quantum communication channel, Quan- tum3, 138 (2019)

    2019

  10. [10]

    Blume-Kohout, J

    R. Blume-Kohout, J. K. Gamble, E. Nielsen, K. Rudinger, J. Mizrahi, K. Fortier, and P. Maunz, Demonstration of qubit operations below a rigorous fault tolerance threshold with gate set tomography, Nature Communications8, 14485 (2017)

    2017

  11. [11]

    A. J. Scott, Optimizing quantum process tomography with uni- tary 2-designs, Journal of Physics A: Mathematical and Theo- retical41, 055308 (2008)

    2008

  12. [12]

    A. Y . Kitaev, Quantum computations: algorithms and error cor- rection, Russian Mathematical Surveys52, 1191 (1997)

    1997

  13. [13]

    Gilchrist, N

    A. Gilchrist, N. K. Langford, and M. A. Nielsen, Distance mea- sures to compare real and ideal quantum processes, Physical Review A71, 062310 (2005)

    2005

  14. [14]

    Watrous, Simpler semidefinite programs for completely bounded norms, arXiv:1207.5726 (2012)

    J. Watrous, Simpler semidefinite programs for completely bounded norms, arXiv:1207.5726 (2012)

    Pith/arXiv arXiv 2012

  15. [15]

    Watrous,The theory of quantum information(Cambridge uni- versity press, 2018)

    J. Watrous,The theory of quantum information(Cambridge uni- versity press, 2018)

    2018

  16. [16]

    Aharonov, A

    D. Aharonov, A. Kitaev, and N. Nisan, Quantum circuits with mixed states, inProceedings of the thirtieth annual ACM sym- posium on Theory of computing(1998) pp. 20–30

    1998

  17. [17]

    Hayashi, Asymptotic estimation theory for a finite- dimensional pure state model, Journal of Physics A: Mathemat- ical and General31, 4633 (1998)

    M. Hayashi, Asymptotic estimation theory for a finite- dimensional pure state model, Journal of Physics A: Mathemat- ical and General31, 4633 (1998)

    1998

  18. [18]

    O’Donnell and J

    R. O’Donnell and J. Wright, Efficient quantum tomography, inProceedings of the forty-eighth annual ACM symposium on Theory of Computing(2016) pp. 899–912

    2016

  19. [19]

    A. A. Mele and L. Bittel, Optimal learning of quantum channels in diamond distance, arXiv:2512.10214 (2025)

    arXiv 2025

  20. [20]

    Choi, Completely positive linear maps on complex ma- trices, Linear algebra and its applications10, 285 (1975)

    M.-D. Choi, Completely positive linear maps on complex ma- trices, Linear algebra and its applications10, 285 (1975)

    1975

  21. [21]

    J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu, Sample- optimal tomography of quantum states, inProceedings of the forty-eighth annual ACM symposium on Theory of Computing (2016) pp. 913–925

    2016

  22. [22]

    Kueng, H

    R. Kueng, H. Rauhut, and U. Terstiege, Low rank matrix recov- ery from rank one measurements, Applied and Computational Harmonic Analysis42, 88 (2017)

    2017

  23. [23]

    S. Chen, B. Huang, J. Li, A. Liu, and M. Sellke, When does adaptivity help for quantum state learning?, in2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)(IEEE, 2023) pp. 391–404

    2023

  24. [24]

    S. Chen, J. Li, and A. Liu, An optimal tradeoff between entan- glement and copy complexity for state tomography, inProceed- ings of the 56th Annual ACM Symposium on Theory of Comput- ing, STOC 2024 (Association for Computing Machinery, New York, NY , USA, 2024) p. 1331–1342

    2024

  25. [25]

    Aharonov, J

    D. Aharonov, J. Cotler, and X.-L. Qi, Quantum algorithmic measurement, Nature Communications13, 887 (2022)

    2022

  26. [26]

    S. Chen, J. Cotler, H.-Y . Huang, and J. Li, Exponential separa- tions between learning with and without quantum memory, in 2021 IEEE 62nd Annual Symposium on Foundations of Com- puter Science (FOCS)(IEEE, 2022) pp. 574–585

    2021

  27. [27]

    Huang, M

    H.-Y . Huang, M. Broughton, J. Cotler, S. Chen, J. Li, M. Mohseni, H. Neven, R. Babbush, R. Kueng, J. Preskill, and J. R. McClean, Quantum advantage in learning from experi- ments, Science376, 1182–1186 (2022)

    2022

  28. [28]

    S. Chen, S. Zhou, A. Seif, and L. Jiang, Quantum advantages for Pauli channel estimation, Physical Review A105, 032435 (2022)

    2022

  29. [29]

    Fawzi, A

    O. Fawzi, A. Oufkir, and D. S. Franc ¸a, Lower bounds on learn- ing Pauli channels with individual measurements, IEEE Trans- actions on Information Theory71, 2642 (2025)

    2025

  30. [30]

    Chen and W

    S. Chen and W. Gong, Efficient Pauli channel estimation with logarithmic quantum memory, PRX Quantum6, 020323 (2025)

    2025

  31. [31]

    S. Chen, C. Oh, S. Zhou, H.-Y . Huang, and L. Jiang, Tight bounds on pauli channel learning without entanglement, Physi- cal Review Letters132, 180805 (2024)

    2024

  32. [32]

    Surawy-Stepney, J

    T. Surawy-Stepney, J. Kahn, R. Kueng, and M. Guta, Projected least-squares quantum process tomography, Quantum6, 844 (2022). 11

    2022

  33. [33]

    Oufkir, Sample-optimal quantum process tomography with non-adaptive incoherent measurements, in2023 IEEE Interna- tional Symposium on Information Theory (ISIT)(IEEE, 2023) pp

    A. Oufkir, Sample-optimal quantum process tomography with non-adaptive incoherent measurements, in2023 IEEE Interna- tional Symposium on Information Theory (ISIT)(IEEE, 2023) pp. 1919–1924

    2023

  34. [34]

    K. Chen, F. Girardi, A. Oufkir, N. Yu, and Z. Zhang, Quan- tum channel tomography: optimal bounds and a heisenberg-to- classical phase transition, arXiv:2604.17369 (2026)

    Pith/arXiv arXiv 2026

  35. [35]

    Gut ¸˘a, J

    M. Gut ¸˘a, J. Kahn, R. Kueng, and J. A. Tropp, Fast state tomog- raphy with optimal error bounds, Journal of Physics A: Mathe- matical and Theoretical53, 204001 (2020)

    2020

  36. [36]

    Gutoski and J

    G. Gutoski and J. Watrous, Toward a general theory of quantum games, inProceedings of the thirty-ninth annual ACM sympo- sium on Theory of computing(2007) pp. 565–574

    2007

  37. [37]

    Chiribella, G

    G. Chiribella, G. M. D’Ariano, and P. Perinotti, Theoreti- cal framework for quantum networks, Physical Review A80, 022339 (2009)

    2009

  38. [38]

    Kabluchko, J

    Z. Kabluchko, J. Prochno, and C. Thaele, Exact asymptotic vol- ume and volume ratio of schatten unit balls, Journal of Approx- imation Theory257, 105457 (2020)

    2020

  39. [39]

    Christensen and A

    A. Christensen and A. Zhao, Learning fermionic linear optics with heisenberg scaling and physical operations, arXiv:2602.05058 (2026)

    arXiv 2026

  40. [40]

    Fanizza, V

    M. Fanizza, V . Iyer, J. Lee, A. A. Mele, and F. A. Mele, Effi- cient learning of bosonic gaussian unitaries, arXiv:2510.05531 (2026)

    Pith/arXiv arXiv 2026

  41. [41]

    Zambrano, S

    L. Zambrano, S. Ramos-Calderer, and R. Kueng, Fast quan- tum measurement tomography with dimension-optimal error bounds, arXiv:2507.04500 (2025)

    Pith/arXiv arXiv 2025

  42. [42]

    Arunachalam and L

    S. Arunachalam and L. Schatzki, Optimal stabilizer testing and learning with limited quantum memory, arXiv:2607.02444 (2026)

    Pith/arXiv arXiv 2026

  43. [43]

    A. W. Harrow, The church of the symmetric subspace, arXiv:1308.6595 (2013)

    Pith/arXiv arXiv 2013

  44. [44]

    A. A. Mele, Introduction to haar measure tools in quantum in- formation: A beginner’s tutorial, Quantum8, 1340 (2024)

    2024

  45. [45]

    Huang, R

    H.-Y . Huang, R. Kueng, and J. Preskill, Predicting many prop- erties of a quantum system from very few measurements, Na- ture Physics16, 1050 (2020)

    2020

  46. [46]

    Quantum memory advantage for quantum process tomography

    S. Boucheron, G. Lugosi, and P. Massart,Concentration In- equalities: A Nonasymptotic Theory of Independence(Oxford University Press, Oxford, 2013). 12 Supplementary Material for “Quantum memory advantage for quantum process tomography” Appendix A: Proof of the single-round tester representation Proof of Lemma 1.We first show that one can always reduce a ...

    2013

  47. [47]

    ≥(4r) −2r2 vol(Br ∞) vol(Br

  48. [48]

    ≥(4r) −2r2 (ar)2r2 = a 4 2r2 .(C12) Settingc vol := 2 log(4/a)proves Eq. (47). For the scaled estimate, we observe thatN C,η is the dilation byCL η of the set{W:∥W∥ 1 ≤1,∥W∥ ∞ ≤1/(4r)}, whereas {W:∥W∥ 1 ≤L η}is the dilation byL η ofB r

  49. [49]

    Since the real dimension is2r 2, we have vol(NC,η) vol{W:∥W∥ 1 ≤L η} =C 2r2 vol{W:∥W∥ 1 ≤1,∥W∥ ∞ ≤1/(4r)} vol(Br

  50. [50]

    15 Appendix D: Proof of the transcript-wise adaptive tester tilt lemma Proof of Lemma 8.FixX 0 ∈G,C >1, and a transcriptz= (y 1,

    ≥C 2r2 e−cvolr2 .(C13) This proves the claim. 15 Appendix D: Proof of the transcript-wise adaptive tester tilt lemma Proof of Lemma 8.FixX 0 ∈G,C >1, and a transcriptz= (y 1, . . . , yT )with positive probability underΦ X0. For readability, writeT t =T t(z), and define qt := Tr(TtJX0 ), a t(W) := Tr(Tt∆W ) qt ,(D1) where∆ W :=J X0+W −J X0. SinceP X0 (z)>0...

  51. [51]

    For eacht∈ {1,

    The estimator Fix an integerT≥1. For eacht∈ {1, . . . , T}, independently perform the following experiment. (i) Sample a Haar-random unit vectorv t ∈A. (ii) PrepareP vt, applyΦonce, and obtain the output stateΦ(P vt ). (iii) Independently sampleU t from Haar measure onU(d out)and measureΦ(P vt )in the orthonormal basis{U t |j⟩}dout j=1 . Let It be the obs...

  52. [52]

    Haar moments and random-basis reconstruction Lemma 11(First three Haar moments [43, 44]).Letu∼µ d, and letΠ (k) sym be the orthogonal projector onto the symmetric subspace of(C d)⊗k. Fork∈ {1,2,3}, Eu∼µd P ⊗k u = Π(k) sym d+k−1 k .(G5) In particular, ifFdenotes the swap operator onC d ⊗C d, then EPu = Id d ,EP ⊗2 u = I+F d(d+ 1) ,EP ⊗3 u = Π(3) sym d+2 3 ...

  53. [53]

    Unbiasedness of the Choi estimator Lemma 13(Choi frame identity).Forv∼µ din, (din + 1)Ev P ⊤ v ⊗Φ(P v) =J Φ +I A ⊗Φ IA din .(G18) Proof.LetFbe the swap operator onA⊗A. Taking the transpose on the first tensor factor of the second Haar-moment identity gives Ev P ⊤ v ⊗P v = IA ⊗I A +F ⊤1 din(din + 1) .(G19) A direct expansion of the swap operator shows that...

  54. [54]

    22 Proof.Let RA := TrB |z⟩ ⟨z|, R B := TrA |z⟩ ⟨z|.(G28) BothR A andR B are density operators

    Dimension-independent directional variance Lemma 15(Directional variance and range).For every unit vectorz∈A⊗B, define Gz :=⟨z|X t |z⟩.(G25) Then Var(Gz)≤140.(G26) Moreover, |Gz − ⟨z|JΦ |z⟩| ≤2D(G27) almost surely. 22 Proof.Let RA := TrB |z⟩ ⟨z|, R B := TrA |z⟩ ⟨z|.(G28) BothR A andR B are density operators. For fixedv, define the positive operator onB Qv...

  55. [55]

    TX t=1 ξt ≥T s # ≤exp −λT s+ T λ2σ2 2(1−λR/3) .(G42) Choose λ:= s σ2 +Rs/3 .(G43) Then0≤λ <3/Rand 1− λR 3 = σ2 σ2 +Rs/3 .(G44) Substitution into Eq. (G42) yields P

    Scalar concentration and a covering net We recall the following standard form of Bernstein’s inequality; see, for example, Ref. [46, Eq. (2.10), p. 36]. For complete- ness, we include a self-contained proof that keeps track of the constants. Lemma 16(Scalar Bernstein inequality).Letξ 1, . . . , ξT be independent mean-zero real random variables satisfying|...

  56. [56]

    Then ∥Φ−Ψ∥ ⋄ ≤d indout ∥JΦ −J Ψ∥∞ =D∥J Φ −J Ψ∥∞ .(G58) 25 Proof.Set∆ := Φ−ΨandJ ∆ :=J Φ −J Ψ

    Projection and conversion to diamond norm Lemma 18(Operator norm of the Choi difference controls diamond norm).LetΦ,Ψ :L(A)→ L(B)be quantum channels. Then ∥Φ−Ψ∥ ⋄ ≤d indout ∥JΦ −J Ψ∥∞ =D∥J Φ −J Ψ∥∞ .(G58) 25 Proof.Set∆ := Φ−ΨandJ ∆ :=J Φ −J Ψ. The map∆is Hermiticity preserving. By the standard pure-state characterization of the diamond norm, with a refere...