Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR21-087 | 22nd June 2021 18:05

#### Eliminating Intermediate Measurements using Pseudorandom Generators

TR21-087
Authors: Uma Girish, Ran Raz
Publication: 22nd June 2021 19:04
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 principle) or $\mathrm{poly}(2^S)$ time [FR21, GRZ21]. Our result is thus a time-efficient and space-efficient simulation of algorithms with intermediate measurements by algorithms without intermediate measurements.