Lab Home  Phone  Search  


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 a shadow tomography protocol is triply efficient if it is sample and timeefficient, and only employs measurements that entangle a constant number of copies of ρ at a time. The classical shadows protocol based on random singlecopy measurements is triply efficient for the set of local Pauli observables. This and other protocols based on random singlecopy 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 twocopy 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 chiboundedness. 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 nqubit Pauli observables. Our protocols for these tasks use twocopy measurements, which is necessary: sampleefficient schemes are provably impossible using only singlecopy measurements. Finally, we give a shadow tomography protocol that compresses an nqubit quantum state into a poly(n)sized classical representation, from which one can extract the expected value of any of the 4n Pauli observables in poly(n) time, up to a small constant error. This is joint work with Robbie King, Robin Kothari, and Ryan Babbush. Bio: David Gosset is a quantum computer scientist who is interested in quantum algorithms and complexity theory. He has worked on theoretical questions relevant to small quantum computers, including understanding the computational power of constantdepth quantum circuits and the limits of classical simulation algorithms. He has also investigated the computational power and complexity of quantum manybody systems, and the application of physicsinspired tools from these areas to quantum computer science. Host: Sam Slezak, CCS3 