ZX-Calculus Intermediate Representation

The ZX-calculus has proven to be a very good general-purpose tool for reducing the T gate count without auxiliary wires. It is particularly powerful when combined with phase polynomial based methods such as TODD.

The body of work in [1, 2, 3] describes a procedure for general T count optimization in quantum circuits and is implemented in pyzx.full_optimize. The main function for ZX-calculus based T-gate optimizations is done in pyzx.full_reduce from [1], for which we want to walk through the basic rules and steps here. The most important take-away is that any quantum circuit can be brought into reduced gadget form, where every internal spider is a non-Clifford or part of a non-Clifford phase gadget (see bottom of the page for full definition). This is what pyzx.full_reduce achieves:

>>> import pyzx as zx
>>> circ = zx.Circuit(5)
>>> circ.add_gate("TOF", 0, 1, 4)
>>> circ.add_gate("TOF", 2, 4, 3)
>>> circ.add_gate("TOF", 0, 1, 4)
>>> circ = circ.to_graph()
>>> zx.full_reduce(circ)
>>> zx.draw(circ)

Spiders or phase gadgets with angles \frac{\pi}{4} (or \frac{7 \pi}{4} for T^\dagger) cost the same as T gates. The original T cost 3 \cdot 7 = 21 of the circuit (seven for each of the three Toffoli gates) is reduced to 15.

You can find experimental PennyLane functions with the same names in the resources tab.

T gate reduction pipeline (pyzx.rull_reduce)

Let us walk through each of the components alongside some code. Let us first define a circuit consisting of three Toffoli gates.

>>> import pyzx as zx
>>> circ = zx.Circuit(5)
>>> circ.add_gate("TOF", 0, 1, 4)
>>> circ.add_gate("TOF", 2, 4, 3)
>>> circ.add_gate("TOF", 0, 1, 4)
>>> zx.draw(circ)

Graph-like normal form

Next we translate the circuit to a normal form that is called graph-like.

>>> circ = circ.to_graph()
>>> zx.to_graph_like(circ)
>>> zx.draw(circ)

Graph-like diagrams are such that all spiders are Z spiders and connected with each other via Hadamard edges. Additionally, every input or output is connected to a Z-spider and every Z-spider is connected to at most one input or output. It can be shown that any quantum circuit can be made graph-like, hence it can be considered a normal form [2]. In this process, non-Clifford gates are never increased and can actually sometimes be decreased (as is the case in the example above, going from 21T to 20T spiders).

Clifford optimization

We can use the following two rules introduced in [2] with which we can optimize the Clifford part of the circuit. The first is called local complementation (LC) and removes the Clifford (\pm\frac{\pi}{2}) spider marked with \color{red}*:

The other rule is called pivoting (P1) and removed the marked Pauli spiders (multiples of \pi):

Using these rules, one can ensure that a graph-like ZX-diagram can be made such that it does not contain any proper Clifford spiders internally, and there are no Pauli spiders adjacent to a boundary spider or adjacent to another Pauli spider (see Theorem 5.4 in [2] and its proof for the algorithm).

This can be done using pyzx.interior_clifford_simp

>>> zx.simplify.interior_clifford_simp(circ)
>>> zx.draw(circ)

Any remaining interior Pauli spider can be removed with the following two pivot rule variations.

This comes at the cost of introducing a phase gadget

which in this case corresponds to the operator \exp\left(-i \alpha (\bigotimes_i Z_i) \right) (see, e.g. GadgetSynth). With these extra rules we can transform the graph-like ZX-diagram such that all phase gadgets are non-Clifford.

>>> zx.simplify.clifford_simp(circ)
>>> zx.draw(circ)

T gate optimization

Now that we have all non-Clifford gates in the form of phase gadgets, we can use the following two rules to reduce their number, thereby reducing the T-gate count.

The process of performing the pivots and then merging non-Clifford phase gadgets is repeated until no new mergers are possible.

The overall procedure is given by algorithm 4.3 in [1]:

1. Apply (LC) until all interior proper Clifford vertices are removed.
2. Apply (P1), (P2) and (P3) until all interior Pauli vertices are removed or transformed into phase-gadgets.
3. Remove all Clifford phase-gadgets using (LC) and (P1)
4. Apply (ID) and (GF) wherever possible. If any matches were found, go back to step 1, otherwise we are done.

This is implemented in pyzx.full_reduce. We can start from the vanilla circuit and let it run all the previous optimization steps.

>>> import pyzx as zx
>>> circ = zx.Circuit(5)
>>> circ.add_gate("TOF", 0, 1, 4)
>>> circ.add_gate("TOF", 2, 4, 3)
>>> circ.add_gate("TOF", 0, 1, 4)
>>> circ = circ.to_graph()
>>> zx.full_reduce(circ)
>>> zx.draw(circ)

This is yet another normal form, called reduced gadget form, and is defined by Definition 4.4 in [1] as:

• Every internal spider is a non-Clifford spider or part of a non-Clifford phase-gadget.
• Every phase-gadget has more than one target.
• No two phase-gadgets have the same set of targets.

Finally, a circuit can be extracted using the methods described in [3] via pyzx.extract_circuit.

>>> circ = zx.extract_circuit(circ)
>>> circ = circ.to_basic_gates()
>>> circ = zx.basic_optimization(circ)
>>> zx.draw(circ)

We can do this with a PennyLane circuit as well:

import pennylane as qml
from pennylane.labs.zxopt import full_reduce

def qfunc():
    qml.Toffoli((0, 1, 4))
    qml.Toffoli((2, 4, 3))
    qml.Toffoli((0, 1, 4))

circ = full_reduce(qfunc)
print(qml.draw(circ)())

0: ────╭X──T†─────╭●────╭●──────────╭X────────────────────────────────────────────────────╭●─╭X─ ···
1: ────│──╭X───T†─│──╭●─│─────╭●────│──╭X──S────────────────────────────╭Z──────────╭Z────│──╰●─ ···
2: ──H─╰●─╰●───T──╰X─╰X─│───T─│──╭●─╰●─╰●──H──T─╭●──────────────────╭●──│──╭X──T──H─│───T─╰X──T† ···
3: ─╭Z──────────────────│─────│──│──────────────╰X──T†─╭Z────────╭●─╰X──╰●─│───T─╭●─│─────────── ···
4: ─╰●──────────────────╰X────╰X─╰X────────────────────╰●──H──T†─╰X──T†────╰●────╰X─╰●──T─────── ···

0: ··· ──S†─╭●─╭X───S─╭●────╭Z────╭Z─╭●─╭X─╭●─┤  
1: ··· ─────│──╰●─────│─────│─────│──╰X─╰●─╰X─┤  
2: ··· ─────╰X──T†────╰X──T─│───H─│───────────┤  
3: ··· ─────────────────────╰●────│───────────┤  
4: ··· ───────────────────────────╰●──H───────┤  

Note that there are minor discrepancies due to some extra post-processing in labs.zxopt.full_reduce. The important thing is that in both cases the T cost is 15.