May 1, 2024 | Robbie King, David Gosset, Robin Kothari, Ryan Babbush
This paper presents a framework for triply efficient shadow tomography, which aims to learn all expectation values of a set of observables from a given quantum state $\rho$ with high precision $\epsilon$. The protocol is sample- and time-efficient, using only a constant number of copies of $\rho$ at a time. The classical shadows protocol based on random single-copy measurements is triply efficient for the set of local Pauli observables. This paper extends this to two-copy shadow tomography for $k$-body fermionic observables and all $n$-qubit Pauli observables. The algorithms use Clifford measurements on two copies of $\rho$ and achieve sample efficiency by leveraging fractional graph coloring techniques. Specifically, the commutation graph of the observables is used to define a fractional coloring, which bounds the sample complexity. The paper also introduces a rapid-retrieval Pauli compression method that allows for efficient extraction of expectation values from a compressed classical representation of the quantum state. The results provide practical and efficient methods for shadow tomography in quantum systems, with applications in quantum simulations and quantum chemistry.This paper presents a framework for triply efficient shadow tomography, which aims to learn all expectation values of a set of observables from a given quantum state $\rho$ with high precision $\epsilon$. The protocol is sample- and time-efficient, using only a constant number of copies of $\rho$ at a time. The classical shadows protocol based on random single-copy measurements is triply efficient for the set of local Pauli observables. This paper extends this to two-copy shadow tomography for $k$-body fermionic observables and all $n$-qubit Pauli observables. The algorithms use Clifford measurements on two copies of $\rho$ and achieve sample efficiency by leveraging fractional graph coloring techniques. Specifically, the commutation graph of the observables is used to define a fractional coloring, which bounds the sample complexity. The paper also introduces a rapid-retrieval Pauli compression method that allows for efficient extraction of expectation values from a compressed classical representation of the quantum state. The results provide practical and efficient methods for shadow tomography in quantum systems, with applications in quantum simulations and quantum chemistry.