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.

我们从计算复杂性的角度对实验量子物理学进行了系统研究，定义了量子算法测量 (QUALMs) 框架，用于研究量子多体物理学中的两个重要实验问题，并显示在使用实验样品的相干性 (空间和时间) 时，相较于分别访问每个实验样本的标准情况，可以实现可证明的指数加速。因此，我们的研究表明，量子计算机可以提供一种新的指数优势：量子实验的资源消耗获得指数级的节省。