Picturing Quantum Software

John van de Wetering

                 

SEFM, Aveiro 2024


https://zxcalc.github.io/book

Quantum Software

the code that runs on a quantum computer

INIT 5
CNOT 1 0
H 2
Z 3
H 0
H 1
CNOT 4 2
...
 ↔

Quantum Software

code that makes that code (better)

Optimisation Simulation & Verification Error Correction

Quantum computing uses gates

  • We will focus on qubit quantum computation.
  • So our fundamental state space is \(\mathbb{C}^2\).
  • In the circuit model we use quantum gates.
  • Single-qubit gates: NOT, S, T, H.
  • Two-qubit gate: CNOT (controlled NOT): $\ket{x,y} \mapsto \ket{x,x\oplus y}$.
  • This is an approximately universal gate set.

Quantum gates as matrices

Note: quantum gates are just matrices...

\( \text{S} = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix} \qquad \text{H} = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \)

\( \text{CNOT} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} \)

... but nobody wants to deal with these things directly.

Quantum gates in circuit notation

X   =   NOT   =     =   \(\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\)

CNOT  =   =   \(\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\)

Hadamard  =   =  \(\frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\)

\(R_Z(\alpha)\) =  =  \(\begin{pmatrix} 1 & 0 \\ 0 & e^{i\alpha} \end{pmatrix}\)

Z := \(R_Z(\pi)\)    S := \(R_Z\left(\frac{\pi}{2}\right)\)    T := \(R_Z\left(\frac{\pi}{4}\right)\)

Quantum circuits

An example quantum circuit:

Optimising circuits the old-fashioned way

...

A better idea: the ZX-calculus

A complete set of equations for qubit QC

So what are these diagrams really?

Spiders

What gates are to circuits, spiders are to ZX-diagrams.

\(\ket{0 \cdots 0}\!\bra{0 \cdots 0} + e^{i \alpha} \ket{1 \cdots 1}\!\bra{1 \cdots 1}\) \(\ket{+ \cdots +}\!\bra{+ \cdots +} + e^{i \alpha} \ket{- \cdots -}\!\bra{- \cdots -}\)

For example:

  =   \(\ket{0}\bra{0} + e^{i \alpha} \ket{1}\bra{1}\)   =   \(\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0 \\ 0 & e^{i\alpha} \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\alpha} \end{pmatrix}\)

  =   \(\ket{+}\bra{+} + e^{i \alpha} \ket{-}\bra{-}\)   =   \(\frac{1}{2} \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} + \frac{1}{2} e^{i\alpha} \begin{pmatrix} 1 & -1 \\ -1 & 1 \end{pmatrix}\)

Spiders cont.

If \(\alpha=0\) we drop the label:

  =   \(\ket{0 \cdots 0}\bra{0 \cdots 0} + \ket{1 \cdots 1}\bra{1 \cdots 1}\)

  =   \(\ket{+ \cdots +}\bra{+ \cdots +} + \ket{- \cdots -}\bra{- \cdots -}\)

Example:

  =   \(\ket{+} + \ket{-} = \sqrt{2}\ket{0}\)         =   \(\ket{0} + \ket{1} = \sqrt{2}\ket{+}\)

  =   \(\ket{+} - \ket{-} = \sqrt{2}\ket{1}\)         =   \(\ket{0} - \ket{1} = \sqrt{2}\ket{-}\)

We ignore these non-zero scalar factors.

Vertical composition

Spiders can be composed in two ways.

Vertical composition gives tensor product:

  =   \(\begin{pmatrix}1 & 0 \\ 0 & 0 \\ 0 & 0 \\ 0 & 1\end{pmatrix}\)

  =   \(\begin{pmatrix}1 & 0 \\ 0 & 0 \\ 0 & 0 \\ 0 & 1\end{pmatrix} \otimes \begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix}\)   =   \(\begin{pmatrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{pmatrix}\)

Another example

  =   \(\begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix} \otimes \frac{1}{\sqrt{2}}\begin{pmatrix}1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0\end{pmatrix}\)

  =   \(\frac{1}{\sqrt{2}}\begin{pmatrix}1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0\end{pmatrix}\)

Horizontal composition

Horizontal composition is regular composition of linear maps:

  =  

\(\frac{1}{\sqrt{2}}\begin{pmatrix}1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0\end{pmatrix} \begin{pmatrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0\end{pmatrix}\)

Building ZX-diagrams

Any ZX-diagram is built by simply iterating these vertical and horizontal compositions.

Symmetries

Note:

Hence, we may write:

Symmetries

In general: only connectivity matters

ZX-diagrams summary

  • Two types of generators: Z-spiders and X-spiders
  • Can compose both horizontally and vertically
  • Wires can connect every which way

How powerful are ZX-diagrams as a representation?

Theorem:

ZX-diagrams are universal: any linear map between qubits can be represented as a ZX-diagram.

So far it's just notation. What can we do with it?

The rules of the ZX-calculus

A complete set of equations for qubit QC

Spider fusion

Connected spiders of same colour fuse

Hadamards and colour-changing

Definition of Hadamard in ZX:

    

Derived rule: commuting Hadamards changes colour

Consequence: Everything in ZX holds with colours reversed

Example 1: GHZ-preparation circuit

Recall that the GHZ-state is \(\ket{000} + \ket{111}\).

The following circuit creates a GHZ-state:

Proof:

Example 2: Teleportation

Let \( \ket{\Psi} \) represent a side of a Bell state.

Then this is the standard quantum teleportation protocol:

Proof:

Q: How to we scale up?

≈ 30 spiders

≈ $10^3$ - $10^8$ spiders

A: Automation

PyZX

  • Open source Python library for circuit optimisation, experimentation, and education using ZX-calculus


https://github.com/zxcalc/pyzx

QuiZX


  • Large scale circuit optimisation and classical simulation library for ZX-calculus


https://github.com/zxcalc/quizx

ZXLive

  • GUI tool based on PyZX


https://github.com/zxcalc/zxlive

The idea

  • Turn equations into directed rewrite rules

          $\Rightarrow$      

  • Give efficient rewriting strategies for tractable fragments of the ZX-calculus, such as the Clifford ZX-calculus

ZX Simplifier

ZX Circuit Optimisation

...has 2 phases. First simplify...


$\Rightarrow$

ZX circuit optimisation

...and extract:

2-qubit gate count reduction



arXiv:2311.08881 | arXiv:2312.02793

T-count reduction



  • "Reducing the number of non-Clifford gates in quantum circuits". AK, van de Wetering. Phys Rev A 2020
  • "Optimal Compilation of Parametrised Circuits". van de Wetering, Yeung, AK. 2024 arXiv:2401.12877

Who cares about T-count anyway?

  • T-count is (probably) very important for fault-tolerant QC
  • Q: Why does it matter today?
  • A: Simulating quantum circuits on a classical (super)computer.

    →

Classical simulation

  • ...is hard (we think)
  • All known algorithms are exponentially hard in some measure of circuit size, e.g.

    # of qubits     tree width
                  T-count $\leftarrow$ stabilizer decompostion

  • Stabilizer rank decomposition: simulate a hard circuit by summing over LOTS of easy circuits

Stabilizer rank

The stabilizer rank of $|\psi\rangle$ is the least $N$ such that: \[ |\psi\rangle = \sum_{i=1}^N k_i |\xi_i\rangle \] for all $|\xi_i\rangle$ stabilizer states.


Gottesman-Knill $\implies$ amplitudes can be computed in $N \cdot$ poly time.

Stabilizer rank

  • Good stabilizer decompositions $\implies$ fast classical simulation
  • Hard to compute in general, but upper bounds exist:
    • Naive: decomposing each T gate into 2 stabilizer terms, e.g.

      $T|{+}\rangle = |0\rangle + e^{i\pi/4} |1\rangle$

      gives $2^t$ terms.
    • Bravyi-Smith-Smolin decomposition of 6 T gates as 7 stabilizer terms:

      gives $2^{0.468t}$ terms.

Idea: Do stabilizer decompositions on ZX-diagrams!

Why?

  • Produces $7^{n/6} \approx 2^{0.468t}$ terms for $t$ T-gates
  • Interleaving ZX-simplification can make that significantly less

ZX-stabiliser decompositions

  • BSS decomposition: $2^{\alpha t}$ terms for $\alpha \approx 0.468$
  • SotA is $\alpha \approx 0.396$ (Qassim, Pashayan, Gosset 2021)
  • ZX-reduction $\Rightarrow$ much lower effective $\alpha$

    arXiv:2109.01076 | arXiv:2403.10964

Quantum error correction

...is done by encoding some space of logical qubits
into a bigger space of physical qubits:


  • $E$ (or just $\textrm{Im}(E)$) is a called a quantum error correcting code
  • QECCs are used to:
    • encode (and sometimes decode) logical states
    • measure physical qubits to detect/correct errors
    • do fault-tolerant computations on encoded qubits

Quantum error correction in ZX

two main approaches:

  • The graphical encoder approach

    $\quad \leadsto \quad$

  • The Pauli web approach

Graphical encoder

  • The idea: represent the encoder isometry $E$ directly as a ZX diagram

    $\quad = \quad$

  • Fault-tolerant QC $:=$ pushing through the encoder

Application: transversal Cliffords





» PQS, Chapter 11

Application: transversal non-Cliffords



...when $(L_X, S_X)$ is a triorthogonal code.

» PQS, Chapter 11

Application: lattice surgery



physical merge $\quad\qquad\leadsto\qquad\qquad\qquad\leadsto\qquad\quad$ logical merge


» PQS, Chapter 11

Application: CSS code transformations


arXiv:2307.02437

Application: canonical forms for encoders

Canonical forms for encoders give convenient expressions of equiv. classes of codes.




arXiv:2301.02356 | arXiv:2406.12083

In Summary

We can use ZX for...

  • Optimising quantum circuits
  • Simulating quantum computations
  • Reason about quantum error correction
  • And a whole lot more!

https://zxcalc.github.io/book


https://zxcalculus.com
(>300 tagged ZX papers, online seminars, Discord)

Advertisement

2-year Master on theory of quantum computing

Thanks for your attention!


https://zxcalc.github.io/book

https://zxcalculus.com
(>300 tagged ZX papers, online seminars, Discord)