Everyone is invited to attend the online lecture of prof.dr. Dorit Aharonov (Hebrew University, Israel).
This lecture is part of the QuSoft Lustrum Month.
For the zoomlink, please contact Yfke Dulek: dulek@cwi.nl
Title: Quantum Algorithmic Measurements
Abstract: While the jury is still out on the prospects of the exciting developments on the quantum algorithmic supremacy front, a new and not less exciting development has been taking place over the past decade: the design of physical experiments has been completely reimagined to include computational elements such as error correction, multiparticle entanglement, and more. One can ask: how much would a full quantum computer help a quantum experimentalist in her lab? Would it improve the precision of certain measurements, or enable probing physical properties which were so far inaccessible? In a recent joint work with Cotler and Qi, we develop a theory of "quantum algorithmic measurements" (QUALMs) which is a hybrid of quantum black box algorithms (the black box is Nature itself) and quantum interactive protocols (with Nature); QUALMs aim to model the most general quantum experimental process, and enable studying such experiments from the point of view of their computational complexity. We use the QUALM model to show a new type of quantum exponential advantage: fully coherent experimental access to the measured system is provably exponentially more efficient than incoherent access, even if the latter is allowed to be adaptive (as usual, it is the lower bound which is difficult). For example, we show that the detection of symmetries in a quantum many-body system exhibits such an exponential separation in QUALM complexity. The theory of QUALMs raises many questions: what other quantum algorithmic ideas can be used to enhance our experimental abilities? And can coherent QUALMs be exponentially advantageous even in our noisy, pre-fault tolerance era? Throughout the talk, and in order to motivate QUALMs and my interest in the computational theory of measurements, I will give examples from the past decade based also on joint works with Arrad, Atia, Ben-Or, Eban, Mahadev, Retzker, Vazirani, and Vinkler.
