One of the main challenges the implementation of quantum optimization algorithms has been facing in the last year is the connectivity of qubits on quantum chips. The parity architecture has emerged as an approach to address this issue by trading qubit connectivity for an overhead in the number of physical qubits by encoding the parity of logical qubits. This qubit overhead comes with so-called parity constraints that can be implemented geometrically locally on the quantum chip. While the parity architecture is suitable for both analog and digital quantum computing, we focus on the digital side in this thesis, and present new insights on the parity approach from two perspectives. First, we investigate its resource requirements for quantum optimization, in particular for the Quantum Approximate Optimization Algorithm (QAOA), and propose a constructive algorithm to reduce these requirements compared to previous strategies. In addition, by viewing the parity constraints as stabilizers, we introduce a strategy to conserve the parity constraints throughout the execution of the QAOA. This is in contrast to previous work on the parity architecture, where the parity constraints were typically enforced via additional energy penalties. Second, we show how the parity framework can be used for universal quantum computation, and how cornerstone algorithms like the quantum Fourier transform benefit from this new approach. Our method essentially allows to trade a high circuit-depth for a qubit overhead, while at the same time offering more flexibility in circuit design by enabling on-the-fly recoding of physical qubits. Furthermore, we present a universal quantum computing approach in the parity architecture based on quantum measurements, which allows for additional reductions in circuit depth. Finally, we outline how the parity architecture can be exploited for quantum error correction. With these findings, we aim to contribute to building the bridge between the current era of non-error-corrected hardware and fault-tolerant quantum computing.
One of the main challenges the implementation of quantum optimization algorithms has been facing in the last year is the connectivity of qubits on quantum chips. The parity architecture has emerged as an approach to address this issue by trading qubit connectivity for an overhead in the number of physical qubits by encoding the parity of logical qubits. This qubit overhead comes with so-called parity constraints that can be implemented geometrically locally on the quantum chip. While the parity architecture is suitable for both analog and digital quantum computing, we focus on the digital side in this thesis, and present new insights on the parity approach from two perspectives. First, we investigate its resource requirements for quantum optimization, in particular for the Quantum Approximate Optimization Algorithm (QAOA), and propose a constructive algorithm to reduce these requirements compared to previous strategies. In addition, by viewing the parity constraints as stabilizers, we introduce a strategy to conserve the parity constraints throughout the execution of the QAOA. This is in contrast to previous work on the parity architecture, where the parity constraints were typically enforced via additional energy penalties. Second, we show how the parity framework can be used for universal quantum computation, and how cornerstone algorithms like the quantum Fourier transform benefit from this new approach. Our method essentially allows to trade a high circuit-depth for a qubit overhead, while at the same time offering more flexibility in circuit design by enabling on-the-fly recoding of physical qubits. Furthermore, we present a universal quantum computing approach in the parity architecture based on quantum measurements, which allows for additional reductions in circuit depth. Finally, we outline how the parity architecture can be exploited for quantum error correction. With these findings, we aim to contribute to building the bridge between the current era of non-error-corrected hardware and fault-tolerant quantum computing.
Quantum computing capabilities have developed rapidly in the last years, both in terms of experimental control of quantum systems and theoretical knowledge of quantum algorithms. During this time, the field has progressed from few-qubit prototypes to small computers that can do non-trivial calculations. In a few cases, these calculations approach the current limits of what classical computers can achieve. At this point in time, it is critical to get the maximal performance out of the available quantum hardware, which requires practical applications, smart algorithms, error mitigation and powerful decoding strategies. One near-term application of these quantum devices is quantum optimization, which utilizes quantum computers to solve combinatorial optimization problems. The way these problems are encoded on the quantum device is crucial and often requires both hardware-independent as well as hardware-specific ideas. A core part of this process is compilation, which translates the high-level quantum algorithm to instructions that can be executed on the physical quantum computer. In this thesis we focus on a specific kind of compilation, which originates from the Lechner-Hauke-Zoller model. We present the parity architecture, which is a hardware-independent way to compile arbitrary combinatorial optimization problems to quantum systems. With the parity architecture, analog and digital quantum algorithms can be executed using only local interactions, at the cost of a qubit overhead. First, we introduce a mathematical framework for the parity compiler using linear algebra and give some practical examples. This framework also allows the encoding of higher-order interactions directly, without the need to convert them to quadratic terms. We then benchmark the resource requirements of the parity architecture for digital algorithms, comparing against standard methods that use qubit routing. After that, we show how to compile for digital quantum devices with arbitrary connectivity. Here, we relax the condition that the interactions in the parity architecture are all completely local, resulting in a more flexible compilation approach. Finally, we show that parity compilation can be done constructively for any optimization problem at the cost of a qubit overhead. This qubit overhead can then be minimized by performing a search through different configurations.
Quantum computation holds the promise of solving certain complex problems exponentially faster than classical computers. However, the high prevalent noise in current quantum devices impedes the accurate execution of even basic algorithms. This can be remedied by protecting quantum information with a quantum error-correcting code, where the logical information of an algorithmic qubit is spread across multiple physical qubits. Individual quantum errors are then located and corrected by the fault-tolerant measurement of multi-qubit stabilizer operators (parity checks). Unfortunately, error correction and fault tolerance both impose large demands on the qubit overhead: hundreds to thousands of physical qubits per logical qubit.
We reduce the spacetime cost of fault tolerance by redesigning key building blocks of an error-corrected quantum computer. First, we develop a combinatorial proof with flag fault tolerance that exponentially reduces the extra qubits needed to measure a stabilizer of any size, while tolerating one fault. We leverage these proofs to then design state preparation circuits for the Steane and Golay codes with 100% yield. Next, we improve error correction on a planar layout by showing that a distance-four code encoding six logical qubits protects information as well as the distance-five surface code, using one-tenth as many physical qubits. Finally, we optimize the time overhead of logical gates in surface code quantum computers by protecting measurement results with a classical code, cutting computation time by a factor of two to six. Our hardware-agnostic optimizations of fault tolerance overheads thus suggest new routes to advance the timeline of error-free quantum computing.
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.
Quantum computation promises to revolutionize information processing by exploiting superposition and entanglement, enabling applications such as quantum simulation, combinatorial optimization, and secure quantum communication. Beyond individual processors, the quantum internet aims to connect quantum nodes through entanglement distribution, enabling distributed computation. However, quantum states are fragile: environmental interactions, imperfect gate operations, and measurement errors can quickly degrade encoded information. Reliable quantum computation therefore requires carefully designed quantum error-correcting codes and fault-tolerant protocols. Unlike classical redundancy schemes, quantum error correction must preserve delicate phase relationships and relies on indirect error detection through syndrome extraction with ancillary qubits, enabling error identification without collapsing encoded states. Topological codes, in particular, emerged early as the preferred choice for many architectures due to their planar structure, local interactions, and natural support for fault-tolerant logical operations. Color codes, for instance, allow transversal implementation of all Clifford gates, whereas non-Clifford operations require magic-state injection. More recent constructions, including quantum low-density parity-check codes, offer higher encoding rates and reduced resource overhead, but require long-range qubit connectivity and more complex protocols. Despite experimental progress, several challenges remain. Many platforms exhibit biased noise, motivating codes that exploit channel asymmetry. Real-time decoding remains a critical bottleneck, as fault-tolerant computation requires low-latency processing of rapidly generated syndrome data. Fault-tolerant logical state initialization also remains resource-intensive and scales poorly with code distance. Addressing these challenges, this thesis develops a unified framework spanning theory and experiment. It provides precise performance analysis of quantum error-correcting codes in the low physical error-rate regime, introduces codes tailored to biased noise, develops fast low-complexity decoding algorithms for real-time operation, and presents modular and efficient protocols for fault-tolerant state preparation of CSS codes. The latter is demonstrated experimentally through the preparation of a logical zero state of the Golay code on the Quantinuum H2 trapped-ion quantum computer.
Quantum computing has made significant advancements in the last years in both hardware and software. Unfortunately, the currently available Noisy Intermediate-Scale Quantum (NISQ) hardware is still heavily affected by noise. Many optimization techniques have been developed to reduce the negative effects thereof, which, however, only works up to a certain point. Therefore, scaling quantum applications from currently considered small research examples to industrial applications requires error-correction techniques to execute quantum circuits in a fault-tolerant fashion and enter the Fault-Tolerant Quantum Computing (FTQC) era. These error-correction techniques introduce dramatic qubit overheads, leading to the requirement of tens of thousands of qubits already for toy-sized examples. Hence, quantum circuit optimization that reduces qubit overheads when shifting from the NISQ to the FTQC era is essential. This raises the question, whether we need to start from scratch, or whether current state-of-the-art optimization techniques can be used as a basis for this. To approach this question, this work investigates the effects of different optimization passes on a representative selection of quantum circuits. Since hardly any tools to automatically design and evaluate FTQC quantum circuits exist yet, we utilize resource estimation to compare the (potential) benefits gained by applying NISQ quantum circuit optimization to estimated FTQC resource requirements. The Results indicate that, indeed, the estimated resource requirements for FTQC can be improved by applying NISQ quantum circuit optimization techniques. At the same time, more detailed investigations show what techniques lead to more benefits for FTQC compared to others, providing guidelines for the transfer of NISQ optimization techniques to the FTQC era.
Motivated by recent breakthroughs in the development of spin-based quantum processing units based on exchange-only (EO) spin qubits, we provide a roadmap for the implementation of quantum algorithms on the EO platform, ranging from the NISQ to the fault-tolerant era. To provide an algorithm-driven perspective on the scaling of quantum chips, we consider a range of applications targeting different stages of hardware maturity and formulate requirements for a successful realization. We show that the compilation method Parity Twine perfectly complements the hardware's capabilities to perform tasks such as the quantum Fourier transform or QAOA. Furthermore, we describe an error detection technique native to Parity Twine, which EO qubits can leverage in a unique and advantageous way to improve algorithm performance. Finally, since both near-term algorithmic benchmarks and a long-term perspective can be found in digital quantum simulation, we specifically discuss the fermionic fast Fourier transform and the simulation of Fermi-Hubbard models. The latter is explicitly discussed in the context of quantum error correction and a partially fault-tolerant realization. By providing detailed resource estimates and identifying scaling bottlenecks on each level, our work offers a quantitative perspective on EO-based quantum computing and will inform future hardware design choices.