Eliminating Intermediate Measurements in Quantum Algorithms - Uma Girish

Dr. F.C. Kohli Centre of Excellence
Perspectives in Mathematical Sciences
January 10-February 4, 2022
Friday, 4 February 2022, 19:30 IST
________________________________________________________________________
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
Uma Girish is a PhD student at Princeton University working under the supervision of Prof Ran Raz. She graduated with a BSc in Mathematics and Computer Science at the Chennai Mathematical Institute in 2016. She completed her Masters in Computer Science at the Chennai Mathematical Institute in 2018, working for her thesis with Prof Piyush Srivastava at the Tata Institute of Fundamental Research. Uma's primary interests are Computational Complexity and Algorithms, with a focussed interest in Quantum Computing and Boolean Function Analysis.