arXiv preprint ·
Unitary RQL Equals RQL
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Matching with Multiple Bottlenecks: Parameterized Complexity and Approximation
A Fast Algorithm for Maltsev Constraints
On the complexity of the single-move labeled token routing problem
Robust subspace designs and the power of a unique small quantum witness
On the Computational Complexity of Hidden Markov Model Identification
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.