Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with BQL:
TR20-087 | 8th June 2020
Uma Girish, Ran Raz, Wei Zhan

Quantum Logspace Algorithm for Powering Matrices with Bounded Norm

Revisions: 1

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\times n$ contraction matrix $A$, and a parameter $T \leq poly(n)$ and outputs the entries of $A^T$, up to (arbitrary) polynomially small additive ... more >>>

ISSN 1433-8092 | Imprint