Tutte Colloquium -David Gosset-Triply efficient shadow tomography

Abstract: Given copies of a quantum state, a shadow tomography protocol aims to learn all expectation values from a fixed set of observables, to within a given precision. We say that such a protocol is triply efficient if it is sample efficient, time efficient, and uses measurements that entangle a constant number of copies of the state at a time.   A natural family of shadow tomography protocols based on random single-copy Clifford measurements can be understood as arising from fractional colorings of a graph G that encodes the commutation structure of the set of observables. Here we describe a framework for two-copy shadow tomography that uses an initial round of Bell measurements to reduce to a fractional coloring problem in an induced subgraph of G with bounded clique number. This coloring problem can be addressed using techniques from graph theory known as chi-boundedness. Using this framework we give the first triply efficient  shadow tomography scheme for the set of local fermionic observables, which arise in a broad class of interacting fermionic systems in physics and chemistry. We also give a triply efficient scheme for the set of all -qubit Pauli observables. Our protocols for these tasks use two-copy measurements, which is necessary: sample-efficient schemes are provably impossible using only single-copy measurements. This is joint work with Robbie King, Robin Kothari, and Ryan Babbush.