Pseudo-randomness and Learning in Quantum Computation

• The contents list places “Conclusions” in section 5.7 and the proof of Theorem 5.2.3 in section 5.8.Source: §5.6 · p. 6

Introduction

• The thesis uses quantum pseudo-randomness to reduce randomness requirements and studies learning and testing operations, including Clifford-group algorithms.It presents random-circuit 2-designs, efficient k-design constructions, and applications including measure concentration.Source: Introduction · pp. 8–9

1.1 Brief Introduction to Quantum Mechanics

• The primer introduces qubit states, circuit models, Dirac notation, POVM measurements, and unitary evolution.Source: §1.1 · pp. 9–10

1.2.1 Pauli Matrices

• n-qubit Pauli strings are tensor products that form an orthogonal matrix basis, and Pauli matrices commute or anticommute.Source: §1.2.1 · p. 11

1.2.2 The Symmetric Group and Permutation Operators

• Permutation operators represent permutations of basis states; the thesis also derives the swap operator’s Pauli expansion and introduces subsystem-permutation lemmas.Source: §1.2.2 · pp. 11–13

1.2.3 Asymptotic Notation

• The thesis defines O, Ω, and Θ asymptotic notation through eventual upper, lower, and matching bounds.Source: §1.2.3 · p. 13

Norms

• The Schatten p-norm is defined using a matrix’s singular values, and the thesis records relationships among these norms.Source: Norms · p. 14

Superoperator Norms

• The 1-norm can increase under tensoring with an identity, whereas the diamond norm is stable and measures distinguishability even with entangled inputs.Source: Superoperator Norms · pp. 14–15

1.3 Previous Publications

• The thesis notes that most material appeared previously and lists publications for Chapters 3–6.Source: §1.3 · pp. 15–16

Pseudo-randomness

• The chapter extends randomness-based gains to quantum computing and studies physical systems whose random interactions determine stationary states and how quickly they are reached.It notes that systems reaching stationarity in a small polynomial time may exhibit that state in practice, unlike systems requiring exponentially long times.Source: Pseudo-randomness · p. 19

2.1 Random Unitaries

• Because n-qubit unitaries require 4^n real parameters, the thesis seeks efficient pseudorandom ensembles that resemble Haar measure for selected applications.A k-design matches the first k moments of the Haar distribution.Source: §2.1 · p. 20
• The thesis shows natural random quantum circuits quickly converge to 2-designs, constructs efficient unitary k-designs for any k subject to dimension restrictions, and applies designs to derandomization.The applications include derandomizing constructions that use large-deviation bounds.Source: §2.1 · pp. 20–21

2.2 k-designs

• A unitary k-design reproduces Haar expectations for polynomials of degree at most k, providing a quantum analogue of k-wise independence.The chapter also introduces state designs, which apply the design condition to functions of state coefficients.Source: §2.2 · p. 21

2.2.1 k-wise Independence

• Quantum k-designs aim to achieve randomness savings analogous to k-wise independent sets, which can save randomness when k is much smaller than the number of variables.The passage gives a three-bit 2-wise independent set as an example that saves one random bit.Source: §2.2.1 · p. 22

State designs

• A state k-design makes k copies of a sampled state indistinguishable from copies of a uniformly random state; its moment and balanced-monomial definitions are equivalent.The equivalence is stated for the definitions in [AE07].Source: State designs · pp. 23–24

Unitary designs

• A unitary k-design makes applying one sampled unitary to k systems indistinguishable from applying a Haar-random unitary, and it generalizes state designs.The channel-based definition is equivalent to its balanced-monomial definition.Source: Unitary designs · p. 25

2.2.3 Approximate k-designs

• Approximate designs can be easier to construct and use fewer unitaries than exact designs; channel distinguishability motivates measuring approximation by diamond-norm distance.The chapter states that several approximate-unitary-design definitions are equivalent up to polynomial dimension factors.Source: §2.2.3 · p. 26, Approximate unitary designs · p. 27

Approximate unitary designs

• The thesis states that approximate unitary k-design definitions are equivalent up to polynomial precision loss, while the TWIRL definition is equivalent to the others only for k = 2.Theorem 4.1.3 also shows that iterating a quantum tensor product expander constructs a unitary design.Source: Approximate unitary designs · p. 28
• Computationally secure approximate designs, nearly indistinguishable from exact designs in polynomial time, could suffice for cryptographic uses, but their applications and constructions remain open.Source: Approximate unitary designs · p. 33

Constructions

• For k = O(n/log n), the thesis gives the first efficient approximate unitary k-design construction for k > 2, running in O(kn + log 1/ǫ) time.It also conjectures that random quantum circuits of length poly(n, k) are approximate unitary k-designs, proving this only for k = 2.Source: Constructions · p. 34

3.1 Introduction: Pseudo-random Quantum Circuits

• Random circuits are efficient to implement at polynomial length and can model randomly interacting physical systems whose equilibration depends on rapid convergence.The motivation is that short-time circuit convergence can give such systems properties of Haar-random systems.Source: §3.1 · p. 35

3.1.1 Random Circuits

• Random circuits built from universal two-qubit gates eventually converge to Haar-distributed unitaries, but the section instead studies lower-order moments because full Haar sampling is not polynomial-time.Each step applies a uniformly chosen gate from the universal set to a randomly chosen qubit pair [ELL05].Source: §3.1.1 · pp. 36–37

3.2.2 Random Circuits as k-designs

• Universal two-qubit gate sets and approximate or exact two-qubit unitary k-designs are k-copy gapped, including the two-qubit Clifford group as an exact 2-design.Examples of universal sets include U(4) and entangling gates together with all single-qubit gates.Source: §3.2.2 · p. 40

3.3 Summary of Results

• For any 2-copy gapped gate distribution, circuits of length t ≥ Cn(n + log 1/ε) form ε-approximate unitary 2-designs under both diamond-norm and twirl definitions.The circuit draws each gate from the distribution and applies it to a randomly chosen qubit pair.Source: §3.3 · p. 40
• The Markov chain governing second-moment evolution has eigenvalue gap O(1/n), a tight bound for some gate sets.This result is established in the course of proving convergence for random circuits.Source: §3.3 · p. 42
• Prior work [ODP07] [DOP07] studied random single-qubit gates and controlled-NOT, proving second moments converge in O(n2(n + log 1/ǫ)); this chapter generalizes the classical Markov-chain approach to arbitrary k-th moments.Source: §3.3 · p. 43

3.4 Analysis of the Moments

• The second-moment operator for Haar averaging is a projector: subsystem permutation operators have eigenvalue 1, and vectors orthogonal to them have eigenvalue 0.The analysis uses a general Hermitian orthogonal basis and establishes properties of the Haar integral relevant to the circuit’s moment evolution.Source: §3.4 · p. 45

3.4.1 k = 1

• For k = 1, the random unitary completely randomizes the state, leaving only the identity term in the moment expansion.The analysis identifies the moment operator as a projector with eigenvalues 0 and 1.Source: §3.4 · p. 46, §3.4.1 · p. 47

3.4.2 k = 2

• For k = 2, the moment operator has zero entries whenever either pair of indices differs, while its diagonal coefficients can be treated as a probability distribution after normalization.The normalized diagonal evolution can then be analyzed as a Markov chain.Source: §3.4.2 · pp. 47–48

3.4.3 Moments for General Universal Random Circuits

• Universal distributions on U(d) are k-copy gapped for every positive integer k, extending the earlier result for distributions supported on two unitaries.The result implies that iterated moment operators converge to the Haar moment operator.Source: §3.4.3 · p. 50

3.5 Convergence

• The convergence analysis maps diagonal second-moment coefficients to a probability distribution only when they are non-negative, then extends the result to general states.For arbitrary states, the passage notes that diagonal coefficients need not be non-negative.Source: §3.5 · p. 53
• The expected diagonal second-moment coefficients approach stationarity in both 2-norm and 1-norm within the stated bounds on t.The 2-norm bound uses t ≥ C′n(n + log 1/ε), and the 1-norm bound uses t ≥ Cn(n + log 2n/ε).Source: §3.5 · pp. 54–55

3.5.1 First Moments Convergence

• For k = 1, a U(4) random circuit gives an exact 1-design once every site has been hit; other gate sets decay according to their gap Δ.The passage also reports that the non-identity coefficient sum becomes small after O(n log n) steps.Source: §3.5.1 · pp. 55–56

3.5.2 Second Moments Convergence

• For second moments, the coefficients with p1 ≠ p2 decay, while the diagonal coefficients evolve as a Markov chain on {0, 1, 2, 3}^n.The Markov-chain analysis is framed for non-negative diagonal coefficients normalized to sum to 1.Source: §3.5.2 · pp. 58–59
• For other gate sets, 00 remains fixed and the stationary distribution on the other 15 states is unchanged, though transitions need not be uniform.The U(4) gate set is analyzed tightly as a reference case.Source: §3.5.2 · p. 60

3.5.3 Markov Chain Analysis

• The analysis uses Markov-chain comparison via paths and flows to bound gaps, including chains that are not reversible.For the irreversible case, it bounds the gap of PP* instead of P.Source: §3.5.3 · p. 63, §3.5.4 · pp. 67, 70

Decomposition; log-Sobolev Constant

• The decomposition theorem combines convergence analyses of separate chain parts, while the log-Sobolev constant supplies tighter mixing-time results for the U(4) case.The log-Sobolev subsection also invokes comparison and product-chain results.Source: Decomposition · p. 65, log-Sobolev Constant · pp. 65–66

3.5.4 Convergence Proof

• The chain’s gap, up to constants, does not depend on the choice of 2-copy gapped gate set, and the chapter reports a tight bound for the U(4) case.Source: §3.5.4 · p. 67
• The U(4) analysis proves a tight mixing-time result, while the gap—not mixing time—determines approximate 2-design closeness.The matrix ˆG is a projector only in the U(4) case.Source: §3.5.4 · p. 71

3.6.1 Second Moments Convergence

• The second moments of the random circuits converge on an O(n log n)-scale, completing the chapter’s convergence analysis.The proof bounds coefficient decay by separating circuits according to how many qubits have been hit.Source: §3.6.1 · pp. 71, 73

3.6.2 Markov Chain of Coefficients

• The coefficient chain’s slow mixing is captured by a zero chain, whose mixing together with a site-hitting argument yields a bound for the full chain.The zero chain tracks the number of zeroes; once it has approximately mixed, a coupon-collector argument bounds the time needed for every site to be hit.Source: §3.6.2 · pp. 73, 75, 77

3.6.3 Proof of Theorem 3.6.4

• The zero-chain mixing proof uses an accelerated walk and three phases to obtain an O(n log n) bound to inverse-polynomial distance.The phases complete successfully with probability at least 1 − 1/poly(n); the proof then applies a mixing result to obtain the stated bound.Source: §3.6.3 · pp. 79–81

3.6.4 Proof of Theorem 3.6.5

• A simpler decomposition argument proves that the zero chain has gap Ω(1/n), a weaker mixing-time bound that still suffices for the main result.The decomposition uses different techniques for the regime with many zeroes and the regime with a constant fraction of zeroes.Source: §3.6.4 · pp. 81–82
• The analysis establishes Ω(1/n) gaps for P1 and ¯P, and, for m = θn with 0 < θ < 0.49, P2 (phase 3 up to relabeling) also has gap Ω(1/n).Source: §3.6.4 · pp. 83–85

3.7 Main Result

• The mixing-time results establish an approximate 2-design, with the proof using the Pauli basis and yielding a diamond-norm bound.The argument proceeds via the 2-norm; the passage also refers to a 1-norm bound for the TWIRL distance measure.Source: §3.7 · pp. 87–88

3.8 Conclusions

• Random circuits are efficient approximate 1- and 2-unitary designs, and the framework generalizes to k-designs, though the stated results cover the first two moments.The conclusions identify approximate k-designs for all k as a next research step.Source: §3.8 · p. 89
• With gates from a universal set that is also universal on U(4), the circuit remains an efficient 2-design; U(4) gates may be replaced by any approximate two-qubit 2-design without changing asymptotic convergence.The text identifies gates chosen uniformly from U(4) as the most natural random-circuit model.Source: §3.8 · p. 89
• O(n(n + log 1/ε)) steps suffice for almost maximal entanglement, compared with O(n^2(n + log 1/ε)) steps proved in [ODP07].The result concerns a system with random two-party interactions.Source: §3.8 · p. 89

Asymmetric Simple Random Walk

• For biased walks, concentration bounds extend to step-varying rightward bias, and a visit-time bound controls time spent at positions ≤x; backward absorption is 1 when p ≤ q and (q/p)^a otherwise.For finitely many steps, the absorption probability is at most the infinite-time bound.Source: Asymmetric Simple Random Walk · pp. 90, 91, 93

Waiting Time

• Waiting at position x is stochastically dominated by a geometric distribution with parameter 2x/5n, and the section invokes a concentration bound for total waiting time.The passage states the per-site waiting-time model as W(x) ∼ Geo(βx/n), with β = 2/5.Source: Waiting Time · p. 93

Phase 1

• In phase 1, the walk moves right across nδ accelerated steps with high probability when δ < 1/2, and its waiting time is bounded with high probability.The phase-1 proof combines the rightward-movement and waiting-time bounds to show successful completion with high probability.Source: Phase 1 · p. 95

Phase 2

• Phase 2 completes successfully with high probability, with its overall failure probability bounded using the union bound.The proof accounts for failure to reach θn, excessive waiting time, or returning to nδ/2.Source: Phase 2 · pp. 100–101

Phase 3

• The restricted zero chain in Phase 3 has spectral gap Ω(1/n) and mixes in O(n log n) steps; Phase 3 completes successfully with high probability.The analysis uses log-Sobolev arguments on the state space beginning at m = θn.Source: Phase 3 · pp. 101, 103

3.9.2 Moment Generating Function Calculations

• For integer s > 0, the moment-generating-function calculations use the identity (2s − 1)!! = 1 × 3 × 5 × … × (2s − 1).The accompanying lemma also lists the even-product form 2 × 4 × 6 × … × 2s.Source: §3.9.2 · pp. 103–104

3.9.3 Mixing Times

• The section converts high-probability mixing bounds into full mixing-time bounds when the walk is within δ = 1/poly(n) of stationarity after O(n log n) steps.The stated objective is to obtain a bound on the steps needed to reach distance ε from stationarity.Source: §3.9.3 · p. 104

4.1 Introduction

• The chapter’s contribution is an efficient construction of a unitary k-design for k up to O(n/log n), via a quantum k-TPE; earlier efficient designs covered only k = 1, 2.The construction uses an efficient classical k-TPE as its main ingredient, and the chapter identifies it as the first efficient unitary k-design construction for any k.Source: §4.1 · pp. 106–107

4.1.1 Quantum Expanders

• An efficient quantum k-TPE yields an efficient approximate unitary k-design when λ = 1 − 1/poly(log N); the construction combines a classical 2k-TPE with a quantum Fourier transform.The quantum Fourier transform takes poly(log N) time, and the construction increases the classical expander’s degree by one.Source: §4.1.1 · pp. 109–110

4.1.2 Main Result

• The construction produces a quantum k-TPE of degree D + 1; any constant-degree, constant-gap classical 2k-TPE therefore yields a quantum k-TPE with constant degree and gap.It requires N = Ω((2k)8k); if 2k > N, its gap drops to zero.Source: §4.1.2 · pp. 110–111

4.2.1 Proof overview

• The proof reduces the gap analysis to showing that F⊗k,k contracts vectors in V0, after approximating one projector by another while keeping the gap constant.The chapter identifies the contraction step as its most technically involved part.Source: §4.2.1 · p. 111

4.2.2 Action of a Classical 2k-TPE

• For a classical 2k-TPE with N ≥ 2k, fixed points are indexed by partitions of {1, …, 2k} encoding which indices are equal or different.Their number is the 2kth Bell number.Source: §4.2.2 · pp. 112–113

Turning Inequality Constraints into Equality Constraints.

• Replacing exact equality-and-inequality constraints with equality-only sets expresses each such set as a union over coarser partitions, enabling inversion by the Möbius function.The equality-only set EΠ allows additional equalities between indices in different blocks of Π.Source: Turning Inequality Constraints into… · pp. 114–115

4.2.3 Fixed Points of a Quantum Expander

• The quantum expander’s fixed space is spanned by states invariant under U⊗k,k for every unitary U, corresponding to subsystem permutations.These states are related to the earlier partition notation through pairings of indices.Source: §4.2.3 · p. 117
• A classical expander has fixed points beyond the desired |EP(π)⟩, so constructing a quantum expander requires suppressing those unwanted fixed points.Source: §4.2.3 · p. 117

4.2.4 Fourier Transform in the Matrix Element Basis

• For |Π1| + |Π2| = 2k, the Fourier-transform overlap equals 1 when Π1 = Π2 = P(π), while other such partition pairs have a nonzero associated matrix.The nonzero-matrix statement is given for N > k.Source: §4.2.4 · p. 120

4.2.5 Proof of Lemma 4.2.2

• The proof separates k! leading-order terms from the remaining contributions, which are kO(k)/N, under the condition 4k^2 < N.The k! leading terms are identified with Π1 = Π2 = P(π).Source: §4.2.5 · pp. 123–124

4.3 Conclusions

• Efficient quantum tensor product expanders can be constructed from efficient classical tensor product expanders, yielding efficient unitary k-designs for any k.The construction requires dimension N = Ω((2k)^(8k)); it does not work for N < 2k, and all-dimension expander constructions remain open.Source: §4.3 · pp. 125–126

5.1.1 Quantum Cryptography

• A unitary 1-design gives an exact quantum one-time pad with an optimal 2n-bit key, whose necessity was shown in.Using 2n bits to label Pauli operators supplies the encryption; exact encryption cannot use a shorter key.Source: §5.1.1 · pp. 127–128

5.1.2 Measurement

• A POVM built from a state 4-design achieves the Haar-random measurement distinguishability bound, and an approximate 4-design suffices.The cited bound applies to mixed states whose ranks sum to at most √d/C for a sufficiently large constant C.Source: §5.1.2 · pp. 129–130

5.1.3 Average Gate Fidelity

• Because average gate fidelity is a balanced degree-2 polynomial, a state 2-design can estimate it efficiently to 1/poly(log d) accuracy.An approximate design suffices for approximate fidelity, whereas naive sampling of random states is not efficient.Source: §5.1.3 · p. 131

5.1.4 Data Hiding

• Approximate unitary 2-designs can replace Haar twirling to prepare data-hiding states efficiently when errors are tolerated.The design is used to replace the Haar integral in constructing the states.Source: §5.1.4 · pp. 131–132

5.1.5 Decoupling and Evolution of Black Holes

• A unitary 2-design suffices for decoupling results, and black-hole recovery can reach fidelity 1 − 2^-c after k + c emitted qubits, given Bob’s initial entanglement with the black hole.For local random circuits, sufficiently rapid convergence to a 2-design is conjectured to make the evolution fast enough; the chapter’s results do not prove this local case.Source: §5.1.5 · pp. 132–133

5.2 Derandomising Large Deviation Bounds

• For k = O(n/log n), approximate designs can be constructed efficiently with negligible error in these applications, while random circuits may naturally produce k-designs if the chapter’s conjecture holds.The chapter proves rapid convergence to a 2-design for a general random-circuit model and conjectures polynomial-time convergence for k = poly(n), k > 2.Source: §5.2 · p. 135

5.2.1 Introductory Problem: Entanglement of a 2-design

• For entanglement, a 2-design preserves the Haar expectation but yields a weaker concentration bound that lacks stronger concentration as dimension grows; higher-k designs give sharp concentration.The introductory example concerns the entropy of one subsystem after applying a random unitary to a fixed pure state.Source: §5.2.1 · pp. 136–137

5.2.2 Main Results

• The main theorem treats degree-K polynomial functions of a unitary, with its bound applying for an integer m satisfying 2mK ≤ k.The supplied passage states this condition but does not include the bound’s full expression.Source: §5.2.2 · p. 137
• 10 log2 n is the design order used for the entropy bound; most states in an O(1)-approximate state n^2-design are useless for measurement-based quantum computing.The entropy argument proceeds via the 2-norm, and the thesis identifies 10 log2 n as the largest design order, up to constants, for which its construction is efficient. The MBQC result follows by showing that the states’ entanglement makes measurement outcomes essentially random.Source: §5.2.2 · pp. 138–139

5.2.3 Optimality of Results

• The bounds are polynomially related to optimal and interpolate from Markov’s inequality to full Haar randomness across the full range.For discrete designs, a nonconstant function must differ from its constant mean on some support element, giving a lower-bound constraint tied to the least probable unitary.Source: §5.2.3 · pp. 139–140

5.3 Main Technique

• The method transfers Haar concentration to k-designs in three steps: bound Haar deviations, bound moments up to order 2m, then apply and optimize Markov’s inequality.The choice of m is optimized subject to the available design order.Source: §5.3 · p. 140

5.3.1 Step 1: Concentration for uniform randomness

• Levy’s Lemma supplies an initial Haar concentration bound for slowly varying functions, with variation measured by the Lipschitz constant.The cited lemma is attributed to Levy, with given as a reference.Source: §5.3.1 · p. 141

5.3.2 Step 2: A bound on the moments

• Tail concentration bounds yield bounds on deviation moments for any m, typically taking the mean as the center.The moment-bound proof is based on an analogous result by Bellare and Rompel.Source: §5.3.2 · pp. 141–142

5.3.3 Step 3: A concentration bound for a k-design

• For balanced polynomials, approximate k-design moments track Haar moments; the resulting concentration argument is limited by the efficient construction’s k = O(log d / log log d) range.The theorem’s moment comparison is then combined with Markov’s inequality; the stated efficiency limit constrains how large m can be chosen.Source: §5.3.3 · pp. 142–144

5.4 Application 1: Entropy of a k-design

• For any initial state, most unitaries drawn from a k-design produce high entanglement across bipartitions when subsystem dimensions are sufficiently far apart.The analysis uses reduced-state purity because entropy is not a polynomial; the expected purity is (dS + dE)/(d + 1), and purity has Lipschitz constant at most 2. The bound does not improve with dimension when dS is approximately dE.Source: §5.4 · pp. 144, 145, 147

5.5 Application 2: k-designs and Statistical Mechanics

• For an ǫ-approximate unitary k-design, almost all sampled unitaries yield a subsystem close to the canonical state, enabling efficient approach to equilibrium when dS is polynomially smaller than dR.The result addresses rapid thermalization: unlike sampling a random pure state, the k-design unitaries can be implemented and sampled efficiently.Source: §5.5 · pp. 148–149

Based Quantum Computing

• Most states in a state n^2-design on n qubits are useless for measurement-based quantum computing, and even many efficiently preparable states are useless [GFE09].For k = n^2, δ = 3 log^2 n + 5, and ε = 1, the bound allows slightly larger deviations from n than Theorem 5.6.2 and gives an exponential bound in n because the design is exponentially large in n.Source: Based Quantum Computing · pp. 152–154

5.7 Conclusions

• The applications show that k-designs transfer Haar-random-unitary large-deviation bounds, generate large amounts of entanglement, and support the equal a priori probabilities principle.The thesis also concludes that most states in sufficiently large state designs are classically simulable for measurement-based quantum computing.Source: §5.7 · pp. 154–155
• The technique cannot directly derandomize bounds that require exponentially small probabilities when designs are only polynomially sized, as with an exponentially large state net.The authors do not know how to handle such nets while keeping k = poly(log d); the product-state net in Section 5.6 is considerably smaller.Source: §5.7 · p. 155

5.8 Proof of Theorem 5.2.3

• The proof section establishes the convenient form of Lemma 5.4.3 stated as Theorem 5.2.3.The proof simplifies the theorem's expression and derives the result under its stated conditions.Source: §5.8 · pp. 155–156

6.1 Introduction

• Assuming the unknown process belongs to a restricted family makes identification possible with fewer queries; a tensor product of arbitrary n-qubit Paulis can be identified with one query.The section contrasts this approach with general state and process tomography, whose measurement requirements grow exponentially with the number of qubits.Source: §6.1 · pp. 158–159

6.2 The Pauli and Clifford Groups and the Gottesman-Chuang Hierarchy

• The hierarchy begins with C1 as the Pauli group and C2 as the Clifford group, the normaliser of the Pauli group; levels above C2 contain a universal gate set.The section defines these groups as the setting for its learning algorithms.Source: §6.2 · p. 160

6.3.1 Learning Pauli Operations

• Pauli operations can be identified with one query in O(n) time by applying the operation to half of a maximally entangled state and distinguishing the orthogonal outputs.This method is the main ingredient for learning operations in the Gottesman–Chuang hierarchy.Source: §6.3.1 · p. 161, §6.3 · p. 161

6.3.2 Learning Clifford Operations

• An unknown Clifford can be determined exactly up to global phase using 2n + 1 queries to it and 2n to its conjugate, with an n-query lower bound.The section notes that the algorithm requires access to the conjugate; without it, O(n^2) queries suffice, but optimal query complexity is unknown.Source: §6.3.2 · pp. 162–164

6.3.3 Learning Gottesman-Chuang Operations

• Operations in Ck can be learned exactly up to phase with query complexity that scales exponentially with k, extending the Clifford-learning method to larger hierarchy levels.The introduction also states that the methods work when the operation is known to be close to a Clifford or a known-level Ck element.Source: §6.1 · p. 159, §6.3.3 · p. 164

6.4 Learning Unitaries Close to Ck Elements

• For a unitary known to be close to a Ck element, the method finds the closest element and has only O(k log n) overhead over exact learning for constant error and failure parameters.The result concerns a phase-invariant distance between unitaries.Source: §6.4 · pp. 165–167

6.5 Clifford Testing

• The Clifford tester decides whether an unknown unitary is close to a Clifford or far from every Clifford under a promise distinguishing the two cases.The section says this property-testing approach can be extended to any level of the Gottesman–Chuang hierarchy, though it presents only the Clifford version.Source: §6.5 · pp. 167–168

6.6 Conclusions and Further Work

• An unknown Clifford can be identified exactly in O(n) queries, optimally, by conjugating Paulis and finding the resulting Pauli; the approach extends to Ck and unitaries close to Ck operations.The conclusion identifies the conjugation CσpC† as the key step.Source: §6.6 · p. 170
• The learning approach may extend to unitary sets whose elements conjugate each Pauli into a linear combination of a constant number of Paulis, using the quantum Goldreich-Levin algorithm [MO08].The authors report finding no interesting such sets beyond the Clifford group; they also suggest the testing results could potentially aid a quantum PCP theorem [ALM+98].Source: §6.6 · p. 170

6.5 Clifford Testing

• The Clifford test distinguishes a black-box unitary close to a Clifford from one far from every Clifford, with an O(1/n) difference between its close and far conditions.The conclusion notes that the method uses both U and U† and leaves open whether low-query testing without U† is possible.Source: §6.6 · pp. 170–171

6.7 Proof of Lemma 6.4.4

• The proof of Lemma 6.4.4 uses induction to show that two distinct Paulis, or two distinct Ck+1 operations, cannot both be within distance ǫ of the same unitary.The supplied proof passages show the base-case and inductive-step contradiction assumptions.Source: §6.7 · p. 171

6.8 Miscellaneous Lemmas

• The miscellaneous lemmas include a result relating two close operators to their conjugations of Pauli operators.Source: §6.8 · p. 172

2. Then we simply apply the triangle inequal-

• Averaging a bound over all Paulis and using their 1-design property yields the desired converse result.The argument first establishes the bound for every σ_p, then takes its average over the Pauli set.Source: §2 · p. 173
• The converse argument begins from a trace inequality stated to hold for every σ_p.That uniform bound is the input to the subsequent Pauli averaging step.Source: §2 · p. 173
• Distances for the generators are extended to distances for the entire Pauli set by induction on the number of generators.The proof uses the triangle inequality for D+.Source: §2 · p. 174