Quantum State Tomography via Compressed Sensing

David Groß, Yi-Kai Liu, Steven T. Flammia, Stephen Becker, Jens EisertPhysical 2010 · DOI · arXiv

Abstract

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.

Introduction

In the development of quantum technologies, verifying the state of a system—a process known as Quantum State Tomography (QST)—is a critical but computationally expensive task. Traditional QST faces an "exponential wall": as the number of qubits $n$ increases, the state space dimension $d = 2^n$ grows exponentially. Standard tomography requires $d^2$ measurement settings. For an 8-qubit system, this translates to over 65,000 settings, requiring weeks of data collection and post-processing.

This paper introduces a novel approach to QST by applying the principles of compressed sensing. By exploiting the fact that most physically relevant quantum states are "nearly pure" (low rank $r$), the authors demonstrate that $O(rd \log^2 d)$ measurements are sufficient for reconstruction. This represents a massive reduction in measurement overhead compared to standard methods.

Methodology

The authors bridge quantum physics with matrix completion, a subset of compressed sensing, using several key techniques:

  1. Convex Optimization: Finding the minimum-rank matrix that fits a set of data is an NP-hard problem. The authors use a "convex proxy"—minimizing the trace norm ($\|\sigma\|_{tr}$)—which transforms the reconstruction into a semidefinite program solvable via efficient algorithms like Singular Value Thresholding (SVT).
  2. Pauli Measurements: Instead of measuring individual matrix elements, which is physically impractical, the method utilizes random Pauli observables. These are standard in quantum laboratories and easily implemented.
  3. The "Golfing Scheme": A recursive construction used to prove that a unique solution exists with high probability, even when the system is significantly undersampled.
  4. Hybrid Sampling: To further accelerate the linear algebra, the authors propose a "hybrid" strategy using structured sets of Pauli strings to ensure a sparse sampling operator.

The method was evaluated using simulated Haar-random states ($n=8$, $d=256$, $r=3$) with added noise, and an experimental proxy based on data from a real-world 8-ion experiment.

Results and Discussion

The compressed sensing approach yields significant improvements in both measurement efficiency and computational speed. For an 8-qubit system, reconstruction was achieved with only a few thousand measurements instead of the standard 65,536. Using the SVT-based approach, reconstruction took approximately one minute on a standard laptop, while the hybrid method reduced this to under 10 seconds.

Fidelity and Trace Distance vs. Sparsity for Hybrid and Random sampling methods.

As shown in the figure above, both the random and hybrid sampling methods achieve high fidelity and low trace distance as the sparsity (the fraction of measurements taken) increases. The method is remarkably stable against noise; even with 5% depolarizing noise, the authors achieved ~95% fidelity reconstructions while sampling only a small fraction of total observables. In the 8-ion experimental case, a rank-3 approximation with 90.5% fidelity was found using less than 30% of the total possible Pauli measurements.

A key advantage of this method is that it requires no a priori assumptions about the state's rank. The algorithm can "certify" the result: if a low-rank state fits the data, it is mathematically guaranteed to be the correct one.

Limitations

While this method drastically reduces the measurement cost coefficient, the dimension $d$ still grows exponentially with the number of qubits ($2^n$). This pushes the practical boundary of QST (e.g., from 8 to perhaps 14 qubits) but does not solve the fundamental scaling of Hilbert space. Additionally, the success of matrix completion depends on "incoherence"—the state must not be too aligned with the measurement basis. While random unitaries can mitigate this, they add experimental complexity. Finally, while the hybrid method performs well, it initially lacked the rigorous mathematical guarantees of purely random Pauli sampling.

Summary updated

Abstract

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(rdlog²d) measurement settings, compared to standard methods that require d² 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.
BibTeX
@inproceedings{gro2010quantum,
  author = {David Groß and Yi-Kai Liu and Steven T. Flammia and Stephen Becker and Jens Eisert},
  title = {{Quantum State Tomography via Compressed Sensing}},
  booktitle = {Physical},
  year = {2010},
  doi = {10.1103/physrevlett.105.150401},
}
Figure