Foundations for learning from noisy quantum experiments

We study our ability to learn physical operations in quantum systems where all operations, from state preparation, dynamics, to measurement, are a priori unknown. We prove that without any prior knowledge, if one can explore the full quantum state space by composing the operations, then every operation could be learned up to an arbitrarily small error. When one cannot explore the full space but the operations are approximately known, we present an efficient algorithm for learning all operations up to a single unlearnable parameter corresponding to the fidelity of the initial state assuming gate-independent noise on Clifford gates. Our algorithm for learning the Clifford gate noise uses a number of experiments linear in the number of parameters, which is quadratically fewer than the best known randomized benchmarking protocol. When these assumptions are not met, the true description of the noise can be fundamentally unlearnable, e.g., we prove that no benchmarking protocol can learn the Pauli noise on Clifford+T gates if the Pauli noise depends on the gates. Even when the noise cannot be learned, we prove that a large quantum advantage can be achieved in a recent learning task performed on the Sycamore quantum processor.