Tobias Michael Fischbach

Quantum computers allow a near-exponential speed-up for specific applications when compared to classical computers. Despite recent advances in the hardware of quantum computers, their practical usage is still severely limited due to a restricted number of available physical qubits and quantum gates, short coherence time, and high error rates. This paper lays the foundation towards a metric independent approach to quantum circuit optimization based on exhaustive search algorithms. This work uses depth-first search and iterative deepening depth-first search. We rely on ZX calculus to represent and optimize quantum circuits through the minimization of a given metric (e.g. the T-gate and edge count). ZX calculus formally guarantees that the semantics of the original circuit is preserved. As ZX calculus is a non-terminating rewriting system, we utilise a novel set of pruning rules to ensure termination while still obtaining high-quality solutions. We provide the first formalization of quantum circuit optimization using ZX calculus and exhaustive search. We extensively benchmark our approach on 100 standard quantum circuits. Finally, our implementation is integrated in the well-known libraries PyZX and Qiskit as a compiler pass to ensure applicability of our results.

Quantum computing promises significant speed-ups for certain algorithms but the practical use of current noisy intermediate-scale quantum (NISQ) era computers remains limited by resources constraints (e.g., noise, qubits, gates, and circuit depth). Quantum circuit optimization is a key mitigation strategy. In this context, ZX-calculus has emerged as an alternative framework that allows for semantics-preserving quantum circuit optimization. We review ZX-based optimization of quantum circuits, categorizing them by optimization techniques, target metrics and intended quantum computing architecture. In addition, we outline critical challenges and future research directions, such as multi-objective optimization, scalable algorithms, and enhanced circuit extraction methods. This survey is valuable for researchers in both combinatorial optimization and quantum computing. For researchers in combinatorial optimization, we provide the background to understand a new challenging combinatorial problem: ZX-based quantum circuit optimization. For researchers in quantum computing, we classify and explain existing circuit optimization techniques.

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.

In this talk I presented an overview of ZX-based quantum circuit optimization and introduced our ZX-Benchmark Framework to the public.

This poster summarizes our previous results on the usage and challenges of exhaustive search of ZX-diagrams. The non-terminating nature of ZX-calculus and the massive state-space require smarter search strategies. I used my presentation to make the case for the use machine learning for ZX-diagram optimization.

Quantum computers allow a near-exponential speed-up for specific applications when compared to classical computers. Despite recent advances in the hardware of quantum computers, their practical usage is still severely limited due to a restricted number of available physical qubits and quantum gates, short coherence time, and high error rates. This paper lays the foundation towards a metric independent approach to quantum circuit optimization based on exhaustive search algorithms. This work uses depth-first search and iterative deepening depth-first search. We rely on ZX calculus to represent and optimize quantum circuits through the minimization of a given metric (e.g. the T-gate and edge count). ZX calculus formally guarantees that the semantics of the original circuit is preserved. As ZX calculus is a non-terminating rewriting system, we utilise a novel set of pruning rules to ensure termination while still obtaining high-quality solutions. We provide the first formalization of quantum circuit optimization using ZX calculus and exhaustive search. We extensively benchmark our approach on 100 standard quantum circuits. Finally, our implementation is integrated in the well-known libraries PyZX and Qiskit as a compiler pass to ensure applicability of our results.