Copy complexity of online quantum shadow tomography

For an unknown d-dimensional quantum state and m adaptively chosen observables 0≤A≤I, estimate each expectation online within ε with probability at least 9/10. The copy-complexity targets are O(log(m)√log(d)/ε³) and O(√m/ε²).

Why it matters and what counts as progress

Why it matters: It asks how efficiently quantum data can answer adaptive online measurements while retaining accuracy throughout the interaction.

What counts as progress: Reduce quantum-copy complexity for adaptive online expectation estimates, with matching accuracy, success probability and observable assumptions.

How the problem developed

2015 · Foundations [1]
Cynthia Dwork and coauthors Developed adaptive data analysis methods for answering adaptively chosen statistical queries.
2018 · Partial result [2]
Scott Aaronson Introduced shadow tomography for estimating many observables of an unknown quantum state.
31 Jul 2026 · Reported claim [3]
Sitan Chen, Ryan O’Donnell, Angelos Pelecanos and John Wright Matched classical copy-complexity rates for online shadow tomography with two quantum algorithms.

AI contribution

Online Shadow Tomography Matching the Classical Bounds

Sitan Chen, Ryan O'Donnell, Angelos Pelecanos, John Wright

For an unknown d-dimensional state and m adaptively chosen observables 0≤A≤I, Chen, O’Donnell, Pelecanos and Wright give online expectation estimates within ε with success probability at least 9/10 using O(log(m)√log(d)/ε³) or O(√m/ε²) copies, respectively.

AI involvementAI-led

ImportanceNotable

Technical verificationFormal (human)

Human understandingFull