Optimising quantum circuits to minimise resource usage is crucial, especially with near-term hardware limited by quantum volume. This paper introduces an optimisation algorithm aiming to minimise non-Clifford gate count and two-qubit gate count by building on ZX-calculus-based strategies. By translating a circuit into a ZX-diagram it can be simplified before being extracted back into a circuit. We assert that simplifications preserve a graph-theoretic property called causal flow. This has the advantage that qubit lines are well defined throughout, permitting a trivial extraction procedure and in turn enabling the calculation of an individual transformation's impact on the resulting circuit. A general procedure for a decision strategy is introduced, inspired by an existing heuristic based method. Both phase teleportation and the neighbour unfusion rule are generalised. In particular, allowing unfusion of multiple neighbours is shown to lead to significant improvements in optimisation. When run on a set of benchmark circuits, the algorithm developed reduces the two-qubit gate count by an average of 19.8%, beating both the previous best ZX-based strategy (14.6%) and non-ZX strategy (18.5%) at the time of publication. This lays a foundation for multiple avenues of improvement. A particularly effective strategy for optimising QFT circuits is also noted, resulting in exactly one two-qubit gate per non-Clifford gate.
Optimising quantum circuits to minimise resource usage is crucial, especially with near-term hardware limited by quantum volume. This paper introduces an optimisation algorithm aiming to minimise non-Clifford gate count and two-qubit gate count by building on ZX-calculus-based strategies. By translating a circuit into a ZX-diagram it can be simplified before being extracted back into a circuit. We assert that simplifications preserve a graph-theoretic property called causal flow. This has the advantage that qubit lines are well defined throughout, permitting a trivial extraction procedure and in turn enabling the calculation of an individual transformation's impact on the resulting circuit. A general procedure for a decision strategy is introduced, inspired by an existing heuristic based method. Both phase teleportation and the neighbour unfusion rule are generalised. In particular, allowing unfusion of multiple neighbours is shown to lead to significant improvements in optimisation. When run on a set of benchmark circuits, the algorithm developed reduces the two-qubit gate count by an average of 19.8%, beating both the previous best ZX-based strategy (14.6%) and non-ZX strategy (18.5%) at the time of publication. This lays a foundation for multiple avenues of improvement. A particularly effective strategy for optimising QFT circuits is also noted, resulting in exactly one two-qubit gate per non-Clifford gate.
We present a completely new approach to quantum circuit optimisation, based on the ZX-calculus. We first interpret quantum circuits as ZX-diagrams, which provide a flexible, lower-level language for describing quantum computations graphically. Then, using the rules of the ZX-calculus, we give a simplification strategy for ZX-diagrams based on the two graph transformations of local complementation and pivoting and show that the resulting reduced diagram can be transformed back into a quantum circuit. While little is known about extracting circuits from arbitrary ZX-diagrams, we show that the underlying graph of our simplified ZX-diagram always has a graph-theoretic property called generalised flow, which in turn yields a deterministic circuit extraction procedure. For Clifford circuits, this extraction procedure yields a new normal form that is both asymptotically optimal in size and gives a new, smaller upper bound on gate depth for nearest-neighbour architectures. For Clifford+T and more general circuits, our technique enables us to to `see around' gates that obstruct the Clifford structure and produce smaller circuits than naïve `cut-and-resynthesise' methods.
In the near term, programming quantum computers will remain severely limited by low quantum volumes.Therefore, it is desirable to implement quantum circuits with the fewest resources possible.For the common Clifford+T circuits, most research is focused on reducing the number of T gates, since they are an order of magnitude more expensive than Clifford gates in quantum error corrected encoding schemes.However, this optimization sometimes leads to more 2-qubit gates, which, even though they are less expensive in terms of fault-tolerance, contribute significantly to the overall circuit cost.Approaches based on the ZX-calculus have recently gained some popularity in the field, but reduction of 2-qubit gates is not their focus.In this work, we present an alternative for improving 2-qubit gate count of a quantum circuit with the ZX-calculus by using heuristics in ZX-diagram simplification.Our approach maintains the good reduction of the T gate count provided by other strategies based on ZX-calculus, thus serving as an extension for other optimization algorithms.Our results show that combining the available ZX-calculus-based optimizations with our algorithms can reduce the number of 2-qubit gates by as much as 40 % compared to current approaches using ZXcalculus.Additionally, we improve the results of the best currently available optimization technique of Nam et.al [22] for some circuits by up to 15 %.
Traditional quantum circuit optimization is performed directly at the circuit level. Alternatively, a quantum circuit can be translated to a ZX-diagram which can be simplified using the rules of the ZX-calculus, after which a simplified circuit can be extracted. However, the best-known extraction procedures can drastically increase the number of 2-qubit gates. In this work, we take advantage of the fact that local changes in a ZX-diagram can drastically affect the complexity of the extracted circuit. We use a pair of congruences (i.e., non-simplification rewrite rules) based on the graph-theoretic notions of local complementation and pivoting to generate local variants of a simplified ZX-diagram. We explore the space of equivalent ZX-diagrams generated by these congruences using simulated annealing and genetic algorithms to obtain a simplified circuit with fewer 2-qubit gates. On randomly generated circuits, our method can outperform state-of-the-art optimization techniques for low-qubit (<10) circuits. On a set of previously reported benchmark circuits with <=14 qubits, our method outperforms off-the-shelf methods in 87% of cases, consistently reducing overall circuit complexity by an additional ~15-30% and eliminating up to 46% of 2-qubit gates. These preliminary results serve as a proof-of-concept for a new circuit optimization strategy in the ZX-calculus.
We present a method for reducing the number of non-Clifford quantum gates, in particularly T-gates, in a circuit, an important task for efficiently implementing fault-tolerant quantum computations. This method matches or beats previous approaches to ancillae-free T-count reduction on the majority of our benchmark circuits, in some cases yielding up to 50% improvement. Our method begins by representing the quantum circuit as a ZX-diagram, a tensor networklike structure that can be transformed and simplified according to the rules of the ZX-calculus. We then extend a recent simplification strategy with a different ingredient, phase gadgetization, which we use to propagate non-Clifford phases through a ZX-diagram to find nonlocal cancellations. Our procedure extends unmodified to arbitrary phase angles and to parameter elimination for variational circuits. Finally, our optimization is self-checking, in the sense that the simplification strategy we propose is powerful enough to independently validate equality of the input circuit and the optimized output circuit. We have implemented the routines of this paper in the open-source library pyzx.
Quantum computers allow a near-exponential speed-up for specific applications when compared to classical computers. Despite recent advances of quantum computing hardware, the practical use of NISQ era devices remains severely limited due to resources constraints (e.g., noise, qubits, gates, circuit depth, and coherence time). 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 QC optimization approaches. Instead of depending upon gate set specific rewriting rules, it offers a compact, universal and semantics-preserving framework for QC optimization. However, ZX-based QC 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 CFlow, GFlow or Pauli flow allow for the extraction of QCs 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 NPNP#P, where the choice of the extraction algorithm can negate ZX-diagram level improvements. This thesis establishes a ZX-based end-to-end pipeline for QC optimization that leverages tree search for metric-agnostic ZX-diagram optimization and \gls{ilp} paired with backtracking search to improve the circuit extraction step. The contributions of this thesis are four-fold: (i) First, it presents a comprehensive survey of ZX-based QC optimization, categorizing them by the employed optimization strategy, the target metric, and the intended quantum computing architecture. (ii) Second, this work formalizes the ZX-diagram optimization problem as the explicit state-space exploration of rewriting rule sequences. (iii) Thirdly, the formal approach is put into practice by implementing tree search algorithms, in particular DFS, IDDFS, and LDS, to reduce the T-gate, and Edge count of ZX-diagrams. Furthermore, the efficacy of different pruning conditions are investigated. Lastly, the novel Local-Elimination (LE) is introduced as a metaheuristic to select growing sub ZX-diagrams around a target spider. Instead of performing tree search optimization on intractable large ZX-diagrams, LE 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 QC types. (iv) Finally, this work enhances two-qubit gate count during circuit extraction by introducing an ILP model that replaces the Gaussian Elimination steps present in current circuit extraction algorithms. Pairing the ILP 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 \emph{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 offer a framework that is useful beyond the scope of this thesis, the framework provides support of configuration files and a unified API to declare experiments. All artifacts produced are in the form of plain text formats (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 the noisy intermediate-scale quantum (NISQ) era, two-qubit gates in quantum circuits are more susceptible to noise than single-qubit gates. Therefore, reducing the number of two-qubit gates is crucial for improving circuit efficiency and reliability. As quantum circuits scale up, the optimization search space becomes increasingly complex, leading to challenges such as low efficiency and suboptimal solutions. To address these issues, this paper proposes a quantum circuit optimization approach based on dynamic grouping and ZX-calculus. First, a random strategy-based dynamic grouping method partitions the circuit into multiple subcircuits. Second, a ZX-calculus guided k-step lookahead search performs equivalent subcircuit filtering to minimize two-qubit gate counts. Third, a delay-aware placement method optimizes the recombined circuit to reduce the overall gate count. Finally, simulated annealing iteratively updates the grouping strategy to achieve an optimized two-qubit gate count. Experimental results on benchmark datasets demonstrate the effectiveness and superiority of the proposed method in reducing two-qubit gates. Compared to the original circuits, the approach achieves an average reduction of 18% in two-qubit gates. It outperforms classical methods with up to 25% reduction, especially on gf circuits, and shows a 4% average improvement over heuristic ZX-calculus-based methods, validating its efficiency.