Minimality in the
Stabilizer & Universal
Fragments of the ZX Calculus


Harry K. Stoltz


We view monoidal categories as a collection of generators \(\mathcal G\) and relations \(\mathcal R\):
…where diagrams are built from the generators through two kinds of composition:
• Sequentially:
• In parallel:
Theorem. Every monoidal category \(\mathcal C\) admits
a presentation of generators \(\mathcal G\) and relations \(\mathcal R\):
Defined inductively by:
It is enough to assign the generators and check the relations.
Captures the “essence” of an axiom.
• If it’s derivable:
Find a derivation!
• If it’s necessary:
Find an alternate interpretation!
For example…
• Complementarity
• Strong complementarity
“Interacting quantum observables: categorical algebra and diagrammatics”
“The ZX-calculus is complete for stabilizer quantum mechanics”
• 10 displayed rules
“Making the stabilizer ZX-calculus complete for scalars”
• 12 rules
“A Simplified Stabilizer ZX-calculus”
• 9 rules!
“Towards a Minimal Stabilizer ZX-calculus”
• Seven of the nine are necessary!
+ only connectivity matters
Definition. Two ZX diagrams are identified when their coloured, phase-labelled undirected multigraphs are isomorphic, preserving the ordered inputs and outputs.
\(E_D\) is a multiset of unordered pairs; \(c_D\) counts closed wire circles.
\[f:V_D\xrightarrow{\sim}V_{D\prime},\qquad f_*E_D=E_{D\prime},\quad \ell_{D\prime}(f(v))=\ell_D(v)\quad(v\in V_D),\]\[f(\mathbf i_D)=\mathbf i_{D\prime},\qquad f(\mathbf o_D)=\mathbf o_{D\prime},\qquad c_D=c_{D\prime}.\]To check that an interpretation respects connectivity:
Theorem. The \((\mathrm{S3}'\mathrm{R})\) rule is necessary:
Consider:
(Structural maps are unchanged.)
Lemma. For any ZX diagram \(D\),
| Rule | Scalar (both sides) |
|---|---|
| \((\mathrm{S1})\) | \(i^{p+q+r+s-2}\) |
| \((\mathrm{S3}'\mathrm L)\) | \(1\) |
| \((\mathrm{B1})\) | \(1\) |
| \((\mathrm{B2}')\) | \(1\) |
| \((\mathrm{EU}')\) | \(i\) |
| \((\mathrm H)\) | \(-1\cdot i^{n+m}\) |
| \((\mathrm{IV}')\) | \(1\) |
| \((\mathrm{ZO}')\) | \(\text{zero}\) |
But…
So,
Theorem. The \((\mathrm{S3}'\mathrm{R})\) rule is necessary:
Definition. Two †SCFAs on \(\mathbb C^d\) are strongly complementary when they form a scaled bialgebra:
Definition. A coherent pair of †SCFAs on \(\mathbb C^d\) is strongly complementary iff the bialgebra law holds:
Theorem. Complementary observables on \(\mathbb C^d\) admit coherent associated †SCFAs. They are strongly complementary iff:
(slightly adapted) Coecke–Duncan–Kissinger–Wang (2012)
\(\therefore\) Our phase carriers
are units in \(R\).
Lemma. These maps form a commutative special dagger Frobenius algebra in \(\mathbf{Mat}_{R^d}\).
Proof. By computation.
Let our Hadamard be any matrix \(H\in M_d(R)\), and
If we want to satisfy…
Only connectivity matters
Color change
Red identity
Let’s try a finite field!
• Spider fusion on the phase gate:
• Hadamard normalization and \(H^2=I\):
\(\Longrightarrow\) need \(\tfrac12\), so \(2\) must be invertible.
\(2=0\)
no square root of \(-1\)
By computation, Copy gives:
The smallest possible dimension \(d>1\) is \(4\).
So, let’s try \((\mathbb F_5)^4\)!
Solve for Hadamard & phase tuple…
All of our non-target rules are sound!
But…
This is a sound interpretation!
Adjoin an infinitesimal to our field.
The ring of dual numbers, with
Multiplication keeps only the constant and first-order terms:
Dual numbers linearize our equations!
In \(R=\mathbb F_5[\varepsilon]/(\varepsilon^2)\), write
where \(H_0\) and \(t_0\) are as before.
Note that
So, \(H^T=H\) and \(H^2=I\) give
Only \(H_1\) and \(p\) remain to determine.
• Copy \(\Rightarrow\) Hadamard
• Euler \(\Rightarrow\) phases
• \(\neg\)Bialgebra \(\Rightarrow\lambda\)
and usual structural maps
Theorem. The bialgebra \((B2^\prime)\) rule is necessary.
Proof. Consider \(\llbracket-\rrbracket^{(B2^\prime)}\).
The interpretation respects connectivity, and all the non-target rules.
But…
\(\blacksquare\)
Explicitly,
“A universal completion of the ZX-calculus”
• Arbitrary real phases
“Two complete axiomatisations of pure-state qubit quantum computing”
• Complete ZX and ZW calculi
“Diagrammatic Reasoning beyond Clifford+T Quantum Mechanics”
• Complete pure-qubit ZX-calculus
“A Near-Minimal Axiomatisation of ZX-Calculus for Pure Qubit Quantum Mechanics”
• 9 rules!
• Individual necessity of \((I_g),\ (I_r),\ (B)\) left open.
For each basis index \(r\), spider fusion gives:
These are group homomorphisms!
Canonically, take:
If we try \(R=\mathbb F_p[\varepsilon]/(\varepsilon^2)\), every phase homomorphism is trivial:
So, the natural choice is
(These phase characters have no \(\varepsilon\)-component!)
Over \(\mathbb F_5[\varepsilon]/(\varepsilon^2)\), our Hadamard is
where \(N\) is the skew matrix acting cyclically on \(|01\rangle,\ |10\rangle,\ |11\rangle\) and zero elsewhere \((N|00\rangle=0)\).
If we try to generalize this to the universal fragment, it fails the Euler law, so we move up to three copies...
Over \(\mathbb C[\varepsilon]/(\varepsilon^2)\), our Hadamard is
where \(N\) is the skew matrix acting cyclically on \(|100\rangle,\ |010\rangle,\ |001\rangle\) and zero on the other five basis vectors.
Our stabilizer phase tuple was
In stabilizer...
In universal...
So...
\(|x|\) is the number of ones in the bit string \(x\).
\(|x|\) is the Hamming weight of \(x\).
Note that...
These are precisely the three basis states mixed by \(N\).
and usual structural maps
Theorem. The \((B)\) rule is necessary:
Proof. The interpretation preserves connectivity.
Computing the matrices, every non-target rule is sound.
One coefficient is \(-\frac{\sqrt2}{4}\varepsilon\) on the left and \(0\) on the right.
and usual structural maps
Theorem. The \((I_g)\) rule is necessary:
Proof. Connectivity and every non-target rule are sound, but
Theorem. The \((I_r)\) rule is derivable:
Proof:
Our interpretations keep a value and a first-order change:
Theorem. Let \(A\) be an algebra over a field \(k\).
A linear map \(\partial:A\to A\) satisfies the Leibniz rule if and only if the polynomial bialgebra \(k[t]\) acts on \(A\) compatibly with multiplication, with \(t\) acting as \(\partial\).
Definition. On formal finite sums of ZX diagrams with phases affine in \(\theta\), a diagrammatic derivative is a family
which preserves sums and satisfies both Leibniz rules:
And it commutes with interpretation: