Quantum Complexity of Experiments

We introduce a theoretical framework to study experimental physics using quantum complexity theory. This allows us to address: what is the computational complexity of an experiment? For several 'model' experiments, we prove that there is an exponential savings in resources if the experimentalist can entangle apparatuses with experimental samples. A novel example is the experimental task of determining the symmetry class of a time evolution operator for a quantum many-body system. Some of our complexity advantages have been realized on Google's Sycamore processor, demonstrating a real-world advantage for learning algorithms with a quantum memory.