REVIEW
Unitary RQL Equals RQL
Quantum Physics · Submitted 5 Oct 2026 · 297 references
Pith's verdict: This resolves the FR21 open problem with a clean one-sided simulation and honest scoping; the one soft spot is that the load-bearing reference-estimation appendix is asserted more than derived and backed by a Lean repo that currently points at a placeholder.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
This paper proves that intermediate measurements can be removed from logarithmic-space quantum computations without sacrificing the one-sided error guarantee: for the standard Clifford+T gate set $\Gamma = \{H, T, \mathrm{CNOT}\}$, the…
The reading
What carries the argument
Its core is the reweighted density-matrix doubling of the source channel. Vectorization $\mathrm{vec}(X) = \sum_{i,j} X_{ij}|i\rangle|j\rangle$ represents a mixed state as a vector on two registers, and a channel with Kraus operators $K_{t,a}$ becomes the doubled operator $\sum_a K_{t,a} \otimes K_{t,a}$. Because a reset has doubled norm $\sqrt{2}$, normalizing each step separately would lose an exponential factor; instead the right factors are reweighted by reference states $\sigma_t = (\Phi_t(\sigma_{t-1}) + \eta I/d)/\kappa$ with $\eta = 1/T$, $\kappa = 1 + \eta$, giving factors $J_{t,a} = \kappa^{-1/2}\sigma_{t-1}^{1/2} K^\dagger_{t,a} \sigma_t^{-1/2}$ and a star branch $J_{t,*} = \sqrt{\eta/(\kappa d)}\sigma_t^{-1/2}$. The identity $W^\dagger_t W_t = I$ with $W_t = \sum_a J_{t,a}|v\rangle|a\rangle + J_{t,*}|v\rangle|*\rangle$ makes each step an isometry, so each doubled contraction $C_t = \sum_a K_{t,a} \otimes J^\dagger_{t,a}$ has norm at most one and consecutive square roots cancel, yielding $C_T\cdots C_1 \mathrm{vec}(\rho_0) = \mathrm{vec}(\rho_T \sigma_T^{-1/2})\sqrt{d\kappa^T}$ and an accepting probability $q^*$ with $p^2/(ed) \le q^* \le p$. These weights are exactly the Petz recovery factors $\sigma^{1/2} L^\dagger \tau^{-1/2}$ for the reference-adjusted channel. The exactness story is separate: the left Kraus factors $K_{t,a}$ are kept exact, the right factors are approximated by the logspace-uniform unitary circuits of Lemma 3.2 built from phase estimation of two-reflection walks, a coherent failure counter composes the steps, and Grover amplification with exact reflections raises acceptance to a constant without ever creating acceptance on a no-instance. Theorem 4.1 replaces this reweighting with a backward propagation of the rejection observable and an exact history test on a certificate supplied by Merlin.
Extended reading notes
Core claim
The central claim is that any absolutely halting, polynomial-time, $O(\log n)$-space quantum computation with intermediate measurements, acceptance at least $2/3$ on yes-instances and exactly zero on no-instances, can be simulated by a computation over the same standard gate set that measures only once at the end, with the same resource bounds and with the zero on no-instances preserved exactly. The mechanism is a reweighted density-matrix doubling of the source channel. Vectorizing a mixed state onto two registers turns each step $\Phi_t(X) = \sum_a K_{t,a} X K^\dagger_{t,a}$ into the doubled operator $\sum_a K_{t,a} \otimes K_{t,a}$, which is not a contraction: a qubit reset has norm $\sqrt{2}$. Perfect soundness is preserved for free, because zero acceptance means every accepting left vector $\Pi K_h |0\rangle$ vanishes, so changing only the right factor of a doubled term cannot create acceptance. To retain acceptance on yes-instances, the right factors are replaced by Petz-type factors $J^\dagger_{t,a} = \kappa^{-1/2}\sigma_t^{-1/2} K_{t,a} \sigma_{t-1}^{1/2}$ built from reference states $\sigma_t$ that follow the channel with a small maximally mixed injection, keeping every eigenvalue at least $1/(d(T+1))$; then each step is an isometry in doubled space, consecutive square roots cancel, and the resulting accepting probability $q^*$ lies between $p^2/(ed)$ and $p$, so unitary amplification restores a constant without introducing acceptance on no-instances.
Load-bearing premise
The whole argument rests on Lemma 3.2: that the reference-state entries $\sigma_t$, and the square-root and inverse-square-root blocks derived from them, can be approximated by polynomial-size, logspace-uniform unitary circuits over $\Gamma$ to any inverse-polynomial tolerance in operator norm, where estimating those entries is itself a BQL threshold problem whose solution invokes the already-published two-sided theorem $\mathrm{BQL} = \mathrm{BQUL}$; if that uniform access or the root synthesis misses its inverse-polynomial tolerance, the reweighted accepting amplitude $q^*$ cannot be retained and the simulation collapses, and the paper uses the two-sided equality as a premise rather than reproving it.
Editorial extensions
If this is right
- Adaptive Clifford+T computations with one-sided bounded error and exact zero acceptance on no-instances can be simulated with only a final measurement, in polynomial time and logarithmic space.
- Any fixed finite gate set with space-computable entries that implements Clifford+T exactly and implements each gate's inverse exactly satisfies $\mathrm{RQL}_G = \mathrm{RQUL}_G$, even when the entries are transcendental, e.g. $\Gamma \cup \{R_\theta\}$ for $\theta = 1$.
- Any fixed finite gate set whose entries lie, up to fixed phases, in one fixed CM field and which implements Clifford+T up to a global phase satisfies $\mathrm{RQL}_G = \mathrm{RQUL}_G = \mathrm{RQL}_\Gamma = \mathrm{RQUL}_\Gamma$, giving gate-set independence within the CM-field family, including totally real and root-of-unity extensions and alternatives such as $\{H, P_M, \mathrm{CNOT}\}$ for $8
- Logarithmic-space quantum Merlin–Arthur verification with perfect completeness (some witness accepted with certainty on every yes-instance) admits an intermediate-measurement-free verifier: $\mathrm{QMAL}_{1,G} = \mathrm{QUMAL}_{1,G}$.
- The separate questions $\mathrm{EQL} = \mathrm{EQUL}$, $\mathrm{QMAL} = \mathrm{QMAL}_1$, and $\mathrm{RQL} = \mathrm{coQUMAL}_1$ remain open; the constructions preserve an existing exact kernel and do not create one from a merely high-acceptance witness.
Reading between the lines
- Because the one-sided proof consumes the two-sided equality $\mathrm{BQL} = \mathrm{BQUL}$ as a published premise — the reference-entry comparators in Lemma 3.2 are themselves BQL threshold problems solved by invoking that theorem — the result is not self-contained; a fully independent resolution of the open problem would need to re-derive the two-sided equality through the same reweighted-doublin
- The CM-field theorem suggests the same $\mathrm{RQL}_G = \mathrm{RQUL}_G$ equality is plausible for any finite gate set whose entries lie in a CM field, such as finitely many roots of unity adjoined to a totally real field; the paper's stated obstruction to arbitrary algebraic fields is that conjugate gates need not be unitary, so the positive trace form used in the rational simulation is unavaila
- The backward-observable history certificate of Theorem 4.1 is structurally the separating vector of a negative span-program witness; testing whether this yields an explicit span-program formulation of RQL computations could connect measurement elimination to span-program size and quantum query complexity.
- With the reference injection $3I/(dT)$ and a pure initial state, the same doubled construction would give amplitudes $\sqrt{p_b}/2$ for the original output probabilities, so an exact implementation would need only one Grover iteration; the paper leaves open whether such an exact implementation over a fixed gate set exists, which is the concrete gap separating it from an $\mathrm{EQL} = \mathrm{EQU
Original 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
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
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
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Intermediate measurements let quantum computations discard information and reuse their workspace. | background 1.00 | 0.05 | 0.02 | asserted 0.93 |
| s1 | Deferring all measurements can require storing their entire history, which need not preserve logarithmic space. | background 0.97 | 0.09 | 0.02 | asserted 0.54 |
| s2 | 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]. | gap 0.71 | 0.03 | 0.03 | asserted 0.96 |
| s3 | 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. | result 0.82 | 0.97 | 0.93 | asserted 1.00 |
| s4 | Our proof extends the density-matrix doubling method of Girish, Raz and Zhan [ GRZ21 ] to general channels, including resets and classical memory. | method 0.90 | 0.90 | 0.04 | asserted 1.00 |
| s5 | 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. | result 0.60 | 0.95 | 0.06 | asserted 1.00 |
| s6 | 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 | result 0.72 | 0.91 | 0.08 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
Figures
Figures reproduced from arXiv:2610.06231 by the authors.
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.