PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators

Steven T. Flammia, David Gross, Yi-Kai Liu, Jens Eisert

arXiv:1205.2300v2quant-ph

TL;DR

Quantum tomography is exponentially resource intensive, motivating methods that exploit low-rank structure without knowing the supporting subspace. The paper uses random Pauli measurements, RIP-based analysis, and trace-norm estimators to obtain near-optimal guarantees and practical reconstructions. Compressed tomography achieves lower-rank sample savings, higher simulated fidelity than MLE, faster processing with incomplete measurements, certifiable estimates, and an extension to low-Kraus-rank processes.

  • Problem

    Quantum tomography requires exponentially many resources in system size, while practical methods must reconstruct unknown low-rank states from incomplete measurements and noisy data.

  • Method

    The paper combines random Pauli measurements, RIP-based low-rank recovery, trace-norm estimators, direct fidelity estimation, and a compressed process-tomography construction.

  • Results

    Compressed tomography requires O(r2d2 log d) copies for constant trace-norm accuracy, has an almost-matching Ω(r2d2/ log d) lower bound, and outperforms MLE in simulated fidelity.

  • Takeaways & Limitations

    Incomplete measurements can preserve reconstruction accuracy while reducing classical data size, and low-rank estimates can be certified regardless of the true state's rank.

  • Takeaways & Limitations

    The gap between the sample-complexity upper and lower bounds remains an open theoretical problem.

Abstract

from arXiv · show

Intuitively, if a density operator has small rank, then it should be easier to estimate from experimental data, since in this case only a few eigenvectors need to be learned. We prove two complementary results that confirm this intuition. First, we show that a low-rank density matrix can be estimated using fewer copies of the state, i.e., the sample complexity of tomography decreases with the rank. Second, we show that unknown low-rank states can be reconstructed from an incomplete set of measurements, using techniques from compressed sensing and matrix completion. These techniques use simple Pauli measurements, and their output can be certified without making any assumptions about the unknown state. We give a new theoretical analysis of compressed tomography, based on the restricted isometry property (RIP) for low-rank matrices. Using these tools, we obtain near-optimal error bounds, for the realistic situation where the data contains noise due to finite statistics, and the density matrix is full-rank with decaying eigenvalues. We also obtain upper-bounds on the sample complexity of compressed tomography, and almost-matching lower bounds on the sample complexity of any procedure using adaptive sequences of Pauli measurements. Using numerical simulations, we compare the performance of two compressed sensing estimators with standard maximum-likelihood estimation (MLE). We find that, given comparable experimental resources, the compressed sensing estimators consistently produce higher-fidelity state reconstructions than MLE. In addition, the use of an incomplete set of measurements leads to faster classical processing with no loss of accuracy. Finally, we show how to certify the accuracy of a low rank estimate using direct fidelity estimation and we describe a method for compressed quantum process tomography that works for processes with small Kraus rank.

I. INTRODUCTION

Compressed tomography exploits low-rank structure to reduce measurements and samples while remaining robust to noise and full-rank tails. The paper develops RIP-based guarantees, near-matching sample-complexity bounds, empirical gains over MLE, certification, and process-tomography extensions.

  • Tomography is resource intensive because an n-qubit system has dimension d = 2n and a density matrix with d2 = 4n entries.
  • Low-rank states can be reconstructed from m = O(rd log d) randomly selected Pauli observables, followed by efficient convex optimization.The approach remains robust when measurements are imprecise or the state is only close to low rank.
  • RIP-based analysis bounds full-rank reconstruction error by a quantity close to the best rank-r approximation, represented by the eigenvalue-spectrum tail.Random Pauli measurements are simultaneously sensitive to all low-rank errors.
  • O(r2d2 log d) copies suffice for constant trace-norm accuracy on rank-r states, while adaptive Pauli tomography requires at least Ω(r2d2/ log d) copies.Thus the compressed-tomography upper bound is nearly tight among procedures using Pauli measurements.
  • Direct fidelity estimation can certify a low-rank estimate even when the true state is not approximately low rank, and the method extends to processes with small Kraus rank.The process-tomography procedure requires Pauli eigenstate preparation and Pauli measurements, without entangling gates or ancillas.
  • In simulations, compressed estimators achieved higher fidelity than MLE, while using m ≪d2 measurements reduced classical data processing from O(d2) to O(m).The matrix Lasso gave the best results, and reconstruction accuracy was fairly insensitive to the number of measurement settings when total experimental time was fixed.

B. Notation and Outline

The paper defines its Pauli-measurement setting, sampling procedure, noisy data model, and convex trace-norm estimators. It then organizes the analysis around error bounds, sample complexity, certification, numerics, and process tomography.

  • Outline: The paper proceeds from estimator definitions and error bounds to sample-complexity upper and lower bounds, certification, numerical investigations, quantum channels, and conclusion.
  • Notation: For n qubits, d = 2n, and the Pauli operators are tensor products of I, σx, σy, and σz.
  • Measurement procedure: The scheme samples m Pauli operators uniformly at random and estimates each expectation value using t/m copies of the unknown state.The resulting data contain statistical noise from the finite number of samples or an adversary.
  • Measurement model: The sampling operator A is normalized so that EA∗A = I, and the measurement output is represented as a noisy vector.
  • Estimators: Both estimators fit the data while minimizing the trace norm, a convex surrogate for rank minimization.The matrix Dantzig selector uses constrained trace minimization, while the matrix Lasso uses least squares with trace-norm regularization.
  • Estimator constraints: The regularization parameters λ and µ are chosen according to the noise level, and positivity can be added without altering the conclusions.

C. Error Bounds

The paper uses RIP for random Pauli measurements to derive strong low-rank recovery error bounds and quantify compressed-tomography sample complexity under finite-statistics noise.

  • RIP-based error bounds: RIP holds for random Pauli sampling when m ≥ Crd log^6 d, enabling strong error bounds for matrix Dantzig selectors and Lasso estimators.This requires a polylogarithmic factor more measurements than earlier dual-certificate results.
  • RIP-based error bounds: For full-rank states, the reconstruction error is governed by statistical noise and the rank-r approximation residual, which is optimal up to a constant factor.The residual is the tail after retaining the largest r eigenvalues and eigenvectors.
  • Sample complexity: O(r^2d^2 log d) copies suffice for constant trace-norm accuracy on rank-r states, while r = d recovers the full-tomography scaling.For target trace-distance accuracy ε, the stated comparison gives O(d^4/ε^2) copies for full tomography.
  • Finite-statistics noise: The analysis converts finite-copy Pauli expectation estimates into a high-probability bound on the measurement-data deviation used by the convex estimators.Matrix Bernstein bounds control the deviation, after which the RIP recovery theorem yields the state-estimation error.

III. LOWER BOUNDS

The lower-bound analysis shows that adaptive single-copy Pauli protocols require nearly the same sample scaling as compressed tomography to estimate generic rank-r states accurately.

  • Lower-bound strategy: The paper proves nearly tight lower bounds for generic rank-r quantum states using adaptive sequences of single-copy Pauli measurements.This extends earlier single-copy lower bounds beyond pure states.
  • Lower-bound strategy: The construction uses many mutually separated states whose Pauli statistics are nearly indistinguishable, making them difficult to identify from limited copies.A randomized argument produces exponentially many such states, and information-theoretic inequalities convert this packing into a copy lower bound.
  • Lower-bound strategy: The minimax framework measures the worst-case probability that an estimator deviates from the unknown state by more than a target error ε.The protocol may adapt each binary measurement to previous outcomes.
  • Scope: The lower-bound argument remains applicable when adaptively selecting from as many as 2^O(n) additional measurements globally unitarily equivalent to Pauli measurements.This extends the stated measurement-setting scope beyond a fixed Pauli set.

IV. CERTIFYING THE STATE ESTIMATE

The paper adapts direct fidelity estimation to certify the fidelity of a low-rank state estimate without assumptions on the unknown state.

  • Certification setup: The certification procedure applies to any positive semidefinite estimate ρ̂ with trace at most one and rank r, regardless of how that estimate was obtained.It therefore also covers estimates selected from variational ansatz families.
  • Direct fidelity estimation: Direct fidelity estimation samples Pauli expectation values according to a distribution determined by known eigenstates or a known pure reference state.A small number of samples from the distribution can estimate the relevant overlap.
  • Direct fidelity estimation: The method estimates matrix elements of the unknown state in the eigenbasis of the low-rank estimate and combines them to infer mixed-state fidelity.For each pair of eigenstates, the matrix element is estimated within a bounded additive error.
  • Certification cost: The fidelity-certification sample cost is asymptotically far smaller than obtaining the original estimate when r is sufficiently small compared with d.The theorem uses single-copy Pauli measurements and provides a probability guarantee for estimating fidelity within ±ε.
  • Certification limitations: The protocol’s error scaling is tight in ε0, although the analysis may admit an improvement by a factor of r and other protocols might do better.This is the paper’s stated limitation of the current certification bound.

V. NUMERICAL SIMULATIONS

Numerical simulations compare compressed-sensing estimators with standard MLE under fixed experimental resources and assess both reconstruction quality and computational implementation.

  • Simulation design: The simulations reconstruct quantum states from Pauli measurements using two compressed-sensing estimators and compare them with standard maximum-likelihood estimation.Convex programming and certifiable interior-point solutions are used to separate estimator performance from heuristic large-scale optimization.
  • Estimator implementation: The compressed-sensing estimators explicitly enforce positivity and renormalize estimates whose trace is below one.These are the simulated modifications used in the numerical comparisons.

A. Setting the Estimator Parameters λ and µ

The simulations used empirically chosen regularization parameters for the matrix Dantzig selector and matrix Lasso, rather than theoretically optimized values. The authors leave optimal parameter selection open.

  • The matrix Dantzig selector used λ = 3d/
  • The matrix Lasso used µ = 4m/, which agrees with λ when m ∼ d for nearly pure states.
  • The parameter choices were based on casual inspection of a few data points using integer constants from 2 through 5.
  • The optimal choices for λ and µ remain an open problem.

B. Time Needed to Switch Measurement Settings

The simulations model a fixed experimental time in which sampling and switching measurement settings compete for resources. This framework captures state drift and makes switching costs central to estimator comparisons.

  • State preparation is assumed reliable only over a characteristic timescale because experimental parameters can drift.
  • The experiment is constrained to a fixed total time T, interpreted as the timescale over which the same state can be prepared confidently.
  • Within T, taking one sample has unit cost while switching measurement configurations costs c.
  • Compressed tomography is expected to outperform standard methods when switching costs are large and informationally complete measurements barely fit within T.
  • The simulations use c = 20, and their conclusions are reported as insensitive to this choice unless c > t prevents measuring more than one observable.

C. Other Simulation Parameters

The simulations evaluate compressed-sensing and maximum-likelihood estimators on noisy five-qubit states using fidelity and trace distance. Convex programs were solved accurately for comparison, while scalability requires specialized algorithms.

  • The simulated states are Haar-random five-qubit states with independent depolarizing noise of strength γ = 0.01.
  • Reconstruction quality is measured by squared fidelity and trace distance relative to the underlying state.
  • The matrix Dantzig selector and matrix Lasso were optimized with the SeDuMi interior-point solver to obtain accurate comparison solutions.
  • For larger qubit systems, specialized solvers such as SVT, TFOCS, or FPCA may be used, although solution quality depends somewhat on the algorithm.
  • The MLE baseline used an iterative algorithm that converged on every tested example.
  • Pauli operators were sampled without replacement.

D. Results and Analysis

Across simulated measurement budgets, compressed-sensing estimators generally outperform MLE, with the strongest advantage at short total times. Matrix Lasso performs best with nearly minimal measurement settings, reducing reconstruction resources without sacrificing fidelity.

  • Compressed-sensing estimators consistently outperform MLE across a wide range of sampled-Pauli counts, even after optimizing MLE over m.
  • At very small total time T, compressed sensing has a large advantage because informationally complete measurements yield highly fluctuating, non-Gaussian statistics.
  • Compressed sensing is not applicable when extremely high-fidelity reconstructions above 95% are required.
  • As T increases, all estimators converge to higher-fidelity estimates, while compressed-sensing fidelity becomes flat above a cutoff in m.
  • The flat fidelity curve suggests that small m values reduce computational cost without a real accuracy drawback.
  • For fixed T, matrix Lasso performs best with nearly minimal m, while MLE consistently underperforms the compressed-sensing estimators.

VI. PROCESS TOMOGRAPHY

Compressed process tomography extends low-rank recovery to quantum channels with small Kraus rank, using Pauli measurements and product-state preparations. The analysis counts settings while leaving sample complexity for future work.

  • Process complexity: Small Kraus-rank processes can be characterized using compressed sensing with substantially fewer settings than general process tomography.The method uses m = O(rd^2 log d) settings, compared with d^4 for general processes.
  • Experimental requirements: The procedure requires only product eigenstates of Pauli operators and Pauli measurements, without ancilla qubits.
  • Counting settings: The process-tomography setting count includes both measurement settings and input settings, with inputs sampled uniformly from a basis of states.This convention accounts for the channel input required by non-ancilla-assisted protocols.
  • Scope: The analysis focuses on the number of settings m and leaves the sample complexity t for future work.
  • Relation to prior methods: The approach differs from basis-sparse process estimation because it assumes low Kraus rank rather than sparsity in a known experimentally accessible basis.The related sparse-basis method can use prior knowledge about the process and measurements adapted to that basis.

A. Our Method

The method maps a low-Kraus-rank process to a low-rank Choi state and applies compressed state tomography, with an equivalent ancilla-free implementation. Its RIP-based analysis establishes near-optimal recovery guarantees, while simulations and the conclusion identify practical scope and open problems.

  • Our Method: The Jamiołkowski isomorphism maps a process with Kraus rank r to a state ρ_E of rank r, enabling compressed state tomography of the process.The ancilla-assisted construction prepares ρ_E by applying the process to half of a maximally entangled state.
  • Our Method: An equivalent ancilla-free procedure samples Pauli eigenstates, applies E, measures P_A, and weights outcomes by the sampled eigenvalue of P_B.These experiments estimate the Jamiołkowski-state expectation values before compressed state reconstruction recovers E.
  • Our Method: The proposed method applies to any small-Kraus-rank process, unlike a related method requiring elementwise sparsity in a known basis.The paper notes that low-rank process structure can be justified for local or few-body noise processes.
  • Theory and guarantees: The estimators achieve trace-distance error ϵ with sample complexity O(r^2d^2ϵ^-2 log d) for rank-r states, with truncation error for higher-rank states.The error scaling is optimal up to constant factors and requires O(rd poly log d) Pauli expectation values.
  • Numerical results: The estimators outperform MLE in the reported simulations, producing higher-fidelity estimates from the same amount of data.
  • Open problems: The paper leaves open tighter upper–lower sample-complexity gaps, optimality beyond minimax risk, analyses for alternative measurements, broader numerical comparisons, and parameter tuning.The reported numerical tests cover a narrow parameter range, and estimator success depends on choosing good λ and µ values.
Loading 1205.2300v2…