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 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.
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 holds the potential to efficiently solve certain problems believed to be intractable for classical computers. Realizing this potential, however, requires substantial physical resources, including large qubit counts, sufficient connectivity, and long coherence times. As current quantum devices are still far from this regime, the efficient compilation of quantum algorithms into hardware-compatible instructions remains a central challenge in quantum computing, especially for near-term applications. A representative example of such applications is combinatorial optimization, where exponentially large search spaces motivate quantum algorithms that leverage interference to approximate solutions more efficiently than classical heuristics, even at modest system sizes. Two prominent paradigms in this context are quantum annealing and the Quantum Approximate Optimization Algorithm (QAOA): Quantum annealing realizes optimization via continuous-time quantum dynamics implemented on analog hardware, while QAOA is a variational, gate-based approach that builds parameterized quantum circuits from problem-specific Hamiltonians. Both paradigms require compilation strategies tailored to the constraints of their respective hardware architectures. Most existing compilation strategies are problem-agnostic and therefore broadly applicable, yet often suboptimal for specific tasks. This thesis uses the graph coloring problem as a case study to investigate a problem-driven approach to quantum compilation, where structural features of the problem class are exploited to design tailored compilation schemes that offer improved efficiency and scalability for the targeted application. To address hardware connectivity constraints, the presented approaches adopt the parity framework, which encodes long-range interactions into single-qubit terms. This thesis develops two novel problem-driven compilation methods for the graph coloring problem, the Bandwidth-Optimized LHZ layout and the 2D-Twine circuit. The former leverages bandwidth minimization to optimize parity encodings for analog quantum annealers, while the latter constructs QAOA unitaries for gate-based optimization using parallelized Parity Twine circuits. Both approaches are benchmarked against general-purpose methods and demonstrate substantial improvements in qubit usage or circuit complexity. These results illustrate the advantages of incorporating problem structure into the compilation process and provide a proof-of-concept for the effectiveness of problem-driven compilation strategies.
Shuttling-based trapped-ion quantum computers (QCCD) rank among the most mature hardware platforms. Existing and envisaged devices exhibit architectural differences in terms of register layout and connectivity. Platform-specific compilers are required to translate quantum circuits into resource-optimized hardware-level command chains. Hardware platforms and compiler software stacks are mostly developed independently of one another by different research communities. This work aims to bridge these communities by abstracting QCCD architectures and native operations, enabling computer scientists to address compilation problems using generic methods without requiring a deep background in the physical operating principles of the platform. The resulting design space is organized into a small set of architectural archetypes, each posing its own compilation problem. We then select and apply compilation methods to one- and two-dimensional QCCD architectures, finding that the routing overhead scales approximately cubically with the number of qubits for the one-dimensional architecture and approximately quadratically for the two-dimensional one. Extending this to compilation with a quantum error-correction layer reveals additional differences and similarities between the physical and logical levels. We conclude that co-design is a requirement rather than an option, and this work provides the vocabulary, archetypes, and compilation abstraction it needs.
Quantum computers hold the promise of solving certain computational problems significantly faster than classical computers. Unlocking the full potential of quantum hardware depends on our ability to efficiently translate high-level quantum algorithms into executable sequences of quantum operations tailored to the specific constraints of a given device, a task known as quantum compilation. Among the most promising applications is the simulation of quantum systems, such as in quantum chemistry, where scalable, error resilient, and experimentally feasible Hamiltonian simulation techniques are essential. In the first part of this thesis, we present recent advances in the field of quantum compilation, emphasizing on efficient gate decomposition and circuit optimization. In particular, we analyze compilation techniques for Clifford circuits and general single-qubit rotations. Clifford operations play a central role in quantum error correction, the characterization of quantum devices and quantum cryptography. We explore asymptotically optimal decomposition methods, including constructions using either two-qubit gates or global entangling operations, the latter being especially well-suited for platforms like trapped ions. For single-qubit unitaries, we discuss approximation schemes that achieve the theoretically optimal scaling of gate count with respect to the desired precision. Beyond gate synthesis, we examine various hardware-aware optimization strategies aimed at reducing circuit depth and gate overhead. These include techniques for qubit routing in systems with limited connectivity, as well as methods for removing redundant operations. The second and primary, scientific contribution of this thesis focuses on implementation of effective many-body interactions on quantum hardware by combining the system’s native dynamics with control operations, which we call Hamiltonian engineering. Motivated by the central role of Hamiltonian simulation in quantum science, we introduce a general and efficient framework for synthesizing arbitrary target Hamiltonians under mild locality constraints. We propose a novel linear programming (LP) approach that computes pulse sequences consisting of single-qubit π or π/2 rotations applied at certain times during free evolution under the system’s native Hamiltonian. Our LP-based framework offers multiple advantages. First, its classical runtime depends only on the number and locality of the interactions in the system Hamiltonian, not directly on the overall system size. Second, we extend the method to include robustness against common error sources such as finite pulse time effects and systematic control errors, leveraging tools from average Hamiltonian theory and robust composite pulses. Our approach enables the efficient realization of high-fidelity Hamiltonian dynamics with minimal experimental overhead. The scalability of the approach are demonstrated through simulations, including the engineering of a random two-body Hamiltonian on a 225 qubit lattice in under a minute of classical preprocessing. In conclusion, this thesis contributes both theoretical insights and practical tools that bridge the gap between algorithm design and experimental implementation in quantum computing. The techniques developed here are directly applicable to a variety of platforms, including trapped ions, neutral atoms, and superconducting circuits. By advancing the frontiers of Hamiltonian engineering, this work enables more efficient, robust, and scalable quantum simulations on nearterm devices. Finally, it brings us closer to realizing quantum technologies, which are possibly capable of solving meaningful problems.
Practical realizations of quantum computers are poised to deliver outstanding computational capabilities far beyond the reach of any classical supercomputer. While classical systems are reliably implemented using CMOS technology, the fabrication of quantum hardware has not yet reached a commercially viable level of maturity. Nowadays, many different technologies are being developed as competing candidates to build the first error-corrected quantum computer. Among the software resources required to operate such a system, quantum compilers translate a high-level description of a quantum algorithm into low-level, technology-dependent quantum instructions. Many quantum algorithms, including Shor's and Grover's algorithms, require to compute some classical logic functions on the quantum computer. The first part of this thesis deals with the problem of compiling quantum circuits that perform such classical Boolean functions, called oracles, into a fault-tolerant set of instructions. Oracle circuits often demand many resources in terms of the number of qubits and gates. The focus is on compiling quantum circuits starting from multi-level logic networks representing large Boolean functions while minimizing the resource footprint of the obtained quantum circuits. At the same time, the trade-off between memory resources and the number of operations typical of such a compilation process is explored. As part of the effort in reducing the resources required to perform a given quantum program, I also present some quantum circuit optimization techniques. The researched algorithms leverage data structures and techniques borrowed and adapted from classical logic synthesis, e.g., SAT solvers, LUT mapping, and multi-level logic networks. I implemented all the compilation algorithms presented in this thesis as part of open-source projects. In particular, I develop and maintain caterpillar---a C++ header-only library dedicated to the quantum compilation of oracles and quantum memory management. The second part of this thesis describes how to equip quantum programming language compilers with automatic accuracy management. Despite the availability of many of such languages, resource estimation of quantum algorithms does not yet support taking approximation errors into account. This general methodology is applicable to any programming language and I demonstrate its integration into the Q# compiler. The technique consists of providing language support to ease the accuracy-aware programming task. The user can define accuracy parameters that will be automatically optimized according to a constraint and a cost function directly generated from the source code. In the presented practical evaluations, the constraint function is the overall allowed accuracy, while the cost function is application-dependent and related to the number of gates. During the optimization process, such functions are evaluated hundreds of times. For this reason, we extract them as (near-)symbolic expressions, whose evaluation time does not depend on the quantum algorithm size. The algorithms and the methodologies presented in this thesis are part of a widespread effort of the research community to build a complete and efficient software stack to program and control the first practical universal quantum computer.
Quantum computing, leveraging the principles of superposition and entanglement, holds the potential to revolutionize computational problem-solving across a wide array of fields, from cryptography to complex system simulations. However, unlocking the full power of quantum computing requires the development of advanced quantum compilation techniques that can efficiently map high-level algorithms onto physical quantum hardware. This paper delves into state-of-the-art optimization strategies within quantum compilers, with a particular focus on methods such as Relaxed Peephole Optimization (RPO), gate reordering techniques for the Quantum Approximate Optimization Algorithm (QAOA), and reinforcement learning (RL)-driven frameworks. It also explores innovative approaches like distributed quantum compilation, parity quantum optimization, and the Paulihedral framework, all designed to minimize gate counts, reduce circuit depth, and optimize overall resource utilization. A key contribution of this work is the introduction of error mitigation techniques that enhance the fidelity and scalability of quantum circuits, particularly on noisy intermediate-scale quantum (NISQ) devices. Through comprehensive empirical evaluations across a variety of quantum algorithms, the paper demonstrates significant improvements in critical performance metrics such as circuit depth, gate count, and execution efficiency, providing a promising direction for optimizing quantum circuit design tailored to diverse quantum hardware platforms.