PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast state tomography with optimal error bounds

Madalin Guta, Jonas Kahn, Richard Kueng, Joel A. Tropp

arXiv:1809.11162v1quant-phcs.ITmath.PR

TL;DR

Quantum tomography needs computationally simple estimators with rigorous finite-sample uncertainty guarantees. This paper develops projected least squares, deriving trace-distance confidence regions through matrix concentration, with competitive sampling complexity and lower-bound saturation for the uniform POVM.

  • Problem

    Quantum tomography lacks broadly available finite-sample error bars for point estimators, while alternative estimators can be computationally costly or have weak convergence guarantees.

  • Method

    PLS computes a least-squares or linear-inversion estimator, projects it onto the quantum-state space, and analyzes it using concentration inequalities for sums of random matrices.

  • Results

    PLS provides non-asymptotic trace-distance confidence regions with competitive sampling complexity; for the uniform POVM, its sampling rate saturates fundamental lower bounds.

  • Takeaways & Limitations

    PLS combines a numerically cheap estimator with rigorous confidence regions across structured POVMs, Pauli measurements, and the uniform POVM.

Abstract

from arXiv · show

Projected least squares (PLS) is an intuitive and numerically cheap technique for quantum state tomography. The method first computes the least-squares estimator (or a linear inversion estimator) and then projects the initial estimate onto the space of states. The main result of this paper equips this point estimator with a rigorous, non-asymptotic confidence region expressed in terms of the trace distance. The analysis holds for a variety of measurements, including 2-designs and Pauli measurements. The sample complexity of the estimator is comparable to the strongest convergence guarantees available in the literature and -- in the case of measuring the uniform POVM -- saturates fundamental lower bounds.The results are derived by reinterpreting the least-squares estimator as a sum of random matrices and applying a matrix-valued concentration inequality. The theory is supported by numerical simulations for mutually unbiased bases, Pauli observables, and Pauli basis measurements.

I. INTRODUCTION

Quantum state tomography needs estimators that reconstruct states while providing reliable finite-sample error information. PLS revisits linear inversion to offer non-asymptotic trace-distance guarantees with competitive sampling and low computational cost.

  • Maximum-likelihood estimation provides point estimates, but error bars are available only asymptotically for fully mixed states.
  • Bayesian and region estimators address uncertainty but can have comparatively high computational cost and weak or implicit convergence guarantees.
  • PLS equips linear inversion with easy-to-interpret, non-asymptotic error guarantees for reconstructing rank-r states in trace distance.The stated sampling rate is roughly r^2dϵ^-2 log d independent samples.
  • PLS has computational cost dominated by forming the least-squares estimator and is numerically cheap compared with prominent alternatives.Numerical simulations report faster performance than maximum-likelihood estimation and compressed sensing.

A. Background and estimator

The estimator converts measurement frequencies into a least-squares or linear-inversion estimate, then projects it onto the quantum-state space. This projection preserves a closed-form, computationally inexpensive procedure while correcting nonphysical estimates.

  • A tomographically complete measurement uses positive semidefinite Hermitian operators whose sum is the identity, with outcome probabilities given by Born's rule.For outcome i, the probability is [p]_i = tr(M_iρ).
  • Measurement frequencies are obtained by preparing n copies, measuring each separately, and counting each outcome.The frequencies converge to the true probabilities as n approaches infinity.
  • The least-squares estimator solves the linear equations obtained by replacing Born-rule probabilities with observed frequencies.This optimization implements linear inversion of the measurement equations.
  • Because linear inversion can have negative eigenvalues, PLS projects its estimate onto the convex set of all quantum states using the Frobenius norm.The resulting estimator is the quantum state closest to the linear-inversion estimate in that norm.
  • PLS has closed-form estimation and projection steps, with total cost dominated by forming the least-squares estimate.The method requires less storage and arithmetic than techniques based on more complicated optimization problems.

A. Error bounds and confidence regions for ˆρn

PLS provides trace-distance convergence guarantees and confidence regions across several measurement systems. Its bounds exploit low rank, achieve competitive sampling rates, and arise by concentrating the least-squares estimator as a sum of independent random matrices.

  • PLS provably converges to the true state in trace distance for structured POVMs, Pauli observables, Pauli basis measurements, and the uniform POVM.
  • The error bound depends on r = min{rank(ρ), rank(ˆρ_n)} and a measurement-dependent ambient-dimension factor g(d).For Pauli basis measurements, g(d) is approximately d^1.6.
  • A trace-norm ball around ˆρ_n, intersected with the state space, forms a δ-confidence region for the true state ρ.Its radius scales with rank(ˆρ_n), g(d), n^-1, and log(d/δ).
  • For structured POVMs and Pauli observables, the sampling rate is comparable to the best theoretical bounds for alternative tomography algorithms and is optimal up to one log(d) factor.
  • The number of samples scales quadratically in the rank rather than the ambient dimension, extending to states or estimates well approximated by rank-r matrices.This behavior is comparable with guarantees for compressed sensing methods designed to exploit low rank.
  • The proof views the least-squares estimator as a sum of independent random matrices and applies matrix concentration before converting the resulting norm bound to trace distance.Projection contracts the Frobenius norm, enabling the final trace-distance guarantee.

B. Optimal performance guarantee for the uniform POVM

For uniform POVM measurements, PLS removes the extraneous dimension factor in the general bound and exactly reproduces the best existing tomography guarantees. The proof uses covering nets, scalar concentration, and conversion from operator-norm to trace-norm error.

  • B. Optimal performance guarantee for the uniform POVM: The uniform POVM removes the dimension factor that may be extraneous in the general PLS error bound.The general factor arises from matrix-valued concentration inequalities.
  • B. Optimal performance guarantee for the uniform POVM: For uniform POVM measurements, Theorem 2 gives a convergence guarantee for the PLS estimator.
  • B. Optimal performance guarantee for the uniform POVM: The uniform-POVM result exactly reproduces the best existing performance guarantees for tomography from independent measurements.
  • B. Optimal performance guarantee for the uniform POVM: The proof replaces the unit sphere by an exponentially sized covering net and applies concentration inequalities to quadratic forms.For each net point, the relevant quantity is a sum of independent random variables with subexponential tails.
  • B. Optimal performance guarantee for the uniform POVM: Operator-norm closeness of the least-squares estimator is converted into trace-norm closeness of PLS with an additional effective-rank factor.

A. Explicit solutions for the least squares estimator (3)

The least-squares estimator has explicit formulas across structured POVMs, Pauli observables, and Pauli basis measurements. These formulas arise by inverting the corresponding measurement maps and are evaluated for the concrete systems studied.

  • A. Explicit solutions for the least squares estimator (3): Tomographically complete measurements are represented as injective linear maps, and their least-squares problem has a closed-form solution.
  • A. Explicit solutions for the least squares estimator (3): The paper evaluates the least-squares formula for the different measurement systems considered, while deferring detailed arguments to the appendix.
  • A. Explicit solutions for the least squares estimator (3): Structured rank-one POVMs include SIC-POVMs, maximal sets of mutually unbiased bases, stabilizer states, and the uniform POVM.These systems are also described as 2-designs.
  • A. Explicit solutions for the least squares estimator (3): For structured POVMs, the defining frame relation can be inverted to simplify the least-squares estimator.
  • A. Explicit solutions for the least squares estimator (3): For Pauli observables, the estimator uses approximated expectation values of the Pauli operator basis.Pauli matrices form a unitary operator basis, making the evaluation straightforward.
  • A. Explicit solutions for the least squares estimator (3): Pauli basis measurements use all 3^k combinations of local x, y, and z settings for d = 2^k.Each setting has 2^k possible outcomes.
  • A. Explicit solutions for the least squares estimator (3): The explicit solutions preserve unit trace, and the structured-measurement evaluation includes a single-qubit depolarizing-channel form.

B. Explicit solutions for the projection step (4)

The projection step maps the least-squares estimate to the nearest quantum state in Frobenius norm through an analytic eigenvalue-thresholding solution. A scalar is selected to enforce unit trace.

  • B. Explicit solutions for the projection step (4): PLS projects the least-squares estimator onto the quantum-state space by minimizing Frobenius distance.The optimization has a simple analytic solution.
  • B. Explicit solutions for the projection step (4): The scalar x0 is chosen so that the projected estimator has trace one, and unit trace of the input ensures uniqueness.

C. Runtime analysis

PLS is computationally lightweight: forming the least-squares estimate dominates a naive implementation, while projection requires an eigenvalue decomposition. Simulations compare PLS and ML trace-distance errors for Pauli basis measurements.

  • C. Runtime analysis: Linear-inversion estimators can be formed by counting frequencies using at most min {m, n} matrix additions.
  • C. Runtime analysis: Figure 1 compares PLS and ML trace-distance errors for 4-qubit Pauli basis measurements across ranks 1, 5, 10, and 16.It uses 100 datasets and 200 repetitions per setting, with an inset showing error versus sample size for a pure target state.
  • C. Runtime analysis: The projection step uses soft-thresholding, with computational cost dominated by the eigenvalue decomposition.
  • C. Runtime analysis: Forming the least-squares estimate is the dominant cost of a naive implementation, although randomized linear algebra may reduce it.

IV. NUMERICAL EXPERIMENTS

The experiments compare PLS with maximum likelihood and compressed sensing for quantum state tomography. PLS is competitive with ML for low-rank states and consistently outperforms CS while being faster to evaluate.

  • PLS incurs trace-norm error within a factor of two of maximum likelihood for low-rank states in Pauli basis measurements.The comparison is performed in dimension d = 24.
  • Compressed sensing reconstructs rank-r states from a random choice of m ≥ C r d log^6(d) Pauli observables via convex optimization.The cited numerical studies suggest m = 256 is appropriate for d = 2^5 and r = 1.
  • PLS consistently outperforms compressed sensing for 5-qubit Pauli observables and a pure target state.The comparison uses m = 256 observables for CS and m = 1024 for PLS as a function of total sample size.
  • PLS was much faster to evaluate than both maximum likelihood and compressed sensing.

V. CONCLUSION AND OUTLOOK

Projected least squares combines a computationally simple estimator with rigorous non-asymptotic trace-distance guarantees across several measurement settings. Its bounds are competitive, nearly optimal in key cases, and extend to approximately low-rank states, while tighter confidence regions remain an open direction.

  • Conclusion: PLS projects the least-squares estimator onto the set of quantum states after estimating outcome probabilities and constructing a linear-inversion estimator.The procedure has three steps: estimate frequencies, solve the least-squares problem, and project onto the quantum-state set.
  • Outlook: Corollary 1 is not yet optimal, motivating bootstrapping and other future work toward tighter confidence regions.The authors also indicate that PLS may be stable under time-dependent state-generation drift.
  • Results: For structured POVMs, Pauli observables, and Pauli basis measurements, PLS provides rigorous non-asymptotic trace-distance confidence regions with sampling rates competitive with existing guarantees.The analysis covers multiple practically relevant measurement systems and supports convergence to the true state in trace distance.
  • Conclusion: Matrix-valued concentration inequalities treat least-squares estimators as sums of independent random matrices, yielding operator- and trace-norm convergence guarantees.The analysis exploits randomness from quantum experiments and transfers operator-norm control to trace-norm control after projection.
  • Results: The general theorem allows a rank parameter to trade sampling rate against reconstruction error, benefiting states that are approximately low-rank.For a faulty preparation model, the resulting trace-norm error is bounded by ϵ + 2p with the corresponding sampling guarantee.
  • Results: For the uniform POVM, the analysis derives stronger convergence guarantees using its symmetry and removes an otherwise extraneous dimension factor.The uniform POVM includes all rank-one projectors, and its high symmetry enables a distinct proof technique.

X. IMPROVED CONVERGENCE GUARANTEES FOR THE UNIFORM POVM

The uniform POVM permits a proof technique that removes the extra log(d) factor from projected least-squares convergence guarantees. The analysis represents the estimator through random matrices, controls operator-norm deviations using covering nets and concentration, and yields rank-dependent trace-norm guarantees matching lower bounds.

  • Motivation: The additional log(d) factor arises from matrix-valued concentration inequalities based only on first and second moments.The paper identifies this factor as a limitation of the initial convergence analysis.
  • Improved convergence: For the uniform POVM, exploiting the complete moment characterization of the outcome distribution avoids the log(d) factor.The resulting argument applies strong high-dimensional probability techniques to this sufficiently symmetric measurement.
  • Proof strategy: A covering net replaces the operator-norm maximization over the complex unit sphere with finitely many scalar random variables.For each net point, the associated empirical average has dimension-independent sub-exponential tail behavior, enabling a union bound.
  • Guarantees: The resulting uniform-POVM bounds reproduce the best known sampling rates and match lower bounds for tomographic procedures in this setting.The proof uses concentration for the net-indexed averages and converts operator-norm control into trace-norm control with an effective-rank factor.
  • Estimator representation: The least-squares estimator is expressed as a sum of independent random matrices whose expectation equals the quantum state.For uniform POVM measurements, each matrix has the form (d + 1)|v⟩⟨v| − I under the outcome distribution induced by ρ.
Loading 1809.11162v1…