1 Introduction↩︎

Quantum computing belongs to the field of quantum information theory and uses quantum mechanical effects to process information. As a consequence, new applications emerge that are intractable for classical computers [1] ( Section 2.1). Although quantum computing promises advances in drug discovery, material science, and climate modeling, its advantages are not universal across applications [2]. But as the quantum computing paradigm differs fundamentally from classical computing, quantum algorithms need to be carefully designed to exceed the performance of classical computers [3].

A quantum circuit [4] is the standard model to express quantum algorithms. Its basic building blocks are qubits and quantum gates. The qubit is the elementary unit of information [5]. A Quantum gate is an operator that acts on the state of qubits. We formally introduce quantum circuits in Section 2.1.

Quantum circuits provide a formal description of quantum algorithms, but their practical realization on existing hardware remains constrained. The current generation of quantum computers has limited practical use, as they are part of the noisy intermediate scale quantum era (NISQ) [3]. In particular, the duration in which a quantum device is stable and can reliably process information —called coherence time— is limited and restrict the available physical qubits. This is due to thermal noise, qubit error rate, gate fidelity, and measurement error [6]. Despite efforts to improve quantum hardware, mitigation strategies, such as quantum error correction and quantum circuit optimization, are required to allow the near-term usage of quantum computers [7], [8].

Quantum circuit optimization reduces the demand for resources of quantum algorithms to address these hardware limitations [7], [9]. We distinguish two classes of quantum circuit optimization: architecture-independent and architecture-dependent. Architecture-independent targets the reduction of noisy gates and circuit depth. The reduction of noisy gates is significant because they are challenging to implement on current architectures and introduce substantial error correction overhead [10]. Reducing the circuit depth is linked to speeding up the execution time of a quantum circuit. Architecture-dependent optimization takes hardware characteristics into account and maps a quantum circuit to a specific quantum device. In particular for superconducting architectures with a grid-based topology, architecture-aware optimization considers qubit connectivity and surface codes [9]. Qubit connectivity is the physical constraint on qubit interactions. Surface codes are the quantum error correction algorithms for different gates.

Conventional quantum circuit-based optimization techniques rely on gate cancellation and gate permutation rules [11]. However, it is necessary to prove that each simplification rule is semantics-preserving with respect to the chosen gate set. Furthermore, multiple rules are often required to capture the same underlying principle (e.g., two rules per single-qubit gate to commute through a CNOT gate).

ZX-calculus emerged as an alternative quantum circuit simplification framework beyond the traditional gate model [12] ( Section 2.2). ZX-calculus expresses the computation as a gate set independent graph called ZX-diagram. ZX-diagrams are always composed of the same few elementary building blocks.

ZX-based optimization techniques take advantage of the small and semantics-preserving set of rewriting rules offered (Section 2.4). ZX-calculus enables reductions beyond the gate level for current and future quantum devices. Therefore, a review of ZX-based quantum circuit optimization techniques is required to evaluate their practical impact and identify opportunities for future research.

In sum, the contributions of this survey are as follows:

1. This survey addresses multiple research communities that are unfamiliar with quantum computing or ZX-calculus by establishing their respective core principles (Section 2).

2. Comprehensive literature overview of ZX-based quantum circuit optimization that is organized by optimization strategies, target metrics, and architectural dependence (Sections 3 and 4).

3. Identification of key challenges and future research directions that can benefit from the diverse background of the target communities (Section 6).

2 Background↩︎

2.1 Quantum Computing↩︎

This section introduces a concise and minimal summary of quantum computing necessary to understand the connection between quantum circuits and ZX-calculus. This short introduction follows the de facto reference textbook for quantum computing and information theory by Nielsen and Chuang [13]. Quantum mechanical descriptions and examples are taken from Griffiths [14].

2.1.0.1 Dirac Notation

The Dirac notation is typically used to work with the linear algebra of a complex vector space, known as the Hilbert space, required by quantum mechanics [15]. Quantum states are complex vectors denoted as kets \(\ket{\phi}\). A Bra \(\bra{\psi} = \left(\ket{\psi}\right)^{\dagger}\) is the Hermitian conjugate, in finite dimensions the conjugate transpose, of a ket \(\ket{\psi}\) indicated by the dagger \(\dagger\). The inner product \(\braket{\phi}{\psi}\) gives the probability amplitude of a quantum system that originates in \(\ket{\psi}\) is in state \(\ket{\phi}\) upon measurement. To preserve the probability of the system, all states throughout this survey are assumed to be normalized vectors (\(\braket{\phi}{\phi} = 1\)).

2.1.0.2 Fundamentals

A key concept in quantum mechanics is superposition. It is a linear combination of states with a given complex-valued probability amplitude. In the following example, \(\@ifstar{\abs}{\abs*}{\alpha}^{2}\) and \(\@ifstar{\abs}{\abs*}{\beta}^{2}\) are the probabilities that the state \(\ket{\Psi}\) is in \(\ket{\phi}\) or \(\ket{\psi}\) [14]. \[\begin{align} \ket{\Psi} & = \alpha \ket{\phi} + \beta \ket{\psi} \\ 1 &= \@ifstar{\abs}{\abs*}{\alpha}^{2} + \@ifstar{\abs}{\abs*}{\beta}^{2} \end{align}\]
Entanglement is another key concept in quantum mechanics. It describes the joint state of composite quantum systems. For a system consisting of the states \(\ket{\phi}\) and \(\ket{\psi}\), their joint state \(\ket{\Psi}\) is given by their tensor product such that \(\ket{\Psi} = \ket{\phi}\otimes\ket{\psi}\).
Operators \(\hat{U}\) are observables that act on a given state \(\ket{\phi}\) and result in a new state \(\ket{\phi_{U}}\) such that \(\ket{\phi_{U}}=\hat{U}\ket{\phi}\). Generally, operators that act in sequence on a state do not commute (e.g. \(\ket{\phi_{UV}}\neq\ket{\phi_{VU}}\)), hence the order of application remains relevant.

All quantum operators follow the superposition principle, such that \(\hat{U}\left(\ket{\phi} + \ket{\psi}\right) = \hat{U}\ket{\phi} + \hat{U}\ket{\psi}\). Furthermore, quantum information theory only deals with unitary operators, thus \(\hat{U}^{\dagger}\hat{U}=\hat{1}\). This restriction is required because only unitary operations preserve the probability of a quantum system under time evolution. The notable exception to this rule is the measurement operator.
In addition, some operators are Hermitian. Hermitian operators remain unchanged under hermitian conjugation, such that \(\hat{U}^{\dagger} = \hat{U}\). This property is in particular true for physical observables, as it results in purely real eigenvalues. Unitary operators that are Hermitian recover the input state after being applied twice.
Quantum computing leverages quantum mechanical principles, such as superposition and entanglement, to process information through the sequential application of unitary operators to quantum states.

2.1.0.3 Qubits

The basic unit of information in quantum computing is the qubit [5]. In contrast to a classical bit that can only represent states 0 and 1, qubits can be either in the computational basis states \(\ket{0}\) and \(\ket{1}\) or in the superposition of multiple basis states. The basis states are a set of orthogonal states that can represent every state as a superposition.

The computational basis is not the sole qubit basis of practical use. Commonly, Pauli bases are chosen for quantum computing ( Table 1). An intuitive tool to visualize single-qubit states with their respective probability amplitude is the Bloch sphere [16]. Figure 2 shows a Bloch sphere with the state \(\ket{\Psi} = \frac{\ket{0} + \ket{1}}{\sqrt{2}} = \ket{+}\) indicated in red. The different axes correspond to the Pauli bases -X (\(\ket{-}\), \(\ket{+}\)), -Y (\(\ket{-i}\), \(\ket{+i}\)) and -Z (\(\ket{0}\), \(\ket{1}\)) bases. The probability a state collapses towards a fixed value during measurement depends on its measurement basis. A measurement of \(\ket{\Psi}\) on the basis of Z would result in \(\ket{0}\) and \(\ket{1}\) with a probability of 50% for each outcome. However, if the same state \(\ket{\Psi}\) is measured in the X-basis, the final state would always be \(\ket{+}\).

Entanglement connects the state of multiple qubits so that they depend on each other [17]. To encode a classical bit string \(\mathbf{00}\) into qubits, the composite state is formed by the tensor product of the computational basis states, thus \(\mathbf{\ket{00} = \ket{0} \otimes \ket{0}}\).

Other prominent examples of entanglement are the Bell states [18]. Bell states are composed of maximally entangled qubits. Maximally entangled qubits are perfectly correlated, and the measurement of one qubit will instantaneously determine the state of the other entangled qubit regardless of their distance. Figure 4 generates the \(\ket{\Psi^{-}}\) Bell state. Highly entangled qubits are essential for quantum error correction [19].

2.1.1 Quantum Circuits↩︎

The quantum circuit model is one way to express quantum computation. Quantum circuits are graphical representations of the manipulation of quantum-mechanical states (qubits) by operators (quantum gates) [4]. Like classical electrical circuits, quantum circuits implement the semantics and control flow of a program. Individual operations are performed by quantum gates. The literature differentiates between random and structured quantum circuits. Randomly generated circuits are typically generated with different weights for the various quantum gates and do not represent a real-world application. Structured circuits are quantum programs that solve real-world problems.

2.1.1.1 Quantum Gates

The elementary building blocks of quantum circuits are quantum gates. Like their classical counterparts, the logic gate in analog computers, quantum gates implement individual operations onto a state. In contrast to classical logic gates, quantum gates are reversible. The reversibility of computation mandates that the input states are always recoverable from the output states [20]. Certain quantum gates have classical analogs; the quantum \(X\) gate is the quantum equivalent of the classical NOT gate. Other gates are unique for the quantum computing paradigm without a classical counterpart; unique quantum gates include the Hadamard \(H\) and \(Z\) gate.

From a quantum-mechanical perspective, all quantum gates are unitary operators that can be represented as unitary matrices. Quantum gates can operate on one or multiple qubits. Single-qubit gates can be visualized as rotations inside the Bloch sphere. Figure 3 highlights the sequential application of the \(HZH\) operators to the \(\ket{0}\) state, acting effectively as the \(X\) gate. The \(Z\), \(X\) and \(H\) gates reappear later in the form of the elementary building blocks of ZX calculus. If a quantum gate is both a unitary and a Hermitian operator, applying the same gate twice recovers the original state.

Quantum computers implement universal gate sets to perform every computation. Although there are infinite number of universal gate sets, in practice the Clifford+T set is chosen. This choice is a result of the Gottesman-Knill theorem, which states that Clifford computations can be efficiently simulated classically [21], [22]. Table 2 lists the gates that make up the Clifford + T-gate set with the corresponding unitary matrices and the quantum circuit notation.

As we saw before, quantum gates are unitary operators that do not necessarily commute. Therefore, different universal gate sets admit different sets of gate commutation rules (e.g., Clifford+T or Toffoli). This is of particular importance, for the field of rule-based quantum circuit optimization [11], [21].

Quantum gates are unitary operators that act on qubits.

2.1.1.2 Quantum Circuits

To process information, quantum circuits combine an application sequence of quantum gates on qubits. Quantum circuits are a linear map of qubits.

They are composed of tensor and matrix products of operators. The matrix product is used for the sequential composition of gates along the program flow. The tensor product entangles multiple qubits with each other. As not all quantum gates commute, the exact sequence needs to be preserved upon composition of the full operator such that the semantics are preserved.

Figure 4 shows a quantum circuit that generates the \(\ket{\Psi^{-}}\) Bell state. The control flow is from left to right. In Dirac notation, the circuit reads as follows: \[CX\dot{(}H\otimes X)\ket{00} = \frac{1}{\sqrt{2}}(\ket{01}-\ket{10}) = \ket{\Psi^{-}}\]

The familiar look of quantum circuits should not deceive one from the fact that quantum computing is a fundamentally different paradigm that enforces different constraints not known by classical computation. The no-cloning theorem states that it is impossible to create a perfect and independent copy of an arbitrary unknown quantum state [23], [24]. As a direct consequence, quantum computing cannot use classical error correction codes that are based on copying information.

A quantum circuit is a linear map of qubits that is composed of sequential quantum gates.

2.1.1.3 Quantum Circuit Optimization

Current generation quantum hardware possesses several resource restrictions, namely physical qubit availability and limited coherence time. Quantum circuit optimization addresses these limitations and can be broadly divided into two categories [7].

Architecture-independent optimization focuses on hardware-agnostic strategies at the logical qubit level without any consideration of their physical implementation. Logical qubits are error corrected qubits composed of several physical qubits. Physical qubits are the actual hardware elements. They are prone to noise and are not error corrected. With the aid of quantum error correction, multiple physical qubits form a logical qubit.

Typical optimization targets are the reduction of multi-qubit gates (e.g., CNOT and SWAP) and T-gates as they require more surface code for error correction [10]. Decreasing the circuit depth reduces the execution time of a quantum circuit. Speeding up the execution time is especially important if the unoptimized circuit cannot be executed during the coherence time. Furthermore, quantum circuit synthesis aims to decompose arbitrary unitary operations into an optimal sequence of quantum gates [9].

Architecture-dependent optimization concentrates on hardware specific characteristics, primarily a circuit’s qubit connectivity (which qubits can directly interact with each other), gate fidelity (accuracy of a gate’s operation), circuit fidelity (accuracy of a full circuit’s unitary operator), and error rate (probability of erroneous state changes) [25]. Multi-qubit gates can only operate on connected qubits. Extra operations, such as SWAP gates, facilitate connections between qubits. Routing optimizes a circuit to respect the architecture’s qubit connectivity, and subsequently reduces the demand for physical qubits. A quantum architecture implements physical qubits from logical qubits. Additionally, architecture-aware synthesis decomposes and aligns parts of the quantum circuit with respect to the connectivity and limitations of a given quantum architecture [9].

Quantum circuit optimization improves the resource requirements of quantum algorithms for current NISQ-era quantum hardware.

2.2 ZX-Calculus↩︎

ZX-calculus is a diagrammatic reasoning frame:work for quantum circuits. Both represent linear maps of qubits, but ZX-calculus allows access to the underlying algebraic structure and symmetries of the generators (elementary building blocks), allowing reasoning and rule-based optimization. Originally introduced in 2008 by Coecke and Duncan [12], ZX-calculus is gaining popularity in the field of quantum circuit optimization with further applications in quantum circuit verification. This section follows the book-sized introduction of Coecke and Kissinger [26] and the shorter introductory paper of van de Wetering [27].

2.2.0.1 Optimization Pipeline

Figure 1 shows an idealized three-step optimization pipeline for ZX-based quantum circuit optimization.

1. Convert: The quantum circuit is converted to an equivalent ZX-diagram. ZX-calculus is universal; hence every quantum circuit can be converted.

2. Search: ZX-diagram modification that optimizes target metric(s), e.g., by applying semantic preserving rewriting rules (Figure 5)

3. Extraction: Circuit extraction (Section 2.5) translates the ZX diagram into an equivalent quantum circuit. Although only diagrams that preserve general or causal flow are extractable in polynomial-time otherwise it is a combinatorial optimization problem that is #P-hard.

The two entry points to optimize ZX-diagrams are the search stage and the extraction stage. The search stage primarily targets ZX-diagram metrics that directly translate or approximate quantum circuit metrics (e.g., Non-Clifford spiders and Hadamard wires). The circuit extraction stage targets quantum circuit metrics (e.g., two-qubit gate count and circuit depth) that are possibly architecture-aware.

2.2.0.2 Fundamentals

An object in ZX-calculus is a labeled open graph that is referred to as a ZX-diagram [28], [29]. The loss of determinism in ZX-diagrams that gives rise to the circuit extraction problem (Section 2.5) is a direct consequence of its open graph properties.

Every quantum circuit can be expressed as a ZX-diagram, but the reverse is not necessarily true. This issue is known as the circuit extraction problem (Section 2.5).

ZX-calculus is especially suited for quantum circuit optimization because it offers a sound rewriting system that is:

• Compact: small number of elementary building blocks and rewriting rules.

• Complete: rewriting rules are semantic-preserving. The rewriting rules of ZX-calculus are complete, even for arbitrary real phases [30]–[33].

• Universal: any quantum circuit can be represented as a ZX-diagram.

The elementary building blocks of quantum circuits are quantum gates and wires. Analogously, the elementary building blocks in ZX-calculus—called generators—are spiders, wires, swap, and Bell states. In contrast to quantum circuits, which can be composed of an infinite amount of universal gate sets, ZX-calculus only contains the same 8 generators irrespective of a quantum circuit’s chosen gate set. The compactness of ZX-calculus is of a particular advantage compared to the quantum circuit representation where the gate commutation rules depend on the chosen gate set (e.g., Clifford gates [21] and rotation gates [11]).

A spider represents a tensor that operates on qubits in the Z-basis \(\left\{\ket{0}, \ket{1} \right\}\) (green) or X-basis \(\left\{\ket{-}, \ket{+} \right\}\) (red). Spiders possess \(n\) inputs, \(m\) outputs, and carry a phase \(\alpha\). The following figure visualizes a Z- and a X-spider with \(n\) inputs and \(m\) outputs and their respective unitary operator in Dirac notation. \[\begin{align} \scalebox{1.25}{ \begin{ZX} \leftManyDots{n} \zxZ{\alpha} \rightManyDots{m} \end{ZX}} &=\ket{0, ...,0}\bra{0,...,0} \\ &+ e^{i\alpha}\ket{1, ...,1}\bra{1,...,1} \\ \scalebox{1.25}{ \begin{ZX} \leftManyDots{n} \zxX{\alpha} \rightManyDots{m} \end{ZX}} &= \ket{+, ...,+}\bra{+,...,+} \\ &+ e^{i\alpha}\ket{-,...,-}\bra{-,...,-}\\ \end{align}\]

The linear map of a spider with phase \(\alpha = 0\) results in the identity matrix \(\underset{2^{m}\times 2^{n}}{1\kern-0.25em\text{l}}\) and therefore acts as a wire. Spiders with phases that are multiples of \(\frac{\pi}{2}\) can implement all Clifford gates. A T-gate corresponds to a Z-spider with a phase of \(\frac{\pi}{4}\). Clifford gates and the T-gate form a universal gate set together.

Wires connect the output of one spider with the inputs of other spiders. The identity matrix \(1\kern-0.25em\text{l}\) implements the linear map of wires. \[\scalebox{1.5}{ \begin{ZX}[ampersand replacement=\&] \zxN{} \rar \&[\zxWCol] \zxN{} \end{ZX}}~=~\ket{0}\bra{0} + \ket{1}\bra{1}\] A yellow box connected by wires indicates a Hadamard generator. An alternative notation are blue dotted wires. Euler decomposition, known as the Hadamard rule (hd), splits a Hadamard generator into a sequence of Z and X spiders [34]. \[\scalebox{1.5}{ \begin{ZX} \zxN{} \rar &[\zxwCol] \zxH{} \rar &[\zxwCol] \zxN{} \end{ZX}}~=~\scalebox{1.25}{ \begin{ZX} \zxN{} \ar[r] & \zxFracZ{\pi}{2} \ar[r] & \zxFracX{\pi}{2} \ar[r] & \zxFracZ{\pi}{2} \ar[r] & \zxN{} \end{ZX}}\] The swap generator swaps the spiders on a wire and implements the same linear map as the swap gate in the quantum circuit notation. \[\begin{align} \scalebox{1.25}{ \begin{ZX} \zxNoneDouble|{} \ar[r,s,start anchor=north,end anchor=south] \ar[r,s,start anchor=south,end anchor=north] &[\zxWCol] \zxNoneDouble|{} \end{ZX}} &=~\ket{00}\bra{00} + \ket{01}\bra{10}\\ &+~\ket{10}\bra{01}+ \ket{11}\bra{11} \end{align}\] In ZX-calculus, bent wires depict the Bell state and the Bell effect and are known as cup and cap. \[\begin{align} \scalebox{1.25}{ \begin{ZX} \zxNone{} \ar[d,C] \\[\zxWRow] \zxNone{} \end{ZX}}~&=~\ket{00} + \ket{11}\\ \scalebox{1.25}{ \begin{ZX} \zxNone{} \ar[d,C-] \\[\zxWRow] \zxNone{} \end{ZX}}~&=~\bra{00} + \bra{11} \\ \end{align}\]

A typical ZX-diagram consists of many connected spiders and Hadamard generators. Matrix multiplication composes the linear map of sequentially connected spiders. The tensor product composes the linear map between non-sequential connected spiders and Hadamards, meaning that generators are parallel to each other.

Only topology matters is an important concept in ZX calculus. It states that the linear map between qubits of a ZX diagram remains unchanged as long as its connectivity stays the same. As a consequence, bending wires (e.g., cups and caps) and moving spiders do not change the ZX diagram [26]. The only topology matters concept is the reason why a calculus based on Z- and X-basis is preferable over a calculus that explicitly introduces Y-spiders. This concept emerges from the symmetry of the Z- and X-basis eigenstates that are self-conjugate while the Y-basis eigenstates are not. In addition, Y-eigenstates can be easily expressed by a composition of Z- and X-spiders.

A ZX-diagram is a labeled open graph composed of generators that can implement the linear map of qubits for every quantum circuit.

2.3 Macroscopic structures↩︎

This paragraph introduces macroscopic structures, larger scale patterns of generators, commonly found in ZX-diagrams that are used by some of the surveyed works. Phase gadgets are structures in ZX-diagrams that add a phase to a state. Legs are wires that connect spiders of the same color to a single spider of the opposite color, which subsequently connects to a state. Figure 6 visualizes a phase gadget with three legs on the left. Phase gadgets can be efficiently decomposed as a single phase gate that is connected by a CNOT ladder on the input and output wire. Similarly to phase polynomials, their unitary can be expressed as matrix exponentials \(e^{-i\theta\otimes_{i}Z_{i}}\) or \(e^{-i\theta\otimes_{i}X_{i}}\). Phase polynomials are a class of circuits that are only composed of CNOT, and phase gates acting in the Z-basis. These circuits are interesting because they can be fully described by an unitary operator that takes the form of a matrix exponential \(e^{-i\frac{\theta}{2}(1-2Px)}\) with \(P\) being the circuit’s parity table. Phase polynomials are a sequence of phase gadgets. Figure 6 shows the phase gadget and its decomposition into a CNOT ladder that implements the unitary \(e^{-i\theta ZZZ }\). Pauli gadgets extend the notion of phase gadgets by allowing each leg to connect to spiders that can be of type X, Y or Z. Spider nests are a special form of phase gadgets, where the phase-carrying spider is always \(\frac{\pi}{4}\).

Phase gadgets, phase-polynomials, Pauli gadgets and spider nests are macroscopic structures commonly found in ZX diagrams that permit efficient optimization.

2.4 Rewriting Rules↩︎

This section introduces the basic rewriting rules of the ZX-calculus that are outlined in Figure 5 [26], [35].

A rewriting rule transforms a ZX-diagram while preserving its underlying semantics under the following definition:

All rules remain valid under color inversion. We give an example of the successive application of some rewriting rules on a simple ZX-diagram in Figure 7.

Spider fusion (f)

Connected spiders of the same color fuse through modulo-\(2\pi\) addition of their phases. The reverse unfusing operation is always possible, because connecting additional spiders with a phase of \(\alpha=0\) will not change the modulo-\(2\pi\) addition. As a consequence, infinite spiders can be unfused. Figure 7 highlights the fusion of two green non-phase-carrying spiders with their neighboring phase-carrying spiders.

Local complementation (lc)

The local complementation rule [36] originates from graph theory. For all directly connected spiders of a target spider, local complementation connects previously unconnected spiders and disconnects previously connected spiders. Pivoting describes a series of local complementations.

Color change (h)

Adding Hadamard generators to each input and output inverts the color of a spider. In Figure 7, all red spiders turn green with the addition of Hadamard generators.

Identity removal (i1, i2)

Non-phase-carrying spiders that are directly connected to other spiders function as wires and leave the linear map of qubits unchanged. The identity matrix \(\underset{2^{m}\times 2^{n}}{1\kern-0.25em\text{l}}\) represents the linear map of such spiders. A single wire replaces a phaseless spider with \(n=1\) and \(m=1\). Similarly, two directly connected Hadamard generators cancel each other out and act as a wire. Furthermore, identity rules are used to convert a ZX-diagram to be graph-like ( Definition 3) by ensuring that spiders always connect with each other through Hadamard generators and by adding potentially missing spiders at the input and output.

Hopf (ho)

The Hopf rule originates from the copy and xor algebras that form a Hopf algebra. If multiple wires connect two opposite colored spiders, the additional wires can be removed pair by pair.

Bialgebra (b)

Similarly to the Hopf rule, the bialgebra rule originates from the commutation relation between the copy and xor algebra. This rule permits connected spiders of opposite colors to move through each other at the cost of potentially adding spiders.

Copy (\(\pi\), c)

\(\pi\) copying moves an input spider that carries the phase \(\alpha=\pi\) through an opposite colored spider to all connected wires while multiplying the phase by \(-1\). If the input spider does not have any input wire (\(n=0\)) and the phase is a multiple of \(\pi\), the opposite colored spider vanishes. This second rule is referred to as the state copying rule, because it copies the computational basis through an opposite-colored spider.

Neighbor unfusion

Staudacher et al. [35] introduce the neighbor unfusion rule, a complement to the spider fusion rule, which enables further optimizations. Subsequent research by McElvanney et al. [37] proves that neighbor unfusion also preserves gflow. This important result allows for the application of the unfusion rule without requiring repeated computationally expensive gflow verifications, thus accelerating the optimization workflow.

The rewriting rules of ZX-calculus allow for semantics-preserving transformations of ZX-diagrams.

2.4.1 ZX-based Quantum Circuit Optimization↩︎

At the heart of ZX-based quantum circuit optimization is the successive application of rewriting rules. To simplify ZX-diagrams using basic rewriting rules, the popular PyZX framework assumes that the ZX-diagrams are graph-like ( Definition 3) [38]. Figure 7 shows an example rewriting rule sequence that results in a graph-like ZX-diagram. Every ZX diagram can be converted to be graph-like using the h-rule and the identity rules i1 and i2.

2.5 Circuit Extraction↩︎

The conversion of ZX-diagrams into quantum circuits necessitates computationally expensive circuit extraction algorithms. Consequently, the circuit characteristics and optimization results are heavily reliant on the chosen extraction method. This section introduces the principles of the circuit extraction algorithm proposed by Duncan et al. [29]. Its extension by Backens et al. [39] is included as the standard algorithm in many works, as it allows for the extraction of phase gadgets.

In principle, circuit extraction is a #P-hard optimization problem [40]. Therefore, it is computationally beneficial to reduce the need of circuit extraction as much as possible. Nevertheless, there are polynomial-time circuit extraction algorithms for ZX-diagrams that maintain a graph-theoretic property known as generalized flow (gflow) or the stricter causal flow (cflow) [39].

These algorithms allow for the extraction of larger ZX-diagrams, but do so at the cost of introducing additional two-qubit gates to preserve the connectivity of spiders. As a result, these extraction algorithms can lead to circuits with an increased gate count and depth compared to the source circuit.

Circuit extraction from ZX-diagrams is computationally expensive, and the specified extraction algorithm determines the characteristics of the resulting quantum circuit.

2.5.0.1 Generalized and Causal Flow

ZX-diagrams are labeled open graphs with undirected edges ( Definition 1). Furthermore, the input and output sides of spiders are interchangeable. Therefore, it is not clear in what order the spiders act on what qubit, making ZX-diagrams non-deterministic. In contrast, a quantum circuit’s gate sequence acts on qubits and is ordered by time. Circuit extraction is not just a mere translation between two different representations, but forces a deterministic behavior.

Circuit extraction asserts the causality of ZX-diagrams by using the one-way model of quantum computing as an intermediate representation. The measurement-based model of quantum computing (MBQC) uses measurement patterns (sequences of qubit measurements in the XZ-, XY-, YZ-planes) and adds correction operators on upcoming qubit measurements [41]. A computation is only deterministic if there exists a sequence of qubit measurements that only adds correction operators on upcoming measurements without affecting past measurements.

In the framework of MBQC, ZX-diagrams can be interpreted as a measurement graph. A ZX-diagram is deterministic if it admits a measurement sequence that corrects future spiders without affecting already measured spiders. For ZX-diagrams that contain only measurements in the XY-plane, it has a deterministic measurement pattern if the ZX-diagram admits causal flow (cflow) [42]. If a ZX-diagram contains measurements in the XZ-, XY-, YZ- planes, the measurement pattern is deterministic if the ZX-diagram admits generalized flow (gflow) [43].

ZX-calculus allows one to translate between measurement-based quantum computing and the quantum circuit model if a deterministic measurement pattern exists [44]. Circuit extraction is only possible for ZX-diagrams where it is possible to assert a deterministic measurement pattern; hence cflow or gflow are preserved.

The presence of causal or generalized flow is necessary to assert a deterministic behavior during circuit extraction.

2.5.0.2 Circuit Extraction in Polynomial-Time

Polynomial-time circuit extraction algorithm exists for ZX-diagrams that preserve cflow or gflow. Duncan et al. introduce the first circuit extraction algorithm for ZX-diagrams that possess cflow [29]. Backens et al. generalize the previous work of Kissinger et al. to perform circuit extraction for ZX-diagrams that have gflow [39].

This section introduces the principles of the circuit extraction algorithm for graph-like (Definition 3) ZX diagrams by Duncan et al. [29]. The techniques to be introduced reemerge in various works that target architecture-aware circuit optimization (e.g., Villoria et al. [45], and Kissinger et al. [46]).

Figure [a] highlights the initial step of circuit extraction. The ZX-diagram is divided into an extracted and unextracted half separated by a frontier. Initially, the extracted half is empty and the complete ZX-diagram is contained in the unextracted half.

Circuit extraction is an iterative process that consists of the following steps until the unextracted half of the ZX-diagram is empty:

• Spiders that have a single input and output wire have a single qubit gate analog (Table 2) and can be extracted directly. Figure [b] shows the extraction of a T-gate in the top row.

• The wire between two directly connected frontier spiders is extracted by a SWAP gate. Figure [c] shows the SWAP gate that results from the extraction of the directly connected frontier spiders \(\epsilon_{2}\) and \(\epsilon_{3}\).

• CNOT gates are used for frontier spiders that are connected to multiple unextracted spiders. Figure [d] shows how a CNOT gate is added to extract the diagonal connection of \(\epsilon_{2}\).

The programmatic extraction of frontier spiders with multiple unextracted connections is based on manipulating the binary biadjacency matrix. All frontier spiders only have a single unextracted connection when their biadjacency matrix is equal to the identity matrix. The biadjacency matrix can be interpreted as a linear system of equations where row additions are bitwise XORs. The quantum gate analog of the XOR operation is the CNOT gate. The goal is to retrieve the identity matrix from the biadjacency matrix using only row additions.

Let’s consider the biadjacency matrix of frontier spiders for Figure [c]: \[\label{eq:biadj} \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 1\\ 0 & 0 & 1\\ \end{bmatrix}\tag{1}\] It is enough to sum up the last two rows to form the identity matrix. This bitwise XOR operation results in the additional CNOT gate between \(\epsilon_{2}\) (control) and \(\epsilon_{3}\) (target) in Figure [d]. Therefore, every row operation adds a CNOT gate to the extracted circuit.

Duncan et al. use Gaussian elimination to solve this linear system of equations and add a CNOT gate for every row addition [29]. However, recent works add constraints on the solutions of the linear system of equations formed by the biadjacency matrix to allow for architecture-aware circuit optimization (e.g., Villoria et al. [45], and Kissinger et al. [46]).

3 Target Metrics↩︎

ZX-calculus allows for architecture-independent and architecture-aware optimization strategies. The objective of quantum circuit optimization is to reduce the resource demand of quantum programs and enable their execution on real NISQ-era quantum computers.

Typical candidates for architecture-independent optimization include the minimization of the logical qubit, T-gate and overall gate count. These optimizations aim to express the program flow in a more compact circuit.

However, in order to produce an executable quantum circuit, architectural characteristics need to be incorporated. Especially for NISQ-era quantum computers, it is essential to consider the quantum error correction overhead introduced by different gates. For many quantum architectures, T-gates and two-qubit gates contribute significantly more noise than typical single-qubit Clifford gates. These noisy gates often require sophisticated error correction that further increases the demand for resources.

Current NISQ architectures are limited by spatial constraints and restricted qubit connectivity, such that not all physical qubits can interact with each other without needing intermediary qubits. Consequently, architecture-aware optimizations are crucial to ensure that a circuit can be synthesized and executed. One way to adapt a quantum circuit for a specific device is routing. Routing maps a quantum circuit onto real hardware with respect to the architecture’s topology and available error correction codes.

3.0.0.1 Circuit depth

Circuit depth is directly linked to the execution time and noise exposure of the circuit. Shallower circuits can be realized and executed faster. A quantum circuit can only be executed reliably on a quantum device if its execution time is shorter than the coherence time. The coherence time and gate error rates vary across architectures and highlight the need for optimization strategies that jointly address architectural constraints and architecture-agnostic resource metrics.

3.0.0.2 Qubit count

Quantum circuits are composed of quantum gates that act on logical qubits. In the context of ZX-diagrams, the number of logical qubits is the maximum number of wires intersected by any vertical cut through the diagram.

3.0.0.3 T-gate count

The T-gate is a particularly noisy single-qubit gate that forms a universal gate set when combined with the Clifford gate set. Unlike typical single-qubit Clifford gates, the T-gate significantly adds quantum error correction overhead to current NISQ architectures. Consequently, a prime objective of architecture-independent optimization is to reduce the T-gate count.

3.0.0.4 Two-qubit gate count

ZX-diagrams consist of generators and not quantum gates. Therefore, it is necessary to translate a ZX-diagram to a quantum circuit using circuit extraction.

The trade-off between the computational requirements of circuit extraction and the quality of the extracted circuit emphasizes the reliance on the circuit extraction algorithm used. Optimization should take place at the ZX-diagram level, bypassing circuit extraction whenever possible. One approach to avoid unnecessary circuit extraction is to estimate the number of two-qubit gates from the number of Hadamard wires contained in ZX diagrams as proposed by Staudacher et al. [35].

Architecture-aware approaches require extra steps during the optimization, circuit extraction, or transpilation stage to create an executable quantum circuit. These optimization strategies need to take hardware-dependent factors such as qubit connectivity and the quantum computer’s topology into account.

4 Taxonomy↩︎

This survey categorizes ZX-based quantum circuit optimization algorithms by their underlying strategy and target metric. Table [tabsurvey] provides a high-level overview of our survey. In case a method approximates quantum circuit metrics at the ZX-diagram level, both are indicated. This becomes necessary to circumvent the computationally expensive circuit extraction. For example, this is the case when the number of two-qubit gates is approximated by the number of Hadamard wires.

In addition, the main optimization algorithm for each approach is listed. If an entry contains "Ad-hoc", the respective work introduces a novel procedure that reduces the indicated metric. If a heuristic is indicated, the optimization is guided by characteristics of the local ZX-diagram. Other entries specify the algorithms used such as simulated annealing (SA), reinforcement learning (RL), genetic algorithms (GA), look-ahead search (LA), linear programming (LP), directed vertex feedback solver (DVFS) and template matching (TM). Moreover, we differentiate between architecture-agnostic ( blue) and architecture-aware ( red) strategies. The following subsections discuss individual approaches and aim to highlight connections and identify future research directions.

[ht!]
  \setlength\tabcolsep{0pt}
  \begin{tabular}{\textwidth}{@{\extracolsep{\fill}}
      >{\columncolor{white}[0pt][6pt]} l
      >{\columncolor{white}[6pt][6pt]}c
      >{\columncolor{white}[6pt][6pt]}l
      >{\columncolor{white}[6pt][6pt]}c
      >{\columncolor{white}[6pt][6pt]}c
      >{\columncolor{white}[6pt][6pt]}c
      >{\columncolor{white}[6pt][6pt]}c
    >{\columncolor{white}[6pt][6pt]}c >{\columncolor{white}[6pt][0pt]}c @{}}
    \toprule
    \textit{Author(s)} & \textit{Year} & \textit{Algorithm} &
    \textit{T} & \textit{2Q} & \textit{Depth} & \textit{Qubits} &
    \textit{Edges}  & \textit{Vertices} \\
    \midrule
    \rowcolor{luxembourg blue!20} Fagan \&
    Duncan~\cite{faganOptimisingCliffordCircuits2019} & 2019 &
    Ad-hoc & &  ✔ & ✔ & & & \\
    \rowcolor{luxembourg red!20} Kissinger et
    al.~\cite{kissinger2019cnotcircuitextractiontopologicallyconstrained}
    & 2019 & Ad-hoc & & ✔ & & & & \\
    \rowcolor{luxembourg blue!20} Beaudrap et
    al.~\cite{beaudrap2020org} & 2020 & Ad-hoc + Heuristic &
    ✔& & & & &  \\
    \rowcolor{luxembourg blue!20} Beaudrap et
    al.~\cite{beaudrap2020extended} & 2020 & Ad-hoc + Heuristic &
    ✔& & & & & \\
    \rowcolor{luxembourg blue!20} Duncan et
    al.~\cite{duncanGraphtheoreticSimplificationQuantum2020} & 2020 &
    Ad-hoc & ✔ & & & & & \\
    \rowcolor{luxembourg blue!20} Kissinger \&
    Wetering~\cite{kissinger2020journal} & 2020 &
    Ad-hoc & ✔ & & & & & \\
    \rowcolor{luxembourg red!20} Cowtan et
    al.~\cite{cowtanPhaseGadgetSynthesis2020} & 2020 & Ad-hoc +
    Greedy & & ✔ & & & & \\
    \rowcolor{luxembourg red!20} Cowtan et
    al.~\cite{cowtan2020genericcompilationstrategyunitary} & 2020 & Ad-hoc &
    & ✔ &  & & & \\
    \rowcolor{luxembourg blue!20} Munson et al.~\cite{munson2021And}
    & 2021 & Ad-hoc + Heuristic & ✔& & & & & \\
                \rowcolor{luxembourg red!20} Zilk et
    al.~\cite{zilk2022photonic} & 2022 &
    Ad-hoc & ✔ & ✔ & ✔ & & & \\
    \rowcolor{luxembourg red!20} Gogioso \&
    Yeung~\cite{gogiosoAnnealingOptimisationMixed2023} & 2023 & SA &
    & ✔ & & & & \\
    \rowcolor{luxembourg blue!20} Staudacher et
    al.~\cite{staudacherReducing2QuBitGate2023} & 2023 & Rand. +
    Heuristic & &  ✔ & & & ✔ & \\
    \rowcolor{luxembourg red!20} Winderl et al.~\cite{Winderl_2023} &
    2023 & Ad-hoc + Heuristic & & ✔ & & & &  \\
    \rowcolor{luxembourg blue!20} Riu et
    al.~\cite{riuReinforcementLearningBased2023} & 2023 & RL & &
    ✔ & & & ✔ & \\
    \rowcolor{luxembourg red!20} Griend et
    al.~\cite{Meijer_van_de_Griend_2023} & 2023 & Ad-hoc +
    Heuristic & & & ✔ & &  & \\
    \rowcolor{luxembourg blue!20}
    Vandaele~\cite{vandaele2024qubitcountoptimizationusingzxcalculus}
    & 2024 & Ad-hoc + DVFS + Greedy & & & & ✔ & & \\
    \rowcolor{luxembourg blue!20}
    Holker~\cite{holkerCausalFlowPreserving2024} & 2024 & Rand. +
    Heuristic & ✔ & & & &  ✔ & \\
    \rowcolor{luxembourg blue!20} Nägele \&
    Marquardt~\cite{nageleOptimizingZXDiagramsDeep2023} & 2024 & RL &
    & & & & & ✔ \\
    \rowcolor{luxembourg red!20} Staudacher et
    al.~\cite{staudacher2024neutralatom} & 2024 & Ad-hoc & &  &
    ✔ & & & \\
    \rowcolor{luxembourg red!20} Ewen et al.~\cite{ewen2025genetic} &
    2025 & GA & &  ✔ & ✔ & &  & \\
    \rowcolor{luxembourg red!20} Huang et
    al.~\cite{huang2024redefininglexicographicalorderingoptimizing} &
    2025 & Ad-hoc + Heuristic & ✔ & ✔ & & & & \\
                \rowcolor{luxembourg blue!20} Mattick et
    al.~\cite{mattick2025optimizingquantumcircuitszx} & 2025 & RL +
    Tree search & &  ✔ & & & ✔ & \\
    \rowcolor{luxembourg blue!20} Fischbach et
    al.~\cite{fischbach2025exhaustivesearchquantumcircuit} & 2025 &
    Tree search & ✔ & & & & ✔ & \\
    \rowcolor{luxembourg red!20} Liu et al.~\cite{liu2024} & 2024 &
    TM & & ✔ & ✔ & & & \\
                    \rowcolor{luxembourg blue!20} Chen et
    al.~\cite{chen2025quantumcircuitoptimizationbased} & 2025 &
    SA + LA & &  ✔ & ✔ & & & \\
    \rowcolor{luxembourg red!20} Villoria et
    al.~\cite{villoria2025optimizationsynthesisquantumcircuits} & 2025 &
    LP + Peephole & &  ✔ & & & & \\
    \bottomrule
  \end{tabular}
  \caption{Overview of the different quantum circuit optimization
    algorithms, the optimization procedure and the main target metrics.
    Architecture-independent approaches are highlighted in blue and
  architecture-aware approaches are highlighted in red.}
  \label{tabsurvey}

4.1 Heuristic↩︎

4.1.1 Circuit depth↩︎

Fagan and Duncan introduced the first ZX-based quantum circuit optimization algorithm [47]. Their optimization strategy moves Pauli gadgets towards the inputs and group CNOT and TONC gates (CNOT gates with switched control and target qubits) that act on the same qubits. They demonstrate a significant reduction of the CNOT gate count by \(\approx 16\%\) and circuit depth up to \(\approx 30 \%\) for pure Clifford circuits.

4.1.1.1 Architecture-aware

Staudacher et al. add an additional step to the circuit extraction algorithm of Backens et al. [39] between the CNOT and single-qubit gate extraction to target neutral-atom architectures [48]. Instead of using the Clifford + T gate set, this work targets a gate set that consists of Z gates, multi-controlled phase gates and global single qubit rotations in the XY-plane. Phase gadgets are the native representation of multi-controlled phase gates. For identified frontier phase gadgets, the fusion rule and reverse gadget fusion rules are applied. Potentially missing phase gadgets are added to extract a full multi-controlled phase gate. neutral-atom quantum computers can natively execute multi-controlled phase gates and are limited by execution time and the total gate count. Especially the global single-qubit rotation is an order of magnitude slower than the multi-controlled phase gate and the Z phase gates. The circuit’s execution time is computed along the circuit as the sum of individual gates execution time, which is assumed to increase with the rotation angle. Their approach outperforms the execution time of Qiskit compiled circuits from \(26\%\) up to \(40\%\), primarily due to the reduction in the number of global phase gates.

4.1.2 T-gate count↩︎

4.1.2.1 Architecture-independent

Kissinger and van de Wetering use the theoretical framework of Duncan et al. [29] to allow semantic preserving optimization of circuits composed of the entire Clifford + T-gate set [49]. Their procedure aims to minimize the T-gate count. Their simplification strategies apply local complementation and pivoting to remove Pauli spiders, spiders with a phase that is a multiple of \(\pi\), at the expense of adding phase gadgets. Applying the identity-removal and gadget fusion rules efficiently remove the phase gadgets. By rerunning the previous algorithm symbolically, it is possible to identify nonlocal phase recombinations that further reduce the T-gate count. This step is known as phase teleportation. The resulting optimization algorithm is implemented as the standard simplification routine in the PyZX library under the name "full reduce". It is found in many optimization pipelines as a pre- or post-processing step for T-gate minimization. The evaluation of a benchmark set that consists of 36 structured standard quantum circuits shows that "full reduce" improves the state-of-the-art T-count on 17% and matches on 72% of the instances. Further improvements were achieved when full reduce is paired with the dedicated T-gate optimizer TODD [50]. Combining both methods improve the T-count in 56 % of the benchmark circuits.

The following approaches develop spider nest identities for \(\frac{\pi}{4}\)-parity-phase operations to eliminate T-gates from quantum circuits [51]. A spider nest is a ZX diagram that consists only of \(\frac{\pi}{4}\) phase gadgets. Instead of rules that modify a single or few generators, spider nest identities take the full nest into account. Munson et al. independently derived the same spider nest identities and generalized them by connecting ZX-calculus and logical AND gates [52].

Beaudrap et al. introduce the phase gadget elimination (PHAGE) strategy, a systematic method that takes advantage of spider nest identities to reduce the T-gate count in ZX-diagrams [51], [53]. The core idea of PHAGE is to decompose larger and more complex phase gadgets into simpler and smaller ones. This decomposition allows for the effective application of spider nest identities to eliminate T-gates. The evaluation of PHAGE on a benchmark set of 35 parameterized circuits reveals that the state-of-the-art T-gate counts are improved for 21 instances under runtime constraints.

4.1.2.2 Architecture-aware

Zilk et al. use the phase teleportation algorithm of Kissinger and van de Wetering [49] to reduce the T-gate count and the Clifford elimination algorithm of Fagan et al. [47] to target photonic quantum computers [54]. The first step in their procedure is to express a quantum circuit only as a sequence of Hadamard, SWAP, and arbitrary Z-phase gates. The resulting circuit is converted to a measurement graph that corresponds to a graph-like (Definition 3) ZX-diagram. This ZX-diagram is optimized with the phase teleportation and Clifford elimination algorithms. Measurement-graphs can be directly converted into hardware instructions. The limiting factor of photonic architectures is the number of available photons and optical instruments. Compared to the standard photonic compiler Perceval [55], the ZX-based approach successfully compiles all benchmarked circuits and mostly outperforms with respect to the photon count and optical instrument count.

4.1.3 Qubit count↩︎

Vandaele et al. introduced an approach to minimize the logical qubit count in ZX-diagrams by systematically reordering and (un)bending spiders [56]. The core idea is to use the rewrite rules to change the structure of the ZX-diagram such that it is possible to find a vertical cut that reduces the maximum number of wires, hence minimizing the logical qubit count. The NP-hard problem of minimizing the number of wires through vertical cuts is formally known as the "fixed-endbags pathwidth problem". Consequently, finding an optimal solution is computationally expensive for large diagrams.

4.1.4 Two-qubit gate count↩︎

4.1.4.1 Architecture-independent

Staudacher et al. demonstrate that an average reduction of the edge count by 23% translates to a two-qubit gate reduction of 16% by applying a set of gflow-preserving rewrite rules (identity removal, spider fusion, local complementation, and pivoting) [35]. They introduce a new heuristic based on the expected change of the Hadamard wire count by the local complementation and pivoting rules [35]. A reduction of the Hadamard wire count correlates with the expected reduction of two-qubit gates. Slightly worsening of the cost function was allowed to permit further improvements later on. Stochastic and greedy algorithms are used to select the rewriting rules. Further integration with the NAM framework allowed for greater edge count reductions of 29% that translated into two-qubit gate reductions of approximately 21%.

In a related work, Holker extends these ideas by focusing on diagrams that preserve the stricter causal flow (cflow) property [57]. If cflow is preserved, the effect of a rewriting rule on the two-qubit gate count can be exactly quantified from change in the wire count, completely bypassing circuit extraction for all intermediate optimization steps. By maintaining cflow, Holker achieves an average two-qubit gate count reduction of 20%. ZX-diagrams with cflow have a circuit-like structure, that allows for a straightforward and efficient extraction. Moreover, verifying cflow is computationally less expensive than verifying gflow. However, it is important to note that only a limited set of rewriting rules, namely identity removal and spider fusion, are known to preserve cflow. This limitation severely restricts the possible diagram transformations but offers a trade-off between the solution quality and verification complexity.

The following two optimization strategies use the tket [58] compiler. Cowtan et al. demonstrated that the efficient pairwise synthesis of Pauli gadgets using tket decreased the average CNOT gate count by \(\approx 55 \%\) and improved the two-qubit depth by \(\approx 58 \%\) [59]. In a subsequent work, Cowtan et el. showed that a three step optimization routine improves the CNOT gate count and depth of the Unitary Coupled Cluster (UCC) Ansatz, a subroutine of Variational Quantum Eigensolvers, by \(69\%\) and \(75\%\) [60]: (i) the partition of the ZX-diagram of the UCC Ansatz into commuting sets is treated as a graph coloring problem, (ii) the resulting Pauli gadgets are converted to Phase gadgets, and (iii) the phase gadgets are efficiently synthesized using Matroid partitioning [61].

Another promising approach to quantum circuit optimization is the aggregation of multiple subcircuits that can be reordered and replaced by optimized template circuits. Template circuits are pre-optimized subcircuits that implement the same program flow as the subcircuit they are meant to substitute. Liu et al. introduce a string-based intermediate representation of subcircuits and a template matching algorithm that improves the CNOT gate count [62]. Although not explicitly relying on rewriting rules for optimization, Liu et al. employ ZX-calculus to verify the correctness of the intermediate representation and their associated templates.

4.1.4.2 Architecture-aware

Kissinger et al. [46] introduce the first architecture-aware optimization algorithm and outperform the existing compiler frameworks QuilC [63] and tket [64]. During circuit extraction, they restrict the Gaussian elimination of the parity map to only include nearest-neighbor rows using the Steiner-Gauss algorithm. Consequently, CNOT gates can only act between neighboring qubits.

Villoria et al. modified the circuit extraction algorithm of Backens et al. [39] to target trap-ion computers that are highly dependent on global gates [45]. Instead of Gaussian elimination, the frontier is extracted solving a linear program that ensures only vertices are extracted which can be included in the same global gate. Afterwards peephole optimization merges the extracted two-qubit gates into global GMS gates. This algorithm outperforms the Qiskit implementation on most quantum circuits.

Van de Griend and Duncan develop a two step recursive optimization strategy that considers qubit connectivity restrictions of the underlying quantum architecture, thus circumventing the need for an additional routing step, by using the notion of phase polynomials [65]. The algorithm introduces a biadjacency matrix \(\mathit{\mathbf{P}}\) between the phase gadgets legs and the attached qubits. For the base recursion step, the phase gadget with with the lowest connectivity that is not needed to synthesize other phase gadgets is removed. The selected phase gadget must be a non cutting vertex, meaning the column in \(\mathit{\mathbf{P}}\) with the most \(0\) or \(1\) entries. Afterwards, the phase gadgets are synthesized by decomposition into a CNOT ladder as shown in Figure 6. The second recursion step removes rows from the remaining phase-gadget biadjacency matrix by row addition. Every row operation adds CNOT gates to the ladder. To eliminate excess CNOT gates, the Steiner-Gauss algorithm is run on the resulting parity map.

Winderl et al. adapt the architecture-aware approach of Gorgioso and Yeung [66] by replacing simulated annealing with a heuristic search in combination with a divide-and-conquer strategy [67]. The first step in their strategy is the simplification of the ZX polynomial by removing, merging, and moving phase gadgets. Afterwards, the ZX-diagram is split into a left parity, a right parity, and a ZX polynomial region. A Gaussian elimination optimization algorithm minimizes the CNOT count based on the combined cost of the region. The cost of removing a phase gadgets legs is computed by the minimal spanning tree of the architectural-dependent connectivity. Their novel heuristic based on the shortest path between the control and target qubit of CNOT gates is used in conjunction with the Steiner-Gauss algorithm to synthesize the phase gadgets in both parity regions. The remaining ZX polynomial is regrouped from a leg-based score and, following a divide-and-conquer strategy, split into subregions again. These steps are recursively repeated until no ZX polynomial remains. Both methods are outperformed by other state-of-the-art algorithms, such as tket [58], for structured circuits. However, the heuristic approach of Winderl et al. [67] exhibits better scaling in the qubit count and CNOT tree depth compared to the stochastic approach by Gogoiso and Yeung [66].

Huang et al. develop a novel approach for architecture-aware synthesis of Trotter operators [68]. Trotterized time evolution operators can be expressed in terms of Pauli gadgets. Pauli gadgets can be described by exponentiation of Pauli strings. Each letter of the Pauli string corresponds to a Pauli gate. The core idea of their approach is to lexicographically reorder the Pauli strings that compose the Pauli gadgets of the Trotter operator. As a result, phase gadget legs with the same letter are grouped on the same qubit. Reordering of non-commuting Pauli gadgets is possible because the introduced error (Trotter error) is outweighed by the error that originates from noisy gates. Their algorithm iteratively diagonalizes and disconnects qubits. The highest entangled qubit is chosen for the current iteration. The diagonalization step places single qubit Clifford gates on the selected qubit until the gadget has either no leg or a Z leg. Based on the Pauli gadget leg, the disconnection step introduces two CNOT gates and up to two single-qubit Clifford gates. This disconnection step reduces the entanglement of the selected qubit. The selection of the qubit is determined by an entanglement heuristic. Qubit entanglement is calculated from the occurrences of the I-gate in the Pauli string and the length difference between the largest and smallest substrings that exclude the I-gate. This approach outperforms the state-of-the-art CNOT count for random circuits and larger couple-cluster unitaries.

4.2 Metaheuristic↩︎

4.2.1 Two-qubit gate count↩︎

4.2.1.1 Architecture-independent

Chen et al. improve the two-qubit gate count by \(2\%\) compared to the heuristic approach of Staudacher et al. [35] using simulated annealing to partition a quantum circuit into subcircuits that are optimized [69]. In a first step, the quantum circuit is divided into sequential layers of gates. Per layer, one single-qubit gate, one target and control qubit of multi-qubit gates can act at most on each qubit. Subcircuits are groups of sequential layers. Starting from a random configuration of subcircuits, each circuit is converted into a ZX-diagram, optimized, and extracted. The resulting circuits are iteratively merged. Following a delayed gate approach, known gate commutation and substitution rules are used to further improve the circuit depth and gate count. The delayed gate approach is implemented in PyZX [38] under the name basic optimization. For each iteration of the simulated annealing algorithm, the starting configuration of the subcircuits is changed.

4.2.1.2 Architecture-aware

Gogioso and Yeung reduce the CNOT count for mixed phase gadgets ZX-diagrams by \(27\%\) on a grid-shaped topology [66]. Their technique is grounded in the decomposition of phase gadgets and is paired with simulated annealing and CNOT conjugation rules. The ZX-diagram is split up into three layers: (i) a left nearest-neighbor CNOT layer, (ii) a right nearest-neighbor CNOT layer, and (iii) a mixed phase gadget ZX-diagram. The cost of implementing a phase gadget is computed from the distance between distinct legs that are mapped onto the topology. This corresponds to the nearest-neighbor CNOT count. The total cost of a circuit is the sum of all its CNOT gates. Simulated annealing is used to explore different phase gadget mappings. To exploit symmetries, the phase gadgets are converted to CNOT ladders (Figure 6), so that gate conjugation rules can be applied.

Ewen et al. introduce a genetic programming approach for synthesizing shallow quantum circuits with fewer two-qubit gates from ZX-diagrams [70]. The original quantum circuit is converted into a ZX-diagram that will be evolved via a set of mutation operations. In their work, they implement two different categories of mutations. Semantics-preserving mutations are formed by the rewriting rules of ZX-calculus. Semantics-breaking mutations, such as edge flipping and edge addition, introduce new connectivity patterns in the ZX-diagram. Although these semantics-breaking mutations violate the correctness of the circuit, they permit the exploration of a larger state-space, at the cost of circuit fidelity. Experimental results demonstrate that ZX-based genetic programming can produce well-balanced circuit solutions, achieving results close to the state-of-the-art for circuit depth, circuit fidelity, and two-qubit gate count.

4.3 Reinforcement Learning↩︎

4.3.1 Metric agnostic↩︎

Nägele and Marquardt implement a scalable and general reinforcement learning framework for the optimization of ZX-diagrams that can be adapted for different metrics [71]. Actions are grouped by node and edge impact, irrespective of the preservation of gflow or cflow. As a consequence, quantum circuit metrics are not considered because of the lack of circuit extraction. In contrast to the RL-approaches of Riu et al. [72] and Mattick et al. [73], the reversibility of rewriting rules is considered beyond spider un/fusion by including the bialgebra rule. Furthermore, the agent can mask actions to improve the efficiency of training.

4.3.2 Two-qubit gate count↩︎

Riu et al. introduce a RL-based approach that uses graph neural networks to minimize the two-qubit gate count [72]. They restrict the set of rewriting rules to gflow-preserving transformations. Circuit extraction is treated as a black-box, simplifying the optimization pipeline. The RL agent is trained to either select and apply a rewriting rule or to terminate the optimization process. The agent can apply multiple rules until it decides to terminate. A reward function guides the decision based on metrics such as the two-qubit gate count. Moreover, the RL framework is highly flexible and can incorporate other reward functions such as T-gate count or circuit depth. A key advantage of this RL-based strategy is the scalability for larger ZX-diagrams. Although the initial training phase can be computationally demanding, the resulting agent can generalize its learned strategies to new diagrams independent of their size. Among the approaches surveyed, the combination of this RL-based optimization approach with Holker’s cflow-preserving framework represents one of the most effective strategies to reduce the two-qubit gate counts in ZX-calculus-based circuit optimization.

4.4 Tree search↩︎

4.4.1 Metric agnostic↩︎

Fischbach et al. propose an exhaustive search strategy combined with pruning conditions to optimize ZX diagrams [74]. The objective of the search is to find a sequence of rewriting rules that optimizes a given metric. Their method explores the state-space using depth-first search (DFS) and iterative deepening depth-first search (IDDFS) by applying all possible rule combinations. Pruning conditions terminate branches of the search tree, e.g., if circuit extraction is impossible. Despite being a complete search for a rewriting rule sequence that minimizes a given metric, the main drawback of their approach is the computational cost. A comparison of their IDDFS-based approach and the T-gate count obtained by the full reduce algorithm of Duncan et al. [29] was performed. The analysis demonstrated equivalent results in 89% of the circuits within a benchmark set of 100 structured circuits. Nevertheless, one strength of their approach is the metric-agnosticism; it is not tied to the optimization of a single metric such as the T-gate count. They demonstrated its flexibility by targeting the edge count, a proxy for two-qubit gates, with the same strategy. While the exhaustive nature of the search makes the approach computationally inefficient for larger circuits, it allows for optimal solutions for small sized circuits.

Mattick et al. propose a hybrid approach that combines RL with a tree search algorithm that uses the full set of standard ZX-calculus rules [73]. Their method slightly outperforms the stochastic and gflow preserving techniques of Staudacher et al. [35] for random circuits. In this framework, the graph neural network replaces the heuristics by learning which and where a rewriting rule should be applied or if the agent needs to stop. The tree search allows to backtrack if not beneficial transformations are encountered. Similarly to Riu et al. [72], the agent learns where to apply which rule in the ZX-diagram based on a reward function that represents a metric. However, at each node of the tree, the agent is allowed to perform only one diagram transformation. The use of the complete set of ZX-calculus rewrite rules permits the exploration of a larger state-space at the cost of post-processing to ensure circuit extraction. The key advantage of this approach is its generality. The framework aims to learn optimal rewrite sequences for any chosen metric and is not limited to minimizing two-qubit gate counts.

5 Framework↩︎

Quantomatic is the first implementation of ZX-calculus for quantum circuit optimization and has been quickly superseeded by PyZX [38], [47]. PyZX is a Python library that implements a two-step graph rewriting system to modify a ZX-diagram. Each rule consists of a matching and a rewriting function. The matching function returns all occurrences of spiders where it is possible to apply the specified rule. The rewriting function transforms the ZX-diagram based on the rule and provided matches. Moreover, it offers an implementation of the T-gate optimization algorithm with the name full reduce. Other notable features of PyZX include circuit verification, extraction, and tight integration into other quantum computing frameworks such as Qiskit [75]. Quizx is a faster Rust implementation of some core features of PyZX by the same project. It offers Python bindings and an API similar to PyZX. The Munich Quantum Toolkit provides another implementation of ZX calculus written in C++, including support for circuit optimization and verification [76].

6 Challenges↩︎

6.0.0.1 Scalability

A major challenge in the optimization of ZX-diagrams lies in the scalability of rule-based rewriting approaches, especially as small real-world quantum circuits result in large ZX-diagrams. With an increase in size of ZX-diagrams, the computational complexity grows rapidly, limiting the practical application of existing techniques to small-scale quantum circuits.

Current heuristic-based optimization strategies typically target a single metric, such as reducing the number of non-Clifford spiders (e.g., Duncan et al. [29], Kissinger et al. [49], and Beaudrap et al. [53]) or minimizing the number of two-qubit gates (e.g., Staudacher et al. [35], Holker et al. [57], and Fagan and Duncan [47]). However, while heuristics improve computational performance, focusing on a single objective fails to capture the complex features of quantum circuits and how to balance them. We identify the clear need for improved heuristics that can balance multiple metrics to improve the computational performance of existing strategies.

Recent works have explored RL approaches for diagram rewriting (Nägele et al. [71], Riu et al. [72], Mattick et al. [73]), demonstrating promising results on small-scale ZX-diagrams. Although RL is still computationally expensive, the training stage can be seen as an upfront cost, as the learned strategies appear to be at least partially generalizable. Further enhancement of RL-based methods on small ZX diagrams could allow better optimization results for large-scale circuits. Moreover, the lack of interpretability and the theoretical background as to why some rewriting sequences are more beneficial than others poses additional challenges. Incorporating explainable RL could form the basis for new and computationally efficient heuristics that are applicable for large-scale ZX-diagrams.

Another promising research direction is the introduction of intermediate representations that can aggregate subdiagrams and enable more efficient state-space exploration, similar to that of Liu et al. [62]. The use of an intermediate representation allows template matching of pre-optimized subcircuits. Chen et al. [69] dynamically group layers into subcircuits. Future work should focus on the efficient partition and resynthesis of quantum circuits for several reasons. Dividing larger quantum circuits into smaller subcircuits is beneficial because the resulting subdiagrams are smaller and can be optimized efficiently. As the different subdiagrams are independent of each other, each instance can be solved in parallel. This flexibility could lead the way for dynamic selection of the optimization algorithm based on the characteristics of each subdiagram. Furthermore, a subdiagram only needs to be optimized once and can be substituted for further instances. Another possible research direction is to allow for the two-dimensional partition of quantum circuits for improved optimization results using the intermediate representation of Liu et al. [62]. Replacing the SA approach that changes the subcircuit partition of Chen et al. [69] with an exhaustive search could further improve the results.

6.0.0.2 Architecture-awareness

Quantum computing architectures fundamentally differ from each other and offer different advantages and limitations that quantum circuit optimization needs to take into account. There are four dominant quantum architectures currently considered by ZX-based quantum circuit optimization: (i) superconducting, (ii) trapped-ion, (iii) neutral-atom, and (iv) photonic quantum architectures.

To create executable quantum circuits for superconducting quantum computers spatial information (topology), qubit connectivity, noise, and error correction. Some work focuses on architecture-aware synthesis of phase gadgets and polynomials (e.g., van de Griend and Duncan [65], Gogioso and Yeung [66], and Winderl et al. [67]) that takes an architecture’s topology into account, others aim to [46] restrict qubit connectivity. However, there is no unified framework that combines the different methods. Transpilation would be more efficient if ZX-diagram optimization could target a specific architecture without the need for additional optimization steps to consider decoherence, gate error, routing, and error correction. Phase gadgets are the native representation of multi-qubit gates in ZX-calculus, therefore improving the architecture and topology aware synthesis is a promising field for future research.

ZX-calculus is a natural candidate for photonic quantum computing because the architecture’s measurement graph corresponds to a graph-like (Definition 3) ZX-diagram. This equivalence permits the modification of the measurement graph using rewriting rules. As the measurement graph can be directly converted into hardware instructions, additional optimization steps are not required. The initial work of Zilke et al. [54] demonstrates the effectiveness of ZX-calculus to target photonic quantum computers. Upcoming work could extend the approach of Zilke et al. to use different optimization algorithms for T-gate and Clifford gate elimination. Especially the RL-approach of Mattick et al. [73] seems to be a promising candidate for photonic architectures, as it balances the quality and exploration of the solution. As photonic architectures do not require circuit extraction, the quality of the solution is not impacted by post-processing and circuit extraction. Furthermore, future work should address photonic architectures with different graph states that compose the measurement graph.

The initial work by Staudacher et al. [48] proof the feasibility of ZX-calculus when targeting neutral-atom architectures. In their work, they adapt the circuit extraction algorithm of Backens et al. [39] to efficiently synthesize the architecture’s native multi-qubit gates. Forthcoming endeavors should include ZX-diagram optimization methods that take the reduction of global phase gates and the preference of multi-qubit gates before circuit extraction into account.

The standout features of trapped-ion quantum computers are the all-to-all qubit connectivity and the use of global gates. Villoria et al. [45] modify the circuit extraction algorithm of Backens et al. [39] to only extract vertices that take part in the same global gate. Phase gadgets are the ZX-calculus equivalent of multi-qubit gates. In the future, work could use the notion of phase gadgets during circuit extraction to improve global gate count and grouping. Furthermore, there is no dedicated ZX-based optimization strategy that targets trap-ion architectures outside of circuit extraction.

6.0.0.3 Circuit extraction

A significant limitation of ZX diagram-based quantum circuit optimization is the computational cost of circuit extraction. In the general case, circuit extraction is a #P-hard combinatorial problem [40]. Although polynomial-time algorithms exist for ZX-diagrams that preserve the graph-theoretic conditions of gflow and cflow, only a small subset of rules have been proven to preserve these flow properties. In addition, verifying the presence of a flow is computationally expensive, with cflow being less demanding than gflow. In the absence of general or causal flow, circuit extraction becomes intractable. Especially noteworthy are the extraction algorithms of Duncan et al. [29] and its extension by Backens et al. [39] that form the basis for various architecture-aware synthesis algorithms (e.g., Kissinger et al. [46], Villoria et al. [45], and Staudacher et al. [48]).

We established that many approaches disregard intermediate ZX diagrams without the presence of general or causal flow, effectively ignoring large parts of the state-space that might contain the optimal solution. Future research should focus on methods that explore intermediate ZX diagrams without preserving flow properties while keeping the overhead introduced by circuit extraction at a minimum. This can be achieved by improving or avoiding circuit extraction as much as possible. Based on Quanz et al. [77] subsequent work should aim to improve parallel circuit extraction to speed up other state-space exploration algorithms.

A promising research direction is to replace the gaussian elimination of the biadjacency matrix during circuit extraction by a LP. Similarly to Villoria et al. [45], future LP formulation could include architectural constraints. Circuit extraction is an iterative process, and the biadjacency matrix only captures the connectivity of the current frontier. Therefore, the LP only encodes current information and it is not guaranteed that the optimal solution of the current LP results in the best global solution. Upcoming work should combine LP-based circuit extraction with a backtracking algorithm that allows to prune LP solutions that result in unfavorable quantum circuits. Another way of providing context for LP-based circuit extraction, is to provide information of the closest already extracted frontier gates for each qubit.

It is important to recognize that the circuit properties strongly depend on the circuit extraction algorithm itself. Current circuit extraction algorithms replicate spider connectivity by two-qubit gates, potentially increasing the circuit depth and two-qubit gate count. Improvements of circuit extraction algorithms, both in computational efficiency and in circuit quality, should allow for better optimization results. In particular, only the work of Villoria et al. [45] treats circuit extraction as a combinatorial problem. Consequently, efficient formulations beyond LP, constraints, and solvers for the circuit extraction problem provide a vast field for future endeavors.

Many non-ad-hoc approaches require regular circuit extraction (e.g., Fischbach et al.[74], Ewen et al. [70], and Riu et al. [72]). A critical challenge to avoid circuit extraction is that many characteristics of quantum circuits, such as the two-qubit gate count or circuit depth, are not native concepts of ZX-diagrams. Investigating other approximations of quantum circuit metrics at the ZX-diagram level, such as Hadamard wires serving as a proxy for two-qubit gates [35], might reduce the amount of circuit extraction required. A promising first step could be the construction of a surrogate model for circuit extraction that can be quickly evaluated by different approaches.

6.0.0.4 Multi-objective optimization

The approaches presented in this survey are designed to primarily target one metric. Nevertheless, it does not suffice to optimize one metric alone to capture the complexity of current quantum computing architectures. Some works follow a lexicographic approach in which one metric after another is improved. A typical example is to first run the elimination of the T-gate by [29], [49] and then optimize the two-qubit gate count on the resulting ZX-diagram (e.g. [35], [47], [57]).

The work of Ewen et al. [70] suggests that the best ZX-diagram results in a circuit close to its best known quantum circuit counter part for circuit depth and two-qubit gate count. However, on the non-target metrics, the best circuits perform worse than their ZX-based counterparts.

So far, there exist no deliberate multi-objective optimization approaches applied to ZX-based quantum circuit optimization that aim to find a trade-off between fundamentally different metrics. Multi-objective optimization seems to be a promising candidate for architecture-aware optimization where a tradeoff between independent metrics and different architectural specifications, such as qubit connectivity and spatial dimensions, is required. Bridging the gap towards multi-objective optimization would greatly simplify the transpilation pipeline, resulting into an integrated and potentially less computationally demanding framework.

6.0.0.5 ZX-diagram feature encoding

Despite many advances in ZX-diagram optimization and circuit extraction techniques, a fundamental question remains: what features of a ZX-diagram actually predict or determine the quality of the resulting quantum circuit? While some connections between the ZX-diagram and the quantum circuit are trivial, e.g., the number of \(\frac{\pi}{4}\)-phase spiders directly translates to the number of T-gates, other features are only an approximation or not translated at all. The example we saw before was that the number of Hadamard edges and the overall spider connectivity serve as a proxy to estimate the two-qubit gate count [35].

Further research on the mapping between ZX-diagram characteristics and quantum circuit properties could enable the development of better optimization methods that explicitly account for architectural constraints. Especially the inclusion cumulative gate error rates, qubit connectivity limitations, and coherence time would alleviate the need of a full transpilation pipeline. Such mappings could serve as a surrogate model that allows quicker heuristic or learning-based optimization without repeatedly requiring circuit extraction and transpilation to assess the quality of the solution.

Furthermore, we propose the systematic addition of characteristics that form a composite metric that aggregates information from features derived from the ZX-diagram, properties of the logical quantum circuit, and characteristics of the final transpiled and executable circuit. Investigating such composite metrics allows to dynamically evaluate characteristics based on the current solution quality and computational cost. Such approaches would allow to identify the relative importance of individual features in determining overall circuit quality. For example, it is unnecessary to take into account accumulated gate error and routing if the initial features already indicate an unfeasible solution.

This adaptive composite metric would allow to exclude or adjust certain optimization steps based on the balance between the expected quality of the solution and the computational cost of fully evaluating that metric. By quantifying this trade-off, the composite metric could be added to many methods that require a cost function while also championing a full compilation workflow without being explicitly designed for it.

7 Conclusion↩︎

This survey provides an overview of quantum circuit optimization using ZX-calculus, with an emphasis on optimization techniques and target metrics. The surveyed works demonstrate that ZX calculus offers a powerful, compact, and universal framework that enables optimizations beyond traditional circuit-level techniques. This survey identified that the adoption of ZX-based methods is impeeded by scalability issues, a reliance on single-objective heuristics, and the computational cost of circuit extraction.

Several promising research directions emerge: future work must expand beyond single-metric optimization and adopt multi-objective optimization that jointly consider architecture-independent and architecture-aware metrics. Additionally, there is a clear need to link ZX-diagram and quantum circuit characteristics, potentially through surrogate models or composite metrics that alleviate the computational cost of circuit extraction. Furthermore, circuit extraction could be improved by leveraging combinatorial optimization with the potential inclusion of architectural constraints. Finally, more approaches should take into account the underlying quantum computing architecture. Especially trapped-ion, neutral-atom, and photonic devices are underrepresented.

Overall, ZX-calculus is positioned as an intermediate representation for circuit optimization, that is capable of bridging diagrammatic reasoning with architectural constraints of current and future quantum hardware. Improvements of heuristics, scalability, and explainable learning-based methods are necessary to design algorithms that handle efficiently the non-terminating nature of ZX-calculus.

In summary, ZX-calculus is a candidate for an integrated framework that allows architecture-independent and architecture-aware quantum circuit optimization for current and future quantum computing hardware.

References↩︎