Eliminating Intermediate Measurements using Pseudorandom Generators

Uma Girish, Ran Raz

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 \m…