Pith. sign in

REVIEW 4 major objections 5 minor 1 cited by

Quantum Catalytic Space

T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Every language computable by a quantum catalytic Turing machine with logarithmic work space and polynomial catalytic space is computable exactly in polynomial time.

desk verdict New model, clean peripheral results, but the QCL⊆EQP proof breaks on a misapplied Helstrom bound and an unjustified mixture step. read the letter →

arxiv 2506.16324 v1 pith:KFXQUQSZ submitted 2025-06-19 quant-ph

Harry Buhrman , Marten Folkertsma , Ian Mertz , Florian Speelman , Sergii Strelchuk , Sathyawageeswar Subramanian , Quinten Tupker This is my paper
classification quant-ph MSC 68Q1268Q1581P68
keywords quantumcatalyticspacelogspacespace-boundedcomputationEQPTC^1thresholdcircuitsone-clean-qubitmodelTuringmachinetape
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper launches the study of catalytic space in the quantum setting: a machine with a small work tape is allowed to borrow a large quantum register that must be returned exactly to its original state. The central result is that any computation in quantum catalytic logspace (QCL) can be performed exactly, with no error, in polynomial time by a standard quantum computer, placing QCL inside EQP. This is the quantum analogue of the classical open problem of whether catalytic logspace equals P, and it resolves that question in the quantum world. The paper also shows that quantum catalytic logspace can simulate log-depth threshold circuits, and that both unitary quantum catalytic logspace and the classical catalytic logspace can be simulated in the one-clean-qubit model.

What carries the argument

The load-bearing mechanism is the runtime-independence theorem (Theorem 8), which says that a quantum catalytic machine's runtime on a fixed input cannot depend on the initial state of the catalytic tape. Its proof combines Lemma 3, an average-case bound of $2^{O(s)}$ over an orthonormal basis of catalytic states, with Lemma 5, which uses the optimal single-copy state-discrimination bound to argue that any difference in runtime distributions between two initial states would force those states to have trace distance 1; a mixture state then produces the contradiction that gives a single run time $t$. This fixed runtime bound converts the aperiodic, non-halting behaviour of catalytic machines into a polynomial clock, which is what makes the Turing-machine/circuit equivalence and the containment in EQP go through. A second piece of machinery is the equivalence of four catalysing state sets (all density matrices, pure states, Pauli product states, and EPR halves), proved via the fact that Pauli eigenstates span the space of matrices.

What would settle it

A concrete counterexample to Theorem 8: build a quantum catalytic Turing machine with logarithmic work space and polynomial catalytic space, and two initial catalytic states with trace distance strictly between 0 and 1, such that the runtime distribution on some input differs for the two states. Such an example would invalidate Lemma 5 and the $\mathsf{QCL} \subseteq \mathsf{EQP}$ containment.

Watch

Extended reading notes

Core claim

The paper's main claim is Theorem 2 / Corollary 3: $\mathsf{QCL} \subseteq \mathsf{EQP}$. For any quantum catalytic Turing machine with $s$ qubits of work space and polynomial catalytic space, for every fixed input the machine's runtime is a fixed value $t$ independent of the initial catalytic state, and that value is at most $2^{O(s)}$; for $s = O(\log n)$ this gives a polynomial-time, error-free simulation. The proof proceeds by showing that the runtime distribution is an observable that can be estimated from a single copy of the catalytic state, so two initial states that yielded different runtime distributions would have to be perfectly distinguishable (trace distance 1); a convexity argument then forces the runtime to be constant. With this runtime bound, the paper establishes that quantum catalytic Turing machines and quantum catalytic circuits define the same complexity classes, and derives the further containments $\mathsf{TC}^1 \subseteq \mathsf{QCL}$, $\mathsf{BQ_UCL} \subseteq \mathsf{DQC1}$, and $\mathsf{CL} \subseteq \mathsf{DQC1}$.

Load-bearing premise

The proof leans on the claim that if two initial catalytic states ever lead to different runtime distributions on the same input, then a single copy of the unknown state can perfectly distinguish them, which is only possible when the two distributions are completely disjoint; overlapping distributions cannot be told apart with certainty from one copy.

Editorial extensions

If this is right

  • $\mathsf{QCL} \subseteq \mathsf{EQP}$ means that any future demonstration of a quantum catalytic advantage must use super-logarithmic work space or allow errors; exact-reset quantum catalytic logspace adds no power beyond exact polynomial time.
  • Theorem 6 gives a circuit model for quantum catalytic space, so future results can work with uniform circuit families rather than Turing machines without loss of generality.
  • $\mathsf{TC}^1 \subseteq \mathsf{QCL}$ shows problems such as determinant and other log-depth threshold computations lie in quantum catalytic logspace, giving concrete problems for which catalytic memory yields quantum-computable algorithms.
  • $\mathsf{CL} \subseteq \mathsf{DQC1}$ places the classical catalytic class inside the one-clean-qubit model, connecting catalytic power to a physically motivated model of quantum computing with little quantum control.
  • Since $\mathsf{EQP} \subseteq \mathsf{BQP}$, quantum catalytic logspace is contained in bounded-error quantum polynomial time, so catalysis does not push logspace beyond $\mathsf{BQP}$.

Reading between the lines

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

  • A natural test of the paper's method is whether the runtime-independence argument survives when resetting is only required to be correct up to a small trace distance; the paper leaves this open, and the proof technique does not obviously extend.
  • The same single-copy discrimination argument could be applied to any classically observable feature of the catalytic state, not just runtime, suggesting a general "no information leakage" principle for exact-reset quantum catalysis.
  • A natural next step, not explored here, is to look for separations between $\mathsf{QCL}$ and $\mathsf{CL}$ or $\mathsf{BQL}$; the paper notes $\mathsf{CL} \subseteq \mathsf{QCL}$ is open, and an oracle or problem that distinguishes them would map out the boundary between classical and quantum catalytic power.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper introduces quantum catalytic space-bounded computation, in which a Turing machine or circuit has a small clean work space and a large catalytic tape initialized to an arbitrary density matrix that must be restored exactly. It claims (i) QCL⊆EQP, i.e., every quantum catalytic logspace language is computable exactly in polynomial time; (ii) equivalence of the Turing machine and circuit formulations of quantum catalytic space; (iii) TC1⊆QCL; and (iv) containment of unitary QCL and of classical CL in the one-clean-qubit model DQC1. The upper bound (i) is derived through a polynomial average runtime bound and a purported proof that the runtime distribution is independent of the initial catalytic state.

Significance. If correct, the QCL⊆EQP result would be striking: it would show that the exact reset condition for arbitrary quantum states strips catalytic logspace of all advantage over exact polynomial time, resolving the quantum analogue of the central open problem in classical catalytic computing. The formalization of quantum catalytic machines, the equivalence of different catalytic state sets, and the containment results for TC1 and DQC1 are interesting and, as far as this report can tell, do not depend on the flawed runtime-independence lemma. The paper is well structured and the model definitions are thoughtful. However, the main upper bound is not supported by the proof as written.

major comments (4)
  1. [Section 4.2, Lemma 5] The proof of Lemma 5 misapplies the Helstrom bound. Lemma 4 provides a procedure that reuses the same physical copy of the catalyst many times, so the discrimination protocol it induces is not a single-copy measurement; after k runs the optimal success probability is governed by the total variation distance between the k-fold product runtime distributions, which tends to 1 for any two distinct distributions and does not imply ||ρ1−ρ2||_1 = 1. If the two runtime distributions overlap, no finite number of samples permits perfect discrimination. Hence the conclusion of Lemma 5 does not follow.
  2. [Section 4.2, Theorem 8] The proof of Theorem 8 relies entirely on Lemma 5, so the runtime-independence theorem is unsupported once Lemma 5 fails. In addition, the argument that T(ρ′) must equal one of T(ρ1) or T(ρ2) is not justified: transitivity only rules out equality to both. The case where T(ρ′) equals neither is not discussed. While that case would also contradict Lemma 5 if the lemma were valid, the proof as written is incomplete. Since Theorem 8 is used to derive Theorem 9 and Corollary 3, the central claim QCL⊆EQP is unproven.
  3. [Section 4.3, Lemma 6 and Theorem 6] Lemma 6 is asserted without proof as the extension of Theorem 8 to 'any classical observable feature' of the initial catalytic state; because Theorem 8 is not established, the circuit-equivalence theorem is unsupported. The proof of Theorem 6 also invokes Theorem 9, which inherits the same gap. This affects the paper's claim that the Turing machine and circuit definitions of quantum catalytic space coincide.
  4. [Section 4.3, Lemma 7] The output-independence requirement of Definition 11 is justified by asserting that approximate indistinguishability of nearby catalytic states forces the output state to be exactly equal for all initial states. This does not follow: being unable to perfectly discriminate two states does not imply that the channel outputs are identical. A rigorous proof is needed, especially because the catalytic condition for arbitrary density matrices is central to the model.
minor comments (5)
  1. [Section 3.2 / Lemma 3] The phrase 'orthonormal basis for D(H_c)' is imprecise, since the set of density matrices is not a linear subspace; the counting argument in Lemma 3 suggests a basis of the full operator algebra, which should be stated explicitly.
  2. [Section 4.1, Lemma 4] The proof should state explicitly that after each run the work tape and classical control are reset, so that repeated runs yield independent samples from T(M,x,η).
  3. [Section 4.3, proof of Theorem 6] The phrase 'by using a method similar to that from the proof of Lemma 12' refers to a lemma that appears later and in a different setting; the obliviousness construction should be described or cited precisely.
  4. [Section 6.2, proof of Theorem 4] The expression with subscripts w0 and w is typographically ambiguous and should be written as a convex combination of two terms with consistent subscripts.
  5. [Throughout] There are several minor typos, e.g., 'restrict out attention' in Section 3.3, which should be corrected in a revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central QCL⊆EQP proof is an original derivation, and cited prior work with overlapping authors is external, published, and not used as a substitute for the paper's own arguments.

full rationale

The paper's derivation chain does not reduce any claimed result to its inputs by construction. Theorem 2 (QCL⊆EQP) is obtained from original lemmas on runtime distributions of quantum catalytic Turing machines; the runtime-independence statement of Theorem 8 is an asserted theorem proved (or attempted to be proved) from the catalytic reset condition, not a restatement of the definition of QCL. Lemma 5 uses the Helstrom bound after Lemma 4 supplies a repeated-run estimation protocol; even if this inference is invalid for overlapping runtime distributions, that is a proof gap, not circularity, because it does not assume the equality of runtimes it is used to derive. The cited classical results (BCK+14 for TC1⊆CL and clean register programs; Dul15/CLMP25 for reversibility; SJ08 for DQC1) are external published theorems; the author overlap on several of these citations is real but does not make them load-bearing self-citations, since they carry independent proofs and are not fitted to the present conclusions. The unproved extension 'Theorem 8 extends to any classical observable feature' (Section 4.3) is explicitly flagged as an observation without proof; it invokes the paper's own argument rather than presupposing the target result, so it is an omitted-proof or correctness concern, not a circular one. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported from the authors' prior work, and no known result is repackaged under new coordinates. The main risk in the paper is the correctness of Lemma 5 and Theorem 8, but that risk is distinct from circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces a new computational model (quantum catalytic machines) but no new physical entities. The central proof depends on the exact reset assumption and the absolute halting assumption, plus standard linear algebra and prior classical catalytic results.

assumptions (4)
  • domain assumption Quantum catalytic Turing machines are absolutely halting: they halt with probability 1 for every input and every initial catalytic state.
    Invoked in Lemma 2 to establish orthogonality of configuration states over time. The paper defines 'absolutely halting' but does not prove that all catalytic machines can be made so.
  • domain assumption The catalytic tape must be reset exactly to its initial state at the end of the computation.
    Core to Definition 11 and used throughout, particularly in Lemma 4 to allow repeated runs with the same copy of the catalytic state.
  • standard math The Helstrom bound correctly characterizes optimal state discrimination with one copy of an unknown state.
    Used in the proof of Lemma 5 to connect trace distance to success probability.
  • domain assumption Classical catalytic results such as BCK+14, Dulek's reversibility theorem, and CLMP25 hold as stated.
    These prior results are used as black boxes for Lemma 9 (TC1 via clean register programs) and Lemma 12 (reversibility and obliviousness). The authors overlap with some of those works, but the results are established in the literature.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Catalytic Space." pith.science (2026). https://pith.science/paper/KFXQUQSZ

@misc{pith2026250616324,
  author       = {Pith},
  title        = {Pith review of: Quantum Catalytic Space},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KFXQUQSZ}},
  note         = {Machine review of arXiv:2506.16324}
}
read the original abstract

Space complexity is a key field of study in theoretical computer science. In the quantum setting there are clear motivations to understand the power of space-restricted computation, as qubits are an especially precious and limited resource. Recently, a new branch of space-bounded complexity called catalytic computing has shown that reusing space is a very powerful computational resource, especially for subroutines that incur little to no space overhead. While quantum catalysis in an information theoretic context, and the power of ``dirty'' qubits for quantum computation, has been studied over the years, these models are generally not suitable for use in quantum space-bounded algorithms, as they either rely on specific catalytic states or destroy the memory being borrowed. We define the notion of catalytic computing in the quantum setting and show a number of initial results about the model. First, we show that quantum catalytic logspace can always be computed quantumly in polynomial time; the classical analogue of this is the largest open question in catalytic computing. This also allows quantum catalytic space to be defined in an equivalent way with respect to circuits instead of Turing machines. We also prove that quantum catalytic logspace can simulate log-depth threshold circuits, a class which is known to contain (and believed to strictly contain) quantum logspace, thus showcasing the power of quantum catalytic space. Finally we show that both unitary quantum catalytic logspace and classical catalytic logspace can be simulated in the one-clean qubit model.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Flexible Catalysis

    quant-ph 2025-10 conditional novelty 8.0 of 10

    Flexible catalysis—allowing a catalyst to transform into another valid catalyst—strictly increases which bipartite quantum state extractions are possible under local unitaries and permutation matrices, and generalizes...

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages · cited by 1 Pith paper

  1. [1]

    Catalytic Embeddings of Quantum Circuits

    [ACG+23] Matthew Amy, Matthew Crawford, Andrew N Glaudell, Melissa L Macasieb, Samuel S Mendelson, and Neil J Ross. Catalytic embeddings of quantum circuits. arXiv preprint arXiv:2305.07720,

    work page Pith review arXiv

  2. [6]

    Eliminating intermediate measurements in space-bounded quantum computation

    [FR21] Bill Fefferman and Zachary Remscrim. Eliminating intermediate measurements in space-bounded quantum computation. InProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 1343–1356, New York, NY, USA,

    work page 2021

  3. [9]

    Mixon (https://mathoverflow.net/users/29873/dustin-g mixon)

    [hgm] Dustin G. Mixon (https://mathoverflow.net/users/29873/dustin-g mixon). How many non-orthogonal vectors fit into a complex vector space? MathOverflow. URL:https://mathoverflow.net/q/458508 (version: 2023-11-16). [Imm88] Neil Immerman. Nondeterministic space is closed under complementation.SIAM Journal on computing, 17(5):935–938,

    work page 2023

  4. [12]

    Quantum circuit complexity

    [Yao93] Andrew Chi-Chih Yao. Quantum circuit complexity. In34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993, pages 352–361. IEEE Computer Society,

    work page 1993

  5. [2009]

    A note on amortized branching program complexity

    [Pot17] Aaron Potechin. A note on amortized branching program complexity. In Ryan O’Donnell, editor,32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, volume 79 ofLIPIcs, pages 4:1–4:12. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik,

    work page 2017

  6. [2014]

    Almost-catalytic Computation

    Association for Computing Machinery. [BDRS24] Sagar Bisoyi, Krishnamoorthy Dinesh, Bhabya Rai, and Jayalal Sarma. Almost- catalytic computation.CoRR, abs/2409.07208,

    work page Pith review arXiv

  7. [2015]

    Fully characterizing lossy catalytic computation

    [FMST25] Marten Folkertsma, Ian Mertz, Florian Speelman, and Quinten Tupker. Fully characterizing lossy catalytic computation. In Raghu Meka, editor,16th Innova- tions in Theoretical Computer Science Conference, ITCS 2025, January 7-10, 2025, Columbia University, New York, NY, USA, volume 325 ofLIPIcs, pages 50:1–50:13. Schloss Dagstuhl - Leibniz-Zentrum ...

    work page 2025

  8. [2017]

    Sheffield, and William Wang

    [PSW25] Edward Pyne, Nathan S. Sheffield, and William Wang. Catalytic communication. In Raghu Meka, editor,16th Innovations in Theoretical Computer Science Conference, ITCS 2025, January 7-10, 2025, Columbia University, New York, NY, USA, volume 325 ofLIPIcs, pages 79:1–79:24. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik,

    work page 2025

Show all 12 references
  1. [2021]

    [GJST24] Chetan Gupta, Rahul Jain, Vimal Raj Sharma, and Raghunath Tewari

    Association for Computing Machinery. [GJST24] Chetan Gupta, Rahul Jain, Vimal Raj Sharma, and Raghunath Tewari. Lossy catalytic computation.Computing Research Repository (CoRR), abs/2408.14670,

    arXiv

  2. [2022]

    Tree evaluation is in spaceO(logn·log logn)

    [CM24] James Cook and Ian Mertz. Tree evaluation is in spaceO(logn·log logn). InPro- ceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, page 1268–1278, New York, NY, USA,

    2024

  3. [2024]

    Quantum logspace algorithm for powering matrices with bounded norm.arXiv preprint arXiv:2006.04880,

    [GRZ20] Uma Girish, Ran Raz, and Wei Zhan. Quantum logspace algorithm for powering matrices with bounded norm.arXiv preprint arXiv:2006.04880,

    2006 arXiv

  4. [2025]

    Trading time and space in catalytic branching programs

    [CM22] James Cook and Ian Mertz. Trading time and space in catalytic branching programs. In Shachar Lovett, editor,37th Computational Complexity Conference, CCC 2022, July 20-23, 2022, Philadelphia, PA, USA, volume 234 ofLIPIcs, pages 8:1–8:21. Schloss Dagstuhl - Leibniz-Zentr...

    2022

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.