Source-linked AI summary
Quantum state tomography via compressed sensing
David Gross, Yi-Kai Liu, Steven T. Flammia, Stephen Becker, Jens Eisert
TL;DR
The paper addresses costly classical post-processing in Pauli-based matrix recovery. It proposes hybrid sparse-representation and approximate k-design approaches, while showing incoherence and certified estimation results but not rigorous guarantees for the hybrid method.
Problem
Pauli-based matrix recovery has more costly classical post-processing because the matrices handled by singular value thresholding are dense.
Method
The paper combines carefully selected Pauli measurements with approximate k-design randomization to obtain sparse representations and sufficient incoherence for matrix-completion algorithms.
Results
Approximate k-design randomization generates sufficient incoherence for the original matrix-completion algorithms to work, and the almost-pure-state scheme produces a reconstructed state with a certified trace-distance bound.
Takeaways & Limitations
The approach can reduce the computational difficulty of Pauli-based recovery and provide certified estimates for almost-pure states.
Takeaways & Limitations
Rigorous guarantees for the hybrid approach are not established because the matrix-completion algorithms require uniform sampling, which the hybrid scheme does not satisfy.
Abstract
from arXiv · showhide
We establish methods for quantum state tomography based on compressed sensing. These methods are specialized for quantum states that are fairly pure, and they offer a significant performance improvement on large quantum systems. In particular, they are able to reconstruct an unknown density matrix of dimension d and rank r using O(rd log^2 d) measurement settings, compared to standard methods that require d^2 settings. Our methods have several features that make them amenable to experimental implementation: they require only simple Pauli measurements, use fast convex optimization, are stable against noise, and can be applied to states that are only approximately low-rank. The acquired data can be used to certify that the state is indeed close to pure, so no a priori assumptions are needed. We present both theoretical bounds and numerical simulations.
Details of the proof of Theorem 1
The appendix formalizes the proof of Theorem 1 by introducing trace-inner-product notation and modeling Pauli-observable selection as independent uniform sampling with replacement.
- The proof introduces the trace inner product for Hermitian operators ρ and σ.
- The observables w(A1), …, w(Am) are modeled as independent, identically distributed samples from the d^2 Pauli matrices.
- Sampling observables without replacement is described as plausibly and provably no worse than sampling with replacement.
Non-commutative large-deviation bound
The proof uses a non-commutative large-deviation inequality for sums of independent matrix-valued random variables and derives a Bernstein-type bound for bounded, zero-mean operator variables.
- A non-commutative large-deviation bound controls sums S = Σ_i X_i of independent matrix-valued random variables.
- For an operator-valued variable Y with ∥Y∥ ≤ 1 and E[Y] = 0, scalar exponential bounds yield a Bernstein-type inequality.
- Applying the bound with Y = λX uses λ = t/(2mσ^2), where σ^2 = ∥E[X^2]∥.
“Case (i)”: large-deviation bound
The first application of the derived concentration inequality verifies Eq. (2) by defining centered super-operator random variables and estimating their variance parameter.
- The proof first applies the Bernstein-type inequality to verify Eq. (2) from the main text.
- It defines Yi as a super-operator and applies the inequality to centered variables Xi = Yi − E[Yi].
- Operator convexity gives σ^2 ≤ ∥E[Y^2]∥, which is then bounded using Hölder’s inequality.
- Substituting this variance estimate into the concentration bound directly yields Eq. (10).
“Case (ii)”: the approximate subgradient
The second proof case establishes that a null measurement perturbation increases the trace norm by combining a subgradient argument with pinching and Hölder inequalities.
- The proof considers a matrix Y in span(w(A1), …, w(Am)) and analyzes the condition following Eq. (3).
- The target is to show that R∆ = 0 implies ∥ρ + ∆∥tr > ∥ρ∥tr.
- For Hermitian σ, sign σ is obtained by applying the scalar sign function to σ’s eigenvalues.
- The trace-norm lower bound separates contributions on the support projector E and its orthogonal complement 1 − E.
- The proof combines the pinching inequality, prior bounds, R∆ = 0, orthogonality, and Hölder’s inequality to complete the estimate.
“Case (ii)”: large deviation bound
The argument derives a deviation bound for an arbitrary matrix in the tangent space using an orthonormal operator basis and a moment-based estimate.
- The deviation bound applies to an arbitrary matrix F in the tangent space T.
- The operators {d^-1/2 w_a} form an orthonormal basis, supporting the norm calculation.
- The resulting probability of failure is then bounded in terms of the rank parameter r.
Details for Observation 1
These details rescale the measurement operator, impose feasibility under noise, and combine upper and lower bounds to control reconstruction error.
- The analysis assumes Paulis are sampled without replacement and considers reasonable regimes such as d ≥ 16, m ≥ 16, and r ≤ d/10.
- The measurement operator is normalized by setting Q = γR, with γ determined by the measurement count and dimension.
- The convex program constrains the rescaled residual through ∥Qσ − Qω∥2 ≤ γε.
- For any feasible estimate, the residual is decomposed into optimization, measurement-noise, and approximate-low-rank terms.
- A lower bound uses tangent and orthogonal components because the required simultaneous control cannot be obtained directly from Markov’s inequality.
- Combining the bounds shows that a trace-norm decrease forces the perturbation to be small, yielding the desired result.
Certified tomography for almost-pure states
For almost-pure states, the method estimates deviation from the leading eigenstate using random Pauli data and an experimentally specified precision, producing a certified error bound.
- O(d) Pauli expectation values suffice to estimate δ1 for rank-one states without assumptions.
- The certification procedure uses O(d log^2 d) random Pauli expectations together with an estimate of measurement precision δ2.
- The target quantity δ1 measures the distance between the true state and its largest-eigenvalue projector.
- Purity estimation uses random Pauli observables, a concentration bound, and a sample-size choice m = 4µd/t^2.
- Combining the purity estimate with the preceding relation yields a certified estimate for δ1.
A hybrid approach to matrix recovery
The hybrid approach groups Pauli measurements to obtain structured matrix samples, while pseudo-randomization addresses incoherence; rigorous guarantees remain limited for the hybrid scheme.
- Matrix recovery with Pauli measurements is more costly to post-process because singular-value thresholding handles non-sparse matrices Rρ.
- A random subset S of size O(r polylog(d)) selects Pauli strings indexed by u and v, producing structured measurements.
- The resulting Rρ has only |S|d nonzero matrix elements, so the hybrid method samples groups rather than independent entries.
- Certain states remain too coherent for the hybrid measurements, especially when eigenvectors nearly align with the standard basis.
- Pseudo-random unitary preprocessing is proposed to overcome these incoherence problems.
- Approximate k-design randomization yields sufficient incoherence for ordinary matrix-completion algorithms, but not a rigorous guarantee for the hybrid scheme.