  Can quantum computational tools enhance the precision and efficiency of
physical experiments? Promising examples are known, but a systematic treatment
and comprehensive framework are missing. We introduce Quantum Algorithmic
Measurements (QUALMs) to enable the study of quantum measurements and
experiments from the perspective of computational complexity and communication
complexity. The measurement process is described, in its utmost generality, by
a many-round quantum interaction protocol between the experimental system and a
full-fledged quantum computer. The QUALM complexity is quantified by the number
of elementary operations performed by the quantum computer, including its
coupling to the experimental system.
  We study how the QUALM complexity depends on the type of allowed access the
quantum computer has to the experimental system: coherent, incoherent, etc. We
provide the first example of a measurement "task", which can be motivated by
the study of Floquet systems, for which the coherent access QUALM complexity is
exponentially better than the incoherent one, even if the latter is adaptive;
this implies that using entanglement between different systems in experiments,
as well as coherence between probes to the physical system at different times,
may lead to exponential savings in resources. We extend our results to derive a
similar exponential advantage for another physically motivated measurement task
which determines the symmetry class of the time evolution operator for a
quantum many-body system.
  Many open questions are raised towards better understanding how quantum
computational tools can be applied in experimental physics. A major question is
whether an exponential advantage in QUALM complexity can be achieved in the
NISQ era.
