Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

This paper proves that vectorizing time-evolved operators turns many dynamical correlator estimation problems into a single shadow-tomography task, with exponential query-complexity separations between protocols with and without ancillas or

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-01 23:11 UTC pith:S7NQYNAD

load-bearing objection Strong theory paper with a genuine proof gap in the headline exponential separation; the gap looks fixable, but it is load-bearing and needs a full proof before the result stands. the 3 major comments →

arxiv 2607.15493 v1 pith:S7NQYNAD submitted 2026-07-16 quant-ph

The Complexity of Dynamical Correlators: Operator Shadows and Exponential Learning Separations

Shao-Hen Chiew , Armando Angrisani , Zoe Holmes This is my paper
classification quant-ph MSC 81P6881P45 PACS 03.67.-a
keywords operator shadowsout-of-time-ordered correlatorsclassical shadowsBell samplingquantum memorysample complexity lower boundsPauli transfer matrixvectorization
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 extends classical shadows from static states to dynamics by defining the shadow of an operator: the classical shadow of the vectorized time-evolved Heisenberg operator. It claims that from one such data set one can simultaneously estimate all local OTOCs, with optimal 9^w and 3^w query scalings, and, via a Clifford variant, all two-point Pauli correlators using O(log(M/δ)/ε⁴) queries. The headline results are two exponential separations: estimating all diagonal OTOCs needs Ω(2^n/ε²) queries without ancillas but only O(n/ε²) with n ancillas, while estimating all OTOCs needs Ω(4^n/ε²) queries without quantum memory but only O(n/ε⁴) with quantum memory. If these bounds are right, they fully characterize the query complexity of OTOC learning in the protocol models considered and formalize when the doubled-Hilbert-space strategy is worth its qubit overhead.

Core claim

The central discovery is that dynamical correlators—OTOCs and two-point functions—can be encoded as expectation values of simple observables on the vectorized state |O(t)⟩⟩ of a time-evolved operator, so that randomized measurement toolkits apply directly to dynamics. Pauli operator shadows achieve O(9^w log(M/δ)/ε²) for weight-w OTOCs, improved to O(3^w) for diagonal ones, with matching lower bounds. Clifford operator shadows achieve O(log(M/δ)/ε⁴) for all two-point correlators. The main results are the exponential separations of Theorems 4 and 5: all diagonal OTOCs require Ω(2^n/ε²) queries for any no-ancilla protocol, even adaptive and with quantum memory, versus O(n/ε²) with n ancillas;

What carries the argument

The machinery is the vectorization map |O⟩⟩_Q = Σ_k tr(Q_k O)/sqrt(Σ_i |tr(Q_i O)|²) |k⟩, which turns an n-qubit Heisenberg operator into a 2n-qubit pure state and maps OTOCs to Pauli expectation values of that state. The ricochet identity (U†OU ⊗ I)|I⟩⟩ = |O(t)⟩⟩ allows efficient preparation of these states as Loschmidt echoes. Classical shadow protocols—Pauli (single-qubit Clifford) and Clifford (global Clifford) ensembles—then produce the operator shadow from which many observables are read out; Bell-basis measurement of the vectorized state gives all diagonal OTOCs. Lower bounds are carried by a three-party communication argument and by reducing hard OTOC instances to Pauli-channel eigen

Load-bearing premise

The Ω(2^n/ε²) no-ancilla lower bound depends on Theorem 15 (Appendix E), which is quoted without proof as an adaptation of an existing Pauli-channel distinguishability bound; if that adaptation fails under this paper's definitions of ancillas and quantum memory, the first exponential separation collapses.

What would settle it

Verify the adaptation in Theorem 15 by locating the original result behind the citation and checking whether its protocol model matches the no-ancilla, adaptive, quantum-memory model used here; if the original theorem assumes no concatenation per run or allows extra registers, the lower bound may not transfer. Alternatively, exhibit a no-ancilla adaptive protocol with quantum memory that distinguishes the depolarizing channel from a uniform mixture of Pauli channels using o(2^n/ε²) queries—the paper predicts none exists.

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

If this is right

  • Low-weight OTOC learning is fully characterized: the 9^w and 3^w algorithms cannot be improved in the no-quantum-memory, local-measurement model.
  • One operator-shadow dataset yields estimates for exponentially many dynamical correlators, converting a one-observable-at-a-time workload into a single post-processing pass.
  • Ancillas, not adaptivity or repeated querying per run, are the decisive resource for diagonal OTOCs; quantum memory is the decisive resource for all OTOCs.
  • The tight Θ(n2^{n−n_anc}/ε²) interpolation gives a resource-frugal family: with fewer ancillas one can still estimate all diagonal OTOCs optimally, at exponentially growing cost.
  • Learning weight-w Pauli transfer matrix elements of unknown channels inherits tight Θ(9^w log M/ε²) and Θ(3^w log M/ε²) bounds.

Where Pith is reading between the lines

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

  • If the separations hold, experiments that can double their qubit count should prefer the 2n-qubit Bell or operator-sampling route whenever sample count is the bottleneck; the exponential gap becomes a concrete qubit-for-samples tradeoff.
  • The proof pattern—reduce OTOC learning to Pauli-channel eigenvalue and PTM estimation—likely extends to other operator properties encoded in the Pauli distribution of |O(t)⟩⟩, such as operator stabilizer entropies or local operator entanglement.
  • A concrete testable extension: for fixed small n (say 8–12), implement both the no-ancilla local Pauli protocol and the n-ancilla Bell-sampling protocol for all diagonal OTOCs and compare query counts; the predicted gap grows as 2^n/n and should be visible at modest sizes.
  • The quadratically worse ε dependence of the Clifford shifted-vectorization route (1/ε⁴ versus 1/ε²) suggests that for high-precision two-point correlator estimation, direct amplitude protocols may dominate unless many observables are needed simultaneously.

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

3 major / 5 minor

Summary. The paper introduces 'operator shadows'—classical shadows of vectorized time-evolved operators—and applies them to the simultaneous estimation of dynamical correlators, including OTOCs and two-point correlators. It presents Pauli and Clifford operator-shadow algorithms (Theorems 1 and 2), Bell-sampling-based algorithms for diagonal OTOCs, and matching or near-matching information-theoretic lower bounds. The headline results are exponential query-complexity separations: for all diagonal OTOCs, protocols without ancillas require Ω(2^n/ε²) queries while n-ancilla protocols achieve O(n/ε²) (Theorem 4); for all OTOCs, protocols without quantum memory require Ω(4^n/ε²) while protocols with quantum memory achieve O(n/ε⁴) (Theorem 5). The paper also provides tight Θ(9^w log M/ε²) and Θ(3^w log M/ε²) bounds for low-weight OTOCs (Theorems 1 and 3) and tight bounds for diagonal PTM-element estimation (Theorem 23).

Significance. If correct, the paper would give a fairly complete characterization of the query complexity of OTOC estimation in several natural resource models, and the exponential separations would be noteworthy: they identify ancillas and quantum memory as resources whose absence makes certain OTOC-learning tasks exponentially harder. The algorithmic sections are a genuine strength: the shadow-norm computations (e.g., L_{P⊗P^T}=3^w I in Appendix B) are explicit, the Bell-sampling estimator for diagonal OTOCs correctly uses the fact that each sample is a sign expectation with variance bounded by 1, and the O(n/ε²) and O(n/ε⁴) upper bounds are constructive and concrete. The lower-bound framework—reducing OTOC estimation to channel-discrimination problems with depolarizing/Pauli-channel hard instances—is a sound high-level strategy. However, the two exponential separations rely on quoted or sketched adaptations of prior results ([46, Thm 7] and [4, Lemma D.5]) whose hypotheses are not verified in the paper. These gaps are load-bearing, so the separations should be treated as conditional until the adaptations are supplied.

major comments (3)
  1. [Appendix E, Theorem 15] The no-ancilla lower bound in Theorem 4.1—the key exponential separation—is obtained by invoking Theorem 15, which is stated as 'adapted from [46], Theorem 7' and quoted without proof. The footnote immediately below Theorem 15 acknowledges that the resource-model terminology differs: [46] calls ancillas 'quantum memory', whereas this paper calls multi-query-per-run 'quantum memory'. As written, it is not established that the [46] lower bound survives when each coherent run may contain multiple adaptive queries of the channel with interleaved processing. If the adaptation is not exactly the cited statement, the Ω(2^n/ε²) bound and the exponential separation in Theorem 4 collapse. The authors should either provide a complete proof of Theorem 15 in this protocol model or state precisely which theorem in [46] is being used and prove that its hypotheses hold for the present notion of no-ancil
  2. [Appendix G, Lemma 9] The second exponential separation (Theorem 5, Ω(4^n/ε²) without quantum memory) rests on Lemma 9, which is described as a 'minor extension' of [4, Lemma D.5]. The extension changes the operator-norm condition from eigenvalues ±1 to ∥O_i∥∞≤1 and restricts the queried channel to the form E†∘P∘E, while the proof paragraph only asserts that the learning-tree and Le Cam arguments carry over. Since the bound Δ(O_ij)=Θ(1/4^n) and the resulting Ω(4^n/ε²) both depend on this lemma, the adaptation should be proved in detail, not merely asserted. Otherwise the second exponential separation is unsupported.
  3. [Appendix F, Theorem 16] The tight Θ(n2^{n-n_anc}/ε²) interpolation result also relies on an external result: the proof of Theorem 16 invokes 'Lemma 6, [3]' for the mutual-information bound I((i,s):{ρ_i,E_i})≤3ε²2^{n_anc}/(2^n−1) without proof. This is less central than the previous two gaps, but since Theorem 4.3 is presented as a tight characterization, the dependence on [3] should be made explicit and the relevant bound either proved or stated with full hypotheses.
minor comments (5)
  1. [Appendix B, Eq. (B7)] The formula for the shadow norm bound contains apparent LaTeX artifacts (e.g., misplaced vertical bars and a missing normalization for I⊗I). Please rewrite Eq. (B7) cleanly.
  2. [Appendix G, Lemma 10] The counting in Lemma 10 is confusing: the text says M=4^n(4^n−1) but then sums over 1≤i≤j≤4^n. Since the Pauli set excludes the identity, the indexing range and count should be stated consistently. Also clarify whether O_ij includes signs ±1/2 as separate observables or whether the ± is generated elsewhere.
  3. [References] References [1] and [47] are the same paper (Chen, Cotler, Huang, Li, FOCS 2021) listed twice. Please merge them.
  4. [Appendix E, proof of Theorem 4] The text says 'Theorem 4.1 and 4.2' but the theorem in the main text is numbered Theorem 4 with parts 1 and 2. Align the numbering.
  5. [Figure 1] The caption defines 'Ω=O_{E,O}' informally; it would be clearer to say 'we abbreviate the Loschmidt-echo channel as Γ_{E,O}' to avoid confusion with the Ω(·) asymptotic notation.

Circularity Check

0 steps flagged

No significant circularity: the central upper and lower bounds are reductions to standard shadow and channel-learning results, and the self-citations to [22] do not carry the load of the main theorems.

full rationale

The paper's algorithmic upper bounds construct unbiased estimators from classical shadows of vectorized operator Choi states; the OTOC estimators are direct expectation values, so there is no fitted-parameter/renaming circularity. The lower bounds reduce OTOC estimation to channel-discrimination tasks and invoke external results ([3], [4], [45], [46], [47]) with proofs or named lemmas from those works; even where an adaptation is quoted without proof (Appendix E, Theorem 15, adapted from [46, Theorem 7], with the text 'quoted without proof' and the footnote noting that [46] calls our 'quantum memory' 'concatenation'), that is a verifiability gap and a terminology-mismatch risk, not a circular step, because the cited bound is not defined in terms of the paper's own target quantity. The self-citation to [22] is used mainly for vectorized preparation and Pauli-distribution sampling; the relevant maps are proved via the ricochet identity and Eq. (A6), and the matching lower bounds and exponential separations do not reduce to that citation. No step was found where an equation, parameter, or estimator is equivalent by construction to the claimed output.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

No numerical fitting appears anywhere; all bounds are analytic. The paper introduces mathematical constructions (operator shadows, shifted-vectorization states) rather than new physical entities, so the invented-entity ledger is empty.

axioms (4)
  • standard math Vectorization, ricochet identity, and Choi-Jamiolkowski isomorphism (Appendix A1).
    Used throughout to map Heisenberg operators to 2n-qubit states; standard background proven in cited references [48-50].
  • standard math Classical-shadow sample-complexity results (Theorems 6–7 of [5]) and Pauli shadow tomography with quantum memory (Theorem 8 of [2]).
    Directly imported for the upper bounds in Theorems 1, 2, and 5.
  • standard math Theorem 15, quoted without proof as an adaptation of [46, Theorem 7], giving Ω(2^n/ε²) for distinguishing depolarizing vs uniform Pauli channels without ancillas.
    Load-bearing for Theorem 4's no-ancilla lower bound; the adaptation to the paper's protocol model is asserted rather than proved.
  • domain assumption The query-access model O_{E,O} = E† ∘ Õ ∘ E, with E doubly stochastic, captures the majority of existing OTOC protocols.
    Section IV and Figure 1; the upper bounds need O_{E,O} to be a physical CPTP channel, and the separations are stated within this access model.

pith-pipeline@v1.3.0-alltime-deepseek · 44767 in / 18762 out tokens · 204542 ms · 2026-08-01T23:11:22.478715+00:00 · methodology

0 comments
read the original abstract

Quantum platforms can realize many-body dynamics beyond classical simulation yet complete readout remains intractable: the cost of extracting accessible information scales exponentially with system size. Classical shadows and Bell sampling offer scalable, multi-observable estimation from randomized or entanglement-assisted measurements. Here we aim to push these ideas beyond static snapshots to dynamical correlators, including out-of-time-ordered correlators (OTOCs) and two-point functions. In particular, we introduce the notion of the shadow of an operator, defined as the classical shadow of the vectorized time-evolved operator. Pauli operator-shadows enable simultaneous estimation of all local OTOCs, while Clifford operator-shadows enable efficient simultaneous estimation of all two-point correlators. Alternatively, Bell sampling allows one to simultaneously compute all diagonal OTOCs. We also prove information-theoretic lower bounds for learning OTOCs, fully characterizing their query complexities in many cases, and yielding exponential separations that formalize when the vectorized approach provides measurement-efficiency advantages.

Figures

Figures reproduced from arXiv: 2607.15493 by Armando Angrisani, Shao-Hen Chiew, Zoe Holmes.

Figure 1
Figure 1. Figure 1: Classes of protocols for learning OTOCs considered in our work, which also captures the majority of existing protocols. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Circuit for computing the diagonal PTM elements of N using n + nanc qubits. An instance of the (n + nanc)-qubit circuit to be run, for a specific choice of S ∈ O and Pr ∈ Pn. All qubits are measured in the computational basis in the end. UBell is the Bell basis transformation, while US transforms to the basis { [PITH_FULL_IMAGE:figures/full_fig_p032_2.png] 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. Efficient computation of real-time correlators using Pauli Propagation

    quant-ph 2026-07 conditional novelty 6.0

    Short-time truncated Pauli propagation combined with low-rank positive semi-definite time extension recovers dynamical structure factors for 1D/2D Heisenberg models beyond the direct Pauli window.

Reference graph

Works this paper leans on

35 extracted references · cited by 1 Pith paper

  1. [1]

    Algorithm 1:Pauli operator shadow, 2nqubits Input:Ncopies of the quantum channel OE,O =E † ◦ ˜O◦ E Output:Nclassical snapshots{ˆρ (1) OE,O , ...,ˆρ(N) OE,O }

    Pauli operator shadow for general local OTOCs The procedures for obtaining the classical shadow of Heisenberg operators, as briefly described in the main text, are summarized as Algorithms 1 and 2 below. Algorithm 1:Pauli operator shadow, 2nqubits Input:Ncopies of the quantum channel OE,O =E † ◦ ˜O◦ E Output:Nclassical snapshots{ˆρ (1) OE,O , ...,ˆρ(N) OE...

  2. [2]

    Pauli operator shadow for diagonal local OTOCs When one only seeks to compute diagonal OTOCs – i.e. quantities of the form{tr(O(t)P O(t)P)/2 n}P – such as when studying local operator geometrical properties, a simple modification of the previous operator shadows protocol yields aO(3 w) scaling in sample complexity, compared to theO(9 w) scaling if Theorem...

  3. [3]

    Classical shadows and Pauli tomography Here, we collect several known results for learning properties of unknown quantum states and channels, to be invoked later. Theorem 6(Pauli classical shadow, [5]).GivenNcopies of the quantum stateρ, consider the task of simultaneously estimatingM(a priori unknown) expectation values{tr(ρQ i)}M i=1 each to additive er...

  4. [4]

    Alice wishes to communicate an integerXin{1, ...,2M}to Bob; they achieve this by encoding them as quantum channels expressible in the formE † ◦ ˜O◦ E

    Proof strategy Consider a three-party communication protocol. Alice wishes to communicate an integerXin{1, ...,2M}to Bob; they achieve this by encoding them as quantum channels expressible in the formE † ◦ ˜O◦ E. Alice then chooses one of the 2Mchannels randomly, and sendsNcopies of it to Bob. Alice’s instances are chosen to take the form: Λa,b,s(·)≡ 1 2n...

  5. [5]

    Alice selects an integerXrandomly from{1, ...,2M}, and preparesNcopies of the corresponding channel Λ a,b,s

  6. [6]

    Alice attempts to send them to Bob, but the copies are intercepted by Loki, who modifies allNcopies to Λ ˜a,˜b,s, withU= Nn α=1 U (α), withU (α) ∈ Usampled from a suitable ensemble

  7. [7]

    Bob, upon receiving the channels, applies the OTOC learning protocol. In each of theNrunsj= 1, ..., N, they prepare (n+k)-qubit initial states|u j⟩, query the channel, and perform local measurements with the rank-1 POVM: Fj ={w id|v ij⟩ ⟨vij|},(C4) with|v ij⟩ ≡Nn+k α=1 |v(α) ij ⟩,d= 2 n+k, and P i wi = 1. Bob receives classical outcomesY= (Y 1, ..., YN ),...

  8. [8]

    With this knowledge, Bob usesYto infer Alice’s selected integerX, identifying the integer to be X, which succeeds with high probability

    Loki reveals the identity ofUto Bob. With this knowledge, Bob usesYto infer Alice’s selected integerX, identifying the integer to be X, which succeeds with high probability. Note that it suffices to consider pure input states and rank-1 POVMs without loss of generality; the former because a mixed input state can always be regarded as part of a larger pure...

  9. [9]

    Lower bounds for estimating diagonal OTOCs We begin with the (simpler) case where the OTOCs to be estimated are promised to be diagonal, which is the formal version of the diagonal OTOC part of Theorem 3 of the main text: Theorem 12(Sample complexity lower bound on predicting local diagonal OTOCs; arbitrary initialization). Consider any protocol that is a...

  10. [10]

    Lower bounds for estimating general OTOCs Next, we prove the lower bound for learning general OTOCs, the formal version of Theorem 3 of the main text: Theorem 13(Sample complexity lower bound on predicting local OTOCs).Consider any protocol that is able to predict any set ofMweight-wOTOCs{tr(E(Q i)OE(Q j)O)/2n}i,j whereQ i, Qj are weight-wtensor product o...

  11. [13]

    24 Proof.We prove each case in turn

    Ifw >⌊n/2⌋andM≤ 32w 2 2n 2w , we have the weakerN≥Ω 3w log(M)/ϵ 2 bound instead, for any such protocol that can initialize as arbitrary states. 24 Proof.We prove each case in turn. In all cases, we take Loki’s random unitaries to be products of independently sampled Haar-random single-qubit unitariesU∼ U H (2), which has the effect of transforming the wei...

  12. [14]

    (C1) such that∀Λ a,b,s, the supports ofP a andP b are completely disjoint, i.e

    Product state initialization, weights satisfyw≤ ⌊n/2⌋andM≤ 32w 2 n w n−w w : We choose Alice’s 2Minstances Eq. (C1) such that∀Λ a,b,s, the supports ofP a andP b are completely disjoint, i.e. supp(P a)∩supp(P b) =∅. This can only be done ifw≤ ⌊n/2⌋, and there areM≤ 32w 2 n w n−w w such choices. The ordering ofa, bwithin theseMchoices are unimportant. As a ...

  13. [15]

    We choose the same hard instances as the above case with disjoint supports, which again factorize to yield Eq

    Arbitrary state initialization, weights satisfyw≤ ⌊n/2⌋andM≤ 32w 2 n w n−w w : The proof mirrors the above case closely. We choose the same hard instances as the above case with disjoint supports, which again factorize to yield Eq. (C34). The first factor again evaluates to 1/3 w using Eq. (C28), and we similarly have Eqs. (C35) and (C36). However, becaus...

  14. [16]

    To upper bound the summand of Eq

    Arbitrary state initialization, any weight, andM≤ 32w 2 2n 2w : In this case, we can no longer make use of the hard instances of the previous cases, and have to make do with the weaker class of instances, whereP a ̸=P b are arbitrary weight-wPauli operators, of which there are 32w 2 2n 2w many. To upper bound the summand of Eq. (C17), it suffices to obser...

  15. [17]

    This is a consequence of the unitality of Heisenberg time-evolution, which is generally absent from Schrodinger-picture time-evolution (which are only required to be CPTP)

    The shifted-vectorization encoding|σ(O⟩ ⟩ We begin by showing that the state|σ(O(t))⟩ ⟩ ≡ 1√ 2 (|I⟩ ⟩+i|O(t)⟩ ⟩) can be prepared under essentially the same conditions as the unshifted state|O(t)⟩ ⟩Q. This is a consequence of the unitality of Heisenberg time-evolution, which is generally absent from Schrodinger-picture time-evolution (which are only requir...

  16. [18]

    and the final basisQhas a tensor product structure over partitions of at most sizeO(log(n)). Proof.The following mirrors the proof for the efficient preparation of|O(t)⟩ ⟩Q of [22], with the only replacement being the conjugation by the rotation operatorR O(θ) =e −iθO/2 instead of the operatorO(t= 0). Making use of the linearity of vectorization, and the ...

  17. [19]

    Reduction of operator overlaps to fidelities We begin with the following fact: Lemma 6.Letˆpσ be anϵ-accurate estimator ofp(σ(O), σ(O ′))takingN=O 1/ϵ2 samples, i.e.: |ˆpσ −p(σ(O), σ(O′))| ≤ϵ.(D4) Thenˆc≡2 √ˆpσ −1is anϵ-accurate estimator ofc(O, O ′)takingN=O 1/ϵ4 samples. Proof.The overlapc(O, O ′) can be written as a function of the fidelity between the...

  18. [20]

    The given channel corresponds to the completely depolarizing channelΛ 0(·)≡ 1 2n Itr(·)

  19. [21]

    29 Proof.By Lemma 2, each channel Λ i, fori= 0,

    The given channel is sampled uniformly from the channels{Λ i}4n−1 i=1 , whereΛ i(·)≡ 1 2n (Itr(·) +αQ i tr(Qi ·)), Qi ∈ Pn\{I⊗n}. 29 Proof.By Lemma 2, each channel Λ i, fori= 0, . . . ,4n −1, can be written in the form Λi ≡ E† i ◦ ˜Pi ◦ Ei. Subsequently, for the input Λ i, the resulting set of diagonal OTOCs associated with the nonidentity Pauli operators...

  20. [22]

    The Pauli channel corresponds to the completely depolarizing channelΛ 0(·)≡ 1 2n Itr(·)

  21. [23]

    The protocol must take at leastΩ(2 n/ϵ2)runs

    The Pauli channel is sampled uniformly from one of the channels{Λ i}4n−1 i=1 , whereΛ i(·)≡ 1 2n (Itr(·) + αQi tr(Qi ·)),Q i ∈ Pn\I⊗n, whereα≤1/3. The protocol must take at leastΩ(2 n/ϵ2)runs. We can now prove Theorem 4. Proof.For the lower bound, consider any protocol that satisfies the assumptions of Theorem 4. By the above Lemma, it can also solve the ...

  22. [24]

    The query complexity lower bound N= Ω(n2 n−nanc /ϵ2)holds

    Lower bound Theorem 16(Lower bound of Theorem 4.3).Consider OTOC learning protocols based on querying channels of the formO E,O =E † ◦ ˜O◦ E(for arbitrary doubly-stochastic mapsEand PaulisO) on arbitrary(n+n anc)-qubit density matrices, with0≤n anc ≤n, but without adaptivity and quantum memory. The query complexity lower bound N= Ω(n2 n−nanc /ϵ2)holds. Pr...

  23. [25]

    They require between 0 tonancilla qubits (for a total ofnto 2nqubits), and can be viewed as interpolating between thenand 2n-qubit algorithms

    Upper bound & optimal algorithms for diagonal OTOCs Next, we describe a set of algorithms (without adaptivity and quantum memory) that solve the All Diagonal OTOC Estimation Problem. They require between 0 tonancilla qubits (for a total ofnto 2nqubits), and can be viewed as interpolating between thenand 2n-qubit algorithms. Their query complexities also a...

  24. [26]

    For each stabilizer groupS∈O, prepare the initial state|I⟩ ⟩ ⊗ ϕS 0

  25. [27]

    twirled channel

    Apply the “twirled channel”N r ≡ ePr ◦ N ◦ePr to subsystemH B ⊗ HC, withP r ∈ Pn chosen randomly

  26. [28]

    Measure this state in the basis{|P v⟩ ⟩ ⊗ ϕS e }v,e and record the obtained outcome (v, e)

  27. [29]

    Compute and record the quantityf v,e,s,u = (−1)⟨u,v⟩+⟨s,e⟩

  28. [30]

    This yields an estimate of 1 2n tr P(u,s)N(P (u,s)) for allP (u,s) that are covered by the stabilizer groupS

    Repeat the above steps and compute the empirical average off v,e,s,u. This yields an estimate of 1 2n tr P(u,s)N(P (u,s)) for allP (u,s) that are covered by the stabilizer groupS

  29. [31]

    After having iterated through all stabilizer groups in the stabilizer coveringO, classical post-processing yields all 4n −1 diagonal PTM elements{ 1 2n tr P(u,s)N(P (u,s)) }(u,s). The only difference with Algorithm 1 of [3], which estimates the Pauli eigenvalues of arbitrary Pauli channels (equivalently, their diagonal PTM elements), is the presence of tw...

  30. [32]

    Because OTOCs can be viewed as PTM elements of the channelO E,O , as (c.f

    Algorithms and upper bounds for estimating arbitrary PTM elements Algorithms 1, 2, 3 and 4 yield the classical shadow of the Choi stateρ OE,O of quantum channels of the form OE,O =E † ◦ ˜O◦ E, which subsequently enables the efficient estimation of OTOCs. Because OTOCs can be viewed as PTM elements of the channelO E,O , as (c.f. also Eq. (C2)): 1 2n tr(E(P...

  31. [33]

    Matching lower bounds for estimating arbitrary PTM elements Theorems 12 and 13 apply to protocols (satisfying the stated properties) that query quantum channels of the form OE,O =E † ◦ ˜O◦ Eto output estimates of OTOCs, which can be viewed as PTM elements of the channelO E,O . Any protocol (satisfying the same properties) that query a general quantum chan...

  32. [34]

    Any such protocol that can initialize as arbitrary product states requires at leastN≥Ω 9w log(M)/ϵ 2 runs to solve this problem, ifw≤ ⌊n/2⌋andM≤ 32w 2 n w n−w w

  33. [35]

    Any such protocol that can initialize as arbitrary states requires at leastN≥Ω (9/2)w log(M)/ϵ 2 runs to solve this problem, ifw≤ ⌊n/2⌋andM≤ 32w 2 n w n−w w

  34. [36]

    Ifw >⌊n/2⌋andM≤ 32w 2 2n 2w , we have the weakerN≥Ω 3w log(M)/ϵ 2 bound instead, for any such protocol that can initialize as arbitrary states. Theorems 21 and 22 complement existing lower bounds on the problem of estimating (all) PTM elements of general channels ([4], Theorem 5.6 (for adaptive protocols)), generalizing it to the case of estimating weight...

  35. [37]

    F amily of tight bounds for estimating all diagonal PTM elements using ancillas Consider the problem of estimating all 4n−1 diagonal PTM elements{tr(P iN(P i))/2n}Pi∈Pn of a general channelN. Since this problem is harder than both the Pauli channel eigenvalue problem and the All Diagonal OTOC Estimation Problem, any lower bound on these two problems immed...