Quantum measurements can be removed from low-space algorithms without error

Unitary RQL Equals RQL

Computational Complexity

Summary

Quantum computers sometimes use measurements during calculations, which can make things tricky to manage with limited memory. The authors show that these measurements can be removed entirely in certain types of quantum algorithms that use very little memory and run efficiently, without losing correctness or making errors on negative cases. Their work extends known methods to more general types of quantum operations and different sets of quantum gates. This helps understand what kinds of quantum computations can be simplified by avoiding intermediate measurements while keeping strong guarantees.

What this means in practice

  • For quantum algorithm designers: Remove intermediate quantum measurements from space-efficient algorithms while preserving exact zero-error behavior on rejected inputs.
  • For quantum compiler developers: Simplify quantum circuits by eliminating intermediate measurements in logarithmic-space algorithms, enabling more uniform circuit implementations.

A theory result. No direct application yet.

Authors

Quinten Tupker

Abstract

Intermediate measurements let quantum computations discard information and reuse their workspace. Deferring all measurements can require storing their entire history, which need not preserve logarithmic space. Fefferman and Remscrim proved that measurements can nevertheless be eliminated with two-sided bounded error, and asked whether the same holds with one-sided error [FR21]. We prove RQLΓ = RQULΓ for the standard gate set Γ = {H, T, CNOT}, preserving polynomial time, logarithmic space, and exactly zero acceptance on no-instances. Our proof extends the density-matrix doubling method of Girish, Raz and Zhan [ GRZ21 ] to general channels, including resets and classical memory. We also prove measurement elimination for broader finite gate sets with exact inverses, including suitable gates with transcendental entries, and establish gate-set independence for a specified family of algebraic gate sets. A separate history-checking construction proves QMAL1,G = QUMAL1,G under explicit gate assumptions: measurements can also be eliminated from logarithmic-space quantum verification while preserving perfect completeness