Unitary RQL Equals RQL

arXiv:2610.06231v1 Announce Type: new 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{\Gamma} = RQUL{\Gamma} for the standard gate set {\Gamma} = {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

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{\Gamma} = RQUL{\Gamma} for the standard gate set {\Gamma} = {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

Quantum Physics (quant-ph); Computational Complexity (cs.CC)

arXiv:2610.06231 [quant-ph]

(or arXiv:2610.06231v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2610.06231 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

formal-verification-source.zip.sha256

formal/README.md

formal/RQL/Bounds.lean

formal/RQL/Counter.lean

formal/RQL/Doubling.lean

formal/RQL/QMAAmplification.lean

formal/RQL/QMAGap.lean

formal/RQL/QMAGates.lean

formal/RQL/QMAGeometry.lean

formal/RQL/QMAHistory.lean

formal/RQL/Recovery.lean

formal/VERIFY-MANIFEST.json

formal/lake-manifest.json

formal/lakefile.toml

formal/verification-report.json

formal/verify.py

(13 additional files not shown) You must enabled JavaScript to view entire file list.

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

analiza aiqbench

Unitary RQL Equals RQL

Subiecte conexe