Diagrammatic reasoning via languages such as ZX Calculus is a powerful tool in theoretical quantum computing. However, physical quantum computers do not understand diagrams and require explicit quantum circuits as inputs. Finding a circuit equivalent to the given diagram is known as circuit extraction. Such problems in graphical calculi form a limitation preventing the wider adoption of diagrammatic reasoning. Computational complexity theory formalises the difficulty of problems. For ZX diagrams, the circuit extraction problem is #P-hard and unlikely to have an efficient algorithm. Therefore, partial solutions are critical. Currently, efficient circuit extraction is only possible for diagrams containing a structure of so-called Pauli flow. This structure is necessary and sufficient for robust determinism in measurement-based quantum computation (MBQC) – a model of quantum computation, an alternative to circuits, where adaptive single-qubit measurements drive computation. Thus, Pauli flow links MBQC, ZX Calculus, and the circuit model. It is known how to find flow structures in polynomial time when they exist; nevertheless, their lengthy and complex definitions often hinder working with them. In this thesis, I present contributions to two connected topics: the hardness of problems in graphical calculi and Pauli flow as a method for overcoming circuit extraction. First, I show that circuit extraction can be #P-hard for phase-free ZH diagrams, extending the previous result for ZX diagrams. I also establish a relation between phase-free ZH and
NP⧣P class. This involves weakening the oracle, crafting a complete problem, and encoding the problem into phase-free ZH. My next contribution concerns Pauli flow. I simplify the Pauli flow definition by providing a new algebraic interpretation. This involves defining two matrices arising from the adjacency matrix of the underlying graph. Then, Pauli flow corresponds to the existence of a right-inverse of the first matrix, which, when multiplied by the second matrix, results in a matrix of a directed acyclic graph. Based on the newly defined algebraic interpretation, I obtain O(n
3) algorithms for finding Pauli flow, improving on the previous O(n
4) bounds. I also introduce a lower bound for Pauli flow-finding by linking it to linear algebra problems over F
2. Finally, when given an unlabelled open graph, I show how to find measurement labelling resulting in Pauli flow.
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.
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.
The ZH calculus is a graphical language for quantum computation reasoning. The phase-free variant offers a simple set of generators that guarantee universality. ZH calculus is effective in MBQC and analysis of quantum circuits constructed with the universal gate set Toffoli+H. While circuits naturally translate to ZH diagrams, finding an ancilla-free circuit equivalent to a given diagram is hard. Here, we show that circuit extraction for phase-free ZH calculus is
#P-hard, extending the existing result for ZX calculus. Another problem believed to be hard is comparing whether two diagrams represent the same process. We show that two closely related problems are
NP#P-complete. The first problem is: given two processes represented as diagrams, determine the existence of a computational basis state on which they equalize. The second problem is checking whether the matrix representation of a given diagram contains an entry equal to a given number. Our proof adapts the proof of Cook-Levin theorem to a reduction from a non-deterministic Turing Machine with access to
#P oracle.
The ZX-calculus is a graphical language for reasoning about ZX-diagrams, a type of tensor networks that can represent arbitrary linear maps between qubits. Using the ZX-calculus, we can intuitively reason about quantum theory, and optimise and validate quantum circuits. In this paper we introduce PyZX, an open source library for automated reasoning with large ZX-diagrams. We give a brief introduction to the ZX-calculus, then show how PyZX implements methods for circuit optimisation, equality validation, and visualisation and how it can be used in tandem with other software. We end with a set of challenges that when solved would enhance the utility of automated diagrammatic reasoning.
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.