Triply efficient shadow tomography

Abstract

Given copies of a quantum state $\rho$, a shadow tomography protocol aims to learn all expectation values from a fixed set of observables, to within a given precision $\epsilon$. We say that a shadow tomography protocol is triply efficient if it is sample- and time-efficient, and only employs measurements that entangle 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 and other 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 $n$-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. Finally, we give a shadow tomography protocol that compresses an $n$-qubit quantum state into a $\text{poly}(n)$-sized classical representation, from which one can extract the expected value of any of the $4^n$ Pauli observables in $\text{poly}(n)$ time, up to a small constant error.

References in corpus (27)

• Electronic Structure Calculations with Dynamical Mean-Field Theory: A Spectral Density Functional Approach
• Improved Simulation of Stabilizer Circuits
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Fermionic quantum computation
• Synthesis of Quantum Logic Circuits
• The Bravyi-Kitaev transformation for quantum computation of electronic structure
• Hybrid Quantum-Classical Hierarchy for Mitigation of Decoherence and Determination of Excited States
• A practical guide to density matrix embedding theory in quantum chemistry
• Information-theoretic bounds on quantum advantage in machine learning
• Measurement Optimization in the Variational Quantum Eigensolver Using a Minimum Clique Cover
• Hybrid quantum-classical approach to correlated materials
• Unbiasing Fermionic Quantum Monte Carlo with a Quantum Computer
• N-electron valence state perturbation theory based on a density matrix renormalization group reference function, with applications to the chromium dimer and poly-p-phenylene vinylene oligomer
• Increasing the representation accuracy of quantum simulations of chemistry without extra quantum resources
• Fermionic partial tomography via classical shadows
• Quantum Overlapping Tomography
• A Compact Fermion to Qubit Mapping
• Nearly Optimal Measurement Scheduling for Partial Tomography of Quantum States
• Systematically improvable multi-scale solver for correlated electron systems
• Matchgate Shadows for Fermionic Quantum Simulation
• Generalized quantum subspace expansion
• Optimal fermion-to-qubit mapping via ternary trees with applications to reduced quantum states learning
• Heisenberg-Weyl Observables: Bloch vectors in phase space
• Rigorous wave function embedding with dynamical fluctuations
• Approximation algorithms for quantum many-body problems
• Uncertainty relations from graph theory
• Bootstrap Embedding on a Quantum Computer

Cited by in corpus (8)

• Operational interpretation of the Stabilizer Entropy
• Single-copy stabilizer testing
• Theory of quantum error mitigation for non-Clifford gates
• Experimental measurement and a physical interpretation of quantum shadow enumerators
• Bell sampling in Quantum Monte Carlo simulations
• Resilience-Runtime Tradeoff Relations for Quantum Algorithms
• Quantum Advantage via Efficient Post-processing on Qudit Classical Shadow tomography
• Optimizing Sparse SYK