Pith. Sign in

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

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on October 6, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

  1. T0 AI review An AI read the paper and answered a fixed list of questions.
  2. T1 Audit Automatic checks that the references and files the paper relies on exist and match.
  3. T2 Compute The paper's code or calculations re-run with the same results.
  4. T3 Formal statement The claims written out in a formal math language a computer can read.
  5. T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 2 major objections · 5 minor · Ask about this paper · The compiled record · Read the full review →
Challenge this review Comment (0) Read on arXiv ↗
Cite ▾
arXiv ID2610.06231 (version 1)
Pith IDCKEZ3QS3, Pith's permanent record of this paper and its review
CitationQuinten Tupker. "Unitary RQL Equals RQL." arXiv:2610.06231 (2026). https://pith.science/paper/CKEZ3QS3
Cite this reviewBibTeX for Pith's review of this paper
Claim paper

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

The paper proves that intermediate measurements can be deferred to a single final measurement in logarithmic-space quantum computation without breaking the one-sided error guarantee: for the standard Clifford+T gate set $\Gamma = \{H, T, \mathrm{CNOT}\}$, $\mathrm{RQL}_\Gamma = \mathrm{RQUL}_\Gamma$, preserving polynomial time, logarithmic space, and exactly zero acceptance on no-instances. This answers an open problem posed by Fefferman and Remscrim, who had settled only the two-sided bounded-error version. The proof extends the density-matrix doubling method of Girish, Raz and Zhan from unital channels to arbitrary channels, including resets and classical memory, by reweighting the doubled evolution with reference states. The same machinery yields measurement elimination for any finite gate set with space-computable entries and exact inverses, and establishes gate-set independence for families of CM-field algebraic gate sets. A separate history-checking construction proves $\mathrm{QMAL}_{1,G} = \mathrm{QUMAL}_{1,G}$, removing intermediate measurements from logarithmic-space quantum verification while preserving perfect completeness.

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-10-06: 1 request, 5,638 input tokens.

What the abstract itself states, as probabilities: claims first 0.08 · states limitation 0.55 · human participants 0.01 · controlled comparison 0.03 · randomized assignment 0.01 · states quantitative result 0.46 · compares with prior results 0.93 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; .

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

What the classifier reports for each sentence. The number is the probability it gave the label.
#sentencerolethe authors' own workstates the main conclusionstrength
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 kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read
  • arXiv listing abstract v1
not examined
  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers
levels run
  • P abstract
not run
  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures
Figure 1. Ordinary logarithmic space. An arrow A → B means A ⊆ B, not necessarily strict. Unlabelled arrows follow from the definitions and displayed equalities; crossing lines are not junctions. Transitive edges and some classes are omitted. The subscript U means unitary until the final measurement. R means bounded error with perfect soundness, N means positive acceptance on yes-instances and zero on no-instances, and PrQL means two-sided unbounded error (often denoted QL). Post allows postselection; C=L is the zero-test class for GapL functions. QUMAL1 has perfect completeness. †: use…
Figure 2. The direct RQL simulation under the gate assumptions of Theorem
Figure 3. Keeping the left Kraus factors exact while approximating the right factors. Read both
Figure 4. Reweighting a qubit reset Φ(X) = Tr(X)|0⟩ ⟨0|. In (a), σ0 = I/2 and σ1 = diag(2 + η, η)/(2κ), where κ = 1 + η. Substitution into the definition of C1 gives the displayed contraction. In (b), the source starts in |0⟩, applies T resets, and accepts |0⟩ with certainty. Normalizing each doubled step as M/√ 2 gives probability 2−T . With η = 1/T, the reference state is the same after every reset; for t ≥ 2, Ct |00⟩ = κ −1/2 |00⟩. Thus reweighting gives q∗ = [(2 + 1/T)(1 + 1/T) T −1 ] −1 , tending to 1/(2e). The curves compare exact matrix products before compilation and amplification.…
Figure 5. Perfect soundness holds history by history. The histories are
Figure 6. The backward history for QMAL1. For a candidate witness v, the original verifier starts in ρ0 = |Ev⟩ ⟨Ev| and applies ρj = Φj (ρj−1). The aligned observable is Bτ−j , so Tr(Bτ−jρj ) is the same rejection probability at every time j. The tuple h(v) denotes an unnormalized vector in a direct sum; its normalized encoding uses O(log n) qubits, not a separate copy of every operator. For a general certificate Z = (v, z0, . . . , zτ ), the three sets of equations are precisely F Z = 0. They force Z = h(v) and Rv = 0. An honest witness on a yes-instance satisfies them exactly; the gap bound…
Figure 7. The unitary verifier constructed from the original
Figure 8. expresses the ideal contraction Ct as a clean block of a unitary circuit. The unitary extension of Wt in this diagram is an abstract operator, so the diagram alone does not assert exact synthesis over a fixed gate set. For bounded error, this operator may be approximated to the accuracy required by the full simulation. The compiled form in Appendix A.3 can also be used for BQL. Appendix B proves the acceptance bounds after reducing the original computation’s error. It also explains why implementing the right Kraus factors uses the known measurement-elimination theorem. A E : |0⟩ B…
Figure 9. The compiled doubled step Cbt ≈ Ct . The purple box replaces the ideal inverse in fig. 8 by the inverse of the implemented circuit Qt . The left Kraus factors Kt,a remain exact; the right Kraus factors H † t,a act on B. Label sums include ∗ and padding labels, with zero left Kraus factors. Green tags are clean-block conditions, not measurements: the physical output is Cbt |ψ⟩AB |00⟩EZ plus a component with nonzero EZ, retained coherently. 39

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.