Exponential separations between learning with and without quantum memory

1 Introduction

• The authors develop flexible lower-bound frameworks that strengthen and generalize prior separations, enabling tighter bounds and broader, more realistic settings than [ACQ21].The framework supports provable separations between algorithms that retain quantum data and conventional algorithms that measure each experiment and retain only classical outcomes.Source: §1 · p. 4

1.1.1 Learning physical systems

• For general shadow tomography, algorithms without quantum memory require Ω(min(M, 2^n)) copies in the worst case, matching the best upper bound up to logarithmic factors and resolving the question posed in.For all M > 1, the lower bound applies to a suitable set of M observables; the paper also proves an Ω(2^n) lower bound for predicting all n-qubit Pauli observables.Source: Shadow tomography · p. 6
• Purity testing exhibits an exponential separation: quantum memory achieves O(1) samples for pure-versus-maximally-mixed testing, whereas memoryless algorithms require Θ(2^(n/2)) samples.The upper bound uses a SWAP test with 2-entangled measurements and n additional memory qubits; the matching memoryless lower bound applies to distinguishing a pure state from the maximally mixed state.Source: Shadow tomography · p. 7

1.1.2 Smooth tradeoffs for learning with quantum memory

• With k qubits of quantum memory, estimating absolute values of all n-qubit Pauli expectations requires Ω(2^((n-k)/3)) copies, while n-qubit memory suffices with O(n) copies.This establishes a first fine-grained tradeoff between memory size and sample complexity, though the full dependence on k remains open.Source: §1.1.2 · p. 7

1.1.3 Learning quantum dynamics

• For quantum dynamics, the paper extends [ACQ21] to unrestricted memoryless algorithms, proving Ω(2^(n/3)) experiments for depolarizing-versus-Haar-unitary testing and Ω(2^(2n/7)) for time-reversal-symmetry discrimination.These lower bounds allow arbitrary ancilla qubits and combine with O(1)-experiment quantum-memory algorithms to yield exponential separations.Source: §1.1.3 · pp. 8–9

2 Technical Overview

• Lower bounds start with Le Cam’s two-point method, comparing a null distribution with a mixture of alternatives through total variation rather than chi-squared or KL divergence.The authors emphasize that direct total-variation analysis is necessary for the Pauli-observable lower bound, where chi-squared methods yield only Ω(poly(n, 1/ε)) samples.Source: §2 · p. 9

2.1 Tree representation

• Adaptive learning algorithms are represented as rooted trees whose nodes encode prior outcomes and whose leaves induce distributions compared under the null and alternative hypotheses [ACQ21].The analysis separates edge-based methods, which bound information gained on individual edges, from path-based methods, which exploit multilinear structure and high-order moments.Source: §2.1 · pp. 10–11

2.2 Edge-based analysis

• Edge-based analysis bounds average discrepancy per measurement, converts it through convexity into one-sided likelihood-ratio bounds, and yields near-optimal memoryless shadow-tomography lower bounds.For Pauli observables, the information quantity δ(O1, ..., OM) is bounded by O(1/2^n), while the same framework extends to Haar-random general observables.Source: §2 · p. 10, §2.2 · p. 12

2.3 Path-based analysis

• Path-based analysis handles cases where many edges have substantial discrepancy by exploiting tensor-product path structure and high-order moments of random states or channels.For purity testing, this produces an Ω(2^(n/2)) lower bound; channel learning instead uses Weingarten expansions and tensor-network manipulations because uniform likelihood-ratio bounds are harder to obtain.Source: §2.3 · pp. 12–14

Learning properties of quantum states

• Quantum tomography requires Θ(22n) samples, making shadow tomography a proposed route around the exponential-in-n barrier.Subsequent shadow-tomography work improved sample-complexity upper bounds, although many algorithms require heavily entangled measurements and substantial quantum memory [BO20].Source: §3 · p. 15
• The Pauli-observable setting is independently important because it supports many quantum-computing applications, including randomized benchmarking and related protocols [PK19] [YVI19] [GAD+19] [HMR+19] [CvSW+20] [HKT+21].Memoryless shadow-tomography algorithms in [HKP20, HKP21b] match the general-case lower bound achieved here and improve bounds in special cases.Source: §3 · p. 15

Quantum property testing

• Quantum property-testing settings such as state discrimination, mixedness, spectrum testing, and state certification previously yielded at most polynomial memory separations [CLO21].The paper’s exponential separations therefore extend beyond the prior scale of these results.Source: §3 · p. 15

Quantum memory tradeoffs for learning

• Lower bounds against memoryless learning progressed from non-adaptive settings to polynomial and exponential gaps for general algorithms, motivating this paper’s synthesis and generalization [CLO21] [ACQ21].Related memory tradeoffs have also been established for classical learning problems.Source: §3 · p. 15

Learning quantum dynamics

• Full quantum-process learning is known as quantum process tomography, while recent work focuses on restricted dynamics such as time-independent Hamiltonians and Pauli channels [EHF19] [FO21].Information-theoretic studies have also examined learning properties of quantum channels [ACQ21] [RYCS21] [CZSJ21].Source: Learning quantum dynamics · pp. 15–16

4 Preliminaries

• The preliminaries define reduced states, maximally mixed states, Pauli-derived states, asymptotic notation, conjugate transpose, transpose, and total variation distance.Source: §4 · p. 16

4.1 Tail bounds

• Tail-bound tools include subexponential definitions, the sub-Gaussian-square fact, Bernstein’s inequality, and Haar concentration for orthogonal and unitary groups.Source: §4.1 · p. 16

4.2 Basic results in quantum information theory

• Quantum-information preliminaries define channels, POVMs, post-measurement states, rank-1 POVMs, Pauli observables, permutation operators, and Haar integration over states [Har13].Rank-1 POVMs can simulate arbitrary POVMs when only classical outcomes are retained, via post-processing.Source: §4.2 · pp. 16–17

4.3 Primer on information-theoretic lower bounds

• The lower-bound primer formulates distinguishing through transcript distributions and reduces impossibility to bounding total variation distance using binary testing and Le Cam’s two-point method.The tasks distinguish a singleton S0 from a distribution over S1, with success threshold 2/3; the technical goal is to upper-bound transcript distance.Source: §4.3 · pp. 18–19

4.4 Learning with and without quantum memory

• The learning framework defines state and channel algorithms without memory, with quantum memory, and with bounded k-qubit memory, including adaptive measurements and retained post-measurement states.Channel learning allows arbitrary input states and measurements; bounded-memory state learning retains k qubits after each joint measurement, while unrestricted memory is recovered as k →∞.Source: §4.4 · pp. 20–21

4.5 Review of tensor network diagrams

• The tensor-network review introduces diagrammatic notation for tensor contractions and cites for broader background.Source: §4.5 · p. 21

Diagrams for individual tensors

• Individual tensor diagrams represent rank-(m,n) multilinear maps with ordered outgoing and incoming legs corresponding to tensor indices.Quantum states, dual states, and matrices are represented as rank-(1,0), rank-(0,1), and rank-(1,1) tensors, respectively.Source: Diagrams for individual tensors · p. 21

Tensor contraction

• Tensor diagrams represent contractions by gluing oppositely oriented legs, with contractions allowed only between matching vector and covector dimensions.Tensor products, scalar multiplication, matrix products, and matrix norms are represented directly within the same diagrammatic notation.Source: Tensor contraction · p. 22, Multiplication by a scalar · p. 22, Tensor products · p. 22

Tensors with legs of different dimensions

• Diagrams distinguish tensor legs belonging to Hilbert spaces of different dimensions, such as qubit solid lines and qutrit dotted lines, including for partial traces.Identity operators and resolutions of the identity extend analogously across tensor factors with differing dimensions.Source: Tensors with legs of different… · p. 23, Identity operator · p. 24, Resolutions of the identity · p. 24

Identity operator

• The identity diagram leaves states and dual states unchanged, while basis and POVM resolutions provide diagrammatic decompositions of identity operators.The identity on multiple copies and on tensor products with differing dimensions follows the same conventions.Source: Identity operator · pp. 23–24, Resolutions of the identity · p. 24

Taking traces and partial traces

• A trace closes matching tensor legs, so a closed loop evaluates to the associated Hilbert-space dimension; partial traces close selected subsystems and commute.Tracing all subsystems equals the full trace, and partial traces remain applicable in compatible spaces of different dimensions.Source: Taking traces and partial traces · pp. 24–25

Isotopies

• Tensor diagrams are invariant under bending, deformation, and crossings of legs, but isotopies must preserve the relative order of outgoing and incoming endpoints.Changing endpoint order would permute the tensor factors rather than merely deform the diagram.Source: Isotopies · pp. 25–26

Permutation operators

• Permutation operators represent the action of the symmetric group on tensor factors, compose according to group multiplication, and invert by horizontal diagram reflection.Their action on product states permutes factors according to the inverse permutation convention.Source: Permutation operators · pp. 26–27

Transposes and partial transposes

• Transposition reverses tensor-leg orientations and reorganizes them diagrammatically, with partial transposition applying the same operation to selected subsystems.The convention extends to higher-rank tensors.Source: Transposes and partial transposes · p. 27

Maximally entangled state

• The unnormalized maximally entangled state is represented diagrammatically using transpose-like black dots, which reverse leg orientation and annihilate in pairs.The pair-annihilation rule reflects that applying transposition twice is the identity.Source: Maximally entangled state · pp. 27–28

5 Exponential separations in learning quantum states

• Quantum-memoryless algorithms are represented by rooted depth-T trees whose nodes encode classical measurement histories and whose edges record adaptive POVM outcomes.Each node has an associated probability, non-leaf nodes perform POVMs, and every root-to-leaf path has length T.Source: §5 · p. 28
• The general lower-bound strategy reduces prediction to distinguishing the maximally mixed state from a uniformly sampled alternative, then applies a one-sided Le Cam bound to the tree’s leaf distributions.A small one-sided difference between the classical-memory distributions suffices even when some leaves have large absolute differences.Source: §5 · p. 29

5.1 Shadow tomography

• Without quantum memory, shadow tomography of M traceless ±1 observables requires the sample complexity given by Theorem 5.5 to estimate all expectation values within ε with probability at least 2/3.The proof constructs alternative states whose corresponding observable expectation is separated from the maximally mixed state, reducing tomography to many-versus-one distinguishing.Source: §5.1 · p. 30

5.1.1 Lower bound for random observables

• For random observables, the resulting lower bound is Ω(min(M/log(M), 2^n)/ε^2) copies, while Pauli observables require the exponential bound stated in Corollary 5.9.The random-observable result holds with constant probability over the observable collection; the Pauli construction uses 2(4^n − 1) observables with both signs.Source: §5.1.1 · p. 33, §5.1.2 · p. 34

5.1.3 Upper bound

• A classical-memory upper bound uses sequential measurements for M ≤ 2^n and classical shadows for M > 2^n, requiring the complexity stated in Theorem 5.10.This upper bound matches the random-observable lower bound up to poly-logarithmic factors in M and the Pauli lower bound up to a factor of n.Source: §5.1.3 · pp. 34–35

5.2.1 Lower bound

• Any algorithm without quantum memory needs the sample complexity stated in Theorem 5.11 to distinguish a pure n-qubit state from the maximally mixed state with probability at least 2/3.The proof again uses the measurement-tree framework and the one-sided distinguishing bound, with Hilbert-space dimension d = 2^n.Source: §5.2.1 · p. 35
• The lower-bound proof relies on a technical lemma that lower-bounds the symmetric-subspace projection norm of tensor products of pure states.The proof represents the relevant quantity using the symmetric-subspace projector and proceeds by induction on the number of copies.Source: §5.2.1 · p. 36

5.2.2 Upper bound

• O(2^(n/2)) copies suffice for a memoryless algorithm to distinguish whether ρ is pure or maximally mixed, matching the lower bound up to constant factors.The algorithm succeeds with probability at least 4/5 over its randomness and the random measurement basis.Source: §5.2.2 · p. 37
• In a Haar-random basis, pure states produce outcome distributions that are Ω(2^(-n/2))-far from uniform with probability at least 9/10, whereas maximally mixed states produce uniform outcomes.Classical L2 uniformity testing then distinguishes these cases using O(2^(n/2)) samples.Source: §5.2.2 · p. 37

6.1 Lower bound with k-qubit of quantum memory

• With k qubits of quantum memory, estimating |tr(Pρ)| for all n-qubit Pauli observables requires T ≥ Ω(2^((n-k)/3)) copies with probability at least 2/3.The lower bound uses a tree representation whose nodes track unnormalized k-qubit memory states and a many-versus-one test between the maximally mixed state and Pauli-indexed states.Source: §6.1 · pp. 38, 41
• For any edge eu,s, at most 2−(n−k)/3 · (4^n −1) Pauli observables are bad, and the proof uses a careful pruning argument that ignores bad Paulis’ contributions.Source: §6.1 · p. 40

6.2 Upper Bound with n-qubit of quantum memory

• With n qubits of quantum memory, an algorithm estimates |tr(P_iρ)|^2 for M Pauli observables to error ε using O(log(M)/ε^2) copies with probability at least 2/3.It stores one copy of ρ and performs entangled Bell-basis measurements on that copy and each new sample.Source: §6.2 · p. 42

7.1 Prerequisites

• A quantum-memory-free channel-learning protocol is represented by a rooted tree whose nodes encode classical measurement histories across adaptive rounds.At each round, the algorithm prepares a state, applies the channel, measures the resulting system, and uses prior outcomes to choose future preparations and measurements.Source: §7.1 · pp. 42–43
• Each tree node carries the probability of reaching that classical-memory state, with root probability 1 and leaf probabilities equal to final transcript probabilities.Non-leaf nodes prepare states, apply the channel, and perform node-dependent rank-1 POVMs; children correspond to measurement outcomes, and every root-to-leaf path has length T.Source: §7.1 · pp. 42–43
• The model permits an auxiliary n′-qubit system entangled with the channel input and joint POVM measurements, making the resulting lower bounds stronger than those for QUALMs without auxiliary systems [ACQ21].The channel acts only on the n-qubit main system, while preparation and measurement may involve the full main-plus-auxiliary Hilbert space.Source: §7.1 · p. 43
• The fixed-unitary task distinguishes, with equal prior probability, an n-qubit completely depolarizing channel from a fixed Haar-random unitary channel.Analogous variants replace the Haar-random unitary with a Haar-random orthogonal or symplectic matrix.Source: §7.1 · p. 43
• Equivalently, the fixed-unitary task distinguishes time-dependent random-unitary dynamics from time-independent dynamics applying one fixed random unitary.The depolarizing channel can be viewed as selecting an independent Haar-random unitary at every application, whereas the alternative uses a single fixed unitary.Source: §7.1 · p. 43
• The symmetry distinction task determines whether a channel belongs to the unitary, orthogonal, or symplectic time-reversal-symmetry class, a problem relevant to characterizing uncharacterized physical systems.The three classes correspond to three forms of time-reversal symmetry.Source: §7.1 · p. 44
• All distinguishing tasks are reduced to a two-hypothesis problem in which the channel is sampled with equal probability from distributions D_A or D_B, and the goal is to identify the source distribution.For quantum-memory-free algorithms represented by rooted trees, Le Cam’s two-point method bounds the probability of solving this distinction task correctly.Source: §7.1 · p. 44

7.2 Review of the Weingarten calculus

• Haar measures on U(d), O(d), and Sp(d/2) are canonical left- and right-invariant measures whose integrals underpin the later proofs.The review also fixes terminology for orthogonal and symplectic matrices and introduces expectation notation for Haar averages.Source: §7.2 · pp. 44–45

7.2.1 Haar averaging over U(d)

• For U(d), Haar moments are expressed through permutations in the symmetric group S_k and the unitary Weingarten function WgU(·, d).The formula computes E_Haar[U^⊗k ⊗ U†⊗k], while mixed moments with unequal numbers of U and U† vanish; WgU is defined as the inverse of the associated matrix G_U.Source: §7.2.1 · pp. 45–46

7.2.2 Haar averaging over O(d)

• For O(d), Haar averaging uses pair partitions P2(2k), with the orthogonal Weingarten function WgO(·, d) inverse to the corresponding matrix G_O.The resulting integrals compute even moments of O, while odd moments vanish; the identity also yields |WgO(σe, d) − d^-k| ≤ O(k^7 d^-(k+2)).Source: §7.2.2 · pp. 46–48

7.2.3 Haar averaging over Sp(d/2)

• For Sp(d/2), Haar averaging follows the orthogonal pair-partition framework, with WgSp(·, d/2) obtained by a signature-dependent modification of WgO.The symplectic identities use the canonical form J and provide an analogous estimate, |WgSp(σe, d/2) − d^-k| ≤ O(k^7/2 d^-(k+2)).Source: §7.2.3 · pp. 48–49

7.3.1 Lower bound without quantum memory

• Theorems 7.9–7.11 establish exponential sample lower bounds for distinguishing the completely depolarizing channel from fixed Haar-random unitary, orthogonal, and symplectic matrix channels with success probability at least 2/3.These results provide the main fixed-unitary hardness statement without quantum memory.Source: §7.3.1 · p. 49
• The argument generalizes [ACQ21] from protocols without auxiliary systems to arbitrary auxiliary dimension d′ = 2^n′, requiring substantive proof modifications because the original bounds degrade by factors of d′^T.The paper identifies this extension as its main technical contribution.Source: §7.3.1 · p. 49

7.3.2 Proof of Theorem 7.9

• For Theorem 7.9, the proof represents each adaptive protocol by root-to-leaf paths, weighted POVM elements, and tensor-product states, then Haar-averages the random unitary channel.Leaf probabilities are organized through path-dependent quantities whose weights sum to the identity.Source: §7.3.2 · p. 50

First term

• The first-term analysis removes absolute values using positivity, sums over leaves via the POVM identity, and applies a Weingarten bound on the deviation from 1/d^T.The supplied passage specifies the estimate |Wg_U(1,d) − 1/d^T| ≤ O(T^7/2/d^(T+2)) for the stated regime.Source: First term · p. 51

Second term

• The second term is controlled with Cauchy–Schwarz, Hölder, positivity, and the identity over leaves, yielding an O(T^2/d) bound via Lemma 6 of [ACQ21].This bounds the contribution with σ ≠ 1 and τ = 1.Source: Second term · pp. 51–52

Third term

• The third term is handled by decomposing τ^-1 into cycles, converting trace norms into trace products, and separately analyzing even- and odd-length cycles.Lemma 7.12 factorizes the tensor-network contribution by cycles, while Lemma 7.13 bounds each factor by tr(eρ_vi eρ_vj).Source: Third term · pp. 52–54
• The cycle analysis ensures each eρ_vi appears exactly once, counts pair contributions from even and odd cycles, and combines the resulting bounds to show the error is o(1) when T ≤ o(d^(1/3)).This final estimate completes the control of the most difficult permutation contribution.Source: Third term · pp. 55–57

• Theorem 7.10 and 7.11 proofs make heavy use of pair partitions.Source: §7.3.3 · p. 57
• The proof uses the established notation p_D(ℓ) and depicts E_Haar[p_O(ℓ)] diagrammatically.Source: §7.3.3 · p. 57
• The argument applies the triangle and Cauchy–Schwarz inequalities before bounding the resulting right-hand sides term by term.The summand notation m,n(ℓ) and J := J⊗t are introduced in this setup.Source: §7.3.3 · p. 57

First term for O(d) case

• In the O(d) case, Cauchy–Schwarz is applied to the first term in (232) to derive an upper bound.Source: First term for O(d) case · p. 57
• The O(d) argument removes absolute values using positivity of the diagrammatic term and then sums over leaves.Source: First term for O(d) case · p. 58
• After the O(d) estimate, the derivation states that an immediate conclusion follows from the displayed bound.Source: First term for O(d) case · p. 58

First term for Sp(d/2) case

• In the Sp(d/2) case, the same Cauchy–Schwarz manipulation is applied to the first term in (233).Source: First term for Sp(d/2) case · p. 58
• The symplectic derivation again removes absolute values around the diagrammatic term and sums over leaves.Source: First term for Sp(d/2) case · p. 58
• The symplectic estimate uses an analogous Corollary 7.8 bound, |WgO(σe, d) − 1 dT | ≤ O(T 7/2/dT+2).Source: First term for Sp(d/2) case · p. 58

Second term for O(d) case

• O(d) second-term analysis yields O(T^7/d^2) + O(T^2/d) after summing over leaves and applying Corollary 7.7 with Lemma 8 of [ACQ21].The derivation uses Cauchy–Schwarz, product-of-traces representations, and trace-norm bounds for positive semidefinite C matrices.Source: Second term for O(d) case · pp. 58–59

Second term for Sp(d/2) case

• The symplectic second term is bounded by O(T^(7/2)/d^2) + O(T^2/d) using Corollary 7.8 with Lemma 10 of [ACQ21].The proof parallels the orthogonal case, adding Hölder’s inequality and the identities ||J||∞ = ||J^t||∞ = 1.Source: Second term for Sp(d/2) case · p. 60

Third term for O(d) case

• For the third O(d) term, the proof rewrites diagrammatic expressions as trace products and bounds their factors with generalized C-matrix trace norms.The bound relies on positive semidefiniteness, tensor-product trace-norm identities, and parity-dependent estimates for matrix factors.Source: Third term for O(d) case · pp. 61–62
• The third-term analysis decomposes M2T-cycles by parity and treats even- and odd-length cycles separately, introducing R_m,- and R_m,+ bounds.A slightly more general lemma is developed so the argument can also apply in the symplectic setting.Source: Third term for O(d) case · pp. 62–64
• Combining the even- and odd-cycle cases gives the desired upper bound for Eqn. (267).The result follows after arranging each trace-product term so every eρv_i appears exactly once and applying the resulting lemma.Source: Third term for O(d) case · p. 64
• The remaining orthogonal bound uses longest-cycle length and inductive sequence counting to control trace products along root-to-leaf paths.The counting tracks singleton and paired indices through sets S_1(T) and S_2(T), with contributions determined by M2T-cycle lengths.Source: Third term for O(d) case · pp. 65–66
• When T = o(d^(1/3)), the final counted contribution is o(1) for an absolute constant c > 0.This conclusion follows from bounding the number of pair permutations by powers of T and combining all prior estimates.Source: Third term for O(d) case · p. 66

Third term for Sp(d/2) case

• The third term in (233) is 1.Source: Third term for Sp(d/2) case · p. 67
• Introducing tilde notation rewrites the diagrammatic term, which is then upper bounded in the 1-norm, yielding a lemma analogous to Lemma 7.17 with AD := JAtJ−1, the symplectic transpose.Source: Third term for Sp(d/2) case · p. 67
• The remaining bound uses the same lemmas as the orthogonal case and identifies NSp(T, ℓ) with NO(T, ℓ), giving o(1) when T ≤o(d^1/3).Source: Third term for Sp(d/2) case · p. 68

Haar-random state distinction

• Any learning algorithm without quantum memory requires a sample lower bound to distinguish the maximally mixed state from a fixed Haar-random pure state with probability at least 2/3.The proof applies the channel to |0⟩⊗n, converting depolarizing versus Haar-random unitary distinction into maximally mixed versus fixed Haar-random state distinction.Source: §7.3.4 · p. 69

Reduction strategy

• These corollaries exemplify a general reduction from learning lower bounds for channel distinction to corresponding lower bounds for state distinction.The first corollary is weaker than Theorem 5.11’s T ≥ Ω(d1/2) bound, while the real-state corollary also follows from [ACQ21] but was not stated there.Source: §7.3.4 · p. 69

Real Haar-random state distinction

• The same memoryless-learning lower-bound strategy applies to distinguishing the maximally mixed state from a fixed, real Haar-random pure state with probability at least 2/3.A real Haar-random state can be generated using a Haar-random orthogonal or symplectic matrix; the symplectic formulation yields the corollary via Theorem 7.11.Source: §7.3.4 · p. 69

7.3.5 Upper bound without quantum memory

• O(2^(n/2)) channel accesses suffice without quantum memory to distinguish a fixed Haar-random unitary channel from a completely depolarizing channel.This upper bound follows by reducing the task to purity testing and applying Theorem 5.13.Source: §7.3.5 · p. 69
• Without quantum memory, the algorithm repeatedly inputs |0^n⟩, measures each channel output in the computational basis, and classifies the resulting classical data.The output is a fixed pure state for a scrambling unitary channel and the completely mixed state for a depolarizing channel.Source: §7.3.5 · pp. 69–70
• The no-memory construction distinguishes scrambling unitary and completely depolarizing channels by reducing their outputs to fixed-pure-state versus completely-mixed-state purity testing.Theorem 5.13 supplies the O(2^(n/2)) sample complexity for this classical-data test.Source: §7.3.5 · pp. 69–70

7.3.6 Upper bound with quantum memory

• O(1) channel applications and O(n) gates suffice with n qubits of quantum memory to distinguish depolarizing from fixed Haar-random unitary channels with constant probability [ACQ21].The result also applies to fixed Haar-random orthogonal or symplectic unitaries.Source: §7.3.6 · p. 70
• The quantum-memory upper bound is gate efficient, requiring only O(n) gate complexity in addition to its n-qubit memory.The protocol succeeds with constant probability.Source: §7.3.6 · p. 70
• The swap-test protocol uses n qubits of memory to store one state copy and obtain quantum interference between two copies of the channel output.For a pure input, depolarization produces a mixed output while a unitary produces a pure output, enabling the distinction.Source: §7.3.6 · p. 70

7.4.1 Lower bound

• Ω(2^(2n/7)) samples are necessary without quantum memory to distinguish fixed Haar-random unitary, orthogonal, and symplectic channels with success probability at least 2/3.The task identifies which symmetry is encoded in the evolution: unitary channels have no additional symmetry, whereas orthogonal and symplectic channels have different time-reversal symmetries.Source: §7.4.1 · pp. 70–71

7.4.2 Upper bound

• The upper and lower bounds do not match, and closing this gap is left as an open question.The distinguishing guarantees rely on symplectic and orthogonal overlaps exceeding 1/2, while the corresponding unitary cases remain below 1/2 with probability at least 14/15.Source: §7.4.2 · pp. 71–72
• A quantum-memory-free upper-bound algorithm uses tomography of three channel outputs followed by threshold tests to classify symplectic, orthogonal, or unitary channels.It tests |bφ_2^t J bφ_3| against 1/2 for symplectic structure, then |bφ_1^t bφ_1| against 1/2 to distinguish orthogonal from unitary structure.Source: §7.4.2 · pp. 71–72
• The tomography step estimates each of three pure output states using O(2^n/ε^2) random Clifford measurements with success probability at least 14/15.The resulting state estimates support the matrix-overlap tests used by the classifier.Source: §7.4.2 · p. 71