Unitary RQL Equals RQL
quant-ph, cs.CC
Submitted: 2026-10-05
Updated: 2026-10-05
Comments: 50 pages, 9 figures
Code: https://github.com/ExampleOne/unitary-rql-lean
License: http://creativecommons.org/licenses/by/4.0/
The gist: Intermediate measurements let quantum computations discard information and reuse their workspace.
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
Sources
- Quantum Amplitude Amplification and Estimation
- Reversing quantum dynamics with near-optimal quantum and classical fidelity
- Space-bounded quantum state testing via space-efficient quantum singular value transformation
Related papers
- Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
- Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
- Polynomial-time classical and quantum simulation of quantum impurity models
- A quasiparticle-protected superconducting qubit
- Theory of quantum-enhanced interferometry with general Markovian light sources
- A convergent hierarchy of spectral gap certificates for qubit Hamiltonians