Source-linked AI summary
Refined sample complexities from the tomographic rate function
Arick Grootveld, Alexander Maloney, Jason Pollack, Peixue Wu
TL;DR
Trace-distance sample complexity can assign several tomography protocols the same scaling, leaving their different probabilities of large estimation errors less clearly distinguished. This paper analyzes covariant protocols through rate functions expressed using a common family of quantum divergences. The rate functions can be strictly ordered, and two protocols optimal in trace distance are separated under a Wasserstein-type sample complexity.
Problem
Protocols with the same trace-distance sample-complexity scaling can have different probabilities of producing the same incorrect estimate, motivating measures that distinguish their performance.
Source: §1 · p. 3Method
The paper derives rate functions for covariant tomography protocols using a common two-parameter family of quantum divergences and applies quantum Marton’s inequality to compare divergence with Wasserstein distance.
Source: §1 · pp. 3–4Results
For some states the protocol rate-function inequalities are strict, and two protocols optimal in trace distance are separated in Wasserstein-type sample complexity.
Source: §1 · pp. 3–4Takeaways & Limitations
Rate functions distinguish protocols whose trace-distance sample complexities share the same scaling, while the Wasserstein-type comparison yields a sample-complexity separation.
Source: §1 · p. 3The modified Haah protocol may not have the same rate function as the analyzed Haah protocol, and its exact rate function is left for future work.
Source: §4.2 · p. 18
Abstract
from arXiv · showhide
Protocols for quantum state tomography can be characterized either by their sample complexity or by the tomographic rate function that governs the large deviation behaviour of error estimates. We establish a framework for the analysis of covariant protocols which allows us to compare these measures. First, we derive the rate functions for several protocols, including random purification-based protocols and the sample-optimal protocol of Haah et al. These rate functions are expressed in terms of a new family of divergences which includes the reverse sandwiched R\'enyi divergence and Keyl's annealed quantum relative entropy as special cases. We show that these rate functions obey a strict ordering, even though the sample complexity of each protocol is order optimal. We consider a different version of sample complexity based on Wasserstein distance rather than trace distance, and show that the ordering of the rate functions implies analogous strict inequalities for the Wasserstein-type sample complexity. Thus the tomographic rate function is a more fine-grained indicator of the performance of a tomography protocol than the usual sample complexity.
1 Introduction
Trace-distance sample complexity can give several protocols the same scaling, while tomographic rate functions distinguish how likely large estimation errors are. The paper compares covariant protocols through rate functions and shows strict rate-function and Wasserstein-type sample-complexity separations.
1 Introduction
- Several protocols identified as optimal or near-optimal in trace-distance sample complexity share the same scaling, despite differing error distributions and probabilities for the same incorrect estimate.This motivates asking whether other measures can distinguish their performance.Source: §1 · p. 3
- Rate functions describe how rapidly the probability of an estimate differing from the true state decays with sample count and capture rare, substantial deviations.Unlike sample-complexity bounds, the rate function is independent of the distance used to measure estimation error.Source: §1 · p. 3
- The paper gives a unified rate-function analysis of Keyl’s protocol, Haah et al.’s sample-optimal protocol, and PGM protocols, including random purification.The analysis focuses on covariant protocols, whose probability distributions are invariant under simultaneous unitary rotation of their arguments.Source: §1 · p. 3
- Power-weighted generalizations of the Haah and PGM protocols have rate functions described by a common two-parameter family of quantum divergences.Keyl’s protocol has the reverse relative entropy as its rate function.Source: §1 · p. 3
- For some states, rate-function inequalities are strict even though the compared protocols have optimal sample complexity; Keyl’s rate function is optimal among covariant protocols.The rate functions are bounded above by the relative entropy.Source: §1 · pp. 3–4
- Two protocols optimal in trace distance are separated in sample complexity under a Wasserstein-type distance at the maximally mixed state, independently of the specified qubit factorization.The analysis uses quantum Marton’s inequality for product states to compare divergence and Wasserstein distance.Source: §1 · p. 4
1.1 Related Work
- Prior large-deviation work studied pure-state estimation, Keyl’s mixed-state protocol, and other estimators; later work established Keyl’s optimal rate among covariant protocols.Related constructions include Haah’s Schur-block protocol and tomography based on pretty-good measurements.Source: §1.1 · pp. 4–5
- Prior sample-complexity research established trace-distance bounds and examined rank-dependent and Bures-related estimation criteria.The cited work includes rank-dependent bounds and Bures-χ2 upper bounds, later improved by removing logarithmic factors.Source: §1.1 · p. 5
2 Preliminaries
The preliminaries introduce the divergence family used to express tomography rate functions and the Schur–Weyl representation structure underlying the analysis.
2 Preliminaries
- The notation sets d as the dimension of the underlying Hilbert space and D_d as its quantum-state space.The preliminaries also denote the unitary group on C^d by U(d).Source: §2 · p. 5
2.1 Divergences
- The new two-parameter Iβ,γ divergence vanishes exactly when σ=ρ and has limits that connect it to the reverse relative entropy.For fixed β, it increases with γ toward Iβ,∞; Iβ,∞ increases toward D_R as β grows.Source: §2.1 · pp. 7–8
2.2 Schur–Weyl duality
- Schur–Weyl duality decomposes the n-fold tensor space into components indexed by Young diagrams, and the Schur transform implements this decomposition.Each diagram has n boxes and at most d rows.Source: §2.2 · p. 8
3 Quantum state tomography
This section defines covariant tomography and distance-dependent sample complexity, then develops the large-deviation framework for estimator errors. Its main theorem derives covariant-protocol rates by combining spectral and within-block behavior.
3 Quantum state tomography
- A covariant protocol transforms its estimate distribution consistently under unitary changes to the true state, making it basis-agnostic.The section also gives a Schur-basis normal form for these protocols.Source: §3 · p. 10
3.1 Sample complexity
- Distance-dependent sample complexity is the smallest sample count at which the probability of error at least ε is no more than δ.The chosen distance measure is part of the definition.Source: §3.1 · p. 11
3.2 Large deviation theory
- A large-deviation principle characterizes asymptotic probabilities through a rate function, and the contraction principle carries that rate through continuous maps.The paper uses this framework to pass from joint outcomes to the reconstructed estimator.Source: §3.2 · p. 12
3.3 Large deviation principle for covariant tomography protocols
- Theorem 3.8 derives a large-deviation principle for covariant tomography by combining weak-Schur spectral behavior with conditional large deviations inside Schur blocks.The resulting principle gives rate functions for both the joint outcomes and the state estimator.Source: §3.3 · pp. 13–14
4 Rate functions for general seed-induced tomography protocols
The section analyzes seed-induced tomography through large-deviation rates, then specializes the framework to Keyl’s and Haah’s protocols. It derives rates for both and notes that the modified Haah protocol may not share the original protocol’s rate.
4 Rate functions for general seed-induced tomography protocols
- Seed-induced tomography first estimates a spectrum from the normalized Young diagram, then uses a seed operator to detect the eigenspace.The estimator is formed from the measured diagram and unitary outcome.Source: §4 · p. 15
4.1 Keyl’s Protocol
- Keyl’s protocol is a seed-induced scheme whose rate function is the reverse relative entropy.The paper gives an alternative proof using the general seed-induced result.Source: §4.1 · pp. 16–17
4.2 Haah’s Protocol
- The section derives a rate function for the β-weighted Haah protocol, while the modified Haah protocol may have a different rate function.The exact rate for the modified protocol is left for future work.Source: §4.2 · pp. 18–19
5 Rate functions for pretty good measurements
The section derives rate functions for pretty-good-measurement tomography, including a power-weighted generalization and a weak-Schur-sampling Hilbert–Schmidt variant. These rates are expressed using the family Iβ,γ, with the weak-Schur variant's rate given by Iβ,β.
5 Rate functions for pretty good measurements
- PGM tomography extends state discrimination to a prior measure over states, and power-weighted measurements generalize the standard PGM protocol.The paper notes that the standard PGM strategy yields a sample-optimal trace-distance tomography scheme.Source: §5 · p. 20
- The power-weighted PGM with uniform spectral prior has a rate function given by the paper's PGM theorem.The section also considers general full-support priors and identifies special cases including the uniform spectral prior and rank-d Hilbert–Schmidt measure.Source: §5 · pp. 21–22
5.1 Weak-Schur sampling Hilbert Schmidt PGM
- The weak-Schur-sampling Hilbert–Schmidt PGM first measures a Schur block and then applies a Hilbert–Schmidt PGM within that block.The block label λ is measured using projectors, and the within-block measurement uses rank m = ℓ(λ).Source: §5.1 · p. 22
- For r = rank(ρ), the bound is (1/n) log Pn,ρ[F] ≤ −inf over σ ∈ F ∩ Dd,r of Iβ,β(σ∥ρ), restricting the infimum to Dd,r.Source: §5.1 · p. 26
6 Separation of sample complexity under Wasserstein-type distance
This section compares Keyl's protocol with the raw Hilbert–Schmidt PGM using normalized quantum Wasserstein distance at the maximally mixed state. The separation proof combines an upper bound for Keyl's failure probability with a lower bound for the PGM under stated parameter conditions.
6 Separation of sample complexity under Wasserstein-type distance
- The separation proof upper-bounds Keyl's Wasserstein failure probability using quantum Marton inequality and lower-bounds the PGM failure probability using random purification.The two bounds are compared at a common confidence level.Source: §6 · pp. 27, 29, 30
- For ζ = (1 − 4ε)τ + 4ε|0^m⟩⟨0^m|, the section derives W1(ζ, τ) = 2mε.Both states are diagonal, so their quantum W1 distance reduces to classical Wasserstein distance on bit strings with the Hamming metric.Source: §6 · p. 28
- The PGM lower bound uses a cap of purifications with overlap at least 1 − ε², whose measure under the uniform pure-state measure is ε²(d² − 1).The cap's reduced states are used to bound the PGM probability of a Wasserstein error at least ε.Source: §6 · p. 29
- Theorem 6.3 states a sample-complexity separation for m-qubit states at τ=Id/d, comparing Keyl’s protocol and raw Hilbert–Schmidt PGM for normalized quantum Wasserstein distance, with 0<ε≤1/16 and 0<δ<1.Source: §6 · pp. 27, 29
7.1 Statement on the use of Artificial Intelligence
The authors disclose AI assistance in proofreading, literature surveys, derivations, argument refinement, and early code generation. They state that they take full responsibility for the manuscript's presentation and mathematical statements.
7.1 Statement on the use of Artificial Intelligence
- The authors say the paper's main ideas were formulated without substantial AI assistance.They identify ChatGPT 6 (Astra) as assisting with proofreading, literature surveys, Appendix B derivations, and refinement of arguments in Sections 4 and 5.Source: §7.1 · p. 30
- ChatGPT 4o and 5.6 Sol were used in early manuscript versions to generate code for Figures 1 and 2, explore concepts, conduct literature surveys, and proofread.Source: §7.1 · p. 30
- The authors take full responsibility for the manuscript's presentation and mathematical statements.Source: §7.1 · p. 30
A Schur-polynomial bounds
This appendix section introduces Schur-polynomial bounds and connects their large-n behavior to the Harish-Chandra–Itzykson–Zuber integral. It uses that connection to obtain an upper bound.
A Schur-polynomial bounds
- A Schur polynomial of a Hermitian operator is a polynomial in its eigenvalues.The section specifies the operator's eigenvalues in decreasing order and considers partitions λ of n.Source: A Schur-polynomial bounds · p. 30
- The upper-bound argument leverages a connection between Schur polynomials and the HCIZ integral.The integral is defined using Hermitian operators A and B and Haar integration over unitaries; its name is attributed to Harish Chandra and Itzykson and Zuber.Source: A Schur-polynomial bounds · p. 31
- The section identifies saddle-point or stationary-phase approximation of the HCIZ integral as a way to derive large-n Schur-polynomial behavior and the rate function.Source: A Schur-polynomial bounds · p. 31
B Properties of Iβ,γ
The section establishes monotonicity properties of Iβ,γ and shows that it is nonnegative, vanishing exactly when σ = ρ. It also connects the limit as γ increases to D_R.
B Properties of Iβ,γ
- Iβ,γ is non-decreasing in β for β ∈ (0, γ] and monotonically increasing in γ.The β argument uses weak majorization of eigenvalue expressions and an increasing convex function; γ monotonicity follows from monotonicity of D_r.Source: B Properties of Iβ,γ · pp. 32–33
- Iβ,γ(σ∥ρ) is nonnegative and equals zero exactly when σ = ρ.The section derives the equality condition using Hölder’s inequality and an equality condition for the associated norm relation.Source: B Properties of Iβ,γ · p. 33
- As γ tends to infinity, Iβ,γ tends to D_R.The section attributes this limit to monotonicity in β and γ and cited theorems on the divergence.Source: B Properties of Iβ,γ · p. 33
C Figure Details
Example C.1 begins with details concerning Figures 1 and 2.
C Figure Details
- Example C.1 begins by introducing details used for Figures 1 and 2.The passage does not specify the details.Source: C Figure Details · p. 33