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.
In this dissertation, we investigate the computational power of quantum Turing machines operating in bounded space. First, we consider space-bounds that are space-constructible and at least logarithmic in the input size. For such space-bounds, it is shown that quantum Turing machines and probabilistic Turing machines are equivalent in power in the unbounded-error setting, in the sense that each model may simulate the other with at most a constant factor increase in space. From this, it follows that any quantum Turing machine computation can be simulated deterministically with at most a quadratic increase in space, and can be simulated deterministically in time at most exponential in the space-bound. Several other facts regarding quantum complexity classes defined in terms of such space-bounds are also proved. Second, we consider the power of quantum Turing machines restricted to constant space. In this case, we first prove that quantum Turing machines having one-sided error and running in linear time are strictly more powerful than probabilistic Turing machines having either one-sided error or having two-sided bounded error and running in polynomial time. Second, we prove that exact (i.e., accepting with probability 0 or 1) constant-space quantum Turing machines upon which no restrictions on running time are placed can recognize languages that cannot be recognized by any bounded-error constant-space probabilistic Turing machine. ii Acknowledgements I would like to take this opportunity to express my gratitude to a number of people. First, I would like to thank my advisor Eric Bach for all that he has taught me, regarding both theoretical computer science and how to be a researcher in general. His advice and support are greatly appreciated. I would also like to thank Anne Condon for her great advice and for many helpful discussions during my years as a graduate student. This dissertation has benefitted greatly from comments and suggestions by Anne and Eric as well.
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).
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.
In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if built, might be used as a dramatically powerful computational tool. This review is about to tell the story of theoretical quantum computation. I left out the developing topic of experimental realizations of the model, and neglected other closely related topics which are quantum information and quantum communication. As a result of narrowing the scope of this paper, I hope it has gained the benefit of being an almost self contained introduction to the exciting field of quantum computation. The review begins with background on theoretical computer science, Turing machines and Boolean circuits. In light of these models, I define quantum computers, and discuss the issue of universal quantum gates. Quantum algorithms, including Shor's factorization algorithm and Grover's algorithm for searching databases, are explained. I will devote much attention to understanding what the origins of the quantum computational power are, and what the limits of this power are. Finally, I describe the recent theoretical results which show that quantum computers maintain their complexity power even in the presence of noise, inaccuracies and finite precision. I tried to put all results in their context, asking what the implications to other issues in computer science and physics are. In the end of this review I make these connections explicit, discussing the possible implications of quantum computation on fundamental physical questions, such as the transition from quantum to classical physics.
We have seen in the previous chapters that quantum computers seem to be more powerful than classical computers for certain problems. There are limits on the power of quantum computers, however. Since a classical computer can simulate a quantum computer, a quantum computer can only compute the same set of functions that a classical computer can. The advantage of using a quantum computer is that the amount of resources needed by a quantum algorithm might be much less than what is needed by the best classical algorithm. In Section 9.1 we briefly define some classical and quantum complexity classes and give some relationships between them. Most of the interesting questions relating classical and quantum complexity classes remain open. For example, we do not yet know if a quantum computer is capable of efficiently solving an NP-complete problem (defined later). One can prove upper bounds on the difficulty of a problem by providing an algorithm that solves that problem, and proving that it will work within in a given running time. But how does one prove a lower bound on the computational complexity of a problem? For example, if we wish to find the product of two n-bit numbers, computing the answer requires outputting roughly 2n bits and that requires Ω(n) steps (in any computing model with finite-sized gates). The best-known upper bound for integer multiplication is O(n log n log log n) steps. It has proved extremely difficult to derive non-trivial lower bounds on the computational complexity of a problem. Most of the known non-trivial lower bounds are in the ‘black-box’ model (for both classical and quantum computing), where we only query the input via a ‘black-box’ of a specific form. We discuss the black-box model in more detail in Section 9.2. We then sketch several approaches for proving black-box lower bounds. The first technique has been called the ‘hybrid method’ and was used to prove that quantum searching requires Ω(√n) queries to succeed with constant probability. The second technique is called the ‘polynomial method’. We then describe a technique based on ‘block sensitivity’, and conclude with a technique known as the ‘adversary method’.