  We initiate the systematic study of experimental quantum physics from the
perspective of computational complexity. To this end, we define the framework
of quantum algorithmic measurements (QUALMs), a hybrid of black box quantum
algorithms and interactive protocols. We use the QUALM framework to study two
important experimental problems in quantum many-body physics: determining
whether a system's Hamiltonian is time-independent or time-dependent, and
determining the symmetry class of the dynamics of the system. We study
abstractions of these problem and show for both cases that if the
experimentalist can use her experimental samples coherently (in both space and
time), a provable exponential speedup is achieved compared to the standard
situation in which each experimental sample is accessed separately. Our work
suggests that quantum computers can provide a new type of exponential
advantage: exponential savings in resources in quantum experiments.
