QSEC Quantum Computing Seminar Series: Quantum Logspace Algorithm for Powering Matrices with Bounded Norm, by Wei Zhan of Princeton

When:
February 9, 2021 @ 12:00 pm – 1:00 pm
2021-02-09T12:00:00-05:00
2021-02-09T13:00:00-05:00
Date: 2/09/2021, 12pm
Speaker: Wei Zhan, Princeton University

Topic: Quantum Logspace Algorithm for Powering Matrices with Bounded Norm

QSEC’s quantum computing subgroup will organize and host a seminar series throughout the upcoming semester. The upcoming seminar will be given by Mr. Wei Zhan of Princeton University. These events are free and open to the public. For any questions, contact qsec@gmu.edu. Below is the abstract of Mr. Zhong’s talk and meeting information:

Abstract
We give a quantum logspace algorithm for powering contraction matrices, that is, matrices with spectral norm at most 1. The algorithm gets as an input an arbitrary n×n contraction matrix A, and a parameter T ≤ poly(n) and outputs the entries of A^T, up to (arbitrary) polynomially small additive error. The algorithm applies only unitary operators, without intermediate measurements.
We use this algorithm to show that the class of quantum logspace algorithms with only quantum memory and with intermediate measurements is equivalent to the class of quantum logspace algorithms with only quantum memory without intermediate measurements. This shows that the deferred-measurement principle, a fundamental principle of quantum computing, applies also for quantum logspace algorithms (without classical memory). More generally, we give a quantum algorithm with space O(S + log T ) that takes as an input the description of a quantum algorithm with quantum space S and time T, with intermediate measurements, and simulates it unitarily with polynomially small error, without intermediate measurements.

Bio:
Wei Zhan is a fourth year Ph.D student in the theory group of the Department of Computer Science at Princeton University, advised by Prof. Ran Raz. His research interest lies in computational complexity theory, especially in space-bounded computation.

Meeting Information
Zoom: https://gmu.zoom.us/j/6094315466