Defense hold at the University of Luxembourg, Esch-sur-Alzette, Luxembourg.
Quantum computers allow a near-exponential speed-up for specific applications when compared to classical computers. Despite recent advances in quantum computing hardware, the practical use of noisy intermediate-scale quantum computing (NISQ) era devices remains severely limited due to resource constraints such as noise, qubits, gates, circuit depth, and coherence time. Quantum circuit (QC) optimization is an essential mitigation strategy to enable the execution of quantum programs on restricted quantum devices. In this context, ZX-calculus emerged as an alternative to conventional gate-level quantum circuit optimization approaches. Instead of depending upon gate-set-specific rewriting rules, it offers a compact, universal, and semantic-preserving framework for quantum circuit optimization. However, ZX-based quantum circuit optimization faces two challenges in practice. On the one hand, ZX-calculus admits a non-terminating rewriting system. On the other hand, ZX-diagrams lose causality. As a consequence, only a subset of ZX-diagrams that preserve causal flow (CFlow), general flow (GFlow), or Pauli flow allow for the extraction of quantum circuits in polynomial time. The first challenge can be addressed by effective heuristics, search algorithms, and pruning conditions, while the latter is an optimization problem with an upper bound of \mathrmNP^\mathrmNP^#\mathrmP, where the choice of the extraction algorithm can negate ZX-diagram-level improvements. This thesis establishes a ZX-based end-to-end pipeline for quantum circuit optimization that leverages tree search for metric-agnostic ZX-diagram optimization and integer linear programming (ILP) paired with backtracking search to improve the circuit extraction step. The contributions of this thesis are four-fold: 1. First, it presents a comprehensive survey of ZX-based quantum circuit optimization, categorizing existing approaches by the employed optimization strategy, the target metric, and the intended quantum computing architecture. 2. Second, this work formalizes the ZX-diagram optimization problem as the explicit state-space exploration of rewriting rule sequences. 3. Third, the formal approach is put into practice by implementing tree search algorithms, in particular depth-first search (DFS), iterative deepening depth-first search (IDDFS), and limited discrepancy search (LDS), to reduce the T-gate and edge count of ZX-diagrams. Furthermore, the efficacy of different pruning conditions is investigated. Lastly, the novel local-elimination (LE) method is introduced as a metaheuristic to select growing sub-ZX-diagrams around a target spider. Instead of performing tree-search optimization on intractably large ZX-diagrams, local-elimination changes one large optimization problem into a sequence of tractable small searches. All tree search strategies are extensively tested on benchmark data sets that contain different quantum circuit types. 4. Finally, this work improves two-qubit gate count during circuit extraction by introducing an integer linear programming model that replaces the Gaussian elimination (GE) steps present in current circuit extraction algorithms. Pairing the integer linear programming model for circuit extraction with backtracking allows the exploration of multiple solutions that take advantage of gate commutation and cancellation rules during extraction. The last research artifact of this thesis is the introduction of *ZX-benchmark*, a declarative end-to-end optimization pipeline and ZX benchmarking framework to compare different optimization and extraction algorithms on the same data sets and under comparable experimental conditions. To this end, it offers access to multiple data sets and various third-party optimizers. With the intent to provide a framework that is useful beyond the scope of this thesis, it supports configuration files and a unified API to declare experiments. All artifacts produced are in plain-text formats, including JavaScript Object Notation (JSON) and OpenQASM. In summary, the thesis advances ZX-based compilation by connecting metric-agnostic diagram rewriting with extraction-aware optimization in a reusable, end-to-end workflow.
