PaperlayerView exact revision on arXiv

Source-linked AI summary

Robustness of quantum spectrum estimation: weak Schur sampling under noisy inputs

Vladyslav Visnevskyi, Laura Mančinska

arXiv:2610.03582v3quant-phcs.ITmath.ITmath.RT

TL;DR

The paper addresses whether optimal collective spectrum estimation remains reliable when input copies are noisy and no longer identical. It proves robustness bounds for weak Schur sampling under product and Wasserstein noise, while showing that weaker input promises can fail. The results establish noise robustness for the Keyl–Werner spectrum estimator, though some per-realisation guarantees require concentration results.

  • Problem

    Optimal quantum learning algorithms are commonly analyzed on identical copies, leaving their guarantees under realistic shot-to-shot input variation less complete.

    Source: §1 · p. 1, Motivation of the problem · p. 2

  • Method

    The proof replaces noisy registers one at a time and uses the estimator's 1/n observable variation to bound cumulative error; a Wasserstein duality argument extends the bound to arbitrary inputs.

    Source: §1 · p. 2, §1.1 · p. 3

  • Results

    For product noise, each copy within trace distance ε, the estimator's expected error is at most its noiseless error plus ε, and the noise-induced ε floor is optimal.

    Source: §1 · p. 2, §1.1 · p. 3

  • Takeaways & Limitations

    The robustness result establishes a guarantee for the standard Keyl–Werner algorithm for quantum spectrum estimation.

    Source: §1 · p. 2

    The stated average-over-noise guarantee does not by itself ensure small error for an individual noise realization; that requires a concentration result.

    Source: §4.7 · p. 15

Abstract

from arXiv · show

We initiate the study of weak Schur sampling (WSS) under noisy inputs. Many optimal quantum learning algorithms rely on this measurement, for instance in quantum spectrum estimation (QSE) and quantum state tomography (QST). The standard analysis of WSS, QSE and QST assumes that the $n$ input copies of the target state $\rho$ are identical, i.e. $\rho^{\otimes n}$. We study what happens when they are not, a more realistic noisy scenario that breaks the very permutation symmetry on which WSS is built. In the simplest model the input is a noisy product state: the copies are independent but not necessarily identical and each is $\epsilon$-close in trace distance to the $d$-dimensional target state $\rho$. A naive argument via the data-processing inequality allows the per-copy errors to accumulate to $n\epsilon$ on the measurement outcome. We show that for QSE via WSS this does not happen: the expected estimation error in total variation is at most $\epsilon+\eta(n,d)$, where $\eta(n,d)=O(d/\sqrt n)$ is the noiseless error, and the additive noise term $\epsilon$ is optimal. The output error does not grow with $n$ even though the input error does; in this sense WSS is robust. Beyond noisy product states, for arbitrary input $\omega$ we show that the error is at most $\eta(n,d)+\frac{1}{n}\|\omega-\rho^{\otimes n}\|_{W_1}$, where $W_1$ is the quantum Wasserstein distance of De Palma et al. In particular, our results imply, for the first time, noise-robustness of Keyl and Werner's seminal algorithm for QSE, more than two decades after its introduction. Finally, we show that the noise cannot be too bad: within our model of robustness the promise on the input cannot be weakened to closeness of single-copy marginals or to a global trace-distance budget alone, as in both cases some inputs defeat every measurement and estimator.

1. Introduction

Optimal quantum learning algorithms are usually analyzed on identical copies, although real inputs can vary across shots and break the permutation symmetry used by collective measurements. The paper establishes robustness guarantees for weak Schur sampling under structured noise, while identifying weaker promises that do not suffice.

1.2. Applications.

  • The guarantees settle the robustness of the Keyl–Werner spectrum estimator, while full tomography's subsequent eigenbasis measurement remains an open question.Weak Schur sampling is the shared first stage of optimal tomography protocols; robustness of that stage does not settle the second.Source: §1 · p. 2, §1.2 · p. 4

1. Introduction

  • The standard perfect-copy analysis leaves a practical gap because shot-to-shot variation removes the permutation symmetry exploited by collective spectrum estimation.The paper motivates robustness as necessary for making optimal learning algorithms practical.Source: §1 · p. 1, Motivation of the problem · p. 2

1.1. Our results.

  • For independent copies each within trace distance ε of ρ, weak Schur sampling estimates its spectrum with expected error η(n,d) + ε, and the ε noise floor is optimal.The additive noise cost does not grow with n, preserving the collective d^2 sample complexity.Source: §1.1 · p. 3
  • The replacement proof bounds each register's contribution by ε/n, so replacing all n noisy registers costs ε; permutation invariance makes the single-register bound independent of replacement order.The estimator's effective observable has eigenvalue spread at most 1/n, yielding the per-register bound.Source: §1.1 · p. 3, Figure 1 · p. 3
  • For arbitrary possibly correlated or entangled inputs, the error is bounded by the noiseless error plus the input's quantum Wasserstein distance from ρ^⊗n divided by n.The paper extends this bound to several settings, including corrupted registers, mixtures, and Wasserstein almost-i.i.d. sources.Source: §1.1 · p. 4
  • Neither exact single-copy marginals nor a global trace-distance promise alone guarantees robust spectrum estimation, even for the best measurement and estimator.With marginals alone, constant worst-case error is possible even when every marginal equals ρ; with global trace distance θ, the worst-case error is Θ(min(θ,1)).Source: §1.1 · p. 4

1.2. Applications.

  • The results also extend to spectrum functionals whose one-box variation is small, while robustness under intermediate or alternative noise models remains open.Examples include entropy, purity, and largest-eigenvalue-weight estimators; the paper does not claim product and Wasserstein noise are the only robust models.Source: §1.1 · p. 4, §1.2 · p. 5

1.3. Connections to existing work.

  • Unlike general reductions from arbitrary inputs to i.i.d. learning, the paper directly analyzes a fixed collective estimator for a target state to which each product-input copy is close.The related-work discussion distinguishes this setup from approaches that incur polynomial dimension overhead or predict a randomly held-out system.Source: §1.3 · p. 6

2. Preliminaries

The preliminaries define the state, distance, and partition notation, then use Schur–Weyl duality to describe weak Schur sampling. The estimator reads the normalized partition label, with noiseless expected error O(d/√n).

2.1. Notation.

  • Trace distance measures state separation, total variation measures probability-vector separation, and partitions λ encode integer row lengths summing to n.A partition is also represented as a Young diagram; addable rows are those where adding a box preserves the partition ordering.Source: §2.1 · p. 7

2.2. Schur–Weyl duality.

  • Schur–Weyl duality block-diagonalizes the commuting GL(d, C) and symmetric-group actions into components labeled by partitions λ.The projectors onto these blocks form the weak Schur sampling measurement, which reveals λ while leaving the within-block state untouched for perfect-copy input.Source: §2.2 · p. 7

2.3. Weak Schur sampling and the spectrum estimator.

  • Weak Schur sampling measures the block label λ and estimates the spectrum with p̂ = λ/n; its outcome law is invariant under permuting input registers.The spectral output of Keyl’s full tomography protocol has the same law, but this paper leaves robustness of its eigenbasis output as an open direction.Source: §2.2 · p. 7, §2.3 · pp. 8–9
  • η(n, d) = O(d/√n) bounds the worst-case noiseless expected estimation error, while the Keyl–Werner concentration result gives exponentially suppressed error probability in nδ² up to a polynomial prefactor in n.The expected-error bound is stated uniformly over states on Cd.Source: §2.3 · pp. 8–9

3. Problem setup and the definition of robustness

The paper models non-identical inputs as independent copies, each within ε trace distance of the target, and defines robustness through output error that does not grow with n. For this model, weak Schur sampling achieves the noiseless error plus an optimal ε noise floor.

3.1. Non-identical input copies: the product model.

  • The product model applies independent, not necessarily identical, channels to the registers, each moving the target state by at most ε in trace distance.The model equivalently allows product inputs whose individual states each lie within ε of ρ; correlated channels are outside this model and are treated separately via Wasserstein distance.Source: §3.1 · p. 9
  • For a fixed noisy input, expectations are over the weak Schur sampling outcome, whose probability is determined by the projective measurement.The outcome function defines an observable whose expectation is linear in the input state.Source: §3.1 · p. 9

3.2. Robustness.

  • Robustness requires output error to separate into a noise-dependent term vanishing with ε and a term vanishing as n grows for fixed d and ε.The n-independent floor captures noise that additional copies cannot remove; output error growing with n could constrain learnable rank and precision.Source: §3.2 · pp. 9–10
  • Theorem 15 gives expected error at most ε + η(n, d), with η(n, d) = O(d/√n), and the ε floor cannot be avoided by any protocol under noisy input.The paper notes this preserves the noiseless rate plus an n-independent floor; some may consider the formal definition too weak or too strong, but this distinction is immaterial to the theorem’s bound.Source: §3.2 · p. 10
  • Definition 6 is presented as a deliberately simple first step rather than a final account of robustness.Alternative notions are discussed elsewhere in the paper.Source: §3.2 · p. 10

4. Robustness of spectrum estimation under product noise

This section studies weak Schur sampling for quantum spectrum estimation under product noise, including independent nonidentical inputs and admissible product-noise channels. It explains the error guarantee and its unavoidable noise floor, while distinguishing average guarantees from guarantees for each noise realization.

4.1. Single-slot operators.

  • A register’s perturbation affects the WSS outcome expectation through a d × d single-slot operator determined by the other registers.The proof reduces each register’s effect to this effective observable, then controls it through its eigenvalue spread.Source: §4 · p. 10, §4.1 · p. 10

4.2. Only the spread matters.

  • Because differences of states are traceless, only the single-slot operator’s spread matters, not its size; the spread can be O(1/n) even when the operator is O(1).This centering argument is the feature that makes the perturbation bound useful.Source: §4.2 · p. 11

4.3. One-box variation and the spread bound.

  • The spread is bounded by one-box variation, which is at most 1/n for λ_k/n and for 1/2∥λ/n−q∥1; branching ensures one register can change only one box.Thus the single-register spread bound is at most 1/n for both functions used in QSE.Source: §4.3 · pp. 11–12

4.4. Sequential replacement of the registers.

  • Replacing the perturbed registers by ρ one at a time costs at most ε in expectation for functions whose one-box variation is at most 1/n.Telescoping the replacements uses the single-register bound, so the per-copy costs add to ε rather than nε.Source: §4.4 · p. 12

4.5. The main result.

  • For independent copies each within ε of ρ, expected QSE error is at most ε+η(n,d), where η(n,d)=O(d/√n); the error does not grow with n.The noiseless statistical error decreases with n until it reaches the additive noise floor ε.Source: §4.5 · p. 13

4.6. Optimality of the noise floor.

  • The ε noise floor is unavoidable: some admissible cases force every measurement and estimator to incur error at least ε/2 for every n, and both terms of the precision bound are necessary up to a logarithmic factor in d.The floor is information-theoretic, while the noiseless minimax error supplies the statistical lower bound.Source: §4.6 · p. 14

4.7. Randomly drawn channels and unbiased noise.

  • For independently random admissible channels, the copies are independent random states within ε of ρ, and linearity makes the noise-averaged outcome factorize over the averaged copies.Source: §4.7 · p. 14
  • Randomized admissible product-noise channels gain nothing over deterministic channels, and Theorem 15 also holds for the joint noise-measurement expectation.Averaging the outcome law over the noise gives the outcome law for the product of the noise-averaged copies.Source: §4.7 · p. 14
  • Under unbiased noise, the marginal outcome law equals the noiseless law for every outcome, so the average error equals the noiseless error with floor 0.The equality averages over both the noise and the measurement.Source: §4.7 · p. 15
  • The unbiased-noise average guarantee does not ensure small error for a particular noise realization; that requires a separate concentration result.The per-realization concentration result is proved in Section B.3.Source: §4.7 · p. 15

5. Beyond product noise: noisy sources bounded in Wasserstein distance

The section extends weak Schur sampling’s robustness analysis from product noise to arbitrary correlated or entangled inputs using quantum Wasserstein distance. A bound on the outcome observables’ register-level sensitivity yields spectrum-estimation error controlled by noiseless error plus Wasserstein distance per register.

5.1. The quantum Wasserstein distance of order one.

  • Quantum W1 extends Hamming distance to register states, distinguishing perturbations by how many registers they affect; for one register it reduces to trace distance.It is dual to an observable’s quantum Lipschitz constant, which measures its dependence on individual registers.Source: §5.1 · pp. 15–16

5.2. Lipschitz constants of the outcome observables of weak Schur sampling.

  • Weak Schur sampling’s outcome observables for λ_k/n and the constant function have quantum Lipschitz constant at most 1/n.This register-sensitivity bound is the key ingredient for extending the guarantee beyond product noise.Source: §5.2 · p. 16

5.3. Robustness for arbitrary inputs.

  • For arbitrary, possibly correlated or entangled input ω, the spectrum-estimation error is bounded by η(n,d) + ||ω − ρ^⊗n||_W1/n.The section applies this general guarantee to several input classes, including a few corrupted registers, mixtures, and Wasserstein almost-i.i.d. sources.Source: §5.3 · pp. 16–17
  • If at most r registers are corrupted, the error is at most η(n,d) + 2r/n, improving to η(n,d) + r/n when the corrupted registers are in product form.A global trace-distance budget θ instead gives η(n,d) + θ; mixtures and Wasserstein almost-i.i.d. sources also receive bounds in the section.Source: §5.3 · p. 17
  • The W1 floor is attained by identical perturbed copies, on which no measurement and estimator can beat ε_W/2 on the corresponding two-point instance.The result uses the same perturbation that establishes optimality of the product-noise floor.Source: §5.3 · p. 17
  • The same W1-based method applies to other collective protocols once their outcome observables’ Lipschitz constants are known.For statistics that are sums of few-body terms, the section notes that the constant is O(1/n) for elementary reasons.Source: §5.3 · p. 17

6. When is the noise too strong? Marginal and global constraints

The section tests two weaker noise promises and gives adversarial inputs showing that neither suffices for robust spectrum estimation. Marginal closeness can fail even exactly, while a global trace-distance budget can permit error that grows with the number of copies.

Marginal constraints

  • At ε = 0, an input with every marginal exactly ρ makes weak Schur sampling output (1, 0, …, 0) with certainty, giving error 1 − p1 for every n.For the same marginal-only promise, every measurement and estimator has worst-case error at least 1/2 p1(1 − p1), independent of n.Source: §6 · p. 18

Marginal and global constraints

  • A single classically correlated mixture of eigenstate product inputs witnesses both failures: its marginals equal ρ, yet its collective weak Schur sampling outcome is deterministic.The mixture averages over eigenbasis choices shared across all copies.Source: §6 · pp. 17–18

Global trace-distance constraints

  • Under a global trace-distance budget θ, the worst-case error can be at least θ(1 − p1), independent of n, even for weak Schur sampling.The lower bound also applies to every measurement and estimator in the stated two-target setting.Source: §6 · p. 18
  • For the global class with budget nε, the worst-case error grows linearly with n until saturation at n ≈ 1/ε.The section contrasts this with the product-noise guarantee ε + O(d/√n) under the same summed trace-distance budget.Source: §6 · pp. 18–19

7. Discussion and open questions

The discussion identifies limits to the present robustness results and outlines open problems. These include extending guarantees to intermediate noise classes, resolving finer error behavior, and analyzing tomography and the full sample-optimal spectrum algorithm beyond weak Schur sampling.

Intermediate noise models

  • Robustness for finite-k marginal constraints, almost-i.i.d. states, and k-wise independent channels remains open, as does how the error interpolates between Θ(ε) and Θ(min(nε, 1)).The section notes that finite-k constraints exclude the exhibited counterexample, but do not settle robustness.Source: Intermediate noise models · p. 19, Open questions · p. 20

Alternative notions of robustness

  • The robustness definition requires fixed-noise output error not to grow with n, although the discussion notes alternative definitions may be useful when precision or noise floors impose a copy cap.The authors leave open which relaxations are meaningful for applications and which noise classes they admit.Source: Alternative notions of robustness · p. 19

Robustness of the eigenbasis estimate: full state tomography

  • For full state tomography, robustness of the eigenbasis-estimation stage remains unestablished because it is nonlinear in the post-measurement state.The analysis in the paper covers the spectrum estimate, not this second measurement stage.Source: Open questions · p. 19

Robustness of the optimal spectrum estimation algorithm

  • For the sample-optimal spectrum algorithm, robustness of its bucketing stage and moment-matching post-processing remains to be established.The paper’s results cover the weak Schur sampling stage; if both additional stages are robust, the claim would extend to the full algorithm.Source: Open questions · p. 20

The exact worst case at finite n

  • It remains unresolved whether the noisy error’s two terms genuinely add or whether the worst case instead behaves like their maximum.The telescoping bound also discards possible cancellation between registers perturbed in opposite directions.Source: Open questions · p. 20

Finer distributional information for the noiseless measurement

  • A fixed-d local central limit theorem for the noiseless measurement law is not available in the cited literature, leaving finer per-realisation distributional information open.The section distinguishes this regime from existing central limit results where d grows with n.Source: Open questions · p. 20

Other collective protocols

  • The method extends to other collective protocols when the outcome observable’s Lipschitz constant is known; several candidate protocols would require that constant to be established.The discussion names entropy and purity estimators, purification, and mixed Schur sampling as targets.Source: Open questions · p. 20

Appendix A. The Keyl measurement and the Keyl formula

The appendix reviews the precision of Keyl’s spectrum estimator and the additional covariant measurement used to estimate eigenbasis information. It also gives the Keyl outcome law for identical copies and notes why that formula does not directly extend to non-identical product inputs.

A.1. Output precision of Keyl’s spectrum estimation.

  • The noiseless expected spectrum-estimation error satisfies η(n,d) = O(d/√n).This bound is uniform over the states considered in the appendix.Source: §A.1 · p. 23

A.2. The eigenbasis measurement.

  • After weak Schur sampling yields λ, Keyl’s protocol measures the V_λ register with a covariant continuous POVM whose outcomes are unitaries U.The post-measurement state on V_λ is s_λ(p)^−1π_λ(ρ).Source: §A.2 · p. 23
  • The full estimator is (λ/n, U), and reconstructs the state as U diag(λ/n) U†.The second measurement estimates eigenbasis information discarded by weak Schur sampling; the appendix reports an optimal O(d²/n) infidelity rate for this construction.Source: §A.2 · p. 23

A.3. The Keyl formula.

  • For n identical copies, the Keyl outcome law is P(λ; ρ^⊗n) = m_λ · s_λ(p).Here m_λ is the dimension of the symmetric-group irreducible representation in block λ, and s_λ(p) is the Schur polynomial.Source: §A.3 · p. 23
  • The identical-copy outcome law follows from permutation invariance and Schur’s lemma applied blockwise to ρ^⊗n.The restriction to V_λ ⊗ M_λ has the form ς_λ ⊗ 1_Mλ, giving the factor m_λ.Source: §A.3 · p. 23
  • For non-identical product inputs, there is no analogue of the identical-copy Keyl formula because the input is not permutation-invariant.The appendix notes that Schur’s lemma therefore does not apply blockwise.Source: §A.3 · p. 24

Appendix B. Single-shot guarantees, confidence amplification, and concentration

This appendix turns the expected-error bounds into guarantees for individual runs and repeated runs, and examines outcome tails and variation in the outcome-distribution centre under random noise.

Appendix B. Single-shot guarantees, confidence amplification, and concentration

  • It covers single-run guarantees and confidence amplification, fixed-input outcome tails, and fluctuations of the outcome-distribution centre across random-noise realisations.The appendix states that these results follow from the same single-register bounds and are not needed for Definition 6.Source: Appendix B · p. 24

B.1. Single-shot guarantees and confidence amplification.

The expected-error bound yields a single-run guarantee for every admissible input, and independent repetitions amplify confidence. For general inputs, the bound uses the quantum Wasserstein distance in place of the product-noise error.

B.1. Single-shot guarantees and confidence amplification.

  • For general input ω, the expected-error bound is E⋆ = η(n, d) + (1/n)||ω − ρ^⊗n||_W1, and Markov’s inequality converts it to a confidence guarantee.The loss lies in [0, 1], and E⋆ is a worst-case bound over admissible inputs.Source: §B.1 · p. 24
  • A single run returns an estimate within 3ε + 3η(n, d) of the true spectrum with probability at least 2/3.More generally, the probability of error exceeding δ is at most E⋆/δ, where E⋆ bounds worst-case expected error.Source: §B.1 · p. 24
  • Independent runs on fresh batches, followed by a selection rule for vector estimates, amplify confidence using k = O(log(1/γ)) runs and nk = O(n log(1/γ)) copies.Each run is good with probability at least 2/3, and the majority-good event permits the selection guarantee.Source: §B.1 · p. 24
  • When δ > 9ε, the required copies per run retain collective d² scaling, while the confidence cost is logarithmic in 1/γ.The stated constants are not optimised.Source: §B.1 · p. 24

B.2. Tail bounds for a fixed input.

The section bounds deviations of weak Schur sampling outcomes for fixed inputs, using smoothed tail estimates and a variance bound. For product inputs, the outcome remains concentrated even without a closeness promise.

B.2. Tail bounds for a fixed input.

  • Smoothing the loss-threshold indicator over a window of width w reduces its one-box variation to at most 1/(nw), at the cost of blurring the threshold by w.The smoothed function bounds the event above δ + w from below and the event above δ from above.Source: §B.2 · p. 25
  • For an admissible product input, a fixed-input deviation bound has an additive ε/w term; for general input, ε is replaced by εW(ω).The bound applies for smoothing width w in (0, 1] and deviation threshold δ > 0.Source: §B.2 · pp. 24–25
  • For every product input, the weak Schur sampling outcome has variance O(1/n) per coordinate, including inputs with no closeness promise.The section notes that this matches the noiseless variance scaling.Source: §B.2 · p. 25
  • Under unbiased noise, the noiseless tail bound transfers exactly, and a Markov bound controls how often the realised-input conditional tail exceeds s.The stated conditional-tail bound is at most a e^(−2nδ²/s).Source: §B.2 · p. 26

B.3. Concentration of the conditional centre.

For randomly drawn admissible product noise, the conditional centre of the outcome distribution concentrates around its noise-average. Combined with concentration around that centre, this yields a single-run error scale that does not depend on ε.

B.3. Concentration of the conditional centre.

  • With high probability over the noise, the conditional centre is close to its noise-average, with fluctuations on the scale O(ε/√n).The centre is the mean outcome for the particular input realised by the noise.Source: §B.3 · p. 26
  • Combining centre fluctuation over noise with outcome fluctuation around the centre yields, with high probability over both randomness sources, a single-run outcome within O(d/√n) of the true spectrum in half ℓ1 distance, independent of ε.Source: §B.3 · p. 26
  • The extra 1/√n factor in centre fluctuations relies on averaging independent noise fluctuations; the deterministic worst-case centre can instead be ε away.The conditional centre's noise-average is the noiseless centre under unbiased noise.Source: §B.3 · p. 26
Loading 2610.03582v3…