Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.06231

Unitary RQL Equals RQL

Quinten Tupker

quant-phcs.CCSubmitted Oct 5, 2026• Announced Oct 6, 2026• 0 citations
arXivHTMLPDF

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.

Some signs of AI-generated textAI use disclosed
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

Related papers

Space-Bounded Unitary Quantum Computation with Postselection

Seiichiro Tani

Space-bounded computation has been a central topic in classical and quantum complexity theory. In the quantum case, every elementary gate must be unitary. This restriction makes it unclear whether the power of space-bounded computation changes by allowing intermediate measurement. In the bounded error case, Fefferman and Remscrim [STOC 2021, pp.1343--1356] and Girish, Raz and Zhan~[ICALP 2021, pp.73:1--73:20] recently provided the break-through results that the power does not change. This paper shows that a similar result holds for space-bounded quantum computation with postselection. Namely, it is proved possible to eliminate intermediate postselections and measurements in the space-bounded quantum computation in the bounded-error setting. Our result strengthens the recent result by Le Gall, Nishimura and Yakaryilmaz~[TQC 2021, pp.10:1--10:17] that logarithmic-space bounded-error quantum computation with intermediate postselections and measurements is equivalent in computational power to logarithmic-space unbounded-error probabilistic computation. As an application, it is shown that bounded-error space-bounded one-clean qubit computation (DQC1) with postselection is equivalent in computational power to unbounded-error space-bounded probabilistic computation, and the computational supremacy of the bounded-error space-bounded DQC1 is interpreted in complexity-theoretic terms.

arXiv:2206.15122•Leibniz international proceedings in informatics•Jan 1, 2022•0 citations

The Space-Time Cost of Purifying Quantum Computations

Mark Zhandry

General quantum computation consists of unitary operations and also measurements. It is well known that intermediate quantum measurements can be deferred to the end of the computation, resulting in an equivalent purely unitary computation. While time efficient, this transformation blows up the space to linear in the running time, which could be super-polynomial for low-space algorithms. Fefferman and Remscrim (STOC'21) and Girish, Raz and Zhan (ICALP'21) show different transformations which are space efficient, but blow up the running time by a factor that is exponential in the space. This leaves the case of algorithms with small-but-super-logarithmic space as incurring a large blowup in either time or space complexity. We show that such a blowup is likely inherent, demonstrating that any "black-box" transformation which removes intermediate measurements must significantly blow up either space or time.

arXiv:2401.07974•Leibniz international proceedings in informatics•Jan 1, 2024•6 citations

Eliminating Intermediate Measurements Using Pseudorandom Generators

Uma Girish, Ran Raz

We show that quantum algorithms of time $T$ and space $S\ge \log T$ with unitary operations and intermediate measurements can be simulated by quantum algorithms of time $T \cdot \mathrm{poly} (S)$ and space $ {O}(S\cdot \log T)$ with unitary operations and without intermediate measurements. The best results prior to this work required either $Ω(T)$ space (by the deferred measurement principle) or $\mathrm{poly}(2^S)$ time [FR21,GRZ21]. Our result is thus a time-efficient and space-efficient simulation of algorithms with unitary operations and intermediate measurements by algorithms with unitary operations and without intermediate measurements. To prove our result, we study pseudorandom generators for quantum space-bounded algorithms. We show that (an instance of) the INW pseudorandom generator for classical space-bounded algorithms [INW94] also fools quantum space-bounded algorithms. More precisely, we show that for quantum space-bounded algorithms that have access to a read-once tape consisting of random bits, the final state of the algorithm when the random bits are drawn from the uniform distribution is nearly identical to the final state when the random bits are drawn using the INW pseudorandom generator. This result applies to general quantum algorithms which can apply unitary operations, perform intermediate measurements and reset qubits.

arXiv:2106.11877•Leibniz international proceedings in informatics•Jun 22, 2021•10 citations

Space-Efficient Error Reduction for Unitary Quantum Computations

Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin +2 more

This paper presents a general space-efficient method for error reduction for unitary quantum computation. Consider a polynomial-time quantum computation with completeness c and soundness s, either with or without a witness (corresponding to QMA and BQP, respectively). To convert this computation into a new computation with error at most 2^{-p}, the most space-efficient method known requires extra workspace of O(p*log(1/(c-s))) qubits. This space requirement is too large for scenarios like logarithmic-space quantum computations. This paper shows an errorreduction method for unitary quantum computations (i.e., computations without intermediate measurements) that requires extra workspace of just O(log(p/(c-s))) qubits. This in particular gives the first method of strong amplification for logarithmic-space unitary quantum computations with two-sided bounded error. This also leads to a number of consequences in complexity theory, such as the uselessness of quantum witnesses in bounded-error logarithmic-space unitary quantum computations, the PSPACE upper bound for QMA with exponentially-small completeness-soundness gap, and strong amplification for matchgate computations.

arXiv:1604.08192•Leibniz international proceedings in informatics•Jan 1, 2016•11 citations

Minimum Quantum Storage from Incomplete Channel Observations

Jeremy Rodgers

How much quantum storage must a hidden implementation retain when experimental observations leave its structure undetermined? This paper establishes exact minimum quantum-storage requirements across all implementations compatible with specified channel observations. The resource is the worst-input expected logarithm of retained quantum dimension across one controlled temporal cut, with unlimited classical records available at no cost. For the channel dimension measure introduced by Cope and Uola, the paper proves their suggested minimax equality relating minimum storage to output Schmidt measure and extends it to every nonempty compact convex set of compatible channels. One common input enforces the resource minimum across all compatible implementations. A finite optimal implementation exists, although an optimal entangled probe need not. For qubit channels, four measured coefficients determine an exact, attained minimum without assuming channel covariance or unitality. An explicit five-Kraus construction attains 99/169, while a separate analytical certificate proves that every compatible implementation must use nontrivial quantum storage with at least that probability on the same specified input. A second exact formula uses only two Pauli-transfer coefficients and yields a minimum storage requirement of 0.58 when both coefficients are jointly constrained to the interval [0.79, 0.81]. The paper also presents semidefinite optimization over compatible experimental uncertainty regions. The results require calibrated quantum inputs and outputs, concealed preparation labels, and accounting for every quantum carrier across the storage cut. They constrain storage resources without reconstructing the hidden implementation or certifying environmental non-Markovianity. Motivated by Shadow Theory’s source/readout distinction, the proofs use standard quantum mechanics and quantum-information mathematics. Version 1.1 includes complete proofs, explicit attaining constructions, worked examples, and discussion of experimental assumptions and limitations. No experimental data are reported.

•Sep 6, 2026•0 citations

Measurement-Free Encoded-Qubit Control and a Two-Local Qutrit Obstruction in a Spin-2 AKLT Plaquette

Boris Batenin, Andrei Preece

Can an encoded quantum state be controlled continuously without repeated measurements to prevent leakage? This study gives a constructive answer for a four-spin-2 AKLT plaquette, where a three-dimensional singlet code sits inside a 625-dimensional physical Hilbert space. The result combines an exact restriction with a coherent control scheme: strictly leakage-free two-site Hamiltonians cannot provide universal control of the full encoded qutrit, yet two explicitly constructed interactions enable universal single-qubit control without intermediate measurements or postselection within a two-dimensional subspace. The classification begins with the complete physical leakage map for all six spin pairs and exchange polynomials through degree four. Exact rational calculations establish rank L = 6 and dim ker L = 18 for the 255 × 24 matrix. Despite this large family of leakage-cancelling combinations, every accessible logical Hamiltonian obeys [A, R] = 0, where R is a fixed geometric involution. Its two-dimensional and one-dimensional eigenspaces therefore remain separate, obstructing universal SU(3) control. The restriction extends to arbitrary anisotropic two-site Hamiltonians that preserve the code. Within the rotationally invariant pair-polynomial model, interactions confined to the four plaquette edges act only as logical scalars; noncommuting protected controls require at least three pair supports and polynomial degree three. The constructive solution uses quadratic and cubic exchange Hamiltonians acting simultaneously on three pairs, including a diagonal link. Their coefficients cancel physical leakage exactly, so QH₂P = QH₃P = 0 throughout the full system, with P projecting onto the code and Q onto its complement. Their logical generators satisfy Lie(iA, iB) ≅ u(2) ⊕ u(1), allowing arbitrary coherent qubit gates while preserving the code at every intermediate time. The manuscript supplies exact certificates and verification procedures, together with operator-norm and calibration-error bounds that make the engineering requirements explicit. The practical opportunity is to remove intermediate code-check measurements from this control scheme; demonstrating a hardware advantage requires calibrated simultaneous interactions, including the diagonal channel, and measured gate fidelity and latency.

•Oct 28, 2026•0 citations
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
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/32/32/3 on yes-instances and exactly zero on no-instances.
It proves RQLΓ=RQULΓ\mathsf{RQL}_\Gamma=\mathsf{RQUL}_\GammaRQLΓ​=RQULΓ​ for Γ={H,T,CNOT}\Gamma=\{H,T,\mathrm{CNOT}\}Γ={H,T,CNOT}, preserving polynomial time and logarithmic space for absolutely halting computations. The equality extends to fixed finite gate sets implementing Clifford+TTT and all primitive inverses exactly, with efficiently computable entries, including some transcendental gates. A separate gate-conversion argument establishes independence from Clifford+TTT when primitive entries lie, up to fixed phases, in a fixed CM field and Clifford+TTT 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 ppp and configuration dimension ddd, the ideal signal satisfies p2/(ed)≤q∗≤pp^2/(ed)\le q_*\le pp2/(ed)≤q∗​≤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 QMAL1,G=QUMAL1,G\mathsf{QMAL}_{1,G}=\mathsf{Q_UMAL}_{1,G}QMAL1,G​=QU​MAL1,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.
Space-bounded computation has been a central topic in classical and quantum complexity theory. In the quantum case, every elementary gate must be unitary. This restriction makes it unclear whether the power of space-bounded computation changes by allowing intermediate measurement. In the bounded error case, Fefferman and Remscrim [STOC 2021, pp.1343--1356] and Girish, Raz and Zhan~[ICALP 2021, pp.73:1--73:20] recently provided the break-through results that the power does not change. This paper shows that a similar result holds for space-bounded quantum computation with postselection. Namely, it is proved possible to eliminate intermediate postselections and measurements in the space-bounded quantum computation in the bounded-error setting. Our result strengthens the recent result by Le Gall, Nishimura and Yakaryilmaz~[TQC 2021, pp.10:1--10:17] that logarithmic-space bounded-error quantum computation with intermediate postselections and measurements is equivalent in computational power to logarithmic-space unbounded-error probabilistic computation. As an application, it is shown that bounded-error space-bounded one-clean qubit computation (DQC1) with postselection is equivalent in computational power to unbounded-error space-bounded probabilistic computation, and the computational supremacy of the bounded-error space-bounded DQC1 is interpreted in complexity-theoretic terms.
General quantum computation consists of unitary operations and also measurements. It is well known that intermediate quantum measurements can be deferred to the end of the computation, resulting in an equivalent purely unitary computation. While time efficient, this transformation blows up the space to linear in the running time, which could be super-polynomial for low-space algorithms. Fefferman and Remscrim (STOC'21) and Girish, Raz and Zhan (ICALP'21) show different transformations which are space efficient, but blow up the running time by a factor that is exponential in the space. This leaves the case of algorithms with small-but-super-logarithmic space as incurring a large blowup in either time or space complexity. We show that such a blowup is likely inherent, demonstrating that any "black-box" transformation which removes intermediate measurements must significantly blow up either space or time.
We show that quantum algorithms of time TTT and space S≥log⁡TS\ge \log TS≥logT with unitary operations and intermediate measurements can be simulated by quantum algorithms of time T⋅poly(S)T \cdot \mathrm{poly} (S)T⋅poly(S) and space $ {O}(S\cdot \log T)$ with unitary operations and without intermediate measurements. The best results prior to this work required either Ω(T)Ω(T)Ω(T) space (by the deferred measurement principle) or poly(2S)\mathrm{poly}(2^S)poly(2S) time [FR21,GRZ21]. Our result is thus a time-efficient and space-efficient simulation of algorithms with unitary operations and intermediate measurements by algorithms with unitary operations and without intermediate measurements. To prove our result, we study pseudorandom generators for quantum space-bounded algorithms. We show that (an instance of) the INW pseudorandom generator for classical space-bounded algorithms [INW94] also fools quantum space-bounded algorithms. More precisely, we show that for quantum space-bounded algorithms that have access to a read-once tape consisting of random bits, the final state of the algorithm when the random bits are drawn from the uniform distribution is nearly identical to the final state when the random bits are drawn using the INW pseudorandom generator. This result applies to general quantum algorithms which can apply unitary operations, perform intermediate measurements and reset qubits.
This paper presents a general space-efficient method for error reduction for unitary quantum computation. Consider a polynomial-time quantum computation with completeness c and soundness s, either with or without a witness (corresponding to QMA and BQP, respectively). To convert this computation into a new computation with error at most 2^{-p}, the most space-efficient method known requires extra workspace of O(p*log(1/(c-s))) qubits. This space requirement is too large for scenarios like logarithmic-space quantum computations. This paper shows an errorreduction method for unitary quantum computations (i.e., computations without intermediate measurements) that requires extra workspace of just O(log(p/(c-s))) qubits. This in particular gives the first method of strong amplification for logarithmic-space unitary quantum computations with two-sided bounded error. This also leads to a number of consequences in complexity theory, such as the uselessness of quantum witnesses in bounded-error logarithmic-space unitary quantum computations, the PSPACE upper bound for QMA with exponentially-small completeness-soundness gap, and strong amplification for matchgate computations.
How much quantum storage must a hidden implementation retain when experimental observations leave its structure undetermined? This paper establishes exact minimum quantum-storage requirements across all implementations compatible with specified channel observations. The resource is the worst-input expected logarithm of retained quantum dimension across one controlled temporal cut, with unlimited classical records available at no cost. For the channel dimension measure introduced by Cope and Uola, the paper proves their suggested minimax equality relating minimum storage to output Schmidt measure and extends it to every nonempty compact convex set of compatible channels. One common input enforces the resource minimum across all compatible implementations. A finite optimal implementation exists, although an optimal entangled probe need not. For qubit channels, four measured coefficients determine an exact, attained minimum without assuming channel covariance or unitality. An explicit five-Kraus construction attains 99/169, while a separate analytical certificate proves that every compatible implementation must use nontrivial quantum storage with at least that probability on the same specified input. A second exact formula uses only two Pauli-transfer coefficients and yields a minimum storage requirement of 0.58 when both coefficients are jointly constrained to the interval [0.79, 0.81]. The paper also presents semidefinite optimization over compatible experimental uncertainty regions. The results require calibrated quantum inputs and outputs, concealed preparation labels, and accounting for every quantum carrier across the storage cut. They constrain storage resources without reconstructing the hidden implementation or certifying environmental non-Markovianity. Motivated by Shadow Theory’s source/readout distinction, the proofs use standard quantum mechanics and quantum-information mathematics. Version 1.1 includes complete proofs, explicit attaining constructions, worked examples, and discussion of experimental assumptions and limitations. No experimental data are reported.
Can an encoded quantum state be controlled continuously without repeated measurements to prevent leakage? This study gives a constructive answer for a four-spin-2 AKLT plaquette, where a three-dimensional singlet code sits inside a 625-dimensional physical Hilbert space. The result combines an exact restriction with a coherent control scheme: strictly leakage-free two-site Hamiltonians cannot provide universal control of the full encoded qutrit, yet two explicitly constructed interactions enable universal single-qubit control without intermediate measurements or postselection within a two-dimensional subspace. The classification begins with the complete physical leakage map for all six spin pairs and exchange polynomials through degree four. Exact rational calculations establish rank L = 6 and dim ker L = 18 for the 255 × 24 matrix. Despite this large family of leakage-cancelling combinations, every accessible logical Hamiltonian obeys [A, R] = 0, where R is a fixed geometric involution. Its two-dimensional and one-dimensional eigenspaces therefore remain separate, obstructing universal SU(3) control. The restriction extends to arbitrary anisotropic two-site Hamiltonians that preserve the code. Within the rotationally invariant pair-polynomial model, interactions confined to the four plaquette edges act only as logical scalars; noncommuting protected controls require at least three pair supports and polynomial degree three. The constructive solution uses quadratic and cubic exchange Hamiltonians acting simultaneously on three pairs, including a diagonal link. Their coefficients cancel physical leakage exactly, so QH₂P = QH₃P = 0 throughout the full system, with P projecting onto the code and Q onto its complement. Their logical generators satisfy Lie(iA, iB) ≅ u(2) ⊕ u(1), allowing arbitrary coherent qubit gates while preserving the code at every intermediate time. The manuscript supplies exact certificates and verification procedures, together with operator-norm and calibration-error bounds that make the engineering requirements explicit. The practical opportunity is to remove intermediate code-check measurements from this control scheme; demonstrating a hardware advantage requires calibrated simultaneous interactions, including the diagonal channel, and measured gate fidelity and latency.