PaperlayerView exact revision on arXiv

Source-linked AI summary

Sample-optimal tomography of quantum states

Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, Nengkun Yu

arXiv:1508.01797v2quant-phcs.IT

TL;DR

The paper studies optimal strategies for learning an unknown quantum state from copies. It proposes POVMs and establishes near-optimal sample complexity, while showing that optimal performance cannot generally be achieved by independent measurements.

  • Problem

    The general quantum tomography problem asks how many copies are needed to determine an unknown mixed quantum state, including whether optimal measurements can be built from independent measurements.

  • Method

    The paper analyzes symmetry-constrained tomography POVMs and proposes a Pretty Good Measurement with a uniform spectrum distribution, alongside lower-bound arguments for general estimation strategies.

  • Results

    The lower bound implies that achieving infidelity δ requires n ≥˜Ω(dr/δ), matching the upper bounds for trace distance and fidelity up to logarithmic factors.

  • Takeaways & Limitations

    Joint measurements are sufficient up to logarithmic factors in the number of unknown parameters, whereas the optimal measurement cannot be a combination of independent measurements.

  • Takeaways & Limitations

    The performance of adaptive measurements and efficient quantum-computer implementation of the joint measurement remain open questions.

Abstract

from arXiv · show

It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. Previously, it was known only that estimating states to error $ε$ in trace distance required $O(dr^2/ε^2)$ copies for a $d$-dimensional density matrix of rank $r$. Here, we give a theoretical measurement scheme (POVM) that requires $O (dr/ δ) \ln (d/δ) $ copies of $ρ$ to error $δ$ in infidelity, and a matching lower bound up to logarithmic factors. This implies $O( (dr / ε^2) \ln (d/ε) )$ copies suffice to achieve error $ε$ in trace distance. We also prove that for independent (product) measurements, $Ω(dr^2/δ^2) / \ln(1/δ)$ copies are necessary in order to achieve error $δ$ in infidelity. For fixed $d$, our measurement can be implemented on a quantum computer in time polynomial in $n$.

I. ACCURACY MEASURES

The paper uses infidelity and trace distance as related accuracy measures for tomography, emphasizing that fidelity can yield sharper copy-complexity bounds. It situates the problem among collective, independent, and adaptive measurement strategies.

  • Accuracy measures: Infidelity 1 −F determines how quickly distinguishability of tensor-power states approaches one, with n = Θ(1/δ) copies for fixed d.The exact asymptotic rate is bounded between ln(1/F) and 2 ln(1/F).
  • Measurement models: The paper studies unrestricted collective measurements while leaving independent and adaptive measurement literature outside its main scope.Adaptive measurements are described as an intermediate model in which each basis can depend on earlier outcomes.
  • Prior results: Earlier work established n = O(dr^2/ϵ^2) sufficiency for independent measurements to achieve trace distance at most ϵ with high probability.The improved bound was obtained by analyzing a prior theorem more closely than its statement suggests.
  • Prior results: The paper improves prior results by estimating the full state with the same copies previously used only for its spectrum, and by proving lower bounds for all estimation strategies.The comparison is especially improved when r ≪d.

B. Two-stage measurement scheme using local asymptotic normality

The proposed two-stage adaptive scheme first localizes an unknown state and then applies local asymptotic normality to estimate it optimally in a neighborhood. Its sample complexity is limited by the cost of entering that neighborhood for high-dimensional states.

  • Two-stage scheme: The first stage uses n1 copies to obtain a confidence region inside a sufficiently small neighborhood of the unknown state.The first-stage measurement is assumed to be non-adaptive and independent across copies.
  • Two-stage scheme: The second stage applies local asymptotic normality to the remaining n2 = n −n1 copies for optimal estimation within that neighborhood.The analysis assumes the channel to Gaussian states is exactly faithful for every n.
  • Sample complexity: If the final accuracy target is no smaller than the first-stage confidence radius, the second stage is redundant and the scheme reduces to non-adaptive independent measurement.The paper concludes that this regime cannot be sample-optimal.
  • Sample complexity: When the final target is smaller than the confidence radius, the second stage requires n2 ≥Ω(d/ϵ_i^2) copies.This lower bound applies under the scheme’s stated two-stage conditions.
  • Limitation: The resulting dependence on d is worse than the independent non-adaptive scheme, although its dependence on ϵ is optimal.The scheme may therefore require too many samples before local asymptotic normality becomes useful for high-dimensional states.

III. REVIEW ON REPRESENTATION THEORY OF UNITARY AND SYMMETRIC GROUPS

This review develops the representation-theoretic framework used for tomography through Schur-Weyl duality, Young diagrams, tableaux, and Schur polynomials. It connects representation characters to eigenvalue structure and rank-sensitive bounds.

  • Schur-Weyl duality: Schur-Weyl duality decomposes n qudits into paired irreducible representations Qλ of GL(d) and Pλ of the symmetric group.The two group actions commute and are mutual commutants on the tensor-product Hilbert space.
  • Young diagrams and tableaux: Young diagrams label partitions λ of n, while standard and semi-standard Young tableaux provide bases and spanning sets for the representation Qλ.Qλ vanishes when λ has more than d rows; surviving tableaux satisfy a majorization condition.
  • Characters and Schur polynomials: For diagonal X, the character of Qλ depends only on X’s eigenvalues and equals a sum of monomials weighted by Kostka numbers.The associated Schur polynomial is homogeneous in d variables.
  • Rank-sensitive bounds: A rank-r density matrix constrains the character function sλ associated with its representation, providing a rank-sensitive ingredient for the tomography bounds.The relevant statement is given as Lemma 2 for d×d density matrices.
  • Characters and Schur polynomials: Majorization identifies which tableau weights contribute to the character and determines how the largest eigenvalues pair with the largest exponents.The proof uses non-negativity of relative entropy to control Schur-polynomial terms.

V. TOMOGRAPHY

The tomography POVM is constructed using permutation and unitary symmetries, with outcomes parameterized by a spectrum and a unitary rotation. Its outcome distribution is then bounded to establish estimation performance for rank-constrained states.

  • The optimal POVM can be chosen invariant under permutations of tensor factors and simultaneous unitary conjugation of the unknown state.The measurement acts on ρ^⊗n without assuming a prior distribution over ρ.
  • The POVM uses positive semidefinite operators indexed by a unitary U and a Young diagram λ partitioning n with at most d rows.The associated diagonal estimate has entries λ/n.
  • The operators M(λ,U)dU form a POVM under Haar probability measure on U(d).Unitary-conjugation and permutation invariance reduce verification to comparing traces.
  • For rank-at-most-r states, the relevant representation space satisfies dim Qλ ≤ (n + 1)^(dr) when λ has no more than r nonzero rows.This dimension bound is used in the probability-density analysis.
  • The POVM output is ρ̂ = U λ̄ U†, and its small-infidelity probability is obtained by integrating the outcome density over estimates with F(ρ,ρ̂) ≤ 1 − δ.The integration ranges over pairs (λ,U) producing estimates outside the target fidelity region.
  • For the qubit example, the output density is supported on circles of Bloch states, while the confidence region becomes small as n increases.The discrete spectrum choices produce circles that become finer with increasing n.

A. Pretty Good Measurement

The paper also constructs a pretty good measurement using an ensemble of tensor-power states over the full state space. A uniform spectrum distribution achieves the same tomography sample-complexity scaling up to constants.

  • The proposed POVM achieves the same tomography sample complexity up to constants.
  • The pretty good measurement uses operators Mi := φ̄^−1/2 piφi φ̄^−1/2 for an ensemble with average state φ̄ := Σi piφi.
  • For tomography, the ensemble states are σ^⊗n and the index ranges over the full state space according to a probability measure dσ.
  • A uniform distribution over the simplex of spectra of σ yields the same scaling in n up to constants as the earlier POVM for rank-at-most-r states.
  • The resulting PGM is defined through a Dirichlet normalization factor involving λ1! ··· λd!/(n + d − 1)!.
  • The POVMs are inspired by the PGM, whose measurement operator for estimate σ is a distorted version of σ^⊗n.Variants use distorted higher powers of the state, with k = 1 giving the PGM and k →∞ corresponding to the Keyl rotated-highest-weight strategy.

VI. LOWER BOUNDS

The paper proves lower bounds for estimating rank-constrained quantum states by converting accurate estimation into reliable communication over large packing nets. These bounds match the upper bounds up to logarithmic factors, while independent measurements require substantially more copies.

  • n ≥˜Ω(dr/δ) copies are necessary to achieve infidelity δ = 1 − F for rank-≤r states.
  • The lower bounds for trace distance and fidelity match the corresponding upper bounds up to logarithmic factors.
  • An independent measurement is a tensor product of n single-copy POVMs, one POVM for each copy.
  • The independent-measurement lower bound applies to measurements estimating every d-dimensional state of rank at most r.
  • The lower-bound proof constructs communication protocols from packing nets and applies Holevo’s theorem to bound the information conveyed by n copies.
  • Packing nets with large cardinality and small Holevo information provide the ensembles used in the lower-bound argument.

A. Probabilistic existence argument

The probabilistic existence argument constructs many separated states by repeatedly sampling Haar-random unitaries and bounding the probability that a new state lies near an existing one. Holevo-information estimates then control the communication capacity of the resulting ensemble.

  • ⌈1/ζ⌉ unitaries can be chosen so their corresponding states are pairwise more than ϵ apart in trace norm.
  • Haar left-invariance bounds the probability that a newly sampled state is ϵ-close to any previously selected state by ζm.
  • The construction begins with the singleton set {I} and inductively adds a unitary while the total collision probability remains below one.
  • For rank-r states, the argument uses unitaries embedded in U(d−r) and states that are maximally mixed on an r-dimensional subspace.
  • The Holevo-information calculation replaces the ensemble average by a symmetry-constrained average and bounds its entropy using binary entropy.

2. Packing nets II & III

Packing Nets II and III provide large families of pairwise-separated states in full-rank and rank-constrained settings. Their cardinalities and Holevo-information bounds supply the ensembles needed for the lower bounds.

  • Packing Nets II & III: exp(d^2/32) states exist when r = d/2, with pairwise trace distance greater than t/2 and Holevo information χ0 ≤ t^2.
  • Packing Nets II & III: exp((1−ϵ)rd/2) states exist for t = 1, with pairwise trace distance greater than 2ϵ and Holevo information χ0 ≤ ln(d/r).

C. Independent Measurement

The independent-measurement lower bound analyzes the classical outcome distributions produced by single-copy POVMs. The argument uses separated state ensembles and bounds their per-copy Holevo information to show that independent schemes cannot attain the collective-measurement scaling.

  • C. Independent Measurement: The infidelity packing construction yields exp(Ω(rd)) states that are δ = Ω(t)-separated in infidelity.
  • C. Independent Measurement: For the rank-d/2 ensemble, the Holevo information per copy is at most nt^2/d.
  • C. Independent Measurement: The analysis uses Haar-random rank-1 POVM projectors after decomposing general POVM elements into rank-1 components.
  • C. Independent Measurement: For the rank-constrained ensemble, the Holevo information is at most 4(nt^2/r) ln(2/t).

VII. IMPLEMENTATION ON A QUANTUM COMPUTER

The tomography strategy uses a continuously infinite-outcome POVM approximated by a finite POVM, with implementation based on the Schur transform and related isometries. The runtime is polynomial in n for fixed d, but the dependence on d remains unresolved and may be exponential.

  • Runtime and limitation: nO(dr) quantum-computer time is obtained for the tomography strategy described in this section.The paper conjectures that runtime polynomial in n, d, and ln(1/ϵ) may be possible, but does not establish it even for r = 1.
  • Measurement construction: The continuous-outcome POVM can be approximated by a finite POVM, beginning with measurement of λ.The λ measurement can be implemented efficiently using the Schur transform or the quantum Fourier transform over the symmetric group.
  • Measurement construction: m = ˜O(dim Qλ/ϵ2) random unitaries suffice for the finite measurement approximation.The resulting measurement is implemented through an isometry after applying the Schur transform.
  • Implementation cost: O((dim Qλ)2m2) gates implement the isometry used in the measurement.The passage identifies C as a normalizing constant in the isometry expression.

VIII. DISCUSSION

The paper nearly resolves quantum tomography sample complexity: joint measurements need only near the number of unknown parameters, while independent measurements cannot achieve this optimum. The discussion highlights adaptive measurements and efficient implementation as open problems.

  • Main conclusions: The sample complexity of general quantum tomography is nearly resolved up to logarithmic factors.The result confirms that joint measurements require roughly as many copies as the number of unknown parameters.
  • Main conclusions: Independent measurements cannot information-theoretically realize the optimal joint-measurement sample complexity.This establishes a separation between the power of independent and collective measurements in the paper’s setting.
  • Open problems: Whether adaptive measurements are asymptotically separated from collective measurements remains open.Adaptive measurements process one copy at a time while allowing later measurements to use histories from other copies.
  • Open problems: For fixed d, the joint measurement can be implemented in polynomial time in n, but its dependence on d is exponential.The paper leaves efficient quantum-computer implementation with favorable dependence on d as an open problem.
  • Related work: A concurrent result gives n = O(dr/ϵ2) copies for trace-distance accuracy ϵ, removing the logarithmic factor from this paper’s corollary.That result does not imply the paper’s fidelity bound, which the authors describe as incomparable.

Appendix A: Overlap of random projectors

The appendix develops a measure-theoretic description of low-rank density matrices and analyzes overlaps involving random projectors. It uses unitary invariance, permutation symmetry, Gaussian variables, and optimized probabilistic bounds.

  • Invariant measures: A U(d)-invariant measure on rank-p density matrices induces a permutation-symmetric measure on probability vectors of length p.The construction represents density matrices through eigenvalues and Haar-random eigenvectors.
  • Invariant measures: The eigenvalues and eigenvectors can be treated as independent random variables in the induced measure representation.Strictly, the construction finds separate measures whose map (η, U) ↦ UηU† reproduces the density-matrix measure.
  • Invariant measures: Sorted eigenvalues induce a measure on the set of sorted nonnegative p-vectors summing to one.The appendix then symmetrizes this measure across permutations by partitioning the simplex into p! pieces.
  • Random-projector analysis: Gaussian coordinates yield normalized random pure states whose reduced density matrices define U(d)-invariant measures on rank-at-most-p states.The direction variable is independent of the magnitude variable, and projector overlaps are expressed through squared norms.
  • Auxiliary results: Markov’s inequality supplies a basic probability bound used in the proof of Lemma 6.The appendix derives Pr[X ≥ a] ≤ EX/a for nonnegative X.
  • Random-projector analysis: The appendix optimizes auxiliary parameters ξ to establish the two-sided random-projector overlap bounds.The choices are ξ = pqz/(1 + z) for one direction and ξ = pqz/(1 − z) for the opposite direction.
Loading 1508.01797v2…