Under the auspices of the Computational Complexity Foundation (CCF)

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