Chennai Mathematical Institute


Thursday, 21 January 2021, 9 pm (IST)
Partha Mukhopadhyay is inviting you to a scheduled Zoom meeting.
Topic: Partha Mukhopadhyay's Zoom Meeting Time: Jan 21, 2021 08:30 PM Mumbai, Kolkata, New Delhi
Join Zoom Meeting
Meeting ID: 860 6182 8564
Passcode: 350528
Quantum Logspace Algorithm for Powering Matrices with Bounded Norm

Uma Girish
Princeton University (USA).


We give a quantum logspace algorithm for powering matrices with spectral norm at most 1. The algorithm gets as input an arbitrary n by n matrix A with spectral norm at most 1 and a parameter k <= poly(n) and outputs the entries of A^k up to (arbitrary) polynomially small additive error. We give several applications of this result to quantum computation without classical memory.

Our results apply to quantum algorithms with purely quantum memory. We show that the class of quantum logspace algorithms with intermediate measurements is equivalent to the class of quantum logspace algorithms without intermediate measurements. This shows that the deferred-measurement principle, a fundamental principle in quantum computing also applies for quantum logspace algorithms. Since unitary transformations are reversible, while measurements are irreversible, an interesting aspect of this result is that any quantum logspace algorithm can be simulated by a reversible quantum logspace algorithm. Since the process of tossing random coins can be simulated using intermediate measurements, our result can also be viewed as a derandomization of quantum logspace algorithms.

This is a joint work with Ran Raz and Wei Zhan.