Our results apply to quantum algorithms with purely quantum memory. We show that the class of quantum logspace algorithms with intermediate measurements is equivalent to the class of quantum logspace algorithms without intermediate measurements. This shows that the deferred-measurement principle, a fundamental principle in quantum computing also applies for quantum logspace algorithms. Since unitary transformations are reversible, while measurements are irreversible, an interesting aspect of this result is that any quantum logspace algorithm can be simulated by a reversible quantum logspace algorithm. Since the process of tossing random coins can be simulated using intermediate measurements, our result can also be viewed as a derandomization of quantum logspace algorithms.

This is a joint work with Ran Raz and Wei Zhan.