This is the second in a series of "graphical grokking" papers in which we study how stabiliser codes can be understood using the ZX-calculus. In this paper we show that certain complex rules involving ZX-diagrams, called spider nest identities, can be captured succinctly using the scalable ZX-calculus, and all such identities can be proved inductively from a single new rule using the Clifford ZX-calculus. This can be combined with the ZX picture of CSS codes, developed in the first "grokking" paper, to give a simple characterisation of the set of all transversal diagonal gates at the third level of the Clifford hierarchy implementable in an arbitrary CSS code.
The ZX-calculus is a graphical language for suitably represented tensor networks, called ZX-diagrams. Calculations are performed by transforming ZX-diagrams with rewrite rules. The ZX-calculus has found applications in reasoning about quantum circuits, condensed matter systems, quantum algorithms, quantum error correcting codes, and counting problems. A key notion is the stabiliser fragment of the ZX-calculus, a subfamily of ZX-diagrams for which rewriting can be done efficiently in terms of derived simplifying rewrites. Recently, higher dimensional qudits - in particular, qutrits - have gained prominence within quantum computing research. The main contribution of this work is the derivation of efficient rewrite strategies for the stabiliser fragment of the qutrit ZX-calculus. Notably, this constitutes a first non-trivial step towards the simplification of qutrit quantum circuits. We then give further unexpected areas in which these rewrite strategies provide complexity-theoretic insight; namely, we reinterpret known results about evaluating the Jones polynomial, an important link invariant in knot theory, and counting graph colourings.
While the quantum circuit model remains the dominant framework for representing and executing quantum algorithms, it is not always the most optimal framework for representing the quantum circuit’s deeper structure. In a standard circuit diagram, computation is shown mainly as a time ordered sequence of gates acting on qubit wires. ZX calculus, by contrast, represents the same process using two families of generators, the Z spiders and the X spiders, together with wires and Hadamard structure, so that algebraic identities, entanglement structure, and rewrite based simplifications become visible directly in the diagram itself. ZX calculus is not another visual representation for the same quantum circuit we have been using, but a graphical calculus in which diagrams carry both computational meaning and transformation rules. This is also the reason for the name ZX ; the formalism is built around the interaction between Z -type and X -type observables, phases, and basis changes. By turning matrix manipulations into diagrammatic rewrites, ZX calculus reduces much of the redundancies and abstract nature usually associated with quantum computation and provides a more structural language for understanding, optimizing, and verifying quantum processes.
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.
Complete sets of graphical rewrite rules enable fully graphical reasoning about quantum computations and have been an area of active research for more than a decade. Many recent applications of the ZX-calculus have made use of the close correspondence between ZX-diagrams and computations in the one-way model of measurement-based quantum computation. In this model, various kinds of flow properties ensure deterministic implementability; for ZX-diagrams, these same properties allow efficient translation into quantum circuits (a problem that is known to be #P-hard in general). Therefore, flow-preserving ZX-calculus rewrite rules are of strong interest.
Here, we extend the set of flow-preserving rules appearing in the literature with a few new rules and extensions of existing rules. We then show that the resulting rule set is complete for all flow-preserving translations between ZX-diagrams of appropriate form. The proof employs a manifestly flow-preserving equivalent of circuit extraction, where a diagram with gflow is transformed, using only flow-preserving rewrite rules, into a diagram with causal flow.
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 %.