Eliminating Intermediate Measurements using Pseudorandom Generators

Understand

We show that quantum algorithms of time $T$ and space $S\ge \log T$ with unitary operations and intermediate measurements can be simulated by quantum algorithms of time $T \cdot \mathrm{poly} (S)$ and space $ {O}(S\cdot \log T)$ with unitary operations and without intermediate measurements.

• The best results 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 unitary operations and intermediate measurements by algorithms with unitary operations and without intermediate measurements.
• To prove our result, we study pseudorandom generators for quantum space-bounded algorithms.