Efficient quantum tomography

DOI10.1145/2897518.2897544MaRDI QIDQ5361889zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.01907

zbMATH Keywords

longest increasing subsequencequantum computingRobinson-Schensted-Knuth correspondencetomography

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Abstract: In the quantum state tomography problem, one wishes to estimate an unknown $d$-dimensional mixed quantum state $ho$, given few copies. We show that $O(d/epsilon)$ copies suffice to obtain an estimate $hatho$ that satisfies $|hatho-ho{|}_F^{2}leqepsilon$ (with high probability). An immediate consequence is that $O(mathrmrank(ho)cdotd/epsilo{n}^2)leqO(d^2/epsilo{n}^2)$ copies suffice to obtain an $epsilon$-accurate estimate in the standard trace distance. This improves on the best known prior result of $O(d^3/epsilo{n}^2)$ copies for full tomography, and even on the best known prior result of $O(d^{2}log(d/epsilon)/epsilo{n}^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 $ho$. Our main result is that $O(kd/epsilo{n}^2)$ copies suffice to output a rank-$k$ approximation $hatho$ whose trace distance error is at most $epsilon$ more than that of the best rank-$k$ approximator to $ho$. This subsumes our above trace distance tomography result and generalizes it to the case when $ho$ 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 $ho$ can be estimated to trace-distance error $epsilon$ using $O(k^2/epsilo{n}^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.

Recommendations

• Sample-optimal tomography of quantum states
• Shadow tomography of quantum states
• Efficient quantum tomography. II
• Shadow tomography of quantum states
• Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators

Cited in

(40)

• Superdensity operators for spacetime quantum mechanics
• Schur-Weyl duality for the Clifford group with applications: property testing, a robust Hudson theorem, and de Finetti representations
• The variational quantum eigensolver: a review of methods and best practices
• Asymptotic performance of port-based teleportation
• Geometry and optimization in quantum information. Abstracts from the workshop held October 3--9, 2021 (hybrid meeting)
• The learnability of quantum states
• Measuring polynomial functions of states
• Relations between convergence rates in Schatten p-norms
• General theory of measurement with two copies of a quantum state
• Efficient quantum tomography. II
• Quantum SDP solvers: large speed-ups, optimality, and applications to quantum learning
• Shadow tomography of quantum states
• Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators
• Quantum state certification
• Shadow tomography of quantum states
• Sample-optimal tomography of quantum states
• Online learning of quantum states
• Fast state tomography with optimal error bounds
• Multi-parameter estimation beyond quantum Fisher information
• Learning and testing quantum states via probabilistic combinatorics and representation theory
• QHSL: a quantum hue, saturation, and lightness color model
• Inapproximability of positive semidefinite permanents and quantum state tomography
• Fast and robust quantum state tomography from few basis measurements
• Error regions in quantum state tomography: computational complexity caused by geometry of quantum states
• Quantum process tomography on cloud-accessible quantum computing platforms
• Improved quantum data analysis
• Self-testing of genuine multipartite non-local and non-maximally entangled states
• Classical shadows meet quantum optimal mass transport
• An introduction to quantum computing for statisticians and data scientists
• Fat shattering, joint measurability, and PAC learnability of POVM hypothesis classes
• Linear programming with unitary-equivariant constraints
• Learning low-degree quantum objects
• Quantum implicit representation of vortex filaments in turbulence
• Unclonable cryptography with unbounded collusions and impossibility of hyperefficient shadow tomography
• Lower bounds for learning quantum states with single-copy measurements
• Sample efficient identity testing and independence testing of quantum states
• Optimal speed-up of multi-step Pontus-Mpemba protocols
• Quantum data sketches
• Quantum tomography from the evolution of a single expectation
• A Block Tensor Train Burer-Monteiro Framework for Low-Rank Quantum State Tomography

This page was built for publication: Efficient quantum tomography

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361889)