Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR21-087 | 22nd June 2021 18:05

Eliminating Intermediate Measurements using Pseudorandom Generators


Authors: Uma Girish, Ran Raz
Publication: 22nd June 2021 19:04
Downloads: 164


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.

To prove our result, we study pseudorandom generators for quantum space-bounded algorithms. We show that (an instance of) the INW pseudorandom generator for classical space-bounded algorithms [INW94] also fools quantum space-bounded algorithms. More precisely, we show that for quantum space-bounded algorithms that have access to a read-once tape consisting of random bits, the final state of the algorithm when the random bits are drawn from the uniform distribution is nearly identical to the final state when the random bits are drawn using the INW pseudorandom generator.

ISSN 1433-8092 | Imprint