PaperlayerView exact revision on arXiv

Source-linked AI summary

Tight Lower Bounds for State Tomography with Limited Entanglement

Ufuk Keskin, Jason Luo, Mahbod Majid, Matthew Radzihovsky

arXiv:2609.05718v1quant-phcs.ITcs.LGmath.IT

TL;DR

State tomography asks how copy complexity changes when measurements may jointly act on only a bounded number of copies. The paper proves a matching lower bound for adaptive block measurements, using a perturbation prior and the transcript of classical outcomes. For every block size, the lower bound matches [PSW26]’s upper bound without a restriction relating block size to accuracy.

  • Problem

    The paper asks how tomography’s copy complexity interpolates between single-copy and unrestricted joint measurements when each block acts on at most k copies.

    Source: §1 · p. 3

  • Method

    The proof uses a perturbation prior and the protocol transcript to derive an information lower bound for adaptive block-measurement protocols.

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

  • Results

    For every k, the lower bound matches [PSW26]’s upper bound without requiring k to be small as a function of ε.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    The matching bounds determine the optimal copy complexity up to absolute constants across all k.

    Source: §1.1 · pp. 3, 5

    The theorem covers sufficiently small ε; extending the bound to larger constant ε would require a different prior.

    Source: §2.4 · p. 13

Abstract

from arXiv · show

We study state tomography when each measurement acts on at most $k$ fresh copies and no quantum memory is retained between blocks. We prove a lower bound matching the upper bound in [arXiv:2510.07788]. Thus the copy complexity of estimating an arbitrary $d$-dimensional state to trace distance $\epsilon$ is, up to absolute constant factors, $\max\{d^3/(\sqrt{k}\epsilon^2),d^2/\epsilon^2\}$ for every $k$ and all sufficiently small $\epsilon$. This removes the earlier restriction that $k$ be small as a function of the accuracy. The lower bound applies to arbitrary measurements within each block and adaptive choices between blocks. The lower bound already applies in a small neighborhood of any state whose smallest eigenvalue is of order $1/d$, even when the center is known. The main ingredient is a uniform Fisher information bound for one measurement block that depends only on the smallest eigenvalue of the state. The proof avoids the perturbative expansion responsible for the restriction in [arXiv:2402.16353]. Fano's inequality for metric balls and a log-Sobolev comparison between mutual and Fisher information then reduce the adaptive protocol to this block bound [arXiv:1607.00550, arXiv:1902.08582].

1 Introduction

State tomography’s copy complexity depends on how many copies can be measured jointly, motivating the intermediate model of adaptive blocks with classical information—but no quantum memory—between them. The paper proves a matching lower bound for every block size and establishes the resulting optimal complexity up to absolute constants.

1 Introduction

  • The unrestricted collective-measurement and single-copy endpoints have copy complexities of order d^2/ε^2 and d^3/ε^2, respectively.The intermediate model asks how complexity changes when each measurement acts on at most k copies.Source: §1 · p. 3

1.1 Our Results

  • For every k, the lower bound matches the upper bound of [PSW26], without requiring k to be small as a function of ε.The theorem allows arbitrary measurements within each block and adaptive choices based on earlier classical outcomes.Source: §1.1 · pp. 3–4, §1 · p. 3
  • The same lower bound holds locally around states with smallest eigenvalue of order 1/d, even when the protocol knows the center.The local result applies to states in a prescribed neighborhood of a center satisfying ρ⋆⪰I_d/(2d).Source: §1.1 · p. 4
  • The lower-bound conclusions remain valid when the protocol has a random total copy count bounded in worst-case expectation.The proof also yields a requirement expressed through block sizes, covering nonuniform and random block sizes.Source: §1.1 · p. 5
  • The upper-bound estimator may output a Hermitian, trace-one matrix with negative eigenvalues; projecting its final average to a closest state costs at most a factor of two in error.Running the estimator at target error ε/2 changes the copy bound only by an absolute constant.Source: §1.1 · p. 5
  • The new lower-bound result resolves the intermediate regime: the endpoints match known single-copy and unrestricted-measurement lower bounds, and the earlier k-to-accuracy restriction is removed.At k=1 the first term matches the single-copy bounds; for k⩾d^2 the second matches the unrestricted bound.Source: §1 · p. 3, §1.1 · p. 5

2 Technical Overview

The proof compares mutual-information bounds for a Gaussian perturbation prior, reducing the adaptive tomography lower bound to a Fisher-information bound for one measurement block. Centering the block analysis at its mean removes the accuracy-dependent restriction of earlier perturbative arguments.

2.1 The Main Theorem from Two Information Bounds

  • For a protocol with full classical transcript Y, successful tomography requires I(∆; Y) ≳ d², while the Fisher-information argument bounds transcript information by I(∆; Y) ≲ (ε²n/d) min{k, d²}; combining these estimates gives a copy lower bound.Source: §2.1 · p. 7
  • Replacing Id/d by a known ρ⋆ ⪰ Id/(2d) gives the same local lower bound for a sufficiently small neighborhood of ρ⋆.The perturbation law and its log-Sobolev and small-ball bounds remain unchanged.Source: §2.1 · p. 7

2.2 The Mutual Information Upper Bound from One Block

  • A log-Sobolev comparison and the Fisher-information chain rule reduce the adaptive transcript to the information from its measurement blocks.This chain rule allows random block sizes, adaptive measurements, and early stopping.Source: §2.2 · pp. 7–8

2.3 The Fisher Information in One Block

  • For ρ ⪰ Id/(4d), the block bound scales as d^2t^(3/2) when t ≤ d^2 and d^3t when t > d^2.The centered unfolded matrix cancels a term of order t^2 tr(ρ^2), avoiding the accuracy-dependent perturbative expansion used in [CLL24].Source: §2.3 · pp. 9, 11, 12

2.4 The Prior and the Mutual Information Lower Bound

  • The truncated Gaussian prior gives exponentially small mass to every trace-norm ball of radius 2ε, uniformly over its center, so metric-ball Fano requires order d^2 mutual information.Its support keeps the perturbed states spectrally bounded; the theorem’s ε ≤ ε0 condition comes from this prior, and larger constant ε would require a different prior.Source: §2.4 · pp. 12–13

3 Related Work

Prior work established the unrestricted and single-copy tomography rates and began characterizing intermediate block sizes. This paper removes the earlier accuracy-dependent block-size restriction using a uniform Fisher-information bound.

Unrestricted joint and single-copy tomography

  • The unrestricted collective-measurement rate is d^2/ε^2, whereas single-copy tomography has rate d^3/ε^2, with a matching lower bound established in.The unrestricted lower bound is due to, and O’Donnell and Wright [OW16] gave a matching procedure.Source: §3 · p. 13

Tomography with limited entanglement

  • The earlier limited-entanglement lower bound of [CLL24] required k ≤ (1/ε)^γ, while its proof expanded ρ^⊗k and its authors conjectured the restriction was an artifact.The present work instead uses a uniform block Fisher-information bound, a log-Sobolev comparison, and metric-ball Fano.Source: §3 · pp. 13–14
  • Together with the upper bound, the authors’ main lower bound determines copy complexity up to absolute constants for every k and all sufficiently small ε.Source: §3 · p. 14

Fisher information in state estimation

  • The block Fisher-information bound applies at every full-rank state in terms of its smallest eigenvalue, and yields an extra factor d/√k over the unrestricted rate when k ≤ d^2.Its proof extends a two-copy change of variables from [ZH18] and combines it with Schur–Weyl estimates from [CLL24].Source: §3 · p. 14

4 Preliminaries

Section 4 fixes notation and gathers the information-theoretic, Gaussian, and Schur–Weyl tools used in the proof. These tools support the blockwise Fisher information bounds, tomography lower bounds, and construction and analysis of the prior.

4.1 Matrix and State Geometry

  • The state parameter is represented in a Frobenius-orthonormal basis of traceless Hermitian matrices, a real space of dimension d^2−1.Gradients with respect to the state parameter use these coordinates.Source: §4.1 · p. 15

4.2 Measurements and Fisher Information

  • Adaptive protocols choose a POVM and block size from the classical history, use at most n copies, and have transcript Fisher information given by the sum of roundwise contributions.Finite POVMs can be reduced to rank-one effects for upper bounds on Fisher information.Source: §4.2 · pp. 16–18

Every POVM M on one copy satisfies

  • For any POVM on t copies of a full-rank state ρ, the directional Fisher information in a unit-Frobenius traceless Hermitian direction F is at most t/λ_min(ρ).This follows from the symmetric logarithmic derivative measurement inequality and tensor additivity.Source: Every POVM M on one copy satisfies · p. 19, §4.2 · p. 19

4.3 Schur–Weyl Duality and the Unfolded Matrix

  • The unfolded matrix G1(u) is the sum of a block vector’s one-copy reduced states and provides a representation of rank-one measurement outcome scores.The vectors associated with outcomes also form a pure-state ensemble decomposition of ρ⊗t.Source: §4.3 · pp. 19–20

The same vectors satisfy

  • Weak Schur sampling measures Schur-subspace projections, and its outcome probabilities depend only on the eigenvalues of the input state.The Schur subspaces arise from the commuting actions of the symmetric group and U(d) on the tensor copies.Source: The same vectors satisfy · p. 21
  • Schur–Weyl moment and unfolded-matrix estimates from [CLL24] support the centered-average bound for ensembles associated with arbitrary POVMs.The moment argument uses a shifted power-sum identity; when r = spec ρ, centering leaves a nonpositive term −t tr(ρ^2).Source: The same vectors satisfy · p. 22

4.4 Entropy, Mutual Information, and Testing

  • A log-Sobolev inequality bounds mutual information through Fisher information, while metric Fano converts estimation accuracy into a lower bound on mutual information [ALPC19, Theorem 1; XR17, Lemma 1].The log-Sobolev result is stated for finite outcomes without requiring regularity of a complete transcript; metric Fano uses natural logarithms.Source: §4.4 · pp. 22–23
  • For dimensions not covered by the Gaussian-prior argument, unrestricted joint-measurement lower bounds still apply, including to adaptive protocols [HHJ+17].Every adaptive protocol induces a POVM on all copies, and the stated lower bound holds even when one joint POVM acts on all n copies.Source: §4.4 · pp. 23–24

4.5 Gaussian Concentration and Log-Sobolev Inequalities

  • Gaussian norm and concentration inequalities, a net bound for traceless-Hermitian Gaussian operator norms, and Anderson’s inequality supply estimates for constructing and analyzing the prior.The operator-norm argument uses a 1/4-net and a union bound.Source: §4.5 · p. 24
  • Caffarelli’s contraction theorem transfers the Gaussian log-Sobolev inequality to a Gaussian conditioned on a closed convex set [Caf00, FGP20; Gro75].The conditioned measure satisfies the stated log-Sobolev inequality for positive smooth functions.Source: §4.5 · p. 25

5 Proof of the Main Lower Bound

The proof establishes a copy lower bound for all dimensions and block sizes at sufficiently small accuracy, then extends the local lower bound to the remaining finite dimensions. It also reduces protocols with a random copy count to bounded-copy protocols.

5 Proof of the Main Lower Bound

  • Theorem 1.3 gives a copy lower bound for every d ≥ 2 and k ≥ 1 at sufficiently small ε, including adaptive protocols.The theorem applies to protocols using at most n copies; the supplied passages do not include the bound’s formula.Source: §5 · p. 25
  • For the local lower bound, translating the Gaussian prior to ρ⋆ proves the result in sufficiently large dimensions, while a two-state test handles the remaining dimensions.The translated prior stays within the prescribed neighborhood and satisfies the mutual-information bound’s hypothesis.Source: §5 · pp. 26–27
  • In the finite-dimensional local case, disjoint trace-distance balls turn successful estimation into a test between two states, yielding n ≥ 1/(1152ε²).The proof bounds the transcript divergence using the eigenvalue distributions of the commuting states, then applies Pinsker’s inequality.Source: §5 · p. 27
  • Truncating a protocol’s copy use produces one using at most 6n copies that still succeeds with probability at least 1/2 on every state.The proof then applies the large-dimension information bounds and, for fixed dimensions, an unrestricted-measurement lower bound.Source: §5 · p. 28
  • For the finite-dimensional local case, truncation at 12n preserves success probability at least 7/12 and yields n ≳ 1/ε².Because only finitely many dimensions remain, this implies the local rate stated in the proof.Source: §5 · p. 28

6 The Prior and the Mutual Information Lower Bound

The proof constructs a truncated Gaussian prior over perturbations of a fixed reference state and establishes properties that support a mutual-information lower bound. Its small-ball control and log-Sobolev inequality combine with metric Fano to make successful tomography require substantial information.

6 The Prior and the Mutual Information Lower Bound

  • The prior samples perturbations Δ around a fixed reference state ρ⋆, using a Gaussian conditioned on a set K.For the main theorem, the reference state is Id/d.Source: §6.1 · pp. 28–29
  • The Gaussian norm estimates establish concentration properties used to show that the conditioning set retains substantial prior mass.The proof combines operator- and Frobenius-norm estimates with a trace-norm lower-tail bound.Source: §6.1 · pp. 29–31
  • The conditioning set keeps the perturbations spectrally controlled so that Id/d + Δ remains a state, with the conditioning event having probability at least 9/10.The proof also establishes the corresponding spectral condition for the supported states.Source: §6.1 · p. 30
  • A log-Sobolev inequality for the conditioned prior and a bound on its trace-norm small-ball masses provide the ingredients for the mutual-information comparison.The proof invokes metric-ball Fano after showing log(1/β) ≳ d² for the prior’s largest trace-norm ball mass β.Source: §6.1 · pp. 29–30

7 Adaptive Protocols and Mutual Information

For adaptive protocols, the paper derives a transcript information bound from the Fisher-information bound for each measurement block. A chain rule and log-Sobolev comparison make the argument apply despite the changing conditional law after each outcome.

7 Adaptive Protocols and Mutual Information

  • Fisher information is used because its chain rule applies at each fixed state, whereas conditioning on outcomes changes the law of Δ.A log-Sobolev comparison and Fisher-information data processing then connect transcript mutual information to the block contributions.Source: §7 · pp. 31–32
  • The adaptive-protocol information bound assumes ρ ⪰ Id/(4d) and a transcript from a protocol using at most n copies almost surely.The proof obtains the Fisher-information bound by applying the adaptive chain rule to the block bound.Source: §7 · pp. 31–32

8 Fisher Information of a Block Measurement

The section establishes a Fisher information bound for measurements on a block of copies, with a first bound that improves the standard estimate in the relevant small-block regime. Its proof centers an average matrix quantity and extends the result to arbitrary measurable outcome spaces.

8 Fisher Information of a Block Measurement

  • Theorem 8.1 treats every POVM on t copies of a full-rank state, for d ≥ 2 and t ≥ 1.Source: §8 · p. 32
  • Centering G1(u_z) at its mean tρ cancels the positive t^2 tr(ρ^2) contribution against the Schur–Weyl moment term, leaving −t tr(ρ^2) ≤ 0.This yields the centered average bound used in the proof.Source: §8 · pp. 32–34
  • For finite POVMs, the proof reduces to rank-one effects, applies the score formula and norm identities, then averages using Lemma 8.2.Splitting effects into rank-one operators can only increase Fisher information.Source: §8 · p. 33
  • Under Eq. (59), the two terms are bounded by constant multiples of d^2t^3/2 and d^3t; when λmin(ρ) is of order 1/d, the first improves the standard estimate for t ≤ d^2.The first bound holds for arbitrary t and ρ and supplies the block-size dependence needed for the main lower bound.Source: §8 · pp. 32–33
  • For arbitrary measurable outcome spaces, finite-range coarsenings inherit the bound, and taking their supremum proves the same bound for the original POVM.Source: §8 · p. 33
Loading 2609.05718v1…