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.
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.
The theory of fault tolerance is a cornerstone of computing and many modern technologies. With the development of quantum science and engineering, fault tolerance has become increasingly important, as quantum systems are intrinsically susceptible to noise. This thesis presents several advances in quantum fault tolerance and develops new connections between fault tolerance and quantum complexity theory. In Part I, we construct a fault-tolerant quantum computation scheme with constant space overhead and near-logarithmic time overhead. This is the lowest overhead achieved to date and and provides the first rigorous proof that fault tolerance based on quantum low-density parity-check (qLDPC) codes can achieve better asymptotic spacetime overhead than conventional schemes. The construction relies on locally testable qLDPC codes and new quantum state distillation algorithms with improved spacetime overhead. Additionally, a variant of these algorithms yields the first magic state distillation algorithm with constant space overhead. In Part II, we make progress on the quantum probabilistically checkable proofs (PCP) conjecture by using ideas from fault tolerance. We introduce a new circuit-to-Hamiltonian mapping that allows Hamiltonians to inherit the fault tolerance properties of quantum circuits. Using this new mapping, we construct the first known template for quantum locality-preserving gap amplification---the quantum analogue of a central ingredient in the classical PCP theorem---and prove that it amplifies the combinatorial gap. The construction develops a new framework for reasoning about gap amplification in terms of fault-tolerant distributed computation, along with new tools in secure multiparty computation and high-dimensional expanders.
As quantum hardware advances toward fault-tolerant operation, an intermediate stage known as early fault-tolerant quantum computing (EFTQC) is emerging, where partial error correction enables meaningful computation. In this regime, the ability of quantum processors to scale in size and depth has become a crucial factor shaping their achievable performance. This study investigates how finite scalability influences resource requirements for simulating open-shell catalytic systems using Quantum Phase Estimation (QPE). The analysis compares hardware archetypes distinguished by fidelity or operation speed under two representative scalability models. Finite scalability increases qubit and runtime demands yet leaves overall scaling behavior intact, with high-fidelity architectures requiring lower minimum scalability to solve equally sized problems. These effects are largely independent of the chosen scalability model. Extending this framework, we examine runtime competitiveness across hardware and code configurations, incorporating surface-code and quantum Low-Density Parity-Check (LDPC)-based fault tolerance under finite scalability. The results identify operating regimes where high-fidelity architectures remain competitive despite slower gate speeds and show that LDPC codes further expand this regime by reducing space-time overhead. Together, these findings highlight the central role of scalability in quantifying performance and guiding the design of next-generation quantum hardware. Continued progress in scalable architectures will be essential for extending quantum computing to increasingly complex scientific and industrial applications.
This dissertation studies the interplay between quantum and classical computational resources through the lens of computational complexity theory. Part I considers low-energy states of quantum systems. We study the complexity of estimating ground- and excited-state energies of local Hamiltonians, given access to a guiding state promised to have non-negligible overlap with the relevant eigenspace. We formalise access models for such guiding states, examine their properties and relations, and study the problem for physically motivated Hamiltonians. We also study the task of obtaining approximate descriptions of ground states, given QMA-oracle access, in the setting of low-locality reduced density matrices. Part II focuses on quantum probabilistically checkable proof systems (QPCPs). We define a general class of QPCPs that allows adaptivity and multiple unentangled provers, and study its relationship to constant-gap local Hamiltonian problems via quantum reductions. Additionally, we investigate quantum–classical PCPs (QCPCPs), where a quantum verifier has either classical or quantum query access to a classical proof. Part III explores alternative complexity measures: unitary query complexity and sample complexity. For unitary query complexity, we develop a lower-bound technique based on unitary channel discrimination. In the context of sample complexity, we introduce and analyse a new sample-to-sample task, called complement sampling, and study the power of quantum computation with quantum samples over their classical counterparts.
Quantum computers promise to solve computational problems that are inaccessible to classical machines. The reliable execution of large-scale quantum algorithms requires robust operations in the presence of noise. Quantum error correction addresses this challenge by encoding quantum information redundantly across several physical qubits, such that errors can be detected and corrected during a computation. However, no single error-correcting code intrinsically supports an inherently robust, fault-tolerant implementation of all gates needed for universal quantum computing. Moreover, most modern approaches to both quantum error correction and the implementation of universal logical operations on encoded qubits rely on mid-circuit measurements and feed-forward control. These types of operations are technologically demanding, often slow, and prone to high error rates, and they limit the overall success probability of quantum algorithms. In this thesis, we develop fault-tolerant protocols and circuits for quantum error correction and universal logical computation, with an emphasis on implementations compatible with current hardware systems. We first focus on fault-tolerant quantum error correction on small codes. By comparing different protocols, we identify trade-offs between compact circuit constructions and their robustness to noise. We then assess their practical performance by comparing numerical simulations of noisy circuits with experimental data. Beyond the preservation of encoded information, we study how universal logic can be implemented in a fault-tolerant manner on encoded qubits. A central approach considered in this thesis is code switching, in which logical information is transferred between two distinct error-correcting codes that support complementary sets of inherently fault-tolerant logical gates. In combination, these codes give access to a complete universal fault-tolerant logical gate set. In this thesis, we determine conditions that allow us to construct fault-tolerant protocols for code switching. We adapt these protocols to the capabilities of current hardware, thereby enabling the first experimental realization of universal fault-tolerant logic by means of code switching. However, the overall performance of these schemes is limited by slow and noisy mid-circuit measurements. To address this bottleneck, we construct a suite of measurement-free fault-tolerant universal operations that do not require any measurements during the execution of an algorithm. In this framework, error correction and logical operations are implemented coherently as part of the quantum circuit, without mid-circuit measurements or in-sequence classical control. We introduce measurement-free code-switching schemes that can be scaled to arbitrary code distances through concatenation, and which thereby provide, in principle, arbitrarily strong error suppression. We further tailor our approach to the capabilities of current trapped-ion quantum processors. New circuit constructions support the first experimental implementation of a logical quantum algorithm without mid-circuit measurements, demonstrated through Grover's search on three encoded qubits. Together, the results of this thesis expand the toolbox for early fault-tolerant quantum computation. They show how protocols for quantum error correction and universal logical gates can be designed without mid-circuit measurements with realistic hardware constraints in mind, opening new pathways towards universal quantum logic.
Recent years have seen quantum computers move from theory to practice, with the first prototypes of \emph{fault-tolerant} quantum computers capable of correcting their own errors. This marks the beginning of an exciting era of \emph{early fault tolerance}, with the first practical applications on the horizon. Among the most promising is quantum simulation, where a quantum computer is used to study another quantum system, such as molecules or materials. However, a central challenge is how to reliably extract accurate information from these early imperfect devices under realistic constraints, including noise, limited qubit numbers, circuit depth, and control. This thesis addresses this challenge by developing and analyzing algorithms for quantum phase estimation in these regimes, a key primitive for determining the energy spectra. It also considers the problem of learning the underlying dynamics of a quantum system, demonstrating the advantage of active control over passive observation. Together, these results contribute to ongoing efforts to overcome the limitations of early quantum hardware through improved algorithms and classical post-processing.
Quantum computing is entering a transitional regime between noisy intermediate-scale quantum (NISQ) processing and early fault-tolerant quantum computation (FTQC), in which increasingly capable hardware is beginning to support repeated syndrome measurements, partial error correction, and logical-qubit operations, while residual physical and logical errors remain non-negligible. In this regime, error suppression, error mitigation, and quantum error correction are increasingly better viewed as complementary layers of a unified error-reduction strategy rather than as separate approaches, with each acting at a different stage of the quantum computation to improve simulation reliability. Thus, in this review, we provide a practical and forward-looking overview of the principal hardware error sources and the corresponding error suppression and mitigation methods for reducing their impact across the current NISQ-FTQC transition. We discuss hardware-aware circuit design, coherent-error suppression, readout mitigation, noise extrapolation, classical inference, and software-supported workflows, with particular emphasis on their implementation on actual quantum processors. We further examine how error mitigation techniques can be adapted to encoded and logical-qubit settings so that they can operate alongside quantum error correction to suppress residual logical errors and improve the accuracy of computation in the early fault-tolerant regime.