arXiv:2610.06231
Unitary RQL Equals RQL
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
AI Summary
Intermediate measurements permit workspace reuse, but deferring them can exceed logarithmic space. This paper asks whether they can be eliminated while preserving one-sided bounded error: acceptance at least $2/3$ on yes-instances and exactly zero on no-instances. It proves $\mathsf{RQL}_\Gamma=\mathsf{RQUL}_\Gamma$ for $\Gamma=\{H,T,\mathrm{CNOT}\}$, preserving polynomial time and logarithmic space for absolutely halting computations. The equality extends to fixed finite gate sets implementing Clifford+$T$ and all primitive inverses exactly, with efficiently computable entries, including some transcendental gates. A separate gate-conversion argument establishes independence from Clifford+$T$ when primitive entries lie, up to fixed phases, in a fixed CM field and Clifford+$T$ is exactly implementable up to phase. The simulation extends density-matrix doubling to general channels, including resets and classical memory. Regularized reference states reweight the doubled steps into contractions, avoiding exponential normalization loss. For source acceptance $p$ and configuration dimension $d$, the ideal signal satisfies $p^2/(ed)\le q_*\le p$. Keeping left Kraus factors exact preserves zero acceptance despite approximating right factors; coherent composition and amplification restore constant acceptance. Right-factor implementation uses the established two-sided measurement-elimination theorem. A separate exact rejection-history test proves $\mathsf{QMAL}_{1,G}=\mathsf{Q_UMAL}_{1,G}$ under explicit inverse and Boolean-gate assumptions. Merlin supplies a logarithmic-size history certificate; an inverse-polynomial constraint gap enables amplification preserving perfect completeness. This retains the witness and does not establish perfect completeness for general QMAL. Measurement elimination with both acceptance and rejection exact, broader gate-set independence, and reference-state implementation without two-sided measurement elimination remain open.
AI tools were used in drafting this article.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 50 pages, 9 figures