Dr. F.C. Kohli Centre of ExcellencePerspectives in Mathematical SciencesJanuary 10–February 4, 2022Friday, 4 February 2022, 19:30 ISTUma Girish, Princeton UniversityTitle Eliminating Intermediate Measurements in Quantum Algorithms (Video Recording) Abstract Does the ability to perform intermediate measurements give power to quantum computation? Alternatively, can algorithms with intermediate measurements be simulated by algorithms without intermediate measurements in an efficient manner? This is a fundamental question in quantum computing and has connections to quantum complexity theory, reversibility of computation, pseudorandomness and error reduction. In this talk we introduce and motivate this problem and present recent advances. The earliest known result is the principle of deferred measurements; it is a well-known principle in quantum computing and gives a simple way to eliminate intermediate measurements. However, it requires a large overhead in space. In this talk, we focus on techniques to eliminate intermediate measurements that have a small overhead in space. We present the results of Fefferman and Remscrim (2021) and of Girish, Raz and Zhan (2021), which demonstrate a space-efficient version of the principle of deferred measurements. These results show that algorithms of time T and space S with intermediate measurements can be simulated by algorithms without intermediate measurements in time T.exp(S) and space O(S+ logT). In particular, it implies that quantum algorithms of logarithmic space do not require intermediate measurements. However, this technique requires a large overhead in time (particularly when S is much larger than logT). We present a result of Girish and Raz (2021) which shows a version of the principle of deferred measurements that is both space-efficient and time-efficient. This result shows a simulation which runs in time poly(T,S) and uses space O(S.logT). In particular, it implies that quantum algorithms of polylogarithmic space and polynomial time do not require intermediate measurements. About the speaker
|