Bell Sampling from Quantum Circuits

A central challenge in the verification of quantum computers is benchmarking their performance as a whole and demonstrating their computational capabilities. In this Letter, we find a universal model of quantum computation, Bell sampling, that can be used for both of those tasks and thus provides an ideal stepping stone toward fault tolerance. In Bell sampling, we measure two copies of a state prepared by a quantum circuit in the transversal Bell basis. We show that the Bell samples are classically intractable to produce and at the same time constitute what we call a ``circuit shadow'': from the Bell samples we can efficiently extract information about the quantum circuit preparing the state, as well as diagnose circuit errors. In addition to known properties that can be efficiently extracted from Bell samples, we give several new and efficient protocols: an estimator of state fidelity, an error-mitigated estimator of Pauli expectation values, a test for the depth of a circuit, and an algorithm to estimate a lower bound on the number of T gates in the circuit. With some additional measurements, the latter algorithm can be used to learn a full description of states prepared by circuits with low T count.