Shadow tomography of quantum states

DOI10.1145/3188745.3188802MaRDI QIDQ5230300zbMATH OpenOpenAlexWikidataFDO

Authors Scott Aaronson

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

information theorymixed stateone-way communicationpostselectionquantum advicequantum money

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Quantum computation (81P68)

Abstract: We introduce the problem of *shadow tomography*: given an unknown $D$-dimensional quantum mixed state $ho$, as well as known two-outcome measurements $E_1,ldots,E_M$, estimate the probability that $E_i$ accepts $ho$, to within additive error $varepsilon$, for each of the $M$ measurements. How many copies of $ho$ are needed to achieve this, with high probability? Surprisingly, we give a procedure that solves the problem by measuring only $widetildeOleft(varepsilo{n}^{-4}cdotlo{g}^{4}McdotlogDight)$ copies. This means, for example, that we can learn the behavior of an arbitrary $n$-qubit state, on all accepting/rejecting circuits of some fixed polynomial size, by measuring only $n^{Oleft(1ight)}$ copies of the state. This resolves an open problem of the author, which arose from his work on private-key quantum money schemes, but which also has applications to quantum copy-protected software, quantum advice, and quantum one-way communication. Recently, building on this work, Brand~ao et al. have given a different approach to shadow tomography using semidefinite programming, which achieves a savings in computation time.

Recommendations

• Shadow tomography of quantum states
• Sample-optimal tomography of quantum states
• Efficient quantum tomography
• Quantum state certification
• The learnability of quantum states

Cited in

(32)

• Shadowed negative binomial state
• Experimental realization of Schumacher's information geometric Bell inequality
• Semi-quantum money
• The learnability of quantum states
• Efficient quantum tomography. II
• scientific article; zbMATH DE number 7559394 (Why is no real title available?)
• Quantum SDP solvers: large speed-ups, optimality, and applications to quantum learning
• Improvements in quantum SDP-solving with applications
• Shadow tomography of quantum states
• Quantum state certification
• Efficient quantum tomography
• Sample-optimal tomography of quantum states
• Monitoring energy drift with shadow Hamiltonians
• Online learning of quantum states
• Learning and testing quantum states via probabilistic combinatorics and representation theory
• Inapproximability of positive semidefinite permanents and quantum state tomography
• Quantum process tomography on cloud-accessible quantum computing platforms
• Public-key encryption with quantum keys
• Toward density functional theory on quantum computers?
• On classical and hybrid shadows of quantum states
• Classical shadows meet quantum optimal mass transport
• Fat shattering, joint measurability, and PAC learnability of POVM hypothesis classes
• Quantum state tomography from observable time traces in closed quantum systems
• Robust combiners and universal constructions for quantum cryptography
• Real classical shadows
• Sample efficient identity testing and independence testing of quantum states
• Quantum data sketches
• Efficient quantum pseudorandomness from Hamiltonian phase states
• Quantum computing inspired iterative refinement for semidefinite optimization
• A Block Tensor Train Burer-Monteiro Framework for Low-Rank Quantum State Tomography
• Consumable data via quantum communication
• Consumable data via quantum communication

This page was built for publication: Shadow tomography of quantum states

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