Triply Efficient Shadow Tomography
Robbie King, David Gosset, Robin Kothari, Ryan Babbush
Abstract
We investigate the problem of efficiently estimating expectation values of large sets of observables from copies of an unknown many-body quantum state. This task, known as shadow tomography, is crucial for quantum simulation and quantum chemistry, where the relevant observables often include <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><a:mi>k</a:mi></a:math>-body fermionic or <d:math xmlns:d="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><d:mi>k</d:mi></d:math>-local Pauli operators. A key goal is to achieve sample efficiency, computational efficiency, and few-copy measurements. We introduce the notion of triply efficient shadow tomography to formalize these requirements. Prior work has shown that single-copy measurements suffice for <g:math xmlns:g="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><g:mi>k</g:mi></g:math>-local Pauli operators with constant <j:math xmlns:j="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><j:mi>k</j:mi></j:math>. However, we prove that for <m:math xmlns:m="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><m:mi>k</m:mi></m:math>-body fermionic observables and the full set of <p:math xmlns:p="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><p:mi>n</p:mi></p:math>-qubit Pauli operators, single-copy protocols fail to achieve sample-efficient tomography. We then present new protocols based on measuring two copies of the state at a time that overcome these lower bounds, providing a triply efficient protocol.