arXiv preprint ·
Pretty good shadow tomography
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We give a shadow tomography algorithm that uses $O(\log(m) \log(m/δ) / \varepsilon^2)$ copies of the input state. Specifically, given a quantum state $ρ$ and observables $O_1,\ldots,O_m$, the algorithm outputs estimates of $\mathrm{tr}(O_iρ)$ for all $i\in[m]$ that are all accurate to within $\pm\varepsilon$, except with probability at most $δ$. The key idea is to work in the average-case setting: for a random state drawn from a known prior, a pretty good measurement on $O(\log(m)/\varepsilon^2)$ copies gives a constant-error guarantee on all but a small fraction of the prior. Boosting this guarantee gives an average-case shadow tomography algorithm, and the minimax principle then (non-constructively) implies the existence of a measurement with the same worst-case guarantee. We also identify an obstruction to further improvement with this approach. While pretty good measurements amplify success over the randomness of the prior, they do not amplify success over the randomness of measurement. This issue appears to be inherent, and gives rise to the remaining $\log(m)$ factor separating the complexity of the quantum problem from its classical counterpart.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Transformer-Based Time-Series Inference of Lindblad Dynamics in Open Quantum Systems
Quantum Darwinism through apparatus-mediated environmental recording
Constraints on the Origin of Universal $1/f^2$ Photon-Count Spectra at Baseband
Excitation of subradiant states in atom chains by surface plasmon waves
Universal Improvement of Channel Fidelity via Entanglement Assistance
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.