Efficient quantum tomography

By Ryan O'Donnell, John Wright. Symposium on the Theory of Computing, 2015

338 citations recorded by the source corpus.

In the quantum state tomography problem, one wishes to estimate an unknown d-dimensional mixed quantum state ρ, given few copies. We show that O(d/ε) copies suffice to obtain an estimate ρ that satisfies ||ρ − ρ||F2 ≤ ε (with high probability). An immediate consequence is that O((ρ) · d/ε2) ≤ O(d2/ε2) copies suffice to obtain an ε-accurate estimate in the standard trace distance. This improves on the best known prior result of O(d3/ε2) copies for full tomography, and even on the best known prior result of O(d2log(d/ε)/ε2) copies for spectrum estimation. Our result is the first to show that nontrivial tomography can be obtained using a number of copies that is just linear in the dimension. Next, we generalize these results to show that one can perform efficient principal component analysis on ρ. Our main result is that O(k d/ε2) copies suffice to output a rank-k approximation ρ whose trace-distance error is at most ε more than that of the best rank-k approximator to ρ. This subsumes our above trace distance tomography result and generalizes it to the case when ρ is not guaranteed to be of low rank. A key part of the proof is the analogous generalization of our spectrum-learning results: we show that the largest k eigenvalues of ρ can be estimated to trace-distance error ε using O(k2/ε2) copies. In turn, this result relies on a new coupling theorem concerning the Robinson–Schensted–Knuth algorithm that should be of independent combinatorial interest.

Subfields: Artificial Intelligence, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/04411cbd3c859e3a0a1190e01ec4c5f72009988a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Shadow tomography of quantum states (2017, neutral): “By Lemma 12 (the Quantum Union Bound), this means that by applying these collective measurements successively, we can learn the truth for every i ∈ [ M ] with probability at least Of course, we also know from the recent work of O’Donnell and Wright [27] and Haah et al. [18] that O (cid:16) D 2 ε 2 (”
Sample-Optimal Tomography of Quantum States (2015, background): “The trace distance bound only says n = Õ(1/ξ2) copies are sufficient to distinguish them, whereas the fidelity bound says n = Õ(1/ξ) copies are sufficient.”
Predicting many properties of a quantum system from very few measurements (2020, background): “Constructive protocols [32, 49] saturate this bound, but require entangled circuits and measurements that act on all state copies simultaneously.”
The randomized measurement toolbox (2022, background): “17 ) and an amount of classical post-processing of the experimental results that is also exponentially large. information about the state, but the applications mentioned above illustrate that many physically relevant features of the state can survive.”
Hamiltonian Simulation by Qubitization (2016, methodology): “As Hermitian operators are also quantum observables, our methodology also offers a new approach for implementing arbitrary functions of measurement operators on quantum states [1, 13, 24, 38].”