Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > INTERMEDIATE MEASUREMENTS:
Reports tagged with intermediate measurements:
TR21-087 | 22nd June 2021
Uma Girish, Ran Raz

Eliminating Intermediate Measurements using Pseudorandom Generators

Revisions: 1

We show that quantum algorithms of time T and space $S \ge \log T$ with intermediate measurements can be simulated by quantum algorithms of time $T\cdot \mathrm{poly}(S)$ and space $O(S\cdot \log T)$ without intermediate measurements. The best simulations prior to this work required either $\Omega(T)$ space (by the deferred measurement ... more >>>




ISSN 1433-8092 | Imprint