PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient quantum tomography II

Ryan O'Donnell, John Wright

arXiv:1612.00034v1quant-phcs.DS

TL;DR

The paper studies quantum tomography and Young-diagram distributions, introducing RSK and Schur-sampling tools to obtain new nonasymptotic results. It derives improved quantum-learning guarantees, including spectrum estimation with O(d^2/ε) copies and PCA-style state learning.

  • Problem

    Learning an unknown quantum state in infidelity remains open, despite known trace-distance complexity and prior upper bounds for infidelity.

  • Method

    The paper analyzes RSK output using a new majorization property and applies weak and strong Schur sampling to quantum state learning.

  • Results

    The spectrum can be learned in Hellinger-squared, KL, and chi-squared divergence using n = O(d^2/ε) copies, while rank-k state learning is extended to additional distance measures.

  • Takeaways & Limitations

    Schur–Weyl distributions connect combinatorial and representation-theoretic analysis with quantum learning and data processing.

  • Takeaways & Limitations

    Theorem 1.26 has qualitatively different limiting behavior for equal versus unequal α_i, so its convergence rate depends on how eigenvalues compare.

Abstract

from arXiv · show

Following [OW16], we continue our analysis of: (1) "Quantum tomography", i.e., learning a quantum state, i.e., the quantum generalization of learning a discrete probability distribution; (2) The distribution of Young diagrams output by the RSK algorithm on random words. Regarding (2), we introduce two powerful new tools: (i) A precise upper bound on the expected length of the longest union of $k$ disjoint increasing subsequences in a random length-$n$ word with letter distribution $α_1 \geq α_2 \geq \cdots \geq α_d$; (ii) A new majorization property of the RSK algorithm that allows one to analyze the Young diagram formed by the lower rows $λ_k, λ_{k+1}, \dots$ of its output. These tools allow us to prove several new theorems concerning the distribution of random Young diagrams in the nonasymptotic regime, giving concrete error bounds that are optimal, or nearly so, in all parameters. As one example, we give a fundamentally new proof of the fact that the expected length of the longest increasing sequence in a random length-$n$ permutation is bounded by $2\sqrt{n}$. This is the $k = 1$, $α_i \equiv \frac1d$, $d \to \infty$ special case of a much more general result we prove: the expected length of the $k$th Young diagram row produced by an $α$-random word is $α_k n \pm 2\sqrt{α_kd n}$. From our new analyses of random Young diagrams we derive several new results in quantum tomography, including: (i) Learning the eigenvalues of an unknown state to $ε$-accuracy in Hellinger-squared, chi-squared, or KL distance, using $n = O(d^2/ε)$ copies; (ii) Learning the optimal rank-$k$ approximation of an unknown state to $ε$-fidelity (Hellinger-squared distance) using $n = \widetilde{O}(kd/ε)$ copies.

1 Introduction

The paper develops nonasymptotic bounds for RSK Young diagrams from random words and applies them to quantum spectrum and state learning. Its results include sharp row-length estimates, new distance-specific tomography bounds, and analyses of truncated and asymptotic behavior.

  • RSK and random Young diagrams: The RSK algorithm maps a word to semistandard Young tableaux with a common Young-diagram shape λ.Its first row equals the longest weakly increasing subsequence, while Greene’s theorem characterizes sums of rows through unions of disjoint increasing subsequences.
  • Techniques: The analysis introduces a majorization property of RSK and bounds lower-row behavior through bumped-letter strings and unions of disjoint increasing subsequences.These tools support results for row sums and excess terms, including asymptotic accuracy when adjacent α-coordinates are sufficiently separated.
  • Quantum state learning: n = O(d^2/ε) copies suffice to learn a state’s spectrum in Hellinger-squared, KL, or chi-squared distance.The paper extends earlier spectrum-learning results to these distance measures and reports correct constant factors for its principal bounds.
  • Principal component analysis: n = O(kd/ε) copies suffice for learning the first k eigenvalues in Hellinger-squared or chi-squared distance, while ℓ2 learning requires n = O(k/ε) copies.The work also studies full-state fidelity PCA, producing rank-k hypotheses competitive with the best rank-k approximation.
  • Asymptotics and scope: The asymptotic theory distinguishes equal α-coordinates from unequal ones, yielding GUE fluctuations within equal-value blocks and Gaussian fluctuations across blocks.This qualitative distinction makes convergence rates depend on separation quantities, while some finite-n bounds remain uniform over d and α.

2 Preliminaries

This section establishes notation and tools for analyzing Schur–Weyl distributions, including RSK stability, monotonicity, and relations among statistical distances.

  • η≤k and η>k denote the sums of the first k and remaining components of a sequence η.
  • The RSK shape map is Lipschitz under Hamming perturbations, enabling distributional comparison through couplings of random words.A coupling with single-letter mismatch probability ε gives expected word Hamming distance εn, after which the RSK bound is iterated.
  • For sorted α, the probability that the next letter creates a box in the first k rows is nondecreasing with the word length n.Letters among the k largest contribute probability α≤k, while the remaining contribution is also shown to be nondecreasing.
  • Hellinger-squared, chi-squared, KL, fidelity, and affinity distances are linked by inequalities that permit converting distance bounds into fidelity guarantees.In particular, dH2(ρ,σ)=ε implies 1−ε/2 ≤ F(ρ,σ), while affinity is bounded between fidelity-related quantities.

3 Bounding the excess

This section analyzes the excess of Young-diagram row sums over multinomial expectations using a modified multinomial distribution that favors top-heavy diagrams. It proves finite-n bounds and identifies the asymptotic excess when the distribution entries are distinct.

  • The Schur–Weyl distribution is analyzed through a modified multinomial distribution that favors top-heavy Young diagrams.The modified density is used for expectations relative to the multinomial distribution, even though it may be signed.
  • The approximation error can depend adversely on d and on the gap α_k−α_{k+1}, but an increasing-property argument avoids this error when estimating the expected excess.The modified-distribution approximation is therefore useful despite potentially unpleasant parameter dependence.
  • The argument recovers the k=1 result previously proved by Its, Tracy, and Widom as a special case.The proof uses multinomial moment identities for the histogram counts.
  • Theorem 3.7 gives a finite-n upper bound for the expected excess of the first k rows over their multinomial expectations.The theorem applies to every sorted distribution α and every k ∈ [d].
  • For distinct α_i, the expected excess converges to Excess_k(α) as n →∞.The limiting quantity becomes singular as α_k and α_{k+1} approach equality.
  • The expected excess is nondecreasing in n, so Excess_k(α) is an upper bound for all n.The authors expect convergence to Excess_k(α) for all α, but do not prove it.

4 Convergence of the Schur–Weyl distribution

This section develops majorization and perturbation tools for controlling Young-diagram rows under the Schur–Weyl distribution. These tools yield bounds, concentration, mean-square estimates, and improved control when adjacent probabilities are poorly separated.

  • 4 Convergence of the Schur–Weyl distribution: Theorem 4.2 weakly majorizes the lower-row diagram λ[k:] by the RSK shape of the word obtained after deleting letters smaller than k.The result follows from the paper’s new RSK majorization theorem.
  • 4.1 Bounds on the first and last rows: Majorization comparisons between probability distributions transfer to expectations of Young-diagram row statistics through Theorems 4.3 and 4.4.The lower-row comparison also gives a bound on the expected last row, including the displayed α_d n−2√… form.
  • 4.1 Bounds on the first and last rows: Theorems 4.5 and 4.6 bound expected row sums and kth-row statistics, and Theorem 4.7 converts these estimates into normalized Young-diagram bounds.The proofs combine majorization, Jensen’s inequality, and earlier estimates.
  • 4.5 Concentration: Each row concentrates exponentially around its mean by bounded differences and Azuma’s inequality.Changing one input letter changes the relevant martingale by at most 2.
  • 4.6 Mean squared error: The mean-square deviation of λ_k from α_k n is at most 42α_kkn + 42α_≥kn.This is stated for every sorted probability distribution and every k ∈ [d].
  • 4.7 An alternate bound on E(n): When α_k−α_{k+1} is tiny or zero, perturbing α yields useful alternatives because Excess_k(α) can become arbitrarily large.The alternate bounds improve constants and can make the error decrease with α_>k.

5 Tomography with Hellinger/infidelity error

This section analyzes the Keyl algorithm’s Hellinger error, reducing the problem to the spectrum of the unknown state and bounding full- and rank-k tomography hypotheses.

  • Algorithm and reduction: The Keyl algorithm samples λ from the Schur–Weyl distribution and V from the corresponding Keyl distribution, then outputs VΛV†.Here Λ = diag(λ/n), while rank-k tomography replaces Λ by Λ(k), which keeps only the first k entries.
  • Algorithm and reduction: Unitary invariance reduces the Hellinger analysis to DH2(Λ,R), with R = V†ρV, and the distribution of R depending only on ρ’s spectrum.The analysis therefore assumes ρ = diag(α) without loss of generality.
  • Supporting bounds: The analysis treats the Keyl distribution through Corollary 5.2, which supplies the permutation-related bound ultimately used in the Hellinger estimates.This isolates the distributional property needed for the tomography argument.
  • Rank-k tomography: Theorem 5.6 bounds Hellinger error for the rank-k hypothesis produced by the Keyl algorithm.Its proof separately accounts for the discarded spectrum beyond rank k and the deviation of the sampled Young-diagram rows.
  • Full tomography: Theorem 5.7 gives the corresponding full-tomography guarantee for rank-r states, with logarithmic dependence controlled by min{r, ln n}.The proof combines bounds on multiplier sums, permutation effects, and Young-diagram fluctuations.

6 The lower-row majorization theorem

This section proves a majorization property that transfers increasing-subsequence information from letters bumped out of a Young-diagram row back to the original input string.

  • The transfer lemma: Theorem 6.1 guarantees disjoint admissible increasing subsequences in the preceding string with total length L + Δ while preserving the curve condition.It starts from admissible chains in b and constructs corresponding chains in w with an enlarged admissible set A′.
  • The majorization theorem: Theorem 6.3 shows that the shape of the bumped-letter string x(k) is majorized by the shape of its corresponding subsequence in x.This is the central RSK property used to control lower rows.
  • The majorization theorem: The proof propagates disjoint increasing subsequences upward through successive bumped strings, increasing their total length by newly admissible letters.Theorem 6.1 supplies the stepwise transfer, and the increments accumulate as Δ = Δ1 + · · · + Δk.
  • The geometric proof: The geometric proof represents words as diagram points and increasing subsequences as northeast chains, then slides beads northwest along jump lines.A key claim is that all white points northwest of the first curve become admissible; induction verifies that deposited points remain ordered and southeast of the next curve.
Loading 1612.00034v1…