Quantum Spectrum Testing

Ryan O'Donnell; John Wright

Source-linked AI summary

Quantum Spectrum Testing

Ryan O'Donnell, John Wright

arXiv:1501.05028v1Jan 21, 2015quant-ph

TL;DR

Property testing asks whether a mixed state's spectrum has a property or is ε-far from satisfying it, potentially avoiding the extra information required to estimate the full state. For unitarily invariant properties, the paper uses weak Schur sampling followed by classical postprocessing as an optimal testing measurement. Testing mixedness takes Θ(d/ε²) copies; rank-r testing requires and suffices Θ(r²/ε) copies with one-sided error.

Problem
Property testing asks whether a mixed state's spectrum has a property or is ε-far from satisfying it, potentially avoiding the extra information required to estimate the full state.
Source: §1 · p. 3
Method
For unitarily invariant properties, the paper uses weak Schur sampling followed by classical postprocessing as an optimal testing measurement.
Source: §2.5 · p. 20
Results
Testing mixedness takes Θ(d/ε²) copies; rank-r testing requires and suffices Θ(r²/ε) copies with one-sided error.
Source: §1.3 · p. 7, §4.1 · p. 33, §4.2 · p. 35
Takeaways & Limitations
Rank-r testing is independent of ambient dimension d: it requires and suffices Θ(r²/ε) copies with one-sided error; with two-sided error, Ω(r/ε) is a lower bound.
Source: §1.3 · p. 7
The EYD upper bound is O(d^2/ε^2 · ln(d/ε)); the authors speculate that the extra ε-dependence is an analysis artifact and O(d^2/ε^2) may suffice.
Source: §1.3 · p. 6

Abstract

from arXiv · show

In this work, we study the problem of testing properties of the spectrum of a mixed quantum state. Here one is given $n$ copies of a mixed state $\rho\in\mathbb{C}^{d\times d}$ and the goal is to distinguish whether $\rho$'s spectrum satisfies some property $\mathcal{P}$ or is at least $\epsilon$-far in $\ell_1$-distance from satisfying $\mathcal{P}$. This problem was promoted in the survey of Montanaro and de Wolf under the name of testing unitarily invariant properties of mixed states. It is the natural quantum analogue of the classical problem of testing symmetric properties of probability distributions. Here, the hope is for algorithms with subquadratic copy complexity in the dimension $d$. This is because the "empirical Young diagram (EYD) algorithm" can estimate the spectrum of a mixed state up to $\epsilon$-accuracy using only $\widetilde{O}(d^2/\epsilon^2)$ copies. In this work, we show that given a mixed state $\rho\in\mathbb{C}^{d\times d}$: (i) $\Theta(d/\epsilon^2)$ copies are necessary and sufficient to test whether $\rho$ is the maximally mixed state, i.e., has spectrum $(\frac1d, ..., \frac1d)$; (ii) $\Theta(r^2/\epsilon)$ copies are necessary and sufficient to test with one-sided error whether $\rho$ has rank $r$, i.e., has at most $r$ nonzero eigenvalues; (iii) $\widetilde{\Theta}(r^2/\Delta)$ copies are necessary and sufficient to distinguish whether $\rho$ is maximally mixed on an $r$-dimensional or an $(r+\Delta)$-dimensional subspace; and (iv) The EYD algorithm requires $\Omega(d^2/\epsilon^2)$ copies to estimate the spectrum of $\rho$ up to $\epsilon$-accuracy, nearly matching the known upper bound. In addition, we simplify part of the proof of the upper bound. Our techniques involve the asymptotic representation theory of the symmetric group; in particular Kerov's algebra of polynomial functions on Young diagrams.

1 Introduction

The introduction frames quantum spectrum testing as the study of unitarily invariant mixed-state properties, relates it to classical symmetric-distribution testing, and previews copy-complexity results and a weak Schur sampling approach. It also outlines how Kerov’s algebra and different polynomial families support lower-bound analysis and statistics-based upper-bound algorithms.

1 Introduction

Quantum spectrum testing covers unitarily invariant mixed-state properties, whose truth depends only on the spectrum, and tests whether that spectrum is ε-far in total variation distance from satisfying the property.This spectrum formulation is equivalent to mixed-state testing for unitarily invariant properties and avoids reasoning directly about trace distance.Source: §1 · pp. 3–4

1.1 Classical property testing of probability distributions

Any classical sample lower bound for testing a symmetric distribution property transfers to quantum spectrum testing as a lower bound on copies.The classical problem is equivalent to testing with access only to lengths of k-increasing subsequences, rather than the full sample word.Source: §1.1 · p. 5

1.2 Related work

Prior work gives EYD spectrum estimation using O(d^2/ε^2 · ln(d/ε)) copies and Θ(r) copies to distinguish spectra uniform on r versus 2r values.The paper presents its EYD lower bound as complementing the known estimation guarantee.Source: §1.2 · p. 6

1.3 Our results

Θ(d/ε^2) copies are necessary and sufficient for maximally-mixed testing, while rank-r testing takes Θ(r^2/ε) copies with one-sided error.For rank testing with two-sided error, the paper also proves a lower bound of Ω(r/ε).Source: §1.3 · pp. 6–7
O(r^2/Δ) copies suffice, and eΩ(r^2/Δ) are necessary, to distinguish spectra uniform on r versus r+Δ eigenvalues, independently of ambient dimension d.Here 1 ≤ Δ ≤ r.Source: §1.3 · p. 7
Ω(d^2/ε^2) copies are required for the EYD algorithm to estimate even the maximally mixed state to ε-accuracy; the paper also gives a simpler upper-bound proof.The lower bound is for the EYD algorithm and does not rule out a different algorithm using fewer copies.Source: §1.3 · p. 7

1.4 Overview of our techniques

Weak Schur sampling reduces spectrum testing to drawing a Young-diagram partition λ from a distribution determined by the spectrum and deciding from λ alone.Unitary and permutation invariance allow the other Schur-basis registers to be discarded without losing relevant information.Source: §1.4 · pp. 7–8
Kerov’s approach studies symmetric polynomial functions on Young diagrams, replacing direct coordinate moments with moments suggested by the algebra of observables.The passage introduces this alternative through an example concerning whether a random Young diagram has coordinates much larger than the rest.Source: §1.4 · p. 8
Kerov’s algebra of observables is generated by the p*_k polynomial family; other families, including e_p_k, c_k, and p♯_μ, reveal different aspects of a partition.The p♯_μ family is especially useful because its expectation under weak Schur sampling can be computed easily for any mixed state, even though it gives no obvious information about partition shape.Source: §1.4 · p. 8
The lower-bound strategy reduces each testing problem to an observable expression that must be small with high probability, then uses polynomial-estimation techniques to prove concentration.The passage describes this as the general outline of the lower bounds.Source: §1.4 · p. 8
Upper-bound algorithms accept or reject using simple statistics of sampled Young diagrams, with the rank tester checking the number of nonzero parts and the uniformity tester checking the content polynomial.Their analyses use the algebra of observables and can also rely on combinatorial interpretations of weak Schur sampling, including its connection to the Robinson–Schensted–Knuth bumping algorithm.Source: §1.4 · p. 9

2.1 Probabilistic distances

This section introduces distances between probability distributions, including permutation-invariant comparison after sorting, and relates these to trace distance between mixed states. It also states useful bounds connecting total variation, chi-squared distance, and KL divergence.

2.1 Probabilistic distances

Total variation distance provides a comparison for discrete probability distributions, while chi-squared distance and KL divergence supply additional, generally nonsymmetric measures.Source: §2.1 · p. 9
Total variation distance is bounded above by one half the square root of chi-squared distance and by the square root of KL divergence.Source: §2.1 · p. 9
Permutation-invariant total variation compares distributions after rearranging their probabilities in nonincreasing order.Source: §2.1 · p. 9
A mixed state has eigenvalues forming a probability distribution, and its trace distance is the standard distance between density matrices.Source: §2.1 · pp. 9–10
For diagonal density matrices, trace distance equals total variation distance between their diagonal-entry distributions.Source: §2.1 · p. 10

2.2 Property testing

Property testing asks whether an object has a property or is sufficiently far from all objects with that property. The section defines several testing settings and establishes equivalence between testing mixed states and testing their spectra for unitarily invariant properties.

2.2 Property testing

A tester accepts objects in a property and rejects objects that are at least ε-far from it, using access to the object and a chosen distance measure.Source: §2.2 · p. 10
The paper considers testing properties of mixed states, unitarily invariant properties, quantum spectrum properties, and symmetric properties of probability distributions.Source: §2.2 · pp. 10–11
Models (ii) and (iii)—unitarily invariant mixed-state properties and quantum spectrum testing—are equivalent.Source: §2.2 · p. 11
For unitarily invariant properties, trace-distance testing of mixed states is equivalent to testing spectra under symmetric total variation distance.Source: §2.2 · p. 11
Quantum spectrum testing is at least as hard as the corresponding classical testing problem for symmetric distribution properties.Source: §2.2 · p. 11

2.3 Partitions and Young diagrams

This section develops partitions, Young diagrams, and tableaux as representations of integer partitions and random words. It then introduces RSK and connects its output to symmetric functions and quantum spectrum testing.

2.3 Partitions and Young diagrams

A partition λ ⊢ n is a nonincreasing list of nonnegative integers summing to n, and partitions also encode permutation cycle types.Source: §2.3 · p. 11
French diagrams use left-justified rows; Russian notation rotates and dilates the diagram, while Maya notation encodes its boundary with pebbles.The Maya pebble sequence uniquely identifies the partition; the Russian boundary is represented as a piecewise-linear curve.Source: §2.3 · pp. 12–13
Cells are indexed by row and column, with content j − i; hook length counts the cell and those directly to its right or above.Source: §2.3 · p. 13

2.3.1 Random words and Young diagrams, and symmetric polynomials

A word’s sorted type is its letter-frequency histogram sorted in nonincreasing order, and semistandard tableaux have weakly increasing rows and strictly increasing columns.Source: §2.3.1 · p. 14
Schur polynomials sum monomials over semistandard tableaux of a given shape, and they are symmetric polynomials.Source: §2.3.1 · p. 15

2.3.2 The RSK algorithm

RSK inserts word letters into successive tableaux, bumping larger entries upward, and returns the shape of the final tableau.Source: §2.3.2 · p. 15
Greene’s theorem characterizes the first k row lengths of the RSK output as the maximum size of a union of k weakly increasing subsequences.Source: §2.3.2 · p. 16
For a random word, the distribution of its RSK partition is invariant under permuting the underlying distribution’s probabilities, and quantum spectrum testing observes this partition rather than the word.Source: §2.3.2 · p. 16

2.4 Representation theory, and the symmetric group

This section reviews finite-group representations and Fourier analysis, then specializes these ideas to the symmetric group. There, partitions index both conjugacy classes and irreducible representations, linking characters and Schur polynomials.

2.4 Representation theory, and the symmetric group

Every representation decomposes into irreducible representations, and the regular representation contains each irrep with multiplicity equal to its dimension.Source: §2.4 · p. 17
The Plancherel distribution assigns an irrep probability proportional to the square of its dimension.Source: §2.4 · p. 17
Group characters are class functions, and the characters of irreducible representations form an orthonormal basis for class functions.Source: §2.4 · p. 17
For the symmetric group, partitions index both conjugacy classes and irreducible representations, and the dimension of the irrep indexed by λ equals the number of standard tableaux of shape λ.Source: §2.4 · p. 18
The Fourier coefficients of the power-sum class function on the symmetric group are Schur polynomials.Source: §2.4 · p. 18

2.5 Weak Schur sampling

Weak Schur sampling reduces testing unitarily invariant properties of a mixed state to analyzing a random partition whose distribution depends only on the state’s spectrum. It is an optimal measurement for these testing tasks, and the paper notes that its upper-bound algorithms can also run efficiently.

2.5 Weak Schur sampling

Factoring out the actions of S_n and U_d leaves a random partition whose distribution depends only on ρ’s spectrum; it is also the RSK shape of an i.i.d. word drawn from that spectrum.Source: §2.5 · p. 19
The algorithm acts on ρ⊗n and outputs a partition λ of n with length at most d.Source: §2.5 · p. 20
Weak Schur sampling is an optimal measurement for testing unitarily invariant properties: it suffices to sample a partition and classically postprocess it.The lemma preserves the tester’s parameters.Source: §2.5 · p. 20
The upper-bound algorithms can run in time polynomial in n, log d, and log(1/ϵ), with the Schur change of basis as their only expensive operation.Source: §2.5 · p. 20

2.6 Understanding the weak Schur sampling distribution

The section characterizes the weak Schur sampling distribution through representation theory and an equivalent classical RSK description. This links the maximally mixed state to the Schur–Weyl distribution and, as d grows with n fixed, to Plancherel measure.

2.6 Understanding the weak Schur sampling distribution

Under weak Schur sampling, the partition distribution for a state with spectrum η equals the distribution of RSK(a) for an i.i.d. word a drawn from η.Source: §2.6 · p. 21
The RSK description gives a quantum-free way to analyze spectrum testing, though the section says representation theory is more powerful for its purposes.Source: §2.6 · p. 21
For the maximally mixed state, the Schur–Weyl distribution is equivalently the RSK shape of a uniformly random word from [d]^n.Source: §2.6 · pp. 21–22
With n fixed and d tending to infinity, the Schur–Weyl distribution tends to Plancherel measure on partitions.Source: §2.6 · p. 22

2.7 Asymptotic theory of the symmetric group

The section reviews limiting shapes and fluctuations for Plancherel and Schur–Weyl random Young diagrams, then records concrete concentration bounds for diagram width and length. These asymptotic results describe typical diagram shapes in regimes where n and d grow.

2.7 Asymptotic theory of the symmetric group

For Plancherel measure, a random diagram’s scaled shape converges to the limiting curve Ω(x), and Kerov’s central limit theorem describes deviations around it.Source: §2.7 · p. 22
When n and d grow with the stated fixed-ratio regime, Schur–Weyl diagrams approach Biane’s limiting curve Ωc.Source: §2.7 · p. 23
When n = o(d^2), the diagram function converges to the ice-cream-cone curve Ω(x) from above.Source: §2.7 · pp. 22, 24
The section records concrete concentration bounds on Schur–Weyl diagram width and length by bounding the occurrence of increasing subsequences in random words.Source: §2.7 · p. 24

2.8 Polynomial algebras

The section introduces shifted symmetric polynomials as an algebra of functions on Young diagrams and describes polynomial families used to study them. It emphasizes central characters because their expectations under Schur–Weyl distributions are simple, and gives tools for expressing them through diagram observables.

2.8 Polynomial algebras

The shifted symmetric polynomial algebra Λ* can be viewed as Kerov’s algebra of polynomial functions on Young diagrams and contains moment-like polynomials with tractable Schur–Weyl expectations.The section identifies p*k as algebraically independent generators and notes their coordinate-moment interpretation.Source: §2.8 · pp. 24–25

2.8.1 Working with the p♯ µ polynomials

Explicit formulas for general p♯_µ polynomials are famously complex, although p♯_k can be computed fairly easily for small k.Source: §2.8 · p. 25

2.8 Polynomial algebras

Central character polynomials p♯_µ form a linear basis of Λ*, and their expectations under Schur–Weyl distributions have a simple expression.Source: §2.8 · pp. 25–26
For the uniform spectrum, the power sum p_µ(η) simplifies to d^(ℓ(µ)-k), yielding a useful special case for the expectation formula.Source: §2.8 · p. 26

2.8.1 Working with the p♯ µ polynomials

Generating-function identities give a finite method to express p♯_k polynomials in terms of the p*k observables.The summation ranges in the identities can be restricted to finite ranges depending on k.Source: §2.8.1 · p. 27
Products of central character polynomials can be expanded using structure constants that count compatible pairs of permutations, supporting conversion between polynomial families.Source: §2.8.1 · p. 28

3 The empirical Young diagram algorithm

This section gives upper and lower bounds for EYD spectrum estimation: it supplies an O(d^2/ε^2) polylogarithmic guarantee and shows a matching-order copy lower bound.

3.1 The upper bound

O(d^2/ε^2)·log(d/ε)·log(1/δ) copies suffice to output an estimate λ with dTV(λ,η) ≤ ε with probability at least 1 − δ.The paper also concludes that any unitarily invariant property is testable with O(d^2/ε^2)·log(d/ε) copies.Source: §3.1 · p. 29
The simplified upper-bound proof reinterprets the majorizing step through RSK, while the lower-bound proof uses Young-diagram polynomial functions and fourth moments to bound fluctuations.Source: §3.1 · p. 29, §3.2 · p. 31

3.2 The lower bound

Ω(d^2/ε^2) copies are necessary for EYD spectrum estimation, making the upper bound nearly tight even when ρ is maximally mixed.Source: §3.2 · p. 30

4 A quantum Paninski theorem

This section establishes that testing whether a d-dimensional mixed state is maximally mixed requires and suffices with Θ(d/epsilon²) copies, presenting a tester and a lower bound based on distinguishing Schur–Weyl distributions. The lower-bound proof derives an alternating-sign Schur polynomial formula, including the odd-dimensional case.

4 A quantum Paninski theorem

Θ(d/epsilon^2) copies are necessary and sufficient to test whether a d-dimensional mixed state is maximally mixed.The upper bound is O(d/epsilon^2); for even d, the lower bound requires at least 0.15d/epsilon^2 copies.Source: §4 · p. 33, §4.1 · p. 33, §4.2 · p. 35

4.1 The upper bound

The Mixedness Tester uses O(d/epsilon^2) copies and accepts the maximally mixed state and rejects states epsilon-far from it with probability at least 2/3.The completeness and soundness guarantees are established using Chebyshev’s inequality.Source: §4.1 · pp. 33–34

4.2 The lower bound: overview

For even d, testing whether a d-dimensional mixed state ρ has the property of being maximally mixed requires at least 0.15d/epsilon^2 copies.Source: §4.2 · p. 35

4.3 Proof of Theorem 4.4

The proof of Theorem 4.4 shows that degree-k terms contribute on the order of n^k rather than the naively expected n^2k.It establishes that contributions from powers n^(k+1) through n^(2k) drop out.Source: §4.3 · p. 36

4.4 A formula for sµ(+1, −1, +1, −1, . . . )

The formula subsection defines a balanced partition as one whose Young diagram can be reduced to empty by successive removal of 2-hooks.A 2-hook is a length-2 hook, or domino, whose removal leaves a valid Young diagram.Source: §4.4 · p. 40
Removing a 2-hook from μ corresponds to removing a 1-hook from one component of its 2-quotient, providing the induction used for the content identity.The 2-quotient is formed from the two alternating sequences of pebbles in μ’s Maya diagram.Source: §4.4 · p. 41
For balanced μ ⊢ k, sμ(+1, −1, +1, −1, …) equals k!! · (d↑[μ]even); if μ is not balanced, the value is 0.Source: §4.4 · p. 42

4.5 Wrapping up the lower bound

The argument in this section completes the proof of Theorem 4.2.Source: §4.5 · pp. 42–43
For odd d ≥ 3, padding the alternating-sign vector with a zero preserves the lower-bound argument, yielding Ω(d/ε^2) copies.The proof uses stability of shifted Schur polynomials and bounds the resulting d − 1 expression by d.Source: §4.5 · p. 43

5 Hardness of distinguishing uniform distributions

The paper proves that distinguishing a state uniform on r versus r + ∆ eigenvalues requires and suffices with O(r^2/∆) copies up to a lower-bound factor. Its upper-bound tester uses a cutoff between the two cases’ expectations.

5 Hardness of distinguishing uniform distributions

O(r^2/∆) copies suffice, and eΩ(r^2/∆) copies are necessary, to distinguish spectra uniform on r versus r + ∆ eigenvalues.The stated range is 1 ≤ ∆ ≤ r.Source: §5 · p. 43

5.1 The upper bound

The tester uses the same variance in both cases and sets its acceptance cutoff midway between their different expectations.The analysis applies Chebyshev’s inequality to bound the error when m = r.Source: §5.1 · p. 44
For r versus r + 1, the Rank Tester is an O(r^2)-copy alternative with one-sided error, unlike the Uniform Distribution Distinguisher.It never rejects in the rank-r case.Source: §5.1 · p. 44

5.2 The lower bound

These parts prove an exponential-in-r^2 lower bound on the copy complexity of rank-r versus rank-r+1 testing by bounding the distance between the corresponding Schur–Weyl distributions.

5.2 The lower bound

The lower-bound target is to show that the rank-r and rank-(r + 1) Schur–Weyl distributions are close unless n ≥ e^Ω(r²).The argument focuses first on Δ = 1; the extension to larger Δ is deferred to Section 5.3.Source: §5.2 · p. 44

5.2.1 Initial approximations

The KL-divergence approximation restricts attention to “usual” partitions, which occur with overwhelming probability when n ≪ r².A partition is defined as usual when its first row and first column satisfy the stated cutoff; the passage says the event has probability 1 − δ for small δ.Source: §5.2.1 · pp. 44–46

5.2.2 Passing to the p♯polynomials

Proposition 5.5 gives an identity on observables with rational coefficients, enabling the argument to express its main term using p♯ polynomials.The error term is treated separately, and the text focuses on bounding the main term when n ≪ r².Source: §5.2.2 · pp. 47–48

5.2.3 Showing the “main term” is small: some intuition

Grouping contributions by |µ| reveals cancellations: contributions that initially appear too large cancel against lower-degree terms from larger k.The text says the cancellation is perfect for complete groups, while terms left over near the cutoff can be made small by choosing ω and C large enough.Source: §5.2.3 · pp. 48–49

5.2.4 Proof that the “main term” is small

A combinatorial identity makes the summed contributions vanish when the inner sum runs through its full range; the remaining partial sums are bounded crudely.The proof uses this cancellation to control the main term after rearranging the summation by |µ|.Source: §5.2.4 · p. 49

5.2.5 Bounding the “error term”

Treating C as an absolute constant, the error bound yields a testing lower bound n ≥ Ω_δ(r^(2−δ)) for every δ > 0.A subsequent technical bound gives A_C ≤ 2^{O(C² log C)}, supporting a more explicit lower bound.Source: §5.2.5 · p. 50
Each replacement linear polynomial has norm at most exp(O(k^2 log k)), so replacing terms in S_k increases its norm by at most another exp(O(k^2 log k)) factor.The coefficient and partition-count bounds yield this polynomial norm bound.Source: §5.2.5 · p. 51

5.2.6 Combining the bounds

e^Omega(r^2) copies are required for rank-r versus rank-(r+1) testing, with the bound obtained at omega = exp(O(log^0.67 r)) and n = r^(2-O(1/log^0.33 r)).At these parameter values, the combined bound is o(1).Source: §5.2.6 · p. 52

5.3 Extension to ∆> 1

For rank testing with a dimension gap Δ>1, the proof sharpens its Pinsker-based lower-bound argument. It extends the bound across intermediate dimensions using the triangle inequality.

5.3 Extension to ∆> 1

The proof notes that Pinsker’s inequality is not sharp in this setting, a key step toward a stronger lower bound when Δ>1.The argument develops variance bounds before completing the lower-bound proof.Source: §5.3 · pp. 52, 55
For r≤r′≤2r, the proof transfers the bound using the triangle inequality and compares the corresponding ω parameters.The ω values differ by at most a factor of 2 over this range.Source: §5.3 · p. 52
The argument completes the rank-testing lower bound (27) after proving Theorem 5.11.Source: §5.3 · pp. 52, 55

6 Quantum rank testing

The section establishes one-sided rank testing at Θ(r^2/ε) copies and gives a tighter O(r^2) bound for uniform spectra on r versus r+1 eigenvalues. It also proves an Ω(r/ε) lower bound for two-sided rank testing.

6.1 Testers with one-sided error

The Rank Tester maps sampled words to an RSK partition and rejects when its height exceeds r, using the equality between partition height and longest decreasing subsequence length.A rank-r state has at most r nonzero eigenvalues, so sampled words cannot have more than r distinct letters.Source: §6.1 · p. 56
Θ(r^2/ε) copies are necessary and sufficient for one-sided testing of whether a state has rank r.The Rank Tester is optimal among one-sided-error algorithms.Source: §6.1 · p. 56
O(r^2) copies suffice to distinguish spectra uniform on r versus r+1 eigenvalues, with one-sided error.For the rank-r case the tester never rejects; for the rank-(r+1) uniform case it rejects with probability at least 2/3.Source: §6.1 · p. 58

6.2 A lower bound for testers with two-sided error

Ω(r/ε) copies are necessary for rank-r testing with two-sided error.The lower-bound argument reduces the task to distinguishing states maximally mixed on subspaces of dimensions r−1 and d−1.Source: §6.2 · pp. 58–59

7 The EYD lower bound (continued)

The EYD lower-bound argument uses convergence of the random partition shape to a limiting curve that remains separated from the uniform-partition curve. The proof supplies a convergence rate uniform over the relevant parameter range, independent of n.

7 The EYD lower bound (continued)

When n≤Cd^2 and d is sufficiently large, the limiting-shape argument yields the EYD lower bound by separating its curve from the uniform-partition curve.The proof uses convergence toward Ωθ and a constant separation from the uniform curve.Source: §7 · pp. 59–60
The proof needs convergence control uniform in θ because the ratio θ can vary with d and known convergence thresholds are unspecified.An adversarial choice of n as a function of d could otherwise keep the argument outside a known threshold.Source: §7 · p. 59

7.1 Proof of Theorem 7.2

The proof obtains a convergence rate depending only on d, adapting law-of-large-numbers arguments from [IO02] and [Mél10a] to the Schur–Weyl distribution.The authors describe the contribution as bookkeeping of existing arguments rather than new ideas.Source: §7.1 · p. 61
The proof controls deviations from Ωθ by bounding expectations of polynomial observables and applying Markov’s inequality.Lemma 7.6 supplies a quantity that tends to zero with d, independent of n.Source: §7.1 · pp. 62–63