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.
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.
Additional qubits can reduce the depth of a quantum circuit by providing workspace for parallel computation, but standard constructions assume that this workspace is initialized in a known state. In this work we study catalytic implementations, i.e. asking whether dirty qubits can instead be used provided that their joint state including any entanglement with other registers is restored exactly at the end of the computation. We show that every n-qubit Clifford circuit has a catalytic implementation of depth O(logn) using O(n2/log2n) catalytic qubits and no clean qubits, matching the asymptotic depth achievable when clean workspace is available. We extend this approach to diagonal elements of any fixed level Ck of the Clifford hierarchy, which admit catalytic implementations of depth O(log(n+1)) with O(nk/log(n)) gates and O(nk/log2(n)) catalytic qubits, as well as to semi-Clifford Gates.
Despite rapid advances in quantum hardware and the appearance of the first devices with active error correction by 2025, fully fault-tolerant quantum computation remains a distant milestone. This thesis investigates how additional resources can enhance computational power across various stages of quantum device development. Part I examines computation before error correction, where only constant-depth circuits are feasible. We introduce LAQCC, which augments such circuits with intermediate measurement and classical computation, and show that this model enables far more powerful computations. In Part II, we study the early fault-tolerance regime, where the main limitation is the number of logical qubits. Inspired by the classical catalytic space model, we introduce a quantum analogue in which a space-bounded quantum machine has access to an auxiliary catalytic register that may be modified during the computation but must be restored at the end. We show that this catalytic resource increases the power of quantum space-bounded machines. In Part III, we study the full fault-tolerant regime and look at the problem of estimating the ground-state energy of a Local Hamiltonian which is central to quantum chemistry. Here, we study the BQP-hard Guided Local Hamiltonian problem (estimating ground-state energy given a guiding state), showing its hardness persists over a broader parameter range. Furthermore, by introducing the Guidable Local Hamiltonian problem, we provide complexity-theoretic evidence that classical guiding-state heuristics are as powerful as quantum ones, in this setting. Finally, this problem also provides restrictions on possible gap-amplification procedures, relevant for the quantum PCP conjecture.
Quantum computers promise transformative speedups, but environmental noise destroys their fragile states. Conventional quantum error correction (QEC) encodes information redundantly across physical qubits, yet fails above a threshold of about 1% and incurs polynomial qubit overhead. A recent theorem from the resource theory of coherence shows that catalytic covariant operations amplify coherence at an unbounded rate, but this result has never been cast as an operational protocol. The challenge is to turn an asymptotic theorem into a recovery scheme that works at any noise strength with realistic resources. Here we show that catalytic coherence amplification can be cast as an error-correction primitive, Catalytic Quantum Error Correction (CQEC), which recovers a known target state from noisy copies without any error magnitude threshold whenever the target's coherent modes are preserved. In an effective model of the recovery map, fidelity exceeds 0.99 across 200 noise configurations spanning d = 4-64; the catalyst cost drops from the constructive bound n* ~ d^4 e^(2 gamma) to 32 copies at matched fidelity (10^4- to 10^9-fold) via a pipeline of dynamical decoupling, Clifford twirling, and recursive swap-test purification. A first explicitly CPTP, exactly covariant joint-channel implementation validates genuine recovery under dephasing at small dimension (0.54 -> 0.77) while showing that shallow circuits consume the catalyst, quantifying the model-vs-channel gap. These results turn an abstract resource-theoretic statement into a concrete protocol candidate complementary to stabilizer- and purification-based QEC; an open-source package reproducing the benchmarks accompanies this work (arXiv:2603.25774, https://github.com/deeptell-inc/cqec).
We prove maximal separations: n-qubit systems can have Θ(n) ergotropy, while every efficient process extracts negligible work, even for Hamiltonians consisting of single-qubit terms. We establish an unconditional existential separation and give an explicit construction in the random oracle model. Assuming the existence of quantum-secure pseudorandom functions, this separation extends to the plain model.
This work uncovers an important connection between ergotropy and the complexity of catalytic computation---computation where auxiliary qubits must be finally restored to their initial state. Relative to a random oracle, we establish relational and decision problems that: (i) can be solved efficiently with λ catalysts; but (ii) cannot be solved by any algorithm with cλ catalysts, for any c<1. We show this by proving query lower bounds for quantum-space bounded algorithms.
As a consequence, for computational ergotropy, catalysts prove to be surprisingly powerful---there is a family of Hamiltonians and states for which catalysts enable efficient extraction of the full Θ(n) ergotropy, while every efficient non-catalytic process extracts negligible work. Furthermore, catalysts also allow us to introduce and instantiate the notion of pseudoergotropy---analogous to pseudorandomness. On the other hand, we show catalysts do not change (information-theoretic) ergotropy.
Finally, our work also sheds light on the classical aspect of the problem. First, most of our constructions rely on classical states and Hamiltonians and therefore imply analogous results for classical ergotropy. Second, we show that certain proof of quantumness protocols can be used to generically separate classical and quantum catalytic ergotropy.
Quantum catalysis, the ability to enable previously impossible transformations by using auxiliary systems without degrading them, has emerged as a powerful tool in various resource theories. Although catalytically enabled state transformations have been formally characterized by the monotonic behavior of entropic quantifiers (e.g., the von Neumann entropy or nonequilibrium free energy), such characterizations often rely on unphysical assumptions, namely, the ability of using catalysts of infinitely large dimension. This approach offers very limited insights into the practical significance of using catalysis for quantum information processing. Here, we address this problem across a broad class of quantum resource theories. Leveraging quantum information tools beyond the asymptotic regime, we establish sufficient conditions for the existence of catalytic transformations with finite-size catalysts. We further unveil connections between finite-size catalysis and multicopy transformations. Notably, we discover a phenomenon of catalytic resonance: by carefully tailoring the catalysts's state, one can drastically reduce the required dimension of the catalyst, thus enabling efficient catalytic transformations with minimal resources. Finally, we illustrate our findings with examples from the resource theories of entanglement and thermodynamics, as well in the context of catalytic unitary transformations.
If a set G of quantum gates is countable, then the operators that can be exactly represented by a circuit over G form a strict subset of the collection of all unitary operators. When G is universal, one circumvents this limitation by resorting to repeated gate approximations: every occurrence of a gate which cannot be exactly represented over G is replaced by an approximating circuit. Here, we introduce catalytic embeddings, which provide an alternative to repeated gate approximations. With catalytic embeddings, approximations are relegated to the preparation of a fixed number of reusable resource states called catalysts. Because the catalysts only need to be prepared once, when catalytic embeddings exist they always produce shorter circuits, in the limit of increasing gate count and target precision. In the present paper, we lay the foundations of the theory of catalytic embeddings and we establish several of their structural properties. In addition, we provide methods to design catalytic embeddings, showing that their construction can be reduced to that of a single fixed matrix when the gates involved have entries in well-behaved rings of algebraic numbers. Finally, we showcase some concrete examples and applications. Notably, we show that catalytic embeddings generalize a technique previously used to implement the Quantum Fourier Transform over the Clifford+T gate set with O(n) gate approximations.