Processing math: 18%

ZX-calculus publications

This is intended to be a complete list of all publications that use the ZX-calculus (and related graphical calculi) in some manner. The guiding principle is that if the paper contains at least one ZX-diagram, then it should be in this list. If you find any errors or feel that a missing publication should be included in this list, please contact John van de Wetering. If you want to keep up-to-date with additions, there is also an RSS feed, and a Twitter account posting updates.

Exhaustive Search for Quantum Circuit Optimization using ZX Calculus
Tobias Fischbach, Pierre Talbot and Pascal Bouvry
Show abstract ⇲ Show bibdata ⇲

arXiv:2503.10983
Keywords: Optimisation, Automation, PyZX.

@article{fischbach2025exhaustive,
    author = {Fischbach, Tobias and Talbot, Pierre and Bouvry, Pascal},
    title = {{Exhaustive Search for Quantum Circuit Optimization using ZX Calculus}},
    year = {2025},
    journal = {arXiv preprint arXiv:2503.10983},
    urldate = {2025-03-14},
    link = {http://arxiv.org/abs/2503.10983},
    keywords = {Optimisation, Automation, PyZX},
    abstract = {Quantum computers allow a near-exponential speed-up for specific applications when compared to classical computers. Despite recent advances in the hardware of quantum computers, their practical usage is still severely limited due to a restricted number of available physical qubits and quantum gates, short coherence time, and high error rates. This paper lays the foundation towards a metric independent approach to quantum circuit optimization based on exhaustive search algorithms. This work uses depth-first search and iterative deepening depth-first search. We rely on ZX calculus to represent and optimize quantum circuits through the minimization of a given metric (e.g. the T-gate and edge count). ZX calculus formally guarantees that the semantics of the original circuit is preserved. As ZX calculus is a non-terminating rewriting system, we utilise a novel set of pruning rules to ensure termination while still obtaining high-quality solutions. We provide the first formalization of quantum circuit optimization using ZX calculus and exhaustive search. We extensively benchmark our approach on 100 standard quantum circuits. Finally, our implementation is integrated in the well-known libraries PyZX and Qiskit as a compiler pass to ensure applicability of our results.}
}

Copy to Clipboard

Bridging wire and gate cutting with ZX-calculus
Marco Schumann, Tobias Stollenwerk and Alessandro Ciani
Show abstract ⇲ Show bibdata ⇲

arXiv:2503.11494
Keywords: Simulation, Optimisation, ZH-calculus.

Quantum circuit cutting refers to a series of techniques that allow one to partition a quantum computation on a large quantum computer into several quantum computations on smaller devices. This usually comes at the price of a sampling overhead, that is quantified by the

$1$ -norm of the associated decomposition. The applicability of these techniques relies on the possibility of finding decompositions of the ideal, global unitaries into quantum operations that can be simulated onto each sub-register, which should ideally minimize the

$1$ -norm. In this work, we show how these decompositions can be obtained diagrammatically using ZX-calculus expanding on the work of Ufrecht et al. [arXiv:2302.00387]. The central idea of our work is that since in ZX-calculus only connectivity matters, it should be possible to cut wires in ZX-diagrams by inserting known decompositions of the identity in standard quantum circuits. We show how, using this basic idea, many of the gate decompositions known in the literature can be re-interpreted as an instance of wire cuts in ZX-diagrams. Furthermore, we obtain improved decompositions for multi-qubit controlled-Z (MCZ) gates with

$1$ -norm equal to

$3$ for any number of qubits and any partition, which we argue to be optimal. Our work gives new ways of thinking about circuit cutting that can be particularly valuable for finding decompositions of large unitary gates. Besides, it sheds light on the question of why exploiting classical communication decreases the 1-norm of a wire cut but does not do so for certain gate decompositions. In particular, using wire cuts with classical communication, we obtain gate decompositions that do not require classical communication.

@article{schumann2025bridging,
    author = {Schumann, Marco and Stollenwerk, Tobias and Ciani, Alessandro},
    title = {{Bridging wire and gate cutting with ZX-calculus}},
    year = {2025},
    journal = {arXiv preprint arXiv:2503.11494},
    urldate = {2025-03-14},
    link = {http://arxiv.org/abs/2503.11494},
    keywords = {Simulation, Optimisation, ZH-calculus},
    abstract = {Quantum circuit cutting refers to a series of techniques that allow one to partition a quantum computation on a large quantum computer into several quantum computations on smaller devices. This usually comes at the price of a sampling overhead, that is quantified by the $1$-norm of the associated decomposition. The applicability of these techniques relies on the possibility of finding decompositions of the ideal, global unitaries into quantum operations that can be simulated onto each sub-register, which should ideally minimize the $1$-norm. In this work, we show how these decompositions can be obtained diagrammatically using ZX-calculus expanding on the work of Ufrecht et al. [arXiv:2302.00387]. The central idea of our work is that since in ZX-calculus only connectivity matters, it should be possible to cut wires in ZX-diagrams by inserting known decompositions of the identity in standard quantum circuits. We show how, using this basic idea, many of the gate decompositions known in the literature can be re-interpreted as an instance of wire cuts in ZX-diagrams. Furthermore, we obtain improved decompositions for multi-qubit controlled-Z (MCZ) gates with $1$-norm equal to $3$ for any number of qubits and any partition, which we argue to be optimal. Our work gives new ways of thinking about circuit cutting that can be particularly valuable for finding decompositions of large unitary gates. Besides, it sheds light on the question of why exploiting classical communication decreases the 1-norm of a wire cut but does not do so for certain gate decompositions. In particular, using wire cuts with classical communication, we obtain gate decompositions that do not require classical communication.}
}

Copy to Clipboard

Graphical Stabilizer Decompositions for Multi-Control Toffoli Gate Dense Quantum Circuits
Yves Vollmeier
Show abstract ⇲ Show bibdata ⇲

arXiv:2503.03798
Keywords: Classical Simulation, Clifford+T, Toffoli, Automation.

@article{vollmeier2025graphical,
    author = {Vollmeier, Yves},
    title = {{Graphical Stabilizer Decompositions for Multi-Control Toffoli Gate Dense Quantum Circuits}},
    year = {2025},
    journal = {arXiv preprint arXiv:2503.03798},
    urldate = {2025-03-05},
    link = {http://arxiv.org/abs/2503.03798},
    keywords = {Classical Simulation, Clifford+T, Toffoli, Automation},
    abstract = {In this thesis, we study concepts in quantum computing using graphical languages, specifically using the ZX-calculus. The core of the research revolves around (graphical) stabilizer decompositions. The first major focus is on the decomposition of non-stabilizer states created from star edges. We discuss previous results and then present novel decompositions that yield a theoretical improvement. The second major focus is on weighting algorithms, applied to the special class of multi-control Toffoli gate dense quantum circuits. The representation of the corresponding gates is based on star edges. The applicability of known methods, such as CNOT-grouping, traditionally used for other classes, is examined in the context of this specific class. We then present a novel weighting algorithm that attempts to determine the best vertex to decompose. A refined version is implemented to simulate a known class of quantum querying algorithms, which is used to search for causal configurations of multiloop Feynman diagrams. For this case, as well as for a generalized benchmark consisting of randomly generated quantum circuits, we demonstrate occasional improvements in the final number of terms against traditional methods. These results are discussed by considering different simplification strategies. This thesis also provides a brief but broad outline of the important preliminaries.}
}

Copy to Clipboard

Unveiling a Hidden Percolation Transition in Monitored Clifford Circuits: Inroads from ZX-Calculus
Einat Buznach, Debanjan Chowdhury and Jonathan Ruhman
Show abstract ⇲ Show bibdata ⇲

arXiv:2502.13211
Keywords: Entanglement, Classical Simulation, Automation, PyZX, Condensed Matter, ZX-calculus.

@article{buznach2025unveiling,
    author = {Buznach, Einat and Chowdhury, Debanjan and Ruhman, Jonathan},
    title = {{Unveiling a Hidden Percolation Transition in Monitored Clifford Circuits: Inroads from ZX-Calculus}},
    year = {2025},
    journal = {arXiv preprint arXiv:2502.13211},
    urldate = {2025-02-18},
    link = {http://arxiv.org/abs/2502.13211},
    keywords = {Entanglement, Classical Simulation, Automation, PyZX, Condensed Matter, ZX-calculus},
    abstract = {We revisit the measurement-induced phase transition (MPT) in Clifford circuits, which are both classically simulable and exhibit critical behavior widely believed to be distinct from classical percolation theory, using ZX-calculus. We analyze the MPT in a dynamical model composed of CNOT, SWAP, identity gates, and Bell-pair measurements, respectively, arranged randomly in a brickwork pattern. Our circuits exhibit a transition that is seemingly distinct from classical percolation based on standard arguments, that is in line with the prevailing understanding in the field. In contrast, by employing ZX-calculus based simplification techniques, we unveil a hidden percolation transition within the circuit structure. Over a range of parameters tied to the probabilities for applying different gates, we demonstrate that the classical percolation transition in the ZX-simplified network coincides with the MPT observed through mutual information. Our findings suggest that the MPT in Clifford circuits is, in fact, controlled by a classical percolation transition in disguise.}
}

Copy to Clipboard

Diagrammatic Quantum Circuit Compression for Hamiltonian Simulation
Victoria Wadewitz, Aaron Szasz, Daan Camps, Katherine Klymko and Tobias Stollenwerk
Show abstract ⇲ Show bibdata ⇲

Software Engineering 2025 – Companion Proceedings
Keywords: Phase Gadgets, Chemistry, Applied, Optimisation, ZX-calculus.

@inproceedings{Wadewitz2025Diagrammatic,
    author = {Wadewitz, Victoria and Szasz, Aaron and Camps, Daan and Klymko, Katherine and Stollenwerk, Tobias},
    title = {Diagrammatic Quantum Circuit Compression for Hamiltonian Simulation},
    year = {2025},
    booktitle = {Software Engineering 2025 – Companion Proceedings},
    publisher = {Gesellschaft für Informatik, Bonn},
    issn = {1617-5468},
    doi = {10.18420/se2025-ws-24},
    urldate = {2025-02-15},
    link = {https://dl.gi.de/items/55b8918c-cccd-4b39-9b57-889735ea1c31},
    keywords = {Phase Gadgets, Chemistry, Applied, Optimisation, ZX-calculus},
    abstract = {One of the promising applications for early quantum computers is the simulation of of dynamical quantum systems. Due to the limited coherence time of such devices, the depth-compression of quantum circuits is crucial to facilitate useful results. It has been shown that certain quantum models can even be compressed to constant depth, meaning it is only linearly dependent on the number of qubits, but independent of the simulation time and the number of Trotter steps. This has been done by extracting the circuit structure derived from the model characteristics via Hamiltonian simulation. Based on these results, we present a diagrammatic approach to circuit compression utilizing a powerful technique for reasoning about quantum circuits called ZX-calculus. We demonstrate our approach by deriving constant-depth circuit compressions for quantum models known to be constant-depth, as well as novel models previously unstudied. Our method could serve as a first step toward the development of more advanced circuit compression methods, that could be employed to enable Hamiltonian simulation of a larger variety of quantum models, and beyond.}
}

Copy to Clipboard

Efficient Heuristics for Classical Simulation of Quantum Circuits Using ZX-Calculus
Wira Azmoon Ahmad
Show abstract ⇲ Show bibdata ⇲

University of Oxford Masters Thesis
Keywords: Classical Simulation, Automation, PyZX, Clifford+T, ZX-calculus, Master Thesis.

Quantum circuits require validation and testing to ensure that they perform as expected. Classical simulation is a powerful tool for this purpose, but it is limited by the exponential growth of complexity with the number of qubits. Nevertheless, using the ZX-calculus, a graphical language for quantum mechanics, we can attempt to reduce how exponential this growth is. Recent developments have allowed focus to be placed on complexity being dependent on the number of T-gates that are in the circuit. Given

$t$ T-gates, if the complexity of classically simulating the circuit is

$O(2\alpha t)$ , the aim is to reduce the value of

$\alpha$ as much as possible, where

$0 < \alpha < 1$ . This thesis presents a heuristic approach toward exploiting the structure of the ZX-diagrams used to represent the quantum circuits, in order to reduce

$\alpha$ . We conceptualise a formal definition of the heuristic method, applying it to existing approaches, and also develop new heuristics that take advantage of the structure made available in the ZX-diagrams. These heuristics perform well in practice, boosting the number of T-gates that can be simulated classically by up to three times as many on certain classes of circuits

@mastersthesis{Ahmad2025Masters,
    author = {Ahmad, Wira Azmoon},
    title = {{Efficient Heuristics for Classical Simulation of Quantum Circuits Using ZX-Calculus}},
    year = {2025},
    school = {University of Oxford},
    urldate = {2025-02-10},
    link = {https://www.cs.ox.ac.uk/people/aleks.kissinger/theses/ahmad-thesis.pdf},
    keywords = {Classical Simulation, Automation, PyZX, Clifford+T, ZX-calculus, Master Thesis},
    abstract = {Quantum circuits require validation and testing to ensure that they perform as expected. Classical simulation is a powerful tool for this purpose, but it is limited by the exponential growth of complexity with the number of qubits. Nevertheless, using the ZX-calculus, a graphical language for quantum mechanics, we can attempt to reduce how exponential this growth is. Recent developments have allowed focus to be placed on complexity being dependent on the number of T-gates that are in the circuit. Given $t$ T-gates, if the complexity of classically simulating the circuit is $O(2\alpha t)$, the aim is to reduce the value of $\alpha$ as much as possible, where $0 < \alpha < 1$. This thesis presents a heuristic approach toward exploiting the structure of the ZX-diagrams used to represent the quantum circuits, in order to reduce $\alpha$. We conceptualise a formal definition of the heuristic method, applying it to existing approaches, and also develop new heuristics that take advantage of the structure made available in the ZX-diagrams. These heuristics perform well in practice, boosting the number of T-gates that can be simulated classically by up to three times as many on certain classes of circuits}
}

Copy to Clipboard

Quantum Computing from Graphs
Andrey Boris Khesin
Show abstract ⇲ Show bibdata ⇲

Massachusetts Institute Of Technology PhD Thesis
Keywords: ZX-calculus, Error Correcting Codes, Clifford Fragment, PhD Thesis.

@phdthesis{Khesin2025thesis,
    author = {Khesin, Andrey Boris},
    title = {{Quantum Computing from Graphs}},
    year = {2025},
    school = {Massachusetts Institute Of Technology},
    urldate = {2025-02-01},
    link = {https://arxiv.org/abs/2501.17959},
    keywords = {ZX-calculus, Error Correcting Codes, Clifford Fragment, PhD Thesis},
    abstract = {While stabilizer tableaus have proven exceptionally useful as a descriptive tool for additive quantum codes, they offer little guidance for concrete constructions or coding algorithm analysis. We introduce a representation of stabilizer codes as graphs with certain structures. Specifically, the graphs take a semi-bipartite form where input nodes map to output nodes, such that output nodes may connect to each other but input nodes may not. Intuitively, the graph's input-output edges represent information propagation of the encoder, while output-output edges represent the code's entanglement. We prove that this graph representation is in bijection with tableaus and give an efficient compilation algorithm that transforms tableaus into graphs. We show that this map is efficiently invertible, which gives a universal recipe for code construction by finding graphs with nice properties. The graph representation gives insight into both code construction and algorithms. To the former, we argue that graphs provide a flexible platform for building codes. We construct several constant-size codes and several infinite code families. We also use graphs to extend the quantum Gilbert-Varshamov bound to a three-way distance-rate-weight trade-off. To the latter, we show that key coding algorithms, distance approximation, weight reduction, and decoding, are unified as instances of a single optimization game on a graph. Moreover, key code properties such as distance, weight, and encoding circuit depth, are all controlled by the graph degree. We give efficient algorithms for producing encoding circuits whose depths scale with the degree and for implementing certain logical diagonal and Clifford gates with reduced depth. Finally, we find an efficient decoding algorithm for certain classes of graphs. These results give evidence that graphs are useful for the study of quantum computing and its implementations.}
}

Copy to Clipboard

Pauli web of the $|Yångle$ state surface code injection
Kwok Ho Wan and Zhenghao Zhong
Show abstract ⇲ Show bibdata ⇲

arXiv:2501.15566
Keywords: Surface Code, Error Correcting Codes, ZX-calculus.

We employ ZX-calculus and Pauli web to understand the

$|Y\rangle$ state injection on the rotated surface code.

@article{howan2025pauli,
    author = {Ho Wan, Kwok and Zhong, Zhenghao},
    title = {{Pauli web of the $|Y\rangle$ state surface code injection}},
    year = {2025},
    journal = {arXiv preprint arXiv:2501.15566},
    urldate = {2025-01-26},
    link = {http://arxiv.org/abs/2501.15566},
    keywords = {Surface Code, Error Correcting Codes, ZX-calculus},
    abstract = {We employ ZX-calculus and Pauli web to understand the $|Y\rangle$ state injection on the rotated surface code.}
}

Copy to Clipboard

Dynamic T-decomposition for classical simulation of quantum circuits
Wira Azmoon Ahmad and Matthew Sutcliffe
Show abstract ⇲ Show bibdata ⇲

arXiv:2412.17182
Keywords: Classical Simulation, PyZX, Applied, Automation, Clifford+T.

It is known that a quantum circuit may be simulated with classical hardware via stabilizer state (T-)decomposition in

$O(2^{\alpha t})$ time, given

$t$ non-Clifford gates and a decomposition efficiency

$\alpha$ . The past years have seen a number of papers presenting new decompositions of lower

$\alpha$ to reduce this runtime and enable simulation of ever larger circuits. More recently, it has been demonstrated that well placed applications of apparently weaker (higher

$\alpha$ ) decompositions can in fact result in better overall efficiency when paired with the circuit simplification strategies of ZX-calculus. In this work, we take the most generalized T-decomposition (namely vertex cutting), which achieves a poor efficiency of

$\alpha=1$ , and identify common structures to which applying this can, after simplification via ZX-calculus rewriting, yield very strong effective efficiencies

$\alpha_{\text{eff}}\ll1$ . By taking into account this broader scope of the ZX-diagram and incorporating the simplification facilitated by the well-motivated cuts, we derive a handful of efficient T-decompositions whose applicabilities are relatively frequent. In benchmarking these new 'dynamic' decompositions against the existing alternatives, we observe a significant reduction in overall

$\alpha$ and hence overall runtime for classical simulation, particularly for certain common circuit classes.

@article{azmoonahmad2024dynamic,
    author = {Azmoon Ahmad, Wira and Sutcliffe, Matthew},
    title = {{Dynamic T-decomposition for classical simulation of quantum circuits}},
    year = {2024},
    journal = {arXiv preprint arXiv:2412.17182},
    urldate = {2024-12-22},
    link = {http://arxiv.org/abs/2412.17182},
    keywords = {Classical Simulation, PyZX, Applied, Automation, Clifford+T},
    abstract = {It is known that a quantum circuit may be simulated with classical hardware via stabilizer state (T-)decomposition in $O(2^{\alpha t})$ time, given $t$ non-Clifford gates and a decomposition efficiency $\alpha$. The past years have seen a number of papers presenting new decompositions of lower $\alpha$ to reduce this runtime and enable simulation of ever larger circuits. More recently, it has been demonstrated that well placed applications of apparently weaker (higher $\alpha$) decompositions can in fact result in better overall efficiency when paired with the circuit simplification strategies of ZX-calculus.   In this work, we take the most generalized T-decomposition (namely vertex cutting), which achieves a poor efficiency of $\alpha=1$, and identify common structures to which applying this can, after simplification via ZX-calculus rewriting, yield very strong effective efficiencies $\alpha_{\text{eff}}\ll1$. By taking into account this broader scope of the ZX-diagram and incorporating the simplification facilitated by the well-motivated cuts, we derive a handful of efficient T-decompositions whose applicabilities are relatively frequent. In benchmarking these new 'dynamic' decompositions against the existing alternatives, we observe a significant reduction in overall $\alpha$ and hence overall runtime for classical simulation, particularly for certain common circuit classes.}
}

Copy to Clipboard

Qubit-count optimization using ZX-calculus
Vivien Vandaele
Show abstract ⇲ Show bibdata ⇲

arXiv:2407.10171
Keywords: Optimisation, Automation, ZX-calculus.

We propose several methods for optimizing the number of qubits in a quantum circuit while preserving the number of non-Clifford gates. One of our approaches consists in reversing, as much as possible, the gadgetization of Hadamard gates, which is a procedure used by some

$T$ -count optimizers to circumvent Hadamard gates at the expense of additional qubits. We prove the NP-hardness of this problem and we present an algorithm for solving it. We also propose a more general approach to optimize the number of qubits by showing how it relates to the problem of finding a minimal-width path-decomposition of the graph associated with a given ZX-diagram. This approach can be used to optimize the number of qubits for any computational model that can natively be depicted in ZX-calculus, such as the Pauli Fusion computational model which can represent lattice surgery operations. We also show how this method can be used to efficiently optimize the number of qubits in a quantum circuit by using the ZX-calculus as an intermediate representation.

@article{vandaele2024qubitcount,
    author = {Vandaele, Vivien},
    title = {{Qubit-count optimization using ZX-calculus}},
    year = {2024},
    journal = {arXiv preprint arXiv:2407.10171},
    urldate = {2024-07-14},
    link = {http://arxiv.org/abs/2407.10171},
    keywords = {Optimisation, Automation, ZX-calculus},
    abstract = {We propose several methods for optimizing the number of qubits in a quantum circuit while preserving the number of non-Clifford gates. One of our approaches consists in reversing, as much as possible, the gadgetization of Hadamard gates, which is a procedure used by some $T$-count optimizers to circumvent Hadamard gates at the expense of additional qubits. We prove the NP-hardness of this problem and we present an algorithm for solving it. We also propose a more general approach to optimize the number of qubits by showing how it relates to the problem of finding a minimal-width path-decomposition of the graph associated with a given ZX-diagram. This approach can be used to optimize the number of qubits for any computational model that can natively be depicted in ZX-calculus, such as the Pauli Fusion computational model which can represent lattice surgery operations. We also show how this method can be used to efficiently optimize the number of qubits in a quantum circuit by using the ZX-calculus as an intermediate representation.}
}

Copy to Clipboard

Tensor networks for non-invertible symmetries in 3+1d and beyond
Pranay Gorantla, Shu-Heng Shao and Nathanan Tantivasadakarn
Show abstract ⇲ Show bibdata ⇲

arXiv:2406.12978
Keywords: Tensor Networks, Condensed Matter, ZX-calculus.

Tensor networks provide a natural language for non-invertible symmetries in general Hamiltonian lattice models. We use ZX-diagrams, which are tensor network presentations of quantum circuits, to define a non-invertible operator implementing the Wegner duality in 3+1d lattice

$\mathbb{Z}_2$ gauge theory. The non-invertible algebra, which mixes with lattice translations, can be efficiently computed using ZX-calculus. We further deform the

$\mathbb{Z}_2$ gauge theory while preserving the duality and find a model with nine exactly degenerate ground states on a torus, consistent with the Lieb-Schultz-Mattis-type constraint imposed by the symmetry. Finally, we provide a ZX-diagram presentation of the non-invertible duality operators (including non-invertible parity/reflection symmetries) of generalized Ising models based on graphs, encompassing the 1+1d Ising model, the three-spin Ising model, the Ashkin-Teller model, and the 2+1d plaquette Ising model. The mixing (or lack thereof) with spatial symmetries is understood from a unifying perspective based on graph theory.

@article{gorantla2024tensor,
    author = {Gorantla, Pranay and Shao, Shu-Heng and Tantivasadakarn, Nathanan},
    title = {{Tensor networks for non-invertible symmetries in 3+1d and beyond}},
    year = {2024},
    journal = {arXiv preprint arXiv:2406.12978},
    urldate = {2024-06-18},
    link = {http://arxiv.org/abs/2406.12978},
    keywords = {Tensor Networks, Condensed Matter, ZX-calculus},
    abstract = {Tensor networks provide a natural language for non-invertible symmetries in general Hamiltonian lattice models. We use ZX-diagrams, which are tensor network presentations of quantum circuits, to define a non-invertible operator implementing the Wegner duality in 3+1d lattice $\mathbb{Z}_2$ gauge theory. The non-invertible algebra, which mixes with lattice translations, can be efficiently computed using ZX-calculus. We further deform the $\mathbb{Z}_2$ gauge theory while preserving the duality and find a model with nine exactly degenerate ground states on a torus, consistent with the Lieb-Schultz-Mattis-type constraint imposed by the symmetry. Finally, we provide a ZX-diagram presentation of the non-invertible duality operators (including non-invertible parity/reflection symmetries) of generalized Ising models based on graphs, encompassing the 1+1d Ising model, the three-spin Ising model, the Ashkin-Teller model, and the 2+1d plaquette Ising model. The mixing (or lack thereof) with spatial symmetries is understood from a unifying perspective based on graph theory.}
}

Copy to Clipboard

Genons, Double Covers and Fault-tolerant Clifford Gates
Simon Burton, Elijah Durso-Sabina and Natalie C. Brown
Show abstract ⇲ Show bibdata ⇲

arXiv:2406.09951
Keywords: Error Correcting Codes, Braids, Clifford Fragment, ZX-Supported.

A great deal of work has been done developing quantum codes with varying overhead and connectivity constraints. However, given the such an abundance of codes, there is a surprising shortage of fault-tolerant logical gates supported therein. We define a construction, such that given an input

$[[n,k,d]]$ code, yields a

$[[2n,2k,\ge d]]$ symplectic double code with naturally occurring fault-tolerant logical Clifford gates. As applied to 2-dimensional

$D(\mathbb{Z}_2)$ -topological codes with genons (twists) and domain walls, we find the symplectic double is genon free, and of possibly higher genus. Braiding of genons on the original code becomes Dehn twists on the symplectic double. Such topological operations are particularly suited for architectures with all-to-all connectivity, and we demonstrate this experimentally on Quantinuum's H1-1 trapped-ion quantum computer.

@article{burton2024genons,
    author = {Burton, Simon and Durso-Sabina, Elijah and C. Brown, Natalie},
    title = {{Genons, Double Covers and Fault-tolerant Clifford Gates}},
    year = {2024},
    journal = {arXiv preprint arXiv:2406.09951},
    urldate = {2024-06-14},
    link = {http://arxiv.org/abs/2406.09951},
    keywords = {Error Correcting Codes, Braids, Clifford Fragment, ZX-Supported},
    abstract = {A great deal of work has been done developing quantum codes with varying overhead and connectivity constraints. However, given the such an abundance of codes, there is a surprising shortage of fault-tolerant logical gates supported therein. We define a construction, such that given an input $[[n,k,d]]$ code, yields a $[[2n,2k,\ge d]]$ symplectic double code with naturally occurring fault-tolerant logical Clifford gates. As applied to 2-dimensional $D(\mathbb{Z}_2)$-topological codes with genons (twists) and domain walls, we find the symplectic double is genon free, and of possibly higher genus. Braiding of genons on the original code becomes Dehn twists on the symplectic double. Such topological operations are particularly suited for architectures with all-to-all connectivity, and we demonstrate this experimentally on Quantinuum's H1-1 trapped-ion quantum computer.}
}

Copy to Clipboard

The Qudit ZH Calculus for Arbitrary Finite Fields: Universality and Application
Dichuan Gao
Show abstract ⇲ Show bibdata ⇲

arXiv:2406.02219
Keywords: ZH-calculus, Completeness, Qudits.

We propose a generalization of the graphical ZH calculus to qudits of prime-power dimensions

$q = p^t$ , implementing field arithmetic in arbitrary finite fields. This is an extension of a previous result by Roy which implemented arithmetic of prime-sized fields; and an alternative to a result by de Beaudrap which extended the ZH to implement cyclic ring arithmetic in

$\mathbb Z / q\mathbb Z$ rather than field arithmetic in

$\mathbb F_q$ . We show this generalized ZH calculus to be universal over matrices

$\mathbb C^{q^n} \to \mathbb C^{q^m}$ with entries in the ring

$\mathbb Z[\omega]$ where

$\omega$ is a

$p$ th root of unity. As an illustration of the necessity of such an extension of ZH for field rather than cyclic ring arithmetic, we offer a graphical description and proof for a quantum algorithm for polynomial interpolation. This algorithm relies on the invertibility of multiplication, and therefore can only be described in a graphical language that implements field, rather than ring, multiplication.

@article{dichuan2024qudit,
    author = {Gao, Dichuan},
    title = {{The Qudit ZH Calculus for Arbitrary Finite Fields: Universality and Application}},
    year = {2024},
    journal = {arXiv preprint arXiv:2406.02219},
    urldate = {2024-06-04},
    link = {http://arxiv.org/abs/2406.02219},
    keywords = {ZH-calculus, Completeness, Qudits},
    abstract = {We propose a generalization of the graphical ZH calculus to qudits of prime-power dimensions $q = p^t$, implementing field arithmetic in arbitrary finite fields. This is an extension of a previous result by Roy which implemented arithmetic of prime-sized fields; and an alternative to a result by de Beaudrap which extended the ZH to implement cyclic ring arithmetic in $\mathbb Z / q\mathbb Z$ rather than field arithmetic in $\mathbb F_q$. We show this generalized ZH calculus to be universal over matrices $\mathbb C^{q^n} \to \mathbb C^{q^m}$ with entries in the ring $\mathbb Z[\omega]$ where $\omega$ is a $p$th root of unity. As an illustration of the necessity of such an extension of ZH for field rather than cyclic ring arithmetic, we offer a graphical description and proof for a quantum algorithm for polynomial interpolation. This algorithm relies on the invertibility of multiplication, and therefore can only be described in a graphical language that implements field, rather than ring, multiplication.}
}

Copy to Clipboard

Constructing $\mathrmNP^\mathord#\mathrm P$-complete problems and $\mathord#\mathrm P$-hardness of circuit extraction in phase-free ZH
Piotr Mitosek
Show abstract ⇲ Show bibdata ⇲ Video 🎥

arXiv:2404.10913
Keywords: ZH-calculus, SAT, Circuit Extraction.

The ZH calculus is a graphical language for quantum computation reasoning. The phase-free variant offers a simple set of generators that guarantee universality. ZH calculus is effective in MBQC and analysis of quantum circuits constructed with the universal gate set Toffoli+H. While circuits naturally translate to ZH diagrams, finding an ancilla-free circuit equivalent to a given diagram is hard. Here, we show that circuit extraction for phase-free ZH calculus is

${\mathord{\#}\mathrm P}$ -hard, extending the existing result for ZX calculus. Another problem believed to be hard is comparing whether two diagrams represent the same process. We show that two closely related problems are

$\mathrm{NP}^{\mathord{\#}\mathrm P}$ -complete. The first problem is: given two processes represented as diagrams, determine the existence of a computational basis state on which they equalize. The second problem is checking whether the matrix representation of a given diagram contains an entry equal to a given number. Our proof adapts the proof of Cook-Levin theorem to a reduction from a non-deterministic Turing Machine with access to

${\mathord{\#}\mathrm P}$ oracle.

@article{mitosek2024constructing,
    author = {Mitosek, Piotr},
    title = {{Constructing $\mathrm{NP}^{\mathord{\#}\mathrm P}$-complete problems and ${\mathord{\#}\mathrm P}$-hardness of circuit extraction in phase-free ZH}},
    year = {2024},
    journal = {arXiv preprint arXiv:2404.10913},
    urldate = {2024-04-16},
    link = {http://arxiv.org/abs/2404.10913},
    keywords = {ZH-calculus, SAT, Circuit Extraction},
    abstract = {The ZH calculus is a graphical language for quantum computation reasoning. The phase-free variant offers a simple set of generators that guarantee universality. ZH calculus is effective in MBQC and analysis of quantum circuits constructed with the universal gate set Toffoli+H. While circuits naturally translate to ZH diagrams, finding an ancilla-free circuit equivalent to a given diagram is hard. Here, we show that circuit extraction for phase-free ZH calculus is ${\mathord{\#}\mathrm P}$-hard, extending the existing result for ZX calculus. Another problem believed to be hard is comparing whether two diagrams represent the same process. We show that two closely related problems are $\mathrm{NP}^{\mathord{\#}\mathrm P}$-complete. The first problem is: given two processes represented as diagrams, determine the existence of a computational basis state on which they equalize. The second problem is checking whether the matrix representation of a given diagram contains an entry equal to a given number. Our proof adapts the proof of Cook-Levin theorem to a reduction from a non-deterministic Turing Machine with access to ${\mathord{\#}\mathrm P}$ oracle.},
    video = {https://www.youtube.com/watch?v=EuqikLkSHX8}
}

Copy to Clipboard

Catalysing Completeness and Universality
Aleks Kissinger, Neil J. Ross and John van de Wetering
Show abstract ⇲ Show bibdata ⇲

arXiv:2404.09915
Keywords: ZH-calculus, Completeness, Clifford+T, Toffoli.

A catalysis state is a quantum state that is used to make some desired operation possible or more efficient, while not being consumed in the process. Recent years have seen catalysis used in state-of-the-art protocols for implementing magic state distillation or small angle phase rotations. In this paper we will see that we can also use catalysis to prove that certain gate sets are computationally universal, and to extend completeness results of graphical languages to larger fragments. In particular, we give a simple proof of the computational universality of the CS+Hadamard gate set using the catalysis of a

$T$ gate using a CS gate, which sidesteps the more complicated analytic arguments of the original proof by Kitaev. This then also gives us a simple self-contained proof of the computational universality of Toffoli+Hadamard. Additionally, we show that the phase-free ZH-calculus can be extended to a larger complete fragment, just by using a single catalysis rule (and one scalar rule).

@article{kissinger2024catalysing,
    author = {Kissinger, Aleks and J. Ross, Neil and van de Wetering, John},
    title = {{Catalysing Completeness and Universality}},
    year = {2024},
    journal = {arXiv preprint arXiv:2404.09915},
    urldate = {2024-04-15},
    link = {http://arxiv.org/abs/2404.09915},
    keywords = {ZH-calculus, Completeness, Clifford+T, Toffoli},
    abstract = {A catalysis state is a quantum state that is used to make some desired operation possible or more efficient, while not being consumed in the process. Recent years have seen catalysis used in state-of-the-art protocols for implementing magic state distillation or small angle phase rotations. In this paper we will see that we can also use catalysis to prove that certain gate sets are computationally universal, and to extend completeness results of graphical languages to larger fragments. In particular, we give a simple proof of the computational universality of the CS+Hadamard gate set using the catalysis of a $T$ gate using a CS gate, which sidesteps the more complicated analytic arguments of the original proof by Kitaev. This then also gives us a simple self-contained proof of the computational universality of Toffoli+Hadamard. Additionally, we show that the phase-free ZH-calculus can be extended to a larger complete fragment, just by using a single catalysis rule (and one scalar rule).}
}

Copy to Clipboard

Zero-temperature entanglement membranes in quantum circuits
Grace M. Sommers, Sarang Gopalakrishnan, Michael J. Gullans and David A. Huse
Show abstract ⇲ Show bibdata ⇲ Video 🎥

arXiv:2404.02975
Keywords: Entanglement, MBQC, Applied, ZX-calculus.

In chaotic quantum systems, the entanglement of a region

$A$ can be described in terms of the surface tension of a spacetime membrane pinned to the boundary of

$A$ . Here, we interpret the tension of this entanglement membrane in terms of the rate at which information "flows" across it. For any orientation of the membrane, one can define (generically nonunitary) dynamics across the membrane; we explore this dynamics in various space-time translation-invariant (STTI) stabilizer circuits in one and two spatial dimensions. We find that the flux of information across the membrane in these STTI circuits reaches a steady state. In the cases where this dynamics is nonunitary and the steady state flux is nonzero, this occurs because the dynamics across the membrane is unitary in a subspace of extensive entropy. This generalized unitarity is present in a broad class of STTI stabilizer circuits, and is also present in some special non-stabilizer models. The existence of multiple unitary (or generalized unitary) directions forces the entanglement membrane tension to be a piecewise linear function of the orientation of the membrane; in this respect, the entanglement membrane behaves like an interface in a zero-temperature classical lattice model. We argue that entanglement membranes in random stabilizer circuits that produce volume-law entanglement are also effectively at zero temperature.

@article{m.sommers2024zerotemperature,
    author = {M. Sommers, Grace and Gopalakrishnan, Sarang and J. Gullans, Michael and A. Huse, David},
    title = {{Zero-temperature entanglement membranes in quantum circuits}},
    year = {2024},
    journal = {arXiv preprint arXiv:2404.02975},
    urldate = {2024-04-03},
    link = {http://arxiv.org/abs/2404.02975},
    keywords = {Entanglement, MBQC, Applied, ZX-calculus},
    abstract = {In chaotic quantum systems, the entanglement of a region $A$ can be described in terms of the surface tension of a spacetime membrane pinned to the boundary of $A$. Here, we interpret the tension of this entanglement membrane in terms of the rate at which information "flows" across it. For any orientation of the membrane, one can define (generically nonunitary) dynamics across the membrane; we explore this dynamics in various space-time translation-invariant (STTI) stabilizer circuits in one and two spatial dimensions. We find that the flux of information across the membrane in these STTI circuits reaches a steady state. In the cases where this dynamics is nonunitary and the steady state flux is nonzero, this occurs because the dynamics across the membrane is unitary in a subspace of extensive entropy. This generalized unitarity is present in a broad class of STTI stabilizer circuits, and is also present in some special non-stabilizer models. The existence of multiple unitary (or generalized unitary) directions forces the entanglement membrane tension to be a piecewise linear function of the orientation of the membrane; in this respect, the entanglement membrane behaves like an interface in a zero-temperature classical lattice model. We argue that entanglement membranes in random stabilizer circuits that produce volume-law entanglement are also effectively at zero temperature.},
    video = {https://www.youtube.com/watch?v=q2UvZS3OmRI}
}

Copy to Clipboard

Procedurally Optimised ZX-Diagram Cutting for Efficient T-Decomposition in Classical Simulation
Matthew Sutcliffe and Aleks Kissinger
Show abstract ⇲ Show bibdata ⇲ Video 🎥

Proceedings of the 21st International Conference on Quantum Physics and Logic, Buenos Aires, Argentina, July 15-19, 2024
Keywords: Classical Simulation, Automation, ZX-calculus.

A quantum circuit may be strongly classically simulated with the aid of ZX-calculus by decomposing its

$t$ T-gates into a sum of

$2^{\alpha t}$ classically computable stabiliser terms. In this paper, we introduce a general procedure to find an optimal pattern of vertex cuts in a ZX-diagram to maximise its T-count reduction at the cost of the fewest cuts. Rather than reducing a Clifford+T diagram based on a fixed routine of decomposing its T-gates directly (as is the conventional approach), we focus instead on taking advantage of certain patterns and structures common to such circuits to, in effect, design by automatic procedure an arrangement of spider decompositions that is optimised for the particular circuit. In short, this works by assigning weights to vertices based on how many T-like gates they are blocking from fusing/cancelling and then appropriately propagating these weights through any neighbours which are then blocking weighted vertices from fusing, and so on. Ultimately, this then provides a set of weightings on relevant nodes, which can then each be cut, starting from the highest weighted down. While this is a heuristic approach, we show that, for circuits small enough to verify, this method achieves the most optimal set of cuts possible

$71\%$ of the time. Furthermore, there is no upper bound for the efficiency achieved by this method, allowing, in principle, an effective decomposition efficiency

$\alpha\rightarrow0$ for highly structured circuits. Even applied to random pseudo-structured circuits (produced from CNOTs, phase gates, and Toffolis), we record the number of stabiliser terms required to reduce all T-gates, via our method as compared to that of the more conventional T-decomposition approaches (with

$\alpha\approx0.47$ ), and show consistent improvements of orders of magnitude, with an effective efficiency

$0.1\lesssim\alpha\lesssim0.2$ .

@inproceedings{sutcliffe2024procedurally,
    author = {Sutcliffe, Matthew and Kissinger, Aleks},
    title = {{Procedurally Optimised ZX-Diagram Cutting for Efficient T-Decomposition in Classical Simulation}},
    year = {2024},
    booktitle = {Proceedings of the 21st International Conference on Quantum Physics and Logic, Buenos Aires, Argentina, July 15-19, 2024},
    editor = {D\'iaz-Caro, Alejandro and Zamdzhiev, Vladimir},
    series = {Electronic Proceedings in Theoretical Computer Science},
    volume = {406},
    pages = {63-78},
    publisher = {Open Publishing Association},
    doi = {10.4204/EPTCS.406.3},
    urldate = {2024-03-16},
    link = {http://arxiv.org/abs/2403.10964},
    keywords = {Classical Simulation, Automation, ZX-calculus},
    abstract = {A quantum circuit may be strongly classically simulated with the aid of ZX-calculus by decomposing its $t$ T-gates into a sum of $2^{\alpha t}$ classically computable stabiliser terms. In this paper, we introduce a general procedure to find an optimal pattern of vertex cuts in a ZX-diagram to maximise its T-count reduction at the cost of the fewest cuts. Rather than reducing a Clifford+T diagram based on a fixed routine of decomposing its T-gates directly (as is the conventional approach), we focus instead on taking advantage of certain patterns and structures common to such circuits to, in effect, design by automatic procedure an arrangement of spider decompositions that is optimised for the particular circuit. In short, this works by assigning weights to vertices based on how many T-like gates they are blocking from fusing/cancelling and then appropriately propagating these weights through any neighbours which are then blocking weighted vertices from fusing, and so on. Ultimately, this then provides a set of weightings on relevant nodes, which can then each be cut, starting from the highest weighted down. While this is a heuristic approach, we show that, for circuits small enough to verify, this method achieves the most optimal set of cuts possible $71\%$ of the time. Furthermore, there is no upper bound for the efficiency achieved by this method, allowing, in principle, an effective decomposition efficiency $\alpha\rightarrow0$ for highly structured circuits. Even applied to random pseudo-structured circuits (produced from CNOTs, phase gates, and Toffolis), we record the number of stabiliser terms required to reduce all T-gates, via our method as compared to that of the more conventional T-decomposition approaches (with $\alpha\approx0.47$), and show consistent improvements of orders of magnitude, with an effective efficiency $0.1\lesssim\alpha\lesssim0.2$.},
    video = {https://www.youtube.com/watch?v=WP0ZVSOsOOM}
}

Copy to Clipboard

A Complete Graphical Language for Linear Optical Circuits with Finite-Photon-Number Sources and Detectors
Nicolas Heurtel
Show abstract ⇲ Show bibdata ⇲ Video 🎥

arXiv:2402.17693
Keywords: Photons, Completeness, ZX-Supported.

Linear optical circuits can be used to manipulate the quantum states of photons as they pass through components including beam splitters and phase shifters. Those photonic states possess a particularly high level of expressiveness, as they reside within the bosonic Fock space, an infinite-dimensional Hilbert space. However, in the domain of linear optical quantum computation, these basic components may not be sufficient to efficiently perform all computations of interest, such as universal quantum computation. To address this limitation it is common to add auxiliary sources and detectors, which enable projections onto auxiliary photonic states and thus increase the versatility of the processes. In this paper, we introduce the

$\textbf{LO}_{fi}$ -calculus, a graphical language to reason on the infinite-dimensional bosonic Fock space with circuits composed of four core elements of linear optics: the phase shifter, the beam splitter, and auxiliary sources and detectors with bounded photon number. We present an equational theory that we prove to be complete: two

$\textbf{LO}_{fi}$ -circuits represent the same quantum process if and only if one can be transformed into the other with the rules of the

$\textbf{LO}_{fi}$ -calculus. We give a unique and compact universal form for such circuits.

@article{heurtel2024complete,
    author = {Heurtel, Nicolas},
    title = {{A Complete Graphical Language for Linear Optical Circuits with Finite-Photon-Number Sources and Detectors}},
    year = {2024},
    journal = {arXiv preprint arXiv:2402.17693},
    urldate = {2024-02-27},
    link = {http://arxiv.org/abs/2402.17693},
    keywords = {Photons, Completeness, ZX-Supported},
    abstract = {Linear optical circuits can be used to manipulate the quantum states of photons as they pass through components including beam splitters and phase shifters. Those photonic states possess a particularly high level of expressiveness, as they reside within the bosonic Fock space, an infinite-dimensional Hilbert space. However, in the domain of linear optical quantum computation, these basic components may not be sufficient to efficiently perform all computations of interest, such as universal quantum computation. To address this limitation it is common to add auxiliary sources and detectors, which enable projections onto auxiliary photonic states and thus increase the versatility of the processes. In this paper, we introduce the $\textbf{LO}_{fi}$-calculus, a graphical language to reason on the infinite-dimensional bosonic Fock space with circuits composed of four core elements of linear optics: the phase shifter, the beam splitter, and auxiliary sources and detectors with bounded photon number. We present an equational theory that we prove to be complete: two $\textbf{LO}_{fi}$-circuits represent the same quantum process if and only if one can be transformed into the other with the rules of the $\textbf{LO}_{fi}$-calculus. We give a unique and compact universal form for such circuits.},
    video = {https://www.youtube.com/watch?v=_0l1KjI0nfA}
}

Copy to Clipboard

Minimal Equational Theories for Quantum Circuits
Alexandre Clément, Noé Delorme and Simon Perdrix
Show abstract ⇲ Show bibdata ⇲ Video 🎥

arXiv:2311.07476
Keywords: ZX-Supported, Completeness, Category Theory, Mixed States.

We introduce the first minimal and complete equational theory for quantum circuits. Hence, we show that any true equation on quantum circuits can be derived from simple rules, all of them being standard except a novel but intuitive one which states that a multi-control

$2\pi$ rotation is nothing but the identity. Our work improves on the recent complete equational theories for quantum circuits, by getting rid of several rules including a fairly unpractical one. One of our main contributions is to prove the minimality of the equational theory, i.e. none of the rules can be derived from the other ones. More generally, we demonstrate that any complete equational theory on quantum circuits (when all gates are unitary) requires rules acting on an unbounded number of qubits. Finally, we also simplify the complete equational theories for quantum circuits with ancillary qubits and/or qubit discarding.

@article{clement2023minimal,
    author = {Cl{\'e}ment, Alexandre and Delorme, No{\'e} and Perdrix, Simon},
    title = {{Minimal Equational Theories for Quantum Circuits}},
    year = {2023},
    journal = {arXiv preprint arXiv:2311.07476},
    urldate = {2023-11-13},
    link = {http://arxiv.org/abs/2311.07476},
    keywords = {ZX-Supported, Completeness, Category Theory, Mixed States},
    abstract = {We introduce the first minimal and complete equational theory for quantum circuits. Hence, we show that any true equation on quantum circuits can be derived from simple rules, all of them being standard except a novel but intuitive one which states that a multi-control $2\pi$ rotation is nothing but the identity. Our work improves on the recent complete equational theories for quantum circuits, by getting rid of several rules including a fairly unpractical one. One of our main contributions is to prove the minimality of the equational theory, i.e. none of the rules can be derived from the other ones. More generally, we demonstrate that any complete equational theory on quantum circuits (when all gates are unitary) requires rules acting on an unbounded number of qubits. Finally, we also simplify the complete equational theories for quantum circuits with ancillary qubits and/or qubit discarding.},
    video = {https://www.youtube.com/watch?v=3q8eqihdtTs}
}

Copy to Clipboard

Rewriting and Completeness of Sum-Over-Paths in Dyadic Fragments of Quantum Computing
Renaud Vilmart
Show abstract ⇲ Show bibdata ⇲

Logical Methods in Computer Science
Keywords: ZH-calculus, Sum-Over-Paths, Completeness, Clifford+T, Toffoli.

The "Sum-Over-Paths" formalism is a way to symbolically manipulate linear maps that describe quantum systems, and is a tool that is used in formal verification of such systems. We give here a new set of rewrite rules for the formalism, and show that it is complete for "Toffoli-Hadamard", the simplest approximately universal fragment of quantum mechanics. We show that the rewriting is terminating, but not confluent (which is expected from the universality of the fragment). We do so using the connection between Sum-over-Paths and graphical language ZH-calculus, and also show how the axiomatisation translates into the latter. We provide generalisations of the presented rewrite rules, that can prove useful when trying to reduce terms in practice, and we show how to graphically make sense of these new rules. We show how to enrich the rewrite system to reach completeness for the dyadic fragments of quantum computation, used in particular in the Quantum Fourier Transform, and obtained by adding phase gates with dyadic multiples of

$\pi$ to the Toffoli-Hadamard gate-set. Finally, we show how to perform sums and concatenation of arbitrary terms, something which is not native in a system designed for analysing gate-based quantum computation, but necessary when considering Hamiltonian-based quantum computation.

@article{vilmart2023rewriting,
    author = {Renaud Vilmart},
    title = {{Rewriting and Completeness of Sum-Over-Paths in Dyadic Fragments of
Quantum Computing}},
    year = {2024},
    journal = {{Logical Methods in Computer Science}},
    volume = {{Volume 20, Issue 1}},
    month = {3},
    doi = {10.46298/lmcs-20(1:20)2024},
    urldate = {2023-07-26},
    link = {http://arxiv.org/abs/2307.14223},
    url = {https://lmcs.episciences.org/13200},
    keywords = {ZH-calculus, Sum-Over-Paths, Completeness, Clifford+T, Toffoli},
    abstract = {The "Sum-Over-Paths" formalism is a way to symbolically manipulate linear maps that describe quantum systems, and is a tool that is used in formal verification of such systems. We give here a new set of rewrite rules for the formalism, and show that it is complete for "Toffoli-Hadamard", the simplest approximately universal fragment of quantum mechanics. We show that the rewriting is terminating, but not confluent (which is expected from the universality of the fragment). We do so using the connection between Sum-over-Paths and graphical language ZH-calculus, and also show how the axiomatisation translates into the latter. We provide generalisations of the presented rewrite rules, that can prove useful when trying to reduce terms in practice, and we show how to graphically make sense of these new rules. We show how to enrich the rewrite system to reach completeness for the dyadic fragments of quantum computation, used in particular in the Quantum Fourier Transform, and obtained by adding phase gates with dyadic multiples of $\pi$ to the Toffoli-Hadamard gate-set. Finally, we show how to perform sums and concatenation of arbitrary terms, something which is not native in a system designed for analysing gate-based quantum computation, but necessary when considering Hamiltonian-based quantum computation.}
}

Copy to Clipboard

The Qudit ZH-Calculus: Generalised Toffoli+Hadamard and Universality
Patrick Roy, John van de Wetering and Lia Yeh
Show abstract ⇲ Show bibdata ⇲

Proceedings of the Twentieth International Conference on Quantum Physics and Logic, Paris, France, 17-21st July 2023
Keywords: Qudits, ZH-calculus, Completeness, Toffoli.

We introduce the qudit ZH-calculus and show how to generalise the phase-free qubit rules to qudits. We prove that for prime dimensions

$d$ , the phase-free qudit ZH-calculus is universal for matrices over the ring

$\mathbb{Z}[e^{2\pi i/d}]$ . For qubits, there is a strong connection between phase-free ZH-diagrams and Toffoli+Hadamard circuits, a computationally universal fragment of quantum circuits. We generalise this connection to qudits, by finding that the two-qudit

$|0\rangle$ -controlled

$X$ gate can be used to construct all classical reversible qudit logic circuits in any odd qudit dimension, which for qubits requires the three-qubit Toffoli gate. We prove that our construction is asymptotically optimal up to a logarithmic term. Twenty years after the celebrated result by Shi proving universality of Toffoli+Hadamard for qubits, we prove that circuits of

$|0\rangle$ -controlled

$X$ and Hadamard gates are approximately universal for qudit quantum computing for any odd prime

$d$ , and moreover that phase-free ZH-diagrams correspond precisely to such circuits allowing postselections.

@inproceedings{roy2023qudit,
    author = {Roy, Patrick and van de Wetering, John and Yeh, Lia},
    title = {{The Qudit ZH-Calculus: Generalised Toffoli+Hadamard and Universality}},
    year = {2023},
    booktitle = {Proceedings of the Twentieth International Conference on Quantum Physics and Logic, Paris, France, 17-21st July 2023},
    editor = {Mansfield, Shane and Val\^iron, Benoit and Zamdzhiev, Vladimir},
    series = {Electronic Proceedings in Theoretical Computer Science},
    volume = {384},
    pages = {142-170},
    publisher = {Open Publishing Association},
    doi = {10.4204/EPTCS.384.9},
    urldate = {2023-07-19},
    link = {http://arxiv.org/abs/2307.10095},
    keywords = {Qudits, ZH-calculus, Completeness, Toffoli},
    abstract = {We introduce the qudit ZH-calculus and show how to generalise the phase-free qubit rules to qudits. We prove that for prime dimensions $d$, the phase-free qudit ZH-calculus is universal for matrices over the ring $\mathbb{Z}[e^{2\pi i/d}]$. For qubits, there is a strong connection between phase-free ZH-diagrams and Toffoli+Hadamard circuits, a computationally universal fragment of quantum circuits. We generalise this connection to qudits, by finding that the two-qudit $|0\rangle$-controlled $X$ gate can be used to construct all classical reversible qudit logic circuits in any odd qudit dimension, which for qubits requires the three-qubit Toffoli gate. We prove that our construction is asymptotically optimal up to a logarithmic term. Twenty years after the celebrated result by Shi proving universality of Toffoli+Hadamard for qubits, we prove that circuits of $|0\rangle$-controlled $X$ and Hadamard gates are approximately universal for qudit quantum computing for any odd prime $d$, and moreover that phase-free ZH-diagrams correspond precisely to such circuits allowing postselections.}
}

Copy to Clipboard

Graphical CSS Code Transformation Using ZX Calculus
Jiaxin Huang, Sarah Meng Li, Lia Yeh, Aleks Kissinger, Michele Mosca and Michael Vasmer
Show abstract ⇲ Show bibdata ⇲ Video 🎥

Proceedings of the Twentieth International Conference on Quantum Physics and Logic, Paris, France, 17-21st July 2023
Keywords: Error Correcting Codes, Clifford Fragment.

In this work, we present a generic approach to transform CSS codes by building upon their equivalence to phase-free ZX diagrams. Using the ZX calculus, we demonstrate diagrammatic transformations between encoding maps associated with different codes. As a motivating example, we give explicit transformations between the Steane code and the quantum Reed-Muller code, since by switching between these two codes, one can obtain a fault-tolerant universal gate set. To this end, we propose a bidirectional rewrite rule to find a (not necessarily transversal) physical implementation for any logical ZX diagram in any CSS code. We then focus on two code transformation techniques:

$\textit{code morphing}$ , a procedure that transforms a code while retaining its fault-tolerant gates, and

$\textit{gauge fixing}$ , where complimentary codes can be obtained from a common subsystem code (e.g., the Steane and the quantum Reed-Muller codes from the [[15,1,3,3]] code). We provide explicit graphical derivations for these techniques and show how ZX and graphical encoder maps relate several equivalent perspectives on these code transforming operations.

@inproceedings{huang2023graphical,
    author = {Huang, Jiaxin and Li, Sarah Meng and Yeh, Lia and Kissinger, Aleks and Mosca, Michele and Vasmer, Michael},
    title = {{Graphical CSS Code Transformation Using ZX Calculus}},
    year = {2023},
    booktitle = {Proceedings of the Twentieth International Conference on Quantum Physics and Logic, Paris, France, 17-21st July 2023},
    editor = {Mansfield, Shane and Val\^iron, Benoit and Zamdzhiev, Vladimir},
    series = {Electronic Proceedings in Theoretical Computer Science},
    volume = {384},
    pages = {1-19},
    publisher = {Open Publishing Association},
    doi = {10.4204/EPTCS.384.1},
    urldate = {2023-07-05},
    link = {http://arxiv.org/abs/2307.02437},
    keywords = {Error Correcting Codes, Clifford Fragment},
    abstract = {In this work, we present a generic approach to transform CSS codes by building upon their equivalence to phase-free ZX diagrams. Using the ZX calculus, we demonstrate diagrammatic transformations between encoding maps associated with different codes. As a motivating example, we give explicit transformations between the Steane code and the quantum Reed-Muller code, since by switching between these two codes, one can obtain a fault-tolerant universal gate set. To this end, we propose a bidirectional rewrite rule to find a (not necessarily transversal) physical implementation for any logical ZX diagram in any CSS code.   We then focus on two code transformation techniques: $\textit{code morphing}$, a procedure that transforms a code while retaining its fault-tolerant gates, and $\textit{gauge fixing}$, where complimentary codes can be obtained from a common subsystem code (e.g., the Steane and the quantum Reed-Muller codes from the [[15,1,3,3]] code). We provide explicit graphical derivations for these techniques and show how ZX and graphical encoder maps relate several equivalent perspectives on these code transforming operations.},
    video = {https://www.youtube.com/watch?v=ZhfQxdjodNs}
}

Copy to Clipboard

Complete Equational Theories for the Sum-Over-Paths with Unbalanced Amplitudes
Matthew Amy
Show abstract ⇲ Show bibdata ⇲

Proceedings of the Twentieth International Conference on Quantum Physics and Logic, Paris, France, 17-21st July 2023
Keywords: ZH-calculus, Completeness, Sum-Over-Paths.

Vilmart recently gave a complete equational theory for the balanced sum-over-paths over Toffoli-Hadamard circuits, and by extension Clifford+

$\mathrm{diag}(1, \zeta_{2^k})$ circuits. Their theory is based on the phase-free ZH-calculus which crucially omits the average rule of the full ZH-calculus, dis-allowing the local summation of amplitudes. Here we study the question of completeness in unbalanced path sums which naturally support local summation. We give a concrete syntax for the unbalanced sum-over-paths and show that, together with symbolic multilinear algebra and the interference rule, various formulations of the average and ortho rules of the ZH-calculus are sufficient to give complete equational theories over arbitrary rings and fields.

@inproceedings{amy2023complete,
    author = {Amy, Matthew},
    title = {{Complete Equational Theories for the Sum-Over-Paths with Unbalanced Amplitudes}},
    year = {2023},
    booktitle = {Proceedings of the Twentieth International Conference on Quantum Physics and Logic, Paris, France, 17-21st July 2023},
    editor = {Mansfield, Shane and Val\^iron, Benoit and Zamdzhiev, Vladimir},
    series = {Electronic Proceedings in Theoretical Computer Science},
    volume = {384},
    pages = {127-141},
    publisher = {Open Publishing Association},
    doi = {10.4204/EPTCS.384.8},
    urldate = {2023-06-28},
    link = {http://arxiv.org/abs/2306.16369},
    keywords = {ZH-calculus, Completeness, Sum-Over-Paths},
    abstract = {Vilmart recently gave a complete equational theory for the balanced sum-over-paths over Toffoli-Hadamard circuits, and by extension Clifford+$\mathrm{diag}(1, \zeta_{2^k})$ circuits. Their theory is based on the phase-free ZH-calculus which crucially omits the average rule of the full ZH-calculus, dis-allowing the local summation of amplitudes. Here we study the question of completeness in unbalanced path sums which naturally support local summation. We give a concrete syntax for the unbalanced sum-over-paths and show that, together with symbolic multilinear algebra and the interference rule, various formulations of the average and ortho rules of the ZH-calculus are sufficient to give complete equational theories over arbitrary rings and fields.}
}

Copy to Clipboard

Non-stabilizerness and entanglement from cat-state injection
Filipa C R Peres, Rafael Wagner and Ernesto F Galvão
Show abstract ⇲ Show bibdata ⇲

New Journal of Physics
Keywords: Classical Simulation, ZX-calculus, Applied, Automation.

Recently, cat states have been used to heuristically improve the runtime of a classical simulator of quantum circuits based on the diagrammatic ZX-calculus. Here we explore the use of cat-state injection within the quantum circuit model. We introduce a new family of cat states

$\left| \mathrm{cat}_m^* \right>$ , and describe circuit gadgets using them to concurrently inject non-stabilizerness (also known as magic) and entanglement into any quantum circuit. We provide numerical evidence that cat-state injection does not lead to speed-up in classical simulation. On the other hand, we show that our gadgets can be used to widen the scope of compelling applications of cat states. Specifically, we show how to leverage them to achieve savings in the number of injected qubits, and also to induce scrambling dynamics in otherwise non-entangling Clifford circuits in a controlled manner.

@article{Peres_2024,
    author = {Filipa C R Peres and Rafael Wagner and Ernesto F Galvão},
    title = {Non-stabilizerness and entanglement from cat-state injection},
    year = {2024},
    journal = {New Journal of Physics},
    volume = {26},
    number = {1},
    month = {jan},
    pages = {013051},
    publisher = {IOP Publishing},
    doi = {10.1088/1367-2630/ad1b80},
    urldate = {2023-05-31},
    link = {http://arxiv.org/abs/2305.19988},
    url = {https://dx.doi.org/10.1088/1367-2630/ad1b80},
    keywords = {Classical Simulation, ZX-calculus, Applied, Automation},
    abstract = {Recently, cat states have been used to heuristically improve the runtime of a classical simulator of quantum circuits based on the diagrammatic ZX-calculus. Here we explore the use of cat-state injection within the quantum circuit model. We introduce a new family of cat states $\left| \mathrm{cat}_m^* \right>$, and describe circuit gadgets using them to concurrently inject non-stabilizerness (also known as magic) and entanglement into any quantum circuit. We provide numerical evidence that cat-state injection does not lead to speed-up in classical simulation. On the other hand, we show that our gadgets can be used to widen the scope of compelling applications of cat states. Specifically, we show how to leverage them to achieve savings in the number of injected qubits, and also to induce scrambling dynamics in otherwise non-entangling Clifford circuits in a controlled manner.}
}

Copy to Clipboard

Scaling W State Circuits in the qudit Clifford Hierarchy
Lia Yeh
Show abstract ⇲ Show bibdata ⇲

Companion Proceedings of the 7th International Conference on the Art, Science, and Engineering of Programming
Keywords: Qudits, Optimisation, ZW-calculus, ZX-calculus.

We identify a novel qudit gate which we call the

$\sqrt[d]{Z}$ gate. This is an alternate generalization of the qutrit

$T$ gate to any odd prime dimension

$d$ , in the

$d^{\text{th}}$ level of the Clifford hierarchy. Using this gate which is efficiently realizable fault-tolerantly should a certain conjecture hold, we deterministically construct in the Clifford+

$\sqrt[d]{Z}$ gate set,

$d$ -qubit

$W$ states in the qudit

$\{ |0\rangle , |1\rangle \}$ subspace. For qutrits, this gives deterministic and fault-tolerant constructions for the qubit

$W$ state of sizes three with

$T$ count 3, six, and powers of three. Furthermore, we adapt these constructions to recursively scale the

$W$ state size to arbitrary size

$N$ , in

$O(N)$ gate count and

$O(\text{log }N)$ depth. This is moreover deterministic for any size qubit

$W$ state, and for any prime

$d$ -dimensional qudit

$W$ state, size a power of

$d$ . For these purposes, we devise constructions of the

$|0\rangle$ -controlled Pauli

$X$ gate and the controlled Hadamard gate in any prime qudit dimension. These decompositions, for which exact synthesis is unknown in Clifford+

$T$ for

$d > 3$ , may be of independent interest.

@inproceedings{yeh2023scaling,
    author = {Yeh, Lia},
    title = {Scaling W State Circuits in the qudit Clifford Hierarchy},
    year = {2023},
    booktitle = {Companion Proceedings of the 7th International Conference on the Art, Science, and Engineering of Programming},
    series = {Programming '23},
    pages = {90–100},
    numpages = {11},
    publisher = {Association for Computing Machinery},
    address = {New York, NY, USA},
    isbn = {9798400707551},
    location = {, Tokyo, Japan, },
    doi = {10.1145/3594671.3594687},
    urldate = {2023-04-25},
    link = {http://arxiv.org/abs/2304.12504},
    url = {https://doi.org/10.1145/3594671.3594687},
    keywords = {Qudits, Optimisation, ZW-calculus, ZX-calculus},
    abstract = {We identify a novel qudit gate which we call the $\sqrt[d]{Z}$ gate. This is an alternate generalization of the qutrit $T$ gate to any odd prime dimension $d$, in the $d^{\text{th}}$ level of the Clifford hierarchy. Using this gate which is efficiently realizable fault-tolerantly should a certain conjecture hold, we deterministically construct in the Clifford+$\sqrt[d]{Z}$ gate set, $d$-qubit $W$ states in the qudit $\{ |0\rangle , |1\rangle \}$ subspace. For qutrits, this gives deterministic and fault-tolerant constructions for the qubit $W$ state of sizes three with $T$ count 3, six, and powers of three.   Furthermore, we adapt these constructions to recursively scale the $W$ state size to arbitrary size $N$, in $O(N)$ gate count and $O(\text{log }N)$ depth. This is moreover deterministic for any size qubit $W$ state, and for any prime $d$-dimensional qudit $W$ state, size a power of $d$.   For these purposes, we devise constructions of the $ |0\rangle $-controlled Pauli $X$ gate and the controlled Hadamard gate in any prime qudit dimension. These decompositions, for which exact synthesis is unknown in Clifford+$T$ for $d > 3$, may be of independent interest.}
}

Copy to Clipboard

The Algebra for Stabilizer Codes
Cole Comfort
Show abstract ⇲ Show bibdata ⇲ Video 🎥

arXiv:2304.10584
Keywords: Clifford Fragment, Qudits, Error Correcting Codes, Spekkens Toy Model, Category Theory, Completeness, Mixed States.

There is a bijection between odd prime dimensional qudit pure stabilizer states modulo invertible scalars and affine Lagrangian subspaces of finite dimensional symplectic

$\mathbb{F}_p$ -vector spaces. In the language of the stabilizer formalism, full rank stabilizer tableaus are exactly the bases for affine Lagrangian subspaces. This correspondence extends to an isomorphism of props where the composition of stabilizer circuits becomes the relational composition of affine subspaces and the tensor product becomes the direct sum. In this paper, we extend this correspondence between stabilizer circuits and tableaus to the mixed setting; by regarding stabilizer codes as affine coisotropic susbspaces (again only in odd prime qudit dimension/for qubit CSS codes). We show that by splitting the projector for a stabilizer code we recover the error detection protocol and the error correction protocol with affine classical processing power.

@article{comfort2023algebrfor,
    author = {Comfort, Cole},
    title = {{The Algebra for Stabilizer Codes}},
    year = {2023},
    journal = {arXiv preprint arXiv:2304.10584},
    urldate = {2023-04-20},
    link = {http://arxiv.org/abs/2304.10584},
    keywords = {Clifford Fragment, Qudits, Error Correcting Codes, Spekkens Toy Model, Category Theory, Completeness, Mixed States },
    abstract = {There is a bijection between odd prime dimensional qudit pure stabilizer states modulo invertible scalars and affine Lagrangian subspaces of finite dimensional symplectic $\mathbb{F}_p$-vector spaces. In the language of the stabilizer formalism, full rank stabilizer tableaus are exactly the bases for affine Lagrangian subspaces. This correspondence extends to an isomorphism of props where the composition of stabilizer circuits becomes the relational composition of affine subspaces and the tensor product becomes the direct sum. In this paper, we extend this correspondence between stabilizer circuits and tableaus to the mixed setting; by regarding stabilizer codes as affine coisotropic susbspaces (again only in odd prime qudit dimension/for qubit CSS codes). We show that by splitting the projector for a stabilizer code we recover the error detection protocol and the error correction protocol with affine classical processing power.},
    video = {https://www.youtube.com/watch?v=80rx6LzWCWo}
}

Copy to Clipboard

Picturing Counting Reductions with the ZH-Calculus
Tuomas Laakkonen, Konstantinos Meichanetzidis and John van de Wetering
Show abstract ⇲ Show bibdata ⇲

Proceedings of the Twentieth International Conference on Quantum Physics and Logic, Paris, France, 17-21st July 2023
Keywords: Classical Simulation, SAT, ZH-calculus, Applied.

Counting the solutions to Boolean formulae defines the problem #SAT, which is complete for the complexity class #P. We use the ZH-calculus, a universal and complete graphical language for linear maps which naturally encodes counting problems in terms of diagrams, to give graphical reductions from #SAT to several related counting problems. Some of these graphical reductions, like to #2SAT, are substantially simpler than known reductions via the matrix permanent. Additionally, our approach allows us to consider the case of counting solutions modulo an integer on equal footing. Finally, since the ZH-calculus was originally introduced to reason about quantum computing, we show that the problem of evaluating ZH-diagrams in the fragment corresponding to the Clifford+T gateset, is in

$FP^{\#P}$ . Our results show that graphical calculi represent an intuitive and useful framework for reasoning about counting problems.

@inproceedings{EPTCS384.6,
    author = {Laakkonen, Tuomas and Meichanetzidis, Konstantinos and van de Wetering, John},
    title = {{Picturing Counting Reductions with the ZH-Calculus}},
    year = {2023},
    booktitle = {Proceedings of the Twentieth International Conference on Quantum Physics and Logic, Paris, France, 17-21st July 2023},
    editor = {Mansfield, Shane and Val\^iron, Benoit and Zamdzhiev, Vladimir},
    series = {Electronic Proceedings in Theoretical Computer Science},
    volume = {384},
    pages = {89-113},
    publisher = {Open Publishing Association},
    doi = {10.4204/EPTCS.384.6},
    urldate = {2023-04-05},
    link = {http://arxiv.org/abs/2304.02524},
    keywords = {Classical Simulation, SAT, ZH-calculus, Applied},
    abstract = {Counting the solutions to Boolean formulae defines the problem #SAT, which is complete for the complexity class #P. We use the ZH-calculus, a universal and complete graphical language for linear maps which naturally encodes counting problems in terms of diagrams, to give graphical reductions from #SAT to several related counting problems. Some of these graphical reductions, like to #2SAT, are substantially simpler than known reductions via the matrix permanent. Additionally, our approach allows us to consider the case of counting solutions modulo an integer on equal footing. Finally, since the ZH-calculus was originally introduced to reason about quantum computing, we show that the problem of evaluating ZH-diagrams in the fragment corresponding to the Clifford+T gateset, is in $FP^{\#P}$. Our results show that graphical calculi represent an intuitive and useful framework for reasoning about counting problems.}
}

Copy to Clipboard

The Zeta Calculus
Nicklas Botö and Fabian Forslund
Show abstract ⇲ Show bibdata ⇲ Video 🎥

arXiv:2303.17399
Keywords: Protocols, Category Theory, Verification, ZX-calculus.

We propose a quantum programming language that generalizes the

$\lambda$ -calculus. The language is non-linear; duplicated variables denote, not cloning of quantum data, but sharing a qubit's state; that is, producing an entangled pair of qubits whose amplitudes are identical with respect to a chosen basis. The language has two abstraction operators,

$\zeta$ and

$\xi$ , corresponding to the Z- and X-bases; each abstraction operator is also parameterised by a phase, indicating a rotation that is applied to the input before it is shared. We give semantics for the language in the ZX-calculus and prove its equational theory sound. We show how this language can provide a good representation of higher-order functions in the quantum world.

@article{boto2023zetcalculus,
    author = {Bot{\"o}, Nicklas and Forslund, Fabian},
    title = {{The Zeta Calculus}},
    year = {2023},
    journal = {arXiv preprint arXiv:2303.17399},
    urldate = {2023-03-30},
    link = {http://arxiv.org/abs/2303.17399},
    keywords = {Protocols, Category Theory, Verification, ZX-calculus},
    abstract = {We propose a quantum programming language that generalizes the $\lambda$-calculus. The language is non-linear; duplicated variables denote, not cloning of quantum data, but sharing a qubit's state; that is, producing an entangled pair of qubits whose amplitudes are identical with respect to a chosen basis. The language has two abstraction operators, $\zeta$ and $\xi$, corresponding to the Z- and X-bases; each abstraction operator is also parameterised by a phase, indicating a rotation that is applied to the input before it is shared. We give semantics for the language in the ZX-calculus and prove its equational theory sound. We show how this language can provide a good representation of higher-order functions in the quantum world.},
    video = {https://www.youtube.com/watch?v=iUHEy3PZCso}
}

Copy to Clipboard

Cutting multi-control quantum gates with ZX calculus
Christian Ufrecht, Maniraman Periyasamy, Sebastian Rietsch, Daniel D. Scherer, Axel Plinge and Christopher Mutschler
Show abstract ⇲ Show bibdata ⇲ Video 🎥

Quantum
Keywords: ZH-calculus, Classical Simulation, Applied.

Circuit cutting, the decomposition of a quantum circuit into independent partitions, has become a promising avenue towards experiments with larger quantum circuits in the noisy-intermediate scale quantum (NISQ) era. While previous work focused on cutting qubit wires or two-qubit gates, in this work we introduce a method for cutting multi-controlled Z gates. We construct a decomposition and prove the upper bound

$\mathcal{O}(6^{2K})$ on the associated sampling overhead, where

$K$ is the number of cuts in the circuit. This bound is independent of the number of control qubits but can be further reduced to

$\mathcal{O}(4.5^{2K})$ for the special case of CCZ gates. Furthermore, we evaluate our proposal on IBM hardware and experimentally show noise resilience due to the strong reduction of CNOT gates in the cut circuits.

@article{ufrecht2023cutting,
    author = {Ufrecht, Christian and Periyasamy, Maniraman and Rietsch, Sebastian and Scherer, Daniel D. and Plinge, Axel and Mutschler, Christopher},
    title = {Cutting multi-control quantum gates with {ZX} calculus},
    year = {2023},
    journal = {{Quantum}},
    volume = {7},
    month = {10},
    pages = {1147},
    publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
    issn = {2521-327X},
    doi = {10.22331/q-2023-10-23-1147},
    urldate = {2023-02-01},
    link = {http://arxiv.org/abs/2302.00387},
    url = {https://doi.org/10.22331/q-2023-10-23-1147},
    keywords = {ZH-calculus, Classical Simulation, Applied},
    abstract = {Circuit cutting, the decomposition of a quantum circuit into independent partitions, has become a promising avenue towards experiments with larger quantum circuits in the noisy-intermediate scale quantum (NISQ) era. While previous work focused on cutting qubit wires or two-qubit gates, in this work we introduce a method for cutting multi-controlled Z gates. We construct a decomposition and prove the upper bound $\mathcal{O}(6^{2K})$ on the associated sampling overhead, where $K$ is the number of cuts in the circuit. This bound is independent of the number of control qubits but can be further reduced to $\mathcal{O}(4.5^{2K})$ for the special case of CCZ gates. Furthermore, we evaluate our proposal on IBM hardware and experimentally show noise resilience due to the strong reduction of CNOT gates in the cut circuits.},
    video = {https://www.youtube.com/watch?v=YPtEIuapWww}
}

Copy to Clipboard

CSS code surgery as a universal construction
Alexander Cowtan and Simon Burton
Show abstract ⇲ Show bibdata ⇲ Video 🎥

arXiv:2301.13738
Keywords: Error Correcting Codes, Category Theory, ZX-Supported.

We define code maps between Calderbank-Shor-Steane (CSS) codes using maps between chain complexes, and describe code surgery between such codes using a specific colimit in the category of chain complexes. As well as describing a surgery operation, this gives a general recipe for new codes. As an application we describe how to

$merge' and$ split' along a shared

$\overline{X}$ or

$\overline{Z}$ operator between arbitrary CSS codes in a fault-tolerant manner, so long as the participating qubits satisfy a technical condition related to gauge fixing. We prove that such merges and splits on LDPC codes yield codes which are themselves LDPC.

@article{cowtan2023css,
    author = {Cowtan, Alexander and Burton, Simon},
    title = {{CSS code surgery as a universal construction}},
    year = {2023},
    journal = {arXiv preprint arXiv:2301.13738},
    urldate = {2023-01-31},
    link = {http://arxiv.org/abs/2301.13738},
    keywords = {Error Correcting Codes, Category Theory, ZX-Supported},
    abstract = {We define code maps between Calderbank-Shor-Steane (CSS) codes using maps between chain complexes, and describe code surgery between such codes using a specific colimit in the category of chain complexes. As well as describing a surgery operation, this gives a general recipe for new codes. As an application we describe how to `merge' and `split' along a shared $\overline{X}$ or $\overline{Z}$ operator between arbitrary CSS codes in a fault-tolerant manner, so long as the participating qubits satisfy a technical condition related to gauge fixing. We prove that such merges and splits on LDPC codes yield codes which are themselves LDPC.},
    video = {https://www.youtube.com/watch?v=XPY53T7DkXc}
}

Copy to Clipboard

Classically Simulating Quantum Supremacy IQP Circuits trough a Random Graph Approach
Julien Codsi and John van de Wetering
Show abstract ⇲ Show bibdata ⇲

arXiv:2212.08609
Keywords: Classical Simulation, Clifford+T, Automation, ZX-calculus, Applied.

Quantum Supremacy is a demonstration of a computation by a quantum computer that can not be performed by the best classical computer in a reasonable time. A well-studied approach to demonstrating this on near-term quantum computers is to use random circuit sampling. It has been suggested that a good candidate for demonstrating quantum supremacy with random circuit sampling is to use \emph{IQP circuits}. These are quantum circuits where the unitary it implements is diagonal. In this paper we introduce improved techniques for classically simulating random IQP circuits. We find a simple algorithm to calculate an amplitude of an

$n$ -qubit IQP circuit with dense random two-qubit interactions in time

$O(\frac{\log^2 n}{n} 2^n )$ , which for sparse circuits (where each qubit interacts with

$O(\log n)$ other qubits) runs in

$o(2^n/\text{poly}(n))$ for any given polynomial. Using a more complicated stabiliser decomposition approach we improve the algorithm for dense circuits to

$O\left(\frac{(\log n)^{4-\beta}}{n^{2-\beta}} 2^n \right)$ where

$\beta \approx 0.396$ . We benchmarked our algorithm and found that we can simulate up to 50-qubit circuits in a couple of minutes on a laptop. We estimate that 70-qubit circuits are within reach for a large computing cluster.

@article{codsi2022classically,
    author = {Codsi, Julien and van de Wetering, John},
    title = {{Classically Simulating Quantum Supremacy IQP Circuits trough a Random Graph Approach}},
    year = {2022},
    journal = {arXiv preprint arXiv:2212.08609},
    urldate = {2022-12-16},
    link = {http://arxiv.org/abs/2212.08609},
    keywords = {Classical Simulation, Clifford+T, Automation, ZX-calculus, Applied},
    abstract = {Quantum Supremacy is a demonstration of a computation by a quantum computer that can not be performed by the best classical computer in a reasonable time. A well-studied approach to demonstrating this on near-term quantum computers is to use random circuit sampling. It has been suggested that a good candidate for demonstrating quantum supremacy with random circuit sampling is to use \emph{IQP circuits}. These are quantum circuits where the unitary it implements is diagonal. In this paper we introduce improved techniques for classically simulating random IQP circuits. We find a simple algorithm to calculate an amplitude of an $n$-qubit IQP circuit with dense random two-qubit interactions in time $O(\frac{\log^2 n}{n} 2^n )$, which for sparse circuits (where each qubit interacts with $O(\log n)$ other qubits) runs in $o(2^n/\text{poly}(n))$ for any given polynomial. Using a more complicated stabiliser decomposition approach we improve the algorithm for dense circuits to $O\left(\frac{(\log n)^{4-\beta}}{n^{2-\beta}} 2^n \right)$ where $\beta \approx 0.396$. We benchmarked our algorithm and found that we can simulate up to 50-qubit circuits in a couple of minutes on a laptop. We estimate that 70-qubit circuits are within reach for a large computing cluster.}
}

Copy to Clipboard

A Graphical #SAT Algorithm for Formulae with Small Clause Density
Tuomas Laakkonen, Konstantinos Meichanetzidis and John van de Wetering
Show abstract ⇲ Show bibdata ⇲

Proceedings of the 21st International Conference on Quantum Physics and Logic, Buenos Aires, Argentina, July 15-19, 2024
Keywords: Classical Simulation, ZH-calculus, SAT, Applied.

We study the counting version of the Boolean satisfiability problem \#SAT using the ZH-calculus, a graphical language originally introduced to reason about quantum circuits. Using this we find a natural extension of \#SAT which we call

$\#SAT_\pm$ , where variables are additionally labeled by phases, which is GapP-complete. Using graphical reasoning, we find a reduction from \#SAT to

$\#2SAT_\pm$ in the ZH-calculus. We observe that the DPLL algorithm for #2SAT can be adapted to

$\#2SAT_\pm$ directly and hence that Wahlstrom's

$O^*(1.2377^n)$ upper bound applies to

$\#2SAT_\pm$ as well. Combining this with our reduction from \#SAT to

$\#2SAT_\pm$ gives us novel upper bounds in terms of clauses and variables that are better than

$O^*(2^n)$ for small clause densities of

$\frac{m}{n} < 2.25$ . This is to our knowledge the first non-trivial upper bound for \#SAT that is independent of clause size. Our algorithm improves on Dubois' upper bound for

$\#kSAT$ whenever

$\frac{m}{n} < 1.85$ and

$k \geq 4$ , and the Williams' average-case analysis whenever

$\frac{m}{n} < 1.21$ and

$k \geq 6$ . We also obtain an unconditional upper bound of

$O^*(1.88^m)$ for

$\#4SAT$ in terms of clauses only, and find an improved bound on

$\#3SAT$ for

$1.2577 < \frac{m}{n} \leq \frac{7}{3}$ . Our results demonstrate that graphical reasoning can lead to new algorithmic insights, even outside the domain of quantum computing that the calculus was intended for.

@inproceedings{laakkonen2022graphical,
    author = {Laakkonen, Tuomas and Meichanetzidis, Konstantinos and van de Wetering, John},
    title = {{A Graphical \#SAT Algorithm for Formulae with Small Clause Density}},
    year = {2024},
    booktitle = {Proceedings of the 21st International Conference on Quantum Physics and Logic, Buenos Aires, Argentina, July 15-19, 2024},
    editor = {D\'iaz-Caro, Alejandro and Zamdzhiev, Vladimir},
    series = {Electronic Proceedings in Theoretical Computer Science},
    volume = {406},
    pages = {137-161},
    publisher = {Open Publishing Association},
    doi = {10.4204/EPTCS.406.7},
    urldate = {2022-12-15},
    link = {http://arxiv.org/abs/2212.08048},
    keywords = {Classical Simulation, ZH-calculus, SAT, Applied},
    abstract = {We study the counting version of the Boolean satisfiability problem \#SAT using the ZH-calculus, a graphical language originally introduced to reason about quantum circuits. Using this we find a natural extension of \#SAT which we call $\#SAT_\pm$, where variables are additionally labeled by phases, which is GapP-complete. Using graphical reasoning, we find a reduction from \#SAT to $\#2SAT_\pm$ in the ZH-calculus. We observe that the DPLL algorithm for #2SAT can be adapted to $\#2SAT_\pm$ directly and hence that Wahlstrom's $O^*(1.2377^n)$ upper bound applies to $\#2SAT_\pm$ as well. Combining this with our reduction from \#SAT to $\#2SAT_\pm$ gives us novel upper bounds in terms of clauses and variables that are better than $O^*(2^n)$ for small clause densities of $\frac{m}{n} < 2.25$. This is to our knowledge the first non-trivial upper bound for \#SAT that is independent of clause size. Our algorithm improves on Dubois' upper bound for $\#kSAT$ whenever $\frac{m}{n} < 1.85$ and $k \geq 4$, and the Williams' average-case analysis whenever $\frac{m}{n} < 1.21$ and $k \geq 6$. We also obtain an unconditional upper bound of $O^*(1.88^m)$ for $\#4SAT$ in terms of clauses only, and find an improved bound on $\#3SAT$ for $1.2577 < \frac{m}{n} \leq \frac{7}{3}$. Our results demonstrate that graphical reasoning can lead to new algorithmic insights, even outside the domain of quantum computing that the calculus was intended for.}
}

Copy to Clipboard

Quantum computation on a 19-qubit wide 2d nearest neighbour qubit array
Alexis Shaw, Michael Bremner, Alexandru Paler, Daniel Herr and Simon J. Devitt
Show abstract ⇲ Show bibdata ⇲

arXiv:2212.01550
Keywords: Surface Code, Lattice Surgery, Applied, Error Correcting Codes, ZX-calculus.

In this paper, we explore the relationship between the width of a qubit lattice constrained in one dimension and physical thresholds for scalable, fault-tolerant quantum computation. To circumvent the traditionally low thresholds of small fixed-width arrays, we deliberately engineer an error bias at the lowest level of encoding using the surface code. We then address this engineered bias at a higher level of encoding using a lattice-surgery surface code bus that exploits this bias, or a repetition code to make logical qubits with unbiased errors out of biased surface code qubits. Arbitrarily low error rates can then be reached by further concatenating with other codes, such as Steane [[7,1,3]] code and the [[15,7,3]] CSS code. This enables a scalable fixed-width quantum computing architecture on a square qubit lattice that is only 19 qubits wide, given physical qubits with an error rate of

$8.0\times 10^{-4}$ . This potentially eases engineering issues in systems with fine qubit pitches, such as quantum dots in silicon or gallium arsenide.

@article{shaw2022quantum,
    author = {Shaw, Alexis and Bremner, Michael and Paler, Alexandru and Herr, Daniel and Devitt, Simon J.},
    title = {{Quantum computation on a 19-qubit wide 2d nearest neighbour qubit array}},
    year = {2022},
    journal = {arXiv preprint arXiv:2212.01550},
    urldate = {2022-12-03},
    link = {http://arxiv.org/abs/2212.01550},
    keywords = {Surface Code, Lattice Surgery, Applied, Error Correcting Codes, ZX-calculus},
    abstract = {In this paper, we explore the relationship between the width of a qubit lattice constrained in one dimension and physical thresholds for scalable, fault-tolerant quantum computation. To circumvent the traditionally low thresholds of small fixed-width arrays, we deliberately engineer an error bias at the lowest level of encoding using the surface code. We then address this engineered bias at a higher level of encoding using a lattice-surgery surface code bus that exploits this bias, or a repetition code to make logical qubits with unbiased errors out of biased surface code qubits. Arbitrarily low error rates can then be reached by further concatenating with other codes, such as Steane [[7,1,3]] code and the [[15,7,3]] CSS code. This enables a scalable fixed-width quantum computing architecture on a square qubit lattice that is only 19 qubits wide, given physical qubits with an error rate of $8.0\times 10^{-4}$. This potentially eases engineering issues in systems with fine qubit pitches, such as quantum dots in silicon or gallium arsenide.}
}

Copy to Clipboard

The ZX-calculus as a language for topological quantum computation
Fatimah Rita Ahmadi and Aleks Kissinger
Show abstract ⇲ Show bibdata ⇲

Journal of Physics A: Mathematical and Theoretical
Keywords: Braids, ZX-calculus, Applied.

Unitary fusion categories formalise the algebraic theory of topological quantum computation. These categories come naturally enriched in a subcategory of the category of Hilbert spaces, and by looking at this subcategory, one can identify a collection of generators for implementing quantum computation. We represent such generators for the Fibonacci and Ising models, namely the encoding of qubits and the associated braid group representations, with the ZX-calculus and show that in both cases, the Yang-Baxter equation is directly connected to an important rule in the complete ZX-calculus known as the P-rule, which enables one to interchange the phase gates defined with respect to complementary bases. In the Ising case, this reduces to a familiar rule relating two distinct Euler decompositions of the Hadamard gate as

$\pi/2$ Z- and X-phase gates, whereas in the Fibonacci case, we give a previously unconsidered exact solution of the P-rule involving the Golden ratio. We demonstrate the utility of these representations by giving graphical derivations of the single-qubit braid equations for Fibonacci anyons and the single- and two-qubit braid equations for Ising anyons. We furthermore present a fully graphical procedure for simulating and simplifying braids with the ZX-representation of Fibonacci anyons.

@article{ritaahmadi2022topological,
    author = {Ahmadi, Fatimah Rita and Kissinger, Aleks},
    title = {{The ZX-calculus as a language for topological quantum computation}},
    year = {2023},
    journal = {Journal of Physics A: Mathematical and Theoretical},
    doi = {10.1088/1751-8121/acef7e},
    urldate = {2022-11-07},
    link = {http://arxiv.org/abs/2211.03855},
    keywords = {Braids, ZX-calculus, Applied},
    abstract = {Unitary fusion categories formalise the algebraic theory of topological quantum computation. These categories come naturally enriched in a subcategory of the category of Hilbert spaces, and by looking at this subcategory, one can identify a collection of generators for implementing quantum computation. We represent such generators for the Fibonacci and Ising models, namely the encoding of qubits and the associated braid group representations, with the ZX-calculus and show that in both cases, the Yang-Baxter equation is directly connected to an important rule in the complete ZX-calculus known as the P-rule, which enables one to interchange the phase gates defined with respect to complementary bases. In the Ising case, this reduces to a familiar rule relating two distinct Euler decompositions of the Hadamard gate as $\pi/2$ Z- and X-phase gates, whereas in the Fibonacci case, we give a previously unconsidered exact solution of the P-rule involving the Golden ratio. We demonstrate the utility of these representations by giving graphical derivations of the single-qubit braid equations for Fibonacci anyons and the single- and two-qubit braid equations for Ising anyons. We furthermore present a fully graphical procedure for simulating and simplifying braids with the ZX-representation of Fibonacci anyons.}
}

Copy to Clipboard

Graphical Stabilizer Decompositions For Counting Problems
Tuomas Laakkonen
Show abstract ⇲ Show bibdata ⇲

University of Oxford Masters Thesis
Keywords: ZX-Calculus, ZH-calculus, Classical Simulation, SAT, Applied, Master Thesis.

Building on the work of de Beaudrap, Kissinger, and Meichanetzidis [dKM21], in this dissertation, we examine the relationship between #SAT and the ZH calculus. We outline their reduction from \#SAT to evaluating ZH diagrams, which shows that evaluating ZH diagrams is \#P-hard, and we extend this to show that evaluating diagrams in certain fragments of the ZH calculus, is

$FP^{\#P}$ -complete. In particular, we show this holds for diagrams where all H-boxes have labels in

$\mathbb{Q}[i,\sqrt{2}]$ , which includes both the Clifford+T and Toffoli-Hadamard fragments natively [BKM+21]. We show the action of the DPLL algorithm [DLL62] for SAT and its derivative CDP [BL99] for \#SAT in terms of ZH-diagrams, and use diagrammatic methods to extend CDP to treat variables and clauses equally. Combining this with an algorithm for \#2SAT by Wahlström [Wah08], we derive novel upper bounds in terms of clauses and variables for \#kSAT that are independent of

$k$ , and better than brute-force for small clause densities of

$\frac{m}{n} < 2.25$ . This improves on the upper bound of Dubois [Dub91] whenever

$\frac{m}{n} < 1.858$ and

$k \geq 4$ , and the average-case analysis by Williams [Wil04] whenever

$\frac{m}{n} < 1.217$ and

$k \geq 6$ . We also obtain an unconditional upper bound of

$O∗(1.88m)$ for \#4SAT in terms of clauses only. Finally, we find novel stabilizer decompositions of certain ZH-diagrams and use this to adapt the algorithm of Kissinger and van de Wetering [Kv21] [KvV22] for evaluating ZX-diagrams using stabilizer decompositions to evaluate \#2SAT instances. We examine the effect of different decomposition strategies on its runtime but conclude that the algorithm as given is not effective, and suggest avenues for further improvement.

@mastersthesis{Laakkonen2022Masters,
    author = {Laakkonen, Tuomas},
    title = {{Graphical Stabilizer Decompositions For Counting Problems}},
    year = {2022},
    school = {University of Oxford},
    urldate = {2022-10-15},
    link = {https://www.cs.ox.ac.uk/people/aleks.kissinger/theses/laakkonen-thesis.pdf},
    keywords = {ZX-Calculus, ZH-calculus, Classical Simulation, SAT, Applied, Master Thesis},
    abstract = {Building on the work of de Beaudrap, Kissinger, and Meichanetzidis [dKM21], in this dissertation, we examine the relationship between #SAT and the ZH calculus. We outline their reduction from \#SAT to evaluating ZH diagrams, which shows that evaluating ZH diagrams is \#P-hard, and we extend this to show that evaluating diagrams in certain fragments of the ZH calculus, is $FP^{\#P}$-complete. In particular, we show this holds for diagrams where all H-boxes have labels in $\mathbb{Q}[i,\sqrt{2}]$, which includes both the Clifford+T and Toffoli-Hadamard fragments natively [BKM+21]. We show the action of the DPLL algorithm [DLL62] for SAT and its derivative CDP [BL99] for \#SAT in terms of ZH-diagrams, and use diagrammatic methods to extend CDP to treat variables and clauses equally. Combining this with an algorithm for \#2SAT by Wahlström [Wah08], we derive novel upper bounds in terms of clauses and variables for \#kSAT that are independent of $k$, and better than brute-force for small clause densities of $\frac{m}{n} < 2.25$.
This improves on the upper bound of Dubois [Dub91] whenever $\frac{m}{n} < 1.858$ and $k \geq 4$, and the average-case analysis by Williams [Wil04] whenever $\frac{m}{n} < 1.217$ and $k \geq 6$. We also obtain an unconditional upper bound of
$O∗(1.88m)$ for \#4SAT in terms of clauses only.
Finally, we find novel stabilizer decompositions of certain ZH-diagrams and use this to adapt the algorithm of Kissinger and van de Wetering [Kv21] [KvV22] for evaluating ZX-diagrams using stabilizer decompositions to evaluate \#2SAT instances. We examine the effect of different decomposition strategies on its runtime but conclude that the algorithm as given is not
effective, and suggest avenues for further improvement.}
}

Copy to Clipboard

A Pair Measurement Surface Code on Pentagons
Craig Gidney
Show abstract ⇲ Show bibdata ⇲

Quantum
Keywords: Surface Code, ZX-calculus, Applied.

In this paper, I present a way to compile the surface code into two-body parity measurements ("pair measurements"), where the pair measurements run along the edges of a Cairo pentagonal tiling. The resulting circuit improves on prior work by Chao et al. by using fewer pair measurements per four-body stabilizer measurement (5 instead of 6) and fewer time steps per round of stabilizer measurement (6 instead of 10). Using Monte Carlo sampling, I show that these improvements increase the threshold of the surface code when compiling into pair measurements from

$\approx 0.2\%$ to

$\approx 0.4\%$ , and also that they improve the teraquop footprint at a

$0.1\%$ physical gate error rate from

$\approx6000$ qubits to

$\approx3000$ qubits. However, I also show that Chao et al's construction will have a smaller teraquop footprint for physical gate error rates below

$\approx 0.03\%$ (due to bidirectional hook errors in my construction). I also compare to the planar honeycomb code, showing that although this work does noticeably reduce the gap between the surface code and the honeycomb code (when compiling into pair measurements), the honeycomb code is still more efficient (threshold

$\approx 0.8\%$ , teraquop footprint at

$0.1\%$ of

$\approx 1000$ ).

@article{Gidney2023pairmeasurement,
    author = {Gidney, Craig},
    title = {A {P}air {M}easurement {S}urface {C}ode on {P}entagons},
    year = {2023},
    journal = {{Quantum}},
    volume = {7},
    month = {10},
    pages = {1156},
    publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
    issn = {2521-327X},
    doi = {10.22331/q-2023-10-25-1156},
    urldate = {2022-06-26},
    link = {http://arxiv.org/abs/2206.12780},
    url = {https://doi.org/10.22331/q-2023-10-25-1156},
    keywords = {Surface Code, ZX-calculus, Applied},
    abstract = {In this paper, I present a way to compile the surface code into two-body parity measurements ("pair measurements"), where the pair measurements run along the edges of a Cairo pentagonal tiling. The resulting circuit improves on prior work by Chao et al. by using fewer pair measurements per four-body stabilizer measurement (5 instead of 6) and fewer time steps per round of stabilizer measurement (6 instead of 10). Using Monte Carlo sampling, I show that these improvements increase the threshold of the surface code when compiling into pair measurements from $\approx 0.2\%$ to $\approx 0.4\%$, and also that they improve the teraquop footprint at a $0.1\%$ physical gate error rate from $\approx6000$ qubits to $\approx3000$ qubits. However, I also show that Chao et al's construction will have a smaller teraquop footprint for physical gate error rates below $\approx 0.03\%$ (due to bidirectional hook errors in my construction). I also compare to the planar honeycomb code, showing that although this work does noticeably reduce the gap between the surface code and the honeycomb code (when compiling into pair measurements), the honeycomb code is still more efficient (threshold $\approx 0.8\%$, teraquop footprint at $0.1\%$ of $\approx 1000$).}
}

Copy to Clipboard

Complete Flow-Preserving Rewrite Rules for MBQC Patterns with Pauli Measurements
Tommy McElvanney and Miriam Backens
Show abstract ⇲ Show bibdata ⇲ Video 🎥

Proceedings 19th International Conference on Quantum Physics and Logic, Wolfson College, Oxford, UK, 27 June - 1 July 2022
Keywords: ZX-calculus, Clifford Fragment, gflow, Circuit Extraction, Local Complementation.

In the one-way model of measurement-based quantum computation (MBQC), computation proceeds via measurements on some standard resource state. So-called flow conditions ensure that the overall computation is deterministic in a suitable sense, with Pauli flow being the most general of these. Existing work on rewriting MBQC patterns while preserving the existence of flow has focused on rewrites that reduce the number of qubits. In this work, we show that introducing new

$Z$ -measured qubits, connected to any subset of the existing qubits, preserves the existence of Pauli flow. Furthermore, we give a unique canonical form for stabilizer ZX-diagrams inspired by recent work of Hu & Khesin [arXiv:2109.10210]. We prove that any MBQC-like stabilizer ZX-diagram with Pauli flow can be rewritten into this canonical form using only rules which preserve the existence of Pauli flow and that each of these rules can be reversed while also preserving the existence of Pauli flow. Hence we have complete graphical rewriting for MBQC-like stabilizer ZX-diagrams with Pauli flow.

@inproceedings{mcelvanney2023complete,
    author = {McElvanney, Tommy and Backens, Miriam},
    title = {Complete Flow-Preserving Rewrite Rules for MBQC Patterns with Pauli Measurements},
    year = {2023},
    booktitle = {Proceedings 19th International Conference on Quantum Physics and Logic, Wolfson College, Oxford, UK, 27 June - 1 July 2022},
    editor = {Gogioso, Stefano and Hoban, Matty},
    series = {Electronic Proceedings in Theoretical Computer Science},
    volume = {394},
    pages = {66-82},
    publisher = {Open Publishing Association},
    doi = {10.4204/EPTCS.394.5},
    urldate = {2022-05-04},
    link = {http://arxiv.org/abs/2205.02009},
    keywords = {ZX-calculus, Clifford Fragment, gflow, Circuit Extraction, Local Complementation},
    abstract = {In the one-way model of measurement-based quantum computation (MBQC), computation proceeds via measurements on some standard resource state. So-called flow conditions ensure that the overall computation is deterministic in a suitable sense, with Pauli flow being the most general of these. Existing work on rewriting MBQC patterns while preserving the existence of flow has focused on rewrites that reduce the number of qubits.   In this work, we show that introducing new $Z$-measured qubits, connected to any subset of the existing qubits, preserves the existence of Pauli flow. Furthermore, we give a unique canonical form for stabilizer ZX-diagrams inspired by recent work of Hu & Khesin [arXiv:2109.10210]. We prove that any MBQC-like stabilizer ZX-diagram with Pauli flow can be rewritten into this canonical form using only rules which preserve the existence of Pauli flow and that each of these rules can be reversed while also preserving the existence of Pauli flow. Hence we have complete graphical rewriting for MBQC-like stabilizer ZX-diagrams with Pauli flow.},
    video = {https://www.youtube.com/watch?v=Hpk3JKdj4vo}
}

Copy to Clipboard

Phase-free ZX diagrams are CSS codes (...or how to graphically grok the surface code)
Aleks Kissinger
Show abstract ⇲ Show bibdata ⇲ Video 🎥

arXiv:2204.14038
Keywords: ZX-calculus, Surface Code, Lattice Surgery, Error correcting codes.

In this paper, we demonstrate a direct correspondence between phase-free ZX diagrams, a graphical notation for representing and manipulating a certain class of linear maps on qubits, and Calderbank-Shor-Steane (CSS) codes, a large family of quantum error correcting codes constructed from classical codes, including for example the Steane code, surface codes, and colour codes. The stabilisers of a CSS code have an especially nice structure arising from a pair of orthogonal

$\mathbb F_2$ -linear subspaces, or in the case of maximal CSS codes, a single subspace and its orthocomplement. On the other hand, phase-free ZX diagrams can always be efficiently reduced to a normal form given by the basis elements of an

$\mathbb F_2$ -linear subspace. Here, we will show that these two ways of describing a quantum state by an

$\mathbb F_2$ -linear subspace

$S$ are in fact the same. Namely, the maximal CSS code generated by

$S$ fixes the quantum state whose ZX normal form is also given by

$S$ . This insight gives us an immediate translation from stabilisers of a maximal CSS code into a ZX diagram describing its associated state. We show that we can extend this translation to stabilisers and logical operators of any (possibly non-maximal) CSS code by "bending wires". To demonstrate the utility of this translation, we give a simple picture of the surface code and a fully graphical derivation of the action of physical lattice surgery operations on the space of logical qubits, completing the ZX presentation of lattice surgery initiated by de Beudrap and Horsman.

@article{kissinger2022phasefree,
    author = {Kissinger, Aleks},
    title = {{Phase-free ZX diagrams are CSS codes (...or how to graphically grok the surface code)}},
    year = {2022},
    journal = {arXiv preprint arXiv:2204.14038},
    urldate = {2022-04-29},
    link = {http://arxiv.org/abs/2204.14038},
    keywords = {ZX-calculus, Surface Code, Lattice Surgery, Error correcting codes},
    abstract = {In this paper, we demonstrate a direct correspondence between phase-free ZX diagrams, a graphical notation for representing and manipulating a certain class of linear maps on qubits, and Calderbank-Shor-Steane (CSS) codes, a large family of quantum error correcting codes constructed from classical codes, including for example the Steane code, surface codes, and colour codes. The stabilisers of a CSS code have an especially nice structure arising from a pair of orthogonal $\mathbb F_2$-linear subspaces, or in the case of maximal CSS codes, a single subspace and its orthocomplement. On the other hand, phase-free ZX diagrams can always be efficiently reduced to a normal form given by the basis elements of an $\mathbb F_2$-linear subspace. Here, we will show that these two ways of describing a quantum state by an $\mathbb F_2$-linear subspace $S$ are in fact the same. Namely, the maximal CSS code generated by $S$ fixes the quantum state whose ZX normal form is also given by $S$.   This insight gives us an immediate translation from stabilisers of a maximal CSS code into a ZX diagram describing its associated state. We show that we can extend this translation to stabilisers and logical operators of any (possibly non-maximal) CSS code by "bending wires". To demonstrate the utility of this translation, we give a simple picture of the surface code and a fully graphical derivation of the action of physical lattice surgery operations on the space of logical qubits, completing the ZX presentation of lattice surgery initiated by de Beudrap and Horsman.},
    video = {https://www.youtube.com/watch?v=VVhBGpCMlwA}
}

Copy to Clipboard

Qudit lattice surgery
Alexander Cowtan
Show abstract ⇲ Show bibdata ⇲ Video 🎥

arXiv:2204.13228
Keywords: ZX-calculus, Qudits, Lattice Surgery, Surface Code.

We observe that lattice surgery, a model of fault-tolerant qubit computation, generalises straightforwardly to arbitrary finite-dimensional qudits. The generalised model is based on the group algebras

$\mathbb{C}\mathbb{Z}_d$ for

$d \geq 2$ . It still requires magic state injection for universal quantum computation. We relate the model to the ZX-calculus, a diagrammatic language based on Hopf-Frobenius algebras.

@article{cowtan2022qudit,
    author = {Cowtan, Alexander},
    title = {{Qudit lattice surgery}},
    year = {2022},
    journal = {arXiv preprint arXiv:2204.13228},
    urldate = {2022-04-27},
    link = {http://arxiv.org/abs/2204.13228},
    keywords = {ZX-calculus, Qudits, Lattice Surgery, Surface Code},
    abstract = {We observe that lattice surgery, a model of fault-tolerant qubit computation, generalises straightforwardly to arbitrary finite-dimensional qudits. The generalised model is based on the group algebras $\mathbb{C}\mathbb{Z}_d$ for $d \geq 2$. It still requires magic state injection for universal quantum computation. We relate the model to the ZX-calculus, a diagrammatic language based on Hopf-Frobenius algebras.},
    video = {https://youtu.be/eNCefHNnw0A?t=3623}
}

Copy to Clipboard

Constructing All Qutrit Controlled Clifford+T gates in Clifford+T
Lia Yeh and John van de Wetering
Show abstract ⇲ Show bibdata ⇲

Reversible Computation
Keywords: Qutrits, Optimisation, Clifford+T, ZX-Supported.

For a number of useful quantum circuits, qudit constructions have been found which reduce resource requirements compared to the best known or best possible qubit construction. However, many of the necessary qutrit gates in these constructions have never been explicitly and efficiently constructed in a fault-tolerant manner. We show how to exactly and unitarily construct any qutrit multiple-controlled Clifford+T unitary using just Clifford+T gates and without using ancillae. The T-count to do so is polynomial in the number of controls k, scaling as

$O(k^{3.585})$ . With our results we can construct ancilla-free Clifford+T implementations of multiple-controlled T gates as well as all versions of the qutrit multiple-controlled Toffoli, while the analogous results for qubits are impossible. As an application of our results, we provide a procedure to implement any ternary classical reversible function on

$n$ trits as an ancilla-free qutrit unitary using

$O(3^n n^{3.585})$ T gates.

@inproceedings{Yeh2022Constructing,
    author = {Yeh, Lia and van de Wetering, John},
    title = {{Constructing All Qutrit Controlled Clifford+T gates in Clifford+T}},
    year = {2022},
    booktitle = {Reversible Computation},
    editor = {Mezzina, Claudio Antares and Podlaski, Krzysztof},
    pages = {28--50},
    publisher = {Springer International Publishing},
    address = {Cham},
    isbn = {978-3-031-09005-9},
    doi = {10.1007/978-3-031-09005-9_3},
    urldate = {2022-04-01},
    link = {https://arxiv.org/abs/2204.00552},
    keywords = {Qutrits, Optimisation, Clifford+T, ZX-Supported},
    abstract = {For a number of useful quantum circuits, qudit constructions have been found which reduce resource requirements compared to the best known or best possible qubit construction. However, many of the necessary qutrit gates in these constructions have never been explicitly and efficiently constructed in a fault-tolerant manner. We show how to exactly and unitarily construct any qutrit multiple-controlled Clifford+T unitary using just Clifford+T gates and without using ancillae. The T-count to do so is polynomial in the number of controls k, scaling as $O(k^{3.585})$. With our results we can construct ancilla-free Clifford+T implementations of multiple-controlled T gates as well as all versions of the qutrit multiple-controlled Toffoli, while the analogous results for qubits are impossible. As an application of our results, we provide a procedure to implement any ternary classical reversible function on $n$ trits as an ancilla-free qutrit unitary using $O(3^n n^{3.585})$ T gates.}
}

Copy to Clipboard

Classical Simulation of Quantum Circuits with Partial and Graphical Stabiliser Decompositions
Aleks Kissinger, John van de Wetering and Renaud Vilmart
Show abstract ⇲ Show bibdata ⇲ Video 🎥

17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)
Keywords: ZX-calculus, Classical Simulation, Applied, PyZX, Automation.

Recent developments in classical simulation of quantum circuits make use of clever decompositions of chunks of magic states into sums of efficiently simulable stabiliser states. We show here how, by considering certain non-stabiliser entangled states which have more favourable decompositions, we can speed up these simulations. This is made possible by using the ZX-calculus, which allows us to easily find instances of these entangled states in the simplified diagram representing the quantum circuit to be simulated. We additionally find a new technique of partial stabiliser decompositions that allow us to trade magic states for stabiliser terms. With this technique we require only

$2^{\alpha t}$ stabiliser terms, where

$\alpha\approx 0.396$ , to simulate a circuit with T-count

$t$ . This matches the

$\alpha$ found by Qassim et al., but whereas they only get this scaling in the asymptotic limit, ours applies for a circuit of any size. Our method builds upon a recently proposed scheme for simulation combining stabiliser decompositions and optimisation strategies implemented in the software QuiZX. With our techniques we manage to reliably simulate 50-qubit 1400 T-count hidden shift circuits in a couple of minutes on a consumer laptop.

@inproceedings{kissinger2022classical,
    author = {Kissinger, Aleks and van de Wetering, John and Vilmart, Renaud},
    title = {{Classical Simulation of Quantum Circuits with Partial and Graphical Stabiliser Decompositions}},
    year = {2022},
    booktitle = {17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)},
    editor = {Le Gall, Fran\c{c}ois and Morimae, Tomoyuki},
    series = {Leibniz International Proceedings in Informatics (LIPIcs)},
    volume = {232},
    pages = {5:1--5:13},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
    address = {Dagstuhl, Germany},
    isbn = {978-3-95977-237-2},
    issn = {1868-8969},
    doi = {10.4230/LIPIcs.TQC.2022.5},
    urldate = {2022-02-18},
    link = {http://arxiv.org/abs/2202.09202},
    keywords = {ZX-calculus, Classical Simulation, Applied, PyZX, Automation},
    abstract = {Recent developments in classical simulation of quantum circuits make use of clever decompositions of chunks of magic states into sums of efficiently simulable stabiliser states. We show here how, by considering certain non-stabiliser entangled states which have more favourable decompositions, we can speed up these simulations. This is made possible by using the ZX-calculus, which allows us to easily find instances of these entangled states in the simplified diagram representing the quantum circuit to be simulated. We additionally find a new technique of partial stabiliser decompositions that allow us to trade magic states for stabiliser terms. With this technique we require only $2^{\alpha t}$ stabiliser terms, where $\alpha\approx 0.396$, to simulate a circuit with T-count $t$. This matches the $\alpha$ found by Qassim et al., but whereas they only get this scaling in the asymptotic limit, ours applies for a circuit of any size. Our method builds upon a recently proposed scheme for simulation combining stabiliser decompositions and optimisation strategies implemented in the software QuiZX. With our techniques we manage to reliably simulate 50-qubit 1400 T-count hidden shift circuits in a couple of minutes on a consumer laptop.},
    video = {https://youtu.be/y3LIDcgrc1k?t=1394}
}

Copy to Clipboard

Circuit Extraction for ZX-Diagrams Can Be #P-Hard
Niel de Beaudrap, Aleks Kissinger and John van de Wetering
Show abstract ⇲ Show bibdata ⇲ Video 🎥

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Keywords: ZX-calculus, Circuit Extraction.

The ZX-calculus is a graphical language for reasoning about quantum computation using ZX-diagrams, a certain flexible generalisation of quantum circuits that can be used to represent linear maps from

$m$ to

$n$ qubits for any

$m,n \geq 0$ . Some applications for the ZX-calculus, such as quantum circuit optimisation and synthesis, rely on being able to efficiently translate a ZX-diagram back into a quantum circuit of comparable size. While several sufficient conditions are known for describing families of ZX-diagrams that can be efficiently transformed back into circuits, it has previously been conjectured that the general problem of circuit extraction is hard. That is, that it should not be possible to efficiently convert an arbitrary ZX-diagram describing a unitary linear map into an equivalent quantum circuit. In this paper we prove this conjecture by showing that the circuit extraction problem is #P-hard, and so is itself at least as hard as strong simulation of quantum circuits. In addition to our main hardness result, which relies specifically on the circuit representation, we give a representation-agnostic hardness result. Namely, we show that any oracle that takes as input a ZX-diagram description of a unitary and produces samples of the output of the associated quantum computation enables efficient probabilistic solutions to NP-complete problems.

@inproceedings{debeaudrap2022circuit,
    author = {de Beaudrap, Niel and Kissinger, Aleks and van de Wetering, John},
    title = {{Circuit Extraction for ZX-Diagrams Can Be #P-Hard}},
    year = {2022},
    booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
    editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
    series = {Leibniz International Proceedings in Informatics (LIPIcs)},
    volume = {229},
    pages = {119:1--119:19},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
    address = {Dagstuhl, Germany},
    isbn = {978-3-95977-235-8},
    issn = {1868-8969},
    doi = {10.4230/LIPIcs.ICALP.2022.119},
    urldate = {2022-02-18},
    link = {http://arxiv.org/abs/2202.09194},
    keywords = {ZX-calculus, Circuit Extraction},
    abstract = {The ZX-calculus is a graphical language for reasoning about quantum computation using ZX-diagrams, a certain flexible generalisation of quantum circuits that can be used to represent linear maps from $m$ to $n$ qubits for any $m,n \geq 0$. Some applications for the ZX-calculus, such as quantum circuit optimisation and synthesis, rely on being able to efficiently translate a ZX-diagram back into a quantum circuit of comparable size. While several sufficient conditions are known for describing families of ZX-diagrams that can be efficiently transformed back into circuits, it has previously been conjectured that the general problem of circuit extraction is hard. That is, that it should not be possible to efficiently convert an arbitrary ZX-diagram describing a unitary linear map into an equivalent quantum circuit. In this paper we prove this conjecture by showing that the circuit extraction problem is #P-hard, and so is itself at least as hard as strong simulation of quantum circuits. In addition to our main hardness result, which relies specifically on the circuit representation, we give a representation-agnostic hardness result. Namely, we show that any oracle that takes as input a ZX-diagram description of a unitary and produces samples of the output of the associated quantum computation enables efficient probabilistic solutions to NP-complete problems.},
    video = {https://www.youtube.com/watch?v=d-2HSa9MHKY}
}

Copy to Clipboard

Qutrit Metaplectic Gates Are a Subset of Clifford+T
Andrew N. Glaudell, Neil J. Ross, John van de Wetering and Lia Yeh
Show abstract ⇲ Show bibdata ⇲

17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)
Keywords: Qutrits, Optimisation, Clifford+T, ZX-Supported.

A popular universal gate set for quantum computing with qubits is Clifford+T, as this can be readily implemented on many fault-tolerant architectures. For qutrits, there is an equivalent T gate, that, like its qubit analogue, makes Clifford+T approximately universal, is injectable by a magic state, and supports magic state distillation. However, it was claimed that a better gate set for qutrits might be Clifford+R, where R=diag(1,1,-1) is the metaplectic gate, as certain protocols and gates could more easily be implemented using the R gate than the T gate. In this paper we show that when we have at least two qutrits, the qutrit Clifford+R unitaries form a strict subset of the Clifford+T unitaries, by finding a direct decomposition of

$R\otimes I$ as a Clifford+T circuit and proving that the T gate cannot be exactly synthesized in Clifford+R. This shows that in fact the T gate is at least as powerful as the R gate, up to a constant factor. Moreover, we additionally show that it is impossible to find a single-qutrit Clifford+T decomposition of the R gate, making our result tight.

@inproceedings{glaudell2022Qutrit,
    author = {Glaudell, Andrew N. and Ross, Neil J. and van de Wetering, John and Yeh, Lia},
    title = {{Qutrit Metaplectic Gates Are a Subset of Clifford+T}},
    year = {2022},
    booktitle = {17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)},
    editor = {Le Gall, Fran\c{c}ois and Morimae, Tomoyuki},
    series = {Leibniz International Proceedings in Informatics (LIPIcs)},
    volume = {232},
    pages = {12:1--12:15},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
    address = {Dagstuhl, Germany},
    isbn = {978-3-95977-237-2},
    issn = {1868-8969},
    doi = {10.4230/LIPIcs.TQC.2022.12},
    urldate = {2022-02-18},
    link = {https://arxiv.org/abs/2202.09235},
    keywords = {Qutrits, Optimisation, Clifford+T, ZX-Supported},
    abstract = {A popular universal gate set for quantum computing with qubits is Clifford+T, as this can be readily implemented on many fault-tolerant architectures. For qutrits, there is an equivalent T gate, that, like its qubit analogue, makes Clifford+T approximately universal, is injectable by a magic state, and supports magic state distillation. However, it was claimed that a better gate set for qutrits might be Clifford+R, where R=diag(1,1,-1) is the metaplectic gate, as certain protocols and gates could more easily be implemented using the R gate than the T gate. In this paper we show that when we have at least two qutrits, the qutrit Clifford+R unitaries form a strict subset of the Clifford+T unitaries, by finding a direct decomposition of $R\otimes I$ as a Clifford+T circuit and proving that the T gate cannot be exactly synthesized in Clifford+R. This shows that in fact the T gate is at least as powerful as the R gate, up to a constant factor. Moreover, we additionally show that it is impossible to find a single-qutrit Clifford+T decomposition of the R gate, making our result tight.}
}

Copy to Clipboard

Quantum double aspects of surface code models
Alexander Cowtan and Shahn Majid
Show abstract ⇲ Show bibdata ⇲

Journal of Mathematical Physics
Keywords: Braids, Surface Code.

We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double

$D(G)$ symmetry, where

$G$ is a finite group. We provide projection operators for its quasiparticles content as irreducible representations of

$D(G)$ and combine this with

$D(G)$ -bimodule properties of open ribbon excitation spaces

$L(s_0,s_1)$ to show how open ribbons can be used to teleport information between their endpoints

$s_0,s_1$ . We give a self-contained account that builds on earlier work but emphasises applications to quantum computing as surface code theory, including gates on

$D(S_3)$ . We show how the theory reduces to a simpler theory for toric codes in the case of

$D( \Bbb Z_n)\cong \Bbb C\Bbb Z_n^2$ , including toric ribbon operators and their braiding. In the other direction, we show how our constructions generalise to

$D(H)$ models based on a finite-dimensional Hopf algebra

$H$ , including site actions of

$D(H)$ and partial results on ribbon equivariance even when the Hopf algebra is not semisimple.

@article{cowtan2021quantum,
    author = {Cowtan, Alexander and Majid, Shahn},
    title = {{Quantum double aspects of surface code models}},
    year = {2022},
    journal = {Journal of Mathematical Physics},
    volume = {63},
    doi = {10.1063/5.0063768},
    urldate = {2021-06-25},
    link = {http://arxiv.org/abs/2107.04411},
    keywords = {Braids, Surface Code},
    abstract = {We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry, where $G$ is a finite group. We provide projection operators for its quasiparticles content as irreducible representations of $D(G)$ and combine this with $D(G)$-bimodule properties of open ribbon excitation spaces $L(s_0,s_1)$ to show how open ribbons can be used to teleport information between their endpoints $s_0,s_1$. We give a self-contained account that builds on earlier work but emphasises applications to quantum computing as surface code theory, including gates on $D(S_3)$. We show how the theory reduces to a simpler theory for toric codes in the case of $D( \Bbb Z_n)\cong \Bbb C\Bbb Z_n^2$, including toric ribbon operators and their braiding. In the other direction, we show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$, including site actions of $D(H)$ and partial results on ribbon equivariance even when the Hopf algebra is not semisimple.}
}

Copy to Clipboard

Completeness of the ZH-calculus
Miriam Backens, Aleks Kissinger, Hector Miller-Bakewell, John van de Wetering and Sal Wolffs
Show abstract ⇲ Show bibdata ⇲ Video 🎥

Compositionality
Keywords: ZH-calculus, Completeness.

There are various gate sets used for describing quantum computation. A particularly popular one consists of Clifford gates and arbitrary single-qubit phase gates. Computations in this gate set can be elegantly described by the ZX-calculus, a graphical language for a class of string diagrams describing linear maps between qubits. The ZX-calculus has proven useful in a variety of areas of quantum information, but is less suitable for reasoning about operations outside its natural gate set such as multi-linear Boolean operations like the Toffoli gate. In this paper we study the ZH-calculus, an alternative graphical language of string diagrams that does allow straightforward encoding of Toffoli gates and other more complicated Boolean logic circuits. We find a set of simple rewrite rules for this calculus and show it is complete with respect to matrices over

$\mathbb{Z}[\frac12]$ , which correspond to the approximately universal Toffoli+Hadamard gateset. Furthermore, we construct an extended version of the ZH-calculus that is complete with respect to matrices over any ring

$R$ where

$1+1$ is not a zero-divisor.

@article{backens2021completenessZH,
    author = {Backens, Miriam and Kissinger, Aleks and Miller-Bakewell, Hector and van de Wetering, John and Wolffs, Sal},
    title = {{Completeness of the ZH-calculus}},
    year = {2023},
    journal = {{Compositionality}},
    volume = {5},
    issue = {5},
    month = {7},
    publisher = {{Compositionality}},
    issn = {2631-4444},
    doi = {10.32408/compositionality-5-5},
    urldate = {2021-03-11},
    link = {https://arxiv.org/abs/2103.06610},
    keywords = {ZH-calculus, Completeness},
    abstract = {There are various gate sets used for describing quantum computation. A particularly popular one consists of Clifford gates and arbitrary single-qubit phase gates. Computations in this gate set can be elegantly described by the ZX-calculus, a graphical language for a class of string diagrams describing linear maps between qubits. The ZX-calculus has proven useful in a variety of areas of quantum information, but is less suitable for reasoning about operations outside its natural gate set such as multi-linear Boolean operations like the Toffoli gate. In this paper we study the ZH-calculus, an alternative graphical language of string diagrams that does allow straightforward encoding of Toffoli gates and other more complicated Boolean logic circuits. We find a set of simple rewrite rules for this calculus and show it is complete with respect to matrices over $\mathbb{Z}[\frac12]$, which correspond to the approximately universal Toffoli+Hadamard gateset. Furthermore, we construct an extended version of the ZH-calculus that is complete with respect to matrices over any ring $R$ where $1+1$ is not a zero-divisor.},
    video = {https://www.youtube.com/watch?v=Shu-EWNl-mE}
}

Copy to Clipboard

Quantum and braided ZX calculus
Shahn Majid
Show abstract ⇲ Show bibdata ⇲ Video 🎥

Journal of Physics A: Mathematical and Theoretical
Keywords: Braids, Frobenius algebras.

We revisit the notion of interacting Frobenius Hopf algebras for ZX-calculus in quantum computing, with focus on allowing the algebras to be noncommutative and coalgebras to be noncocommutative. We introduce the notion of *-structures in ZX-calculus at this algebraic level and construct examples based on the quantum group

$u_q(sl_2)$ at a root of unity. We provide an abstract formulation of the Hadamard gate at this level and clarify its relationship to Hopf algebra self-duality. We then solve the problem of extending the notion of interacting Hopf algebras and ZX-calculus to take place in a braided tensor category. In the ribbon case, the Hadamard gate coming from braided self-duality obeys a modular identity. We give the example of

$b_q(sl_2)$ , the self-dual braided version of

$u_q(sl_2)$ .

@article{majid2021quantum,
    author = {Majid, Shahn},
    title = {{Quantum and braided ZX calculus}},
    year = {2022},
    journal = {Journal of Physics A: Mathematical and Theoretical},
    doi = {10.1088/1751-8121/ac631f},
    urldate = {2021-03-11},
    link = {http://arxiv.org/abs/2103.07264},
    keywords = {Braids, Frobenius algebras},
    abstract = {We revisit the notion of interacting Frobenius Hopf algebras for ZX-calculus in quantum computing, with focus on allowing the algebras to be noncommutative and coalgebras to be noncocommutative. We introduce the notion of *-structures in ZX-calculus at this algebraic level and construct examples based on the quantum group $u_q(sl_2)$ at a root of unity. We provide an abstract formulation of the Hadamard gate at this level and clarify its relationship to Hopf algebra self-duality. We then solve the problem of extending the notion of interacting Hopf algebras and ZX-calculus to take place in a braided tensor category. In the ribbon case, the Hadamard gate coming from braided self-duality obeys a modular identity. We give the example of $b_q(sl_2)$, the self-dual braided version of $u_q(sl_2)$.},
    video = {https://www.youtube.com/watch?v=sXpT8Xhpwuw}
}

Copy to Clipboard

Kindergarden quantum mechanics graduates (...or how I learned to stop gluing LEGO together and love the ZX-calculus)
Bob Coecke, Dominic Horsman, Aleks Kissinger and Quanlong Wang
Show abstract ⇲ Show bibdata ⇲

Theoretical Computer Science
Keywords: ZX-calculus, NLP, MBQC.
This paper is a $spiritual child' of the 2005 lecture notes Kindergarten Quantum Mechanics, which showed how a simple, pictorial extension of Dirac notation allowed several quantum features to be easily expressed and derived, using language even a kindergartner can understand. Central to that approach was the use of pictures and pictorial transformation rules to understand and derive features of quantum theory and computation. However, this approach left many wondering$ where's the beef?' In other words, was this new approach capable of producing new results, or was it simply an aesthetically pleasing way to restate stuff we already know? The aim of this sequel paper is to say $here's the beef!', and highlight some of the major results of the approach advocated in Kindergarten Quantum Mechanics, and how they are being applied to tackle practical problems on real quantum computers. We will focus mainly on what has become the Swiss army knife of the pictorial formalism: the ZX-calculus. First we look at some of the ideas behind the ZX-calculus, comparing and contrasting it with the usual quantum circuit formalism. We then survey results from the past 2 years falling into three categories: (1) completeness of the rules of the ZX-calculus, (2) state-of-the-art quantum circuit optimisation results in commercial and open-source quantum compilers relying on ZX, and (3) the use of ZX in translating real-world stuff like natural language into quantum circuits that can be run on today's (very limited) quantum hardware. We also take the title literally, and outline an ongoing experiment aiming to show that ZX-calculus enables children to do cutting-edge quantum computing stuff. If anything, this would truly confirm that$ kindergarten quantum mechanics' wasn't just a joke.
```
@article{coecke2021kindergarden,
    author = {Coecke, Bob and Horsman, Dominic and Kissinger, Aleks and Wang, Quanlong},
    title = {{Kindergarden quantum mechanics graduates (...or how I learned to stop gluing LEGO together and love the ZX-calculus)}},
    year = {2022},
    journal = {Theoretical Computer Science},
    volume = {897},
    month = {1},
    pages = {1--22},
    doi = {10.1016/j.tcs.2021.07.024},
    urldate = {2021-02-22},
    link = {http://arxiv.org/abs/2102.10984},
    keywords = {ZX-calculus, NLP, MBQC},
    abstract = {This paper is a `spiritual child' of the 2005 lecture notes Kindergarten Quantum Mechanics, which showed how a simple, pictorial extension of Dirac notation allowed several quantum features to be easily expressed and derived, using language even a kindergartner can understand. Central to that approach was the use of pictures and pictorial transformation rules to understand and derive features of quantum theory and computation. However, this approach left many wondering `where's the beef?' In other words, was this new approach capable of producing new results, or was it simply an aesthetically pleasing way to restate stuff we already know?   The aim of this sequel paper is to say `here's the beef!', and highlight some of the major results of the approach advocated in Kindergarten Quantum Mechanics, and how they are being applied to tackle practical problems on real quantum computers. We will focus mainly on what has become the Swiss army knife of the pictorial formalism: the ZX-calculus. First we look at some of the ideas behind the ZX-calculus, comparing and contrasting it with the usual quantum circuit formalism. We then survey results from the past 2 years falling into three categories: (1) completeness of the rules of the ZX-calculus, (2) state-of-the-art quantum circuit optimisation results in commercial and open-source quantum compilers relying on ZX, and (3) the use of ZX in translating real-world stuff like natural language into quantum circuits that can be run on today's (very limited) quantum hardware.   We also take the title literally, and outline an ongoing experiment aiming to show that ZX-calculus enables children to do cutting-edge quantum computing stuff. If anything, this would truly confirm that `kindergarten quantum mechanics' wasn't just a joke.}
}
```
Copy to Clipboard

Distributive Laws, Spans and the ZX-Calculus
Cole Comfort
Show abstract ⇲ Show bibdata ⇲ Video 🎥

arXiv:2102.04386
Keywords: ZX-calculus, Category Theory, Completeness.

We modularly build increasingly larger fragments of the ZX-calculus by modularly adding new generators and relations, at each point, giving some concrete semantics in terms of some category of spans. This is performed using Lack's technique of composing props via distributive laws, as well as the technique of pushout cubes of Zanasi. We do this for the fragment of the ZX-calculus with only the black

$\pi$ -phase (and no Hadamard gate) as well as well as the fragment which additionally has the and gate as a generator (which is equivalent to the natural number H-box fragment of the ZH calculus). In the former case, we show that this is equivalent to the full subcategory of spans of (possibly empty) free, finite dimensional affine

$\mathbb F_2$ -vector spaces, where the objects are the non-empty affine vector spaces. In the latter case, we show that this is equivalent to the full subcategory of spans of finite sets where the objects are powers of the two element set. Because these fragments of the ZX-calculus have semantics in terms of full subcategories of categories of spans, they can not be presented by distributive laws over groupoids. Instead, we first construct their subcategories of partial isomorphisms via distributive laws over all isomorphims with subobjects adoined. After which, the full subcategory of spans are obtained by freely adjoining units and counits the the semi-Frobenius structures given by the diagonal and codiagonal maps.

@article{comfort2021distributive,
    author = {Comfort, Cole},
    title = {{Distributive Laws, Spans and the ZX-Calculus}},
    year = {2021},
    journal = {arXiv preprint arXiv:2102.04386},
    urldate = {2021-02-08},
    link = {http://arxiv.org/abs/2102.04386},
    keywords = {ZX-calculus, Category Theory, Completeness},
    abstract = {We modularly build increasingly larger fragments of the ZX-calculus by modularly adding new generators and relations, at each point, giving some concrete semantics in terms of some category of spans. This is performed using Lack's technique of composing props via distributive laws, as well as the technique of pushout cubes of Zanasi. We do this for the fragment of the ZX-calculus with only the black $\pi$-phase (and no Hadamard gate) as well as well as the fragment which additionally has the and gate as a generator (which is equivalent to the natural number H-box fragment of the ZH calculus). In the former case, we show that this is equivalent to the full subcategory of spans of (possibly empty) free, finite dimensional affine $\mathbb F_2$-vector spaces, where the objects are the non-empty affine vector spaces. In the latter case, we show that this is equivalent to the full subcategory of spans of finite sets where the objects are powers of the two element set. Because these fragments of the ZX-calculus have semantics in terms of full subcategories of categories of spans, they can not be presented by distributive laws over groupoids. Instead, we first construct their subcategories of partial isomorphisms via distributive laws over all isomorphims with subobjects adoined. After which, the full subcategory of spans are obtained by freely adjoining units and counits the the semi-Frobenius structures given by the diagonal and codiagonal maps.},
    video = {https://www.youtube.com/watch?v=PF2uwuoZrbs}
}

Copy to Clipboard

Tensor Network Rewriting Strategies for Satisfiability and Counting
Niel de Beaudrap, Aleks Kissinger and Konstantinos Meichanetzidis
Show abstract ⇲ Show bibdata ⇲ Video 🎥

Proceedings 17th International Conference on Quantum Physics and Logic, Paris, France, June 2 - 6, 2020
Keywords: ZH-calculus, Tensor networks, SAT, Applied.

We provide a graphical treatment of SAT and \#SAT on equal footing. Instances of \#SAT can be represented as tensor networks in a standard way. These tensor networks are interpreted by diagrams of the ZH-calculus: a system to reason about tensors over

$\mathbb{C}$ in terms of diagrams built from simple generators, in which computation may be carried out by \emph{transformations of diagrams alone}. In general, nodes of ZH diagrams take parameters over

$\mathbb{C}$ which determine the tensor coefficients; for the standard representation of \#SAT instances, the coefficients take the value

$0$ or

$1$ . Then, by choosing the coefficients of a diagram to range over

$\mathbb B$ , we represent the corresponding instance of SAT. Thus, by interpreting a diagram either over the boolean semiring or the complex numbers, we instantiate either the \emph{decision} or \emph{counting} version of the problem. We find that for classes known to be in P, such as

$2$ SAT and \#XORSAT, the existence of appropriate rewrite rules allows for efficient simplification of the diagram, producing the solution in polynomial time. In contrast, for classes known to be NP-complete, such as

$3$ SAT, or \#P-complete, such as \#

$2$ SAT, the corresponding rewrite rules introduce hyperedges to the diagrams, in numbers which are not easily bounded above by a polynomial. This diagrammatic approach unifies the diagnosis of the complexity of CSPs and \#CSPs and shows promise in aiding tensor network contraction-based algorithms.

@inproceedings{debeaudrap2020tensor,
    author = {de Beaudrap, Niel and Kissinger, Aleks and Meichanetzidis, Konstantinos},
    title = {{Tensor Network Rewriting Strategies for Satisfiability and Counting}},
    year = {2021},
    booktitle = {Proceedings 17th International Conference on Quantum Physics and Logic, Paris, France, June 2 - 6, 2020},
    editor = {Valiron, Beno\^it and Mansfield, Shane and Arrighi, Pablo and Panangaden, Prakash},
    series = {Electronic Proceedings in Theoretical Computer Science},
    volume = {340},
    pages = {46-59},
    publisher = {Open Publishing Association},
    doi = {10.4204/EPTCS.340.3},
    urldate = {2020-04-14},
    link = {http://arxiv.org/abs/2004.06455},
    keywords = {ZH-calculus, Tensor networks, SAT, Applied},
    abstract = {We provide a graphical treatment of SAT and \#SAT on equal footing. Instances of \#SAT can be represented as tensor networks in a standard way. These tensor networks are interpreted by diagrams of the ZH-calculus: a system to reason about tensors over $\mathbb{C}$ in terms of diagrams built from simple generators, in which computation may be carried out by \emph{transformations of diagrams alone}. In general, nodes of ZH diagrams take parameters over $\mathbb{C}$ which determine the tensor coefficients; for the standard representation of \#SAT instances, the coefficients take the value $0$ or $1$. Then, by choosing the coefficients of a diagram to range over $\mathbb B$, we represent the corresponding instance of SAT. Thus, by interpreting a diagram either over the boolean semiring or the complex numbers, we instantiate either the \emph{decision} or \emph{counting} version of the problem. We find that for classes known to be in P, such as $2$SAT and \#XORSAT, the existence of appropriate rewrite rules allows for efficient simplification of the diagram, producing the solution in polynomial time. In contrast, for classes known to be NP-complete, such as $3$SAT, or \#P-complete, such as \#$2$SAT, the corresponding rewrite rules introduce hyperedges to the diagrams, in numbers which are not easily bounded above by a polynomial. This diagrammatic approach unifies the diagnosis of the complexity of CSPs and \#CSPs and shows promise in aiding tensor network contraction-based algorithms.},
    video = {https://www.youtube.com/watch?v=JYnkOflmF5M}
}

Copy to Clipboard

Architecture-Aware Synthesis of Phase Polynomials for NISQ Devices
Arianne Meijer-van de Griend and Ross Duncan
Show abstract ⇲ Show bibdata ⇲ Video 🎥

Proceedings 19th International Conference on Quantum Physics and Logic, Wolfson College, Oxford, UK, 27 June - 1 July 2022
Keywords: Phase gadgets, Optimisation, Applied, ZX-Supported.

We propose a new algorithm to synthesise quantum circuits for phase polynomials, which takes into account the qubit connectivity of the quantum computer. We focus on the architectures of currently available NISQ devices. Our algorithm generates circuits with a smaller CNOT depth than the algorithms currently used in Staq and t

$|$ ket

$\rangle$ , while improving the runtime with respect the former.

@inproceedings{meijer-vandegriend2023architectureaware,
    author = {Meijer-van de Griend, Arianne and Duncan, Ross},
    title = {Architecture-Aware Synthesis of Phase Polynomials for NISQ Devices},
    year = {2023},
    booktitle = {Proceedings 19th International Conference on Quantum Physics and Logic, Wolfson College, Oxford, UK, 27 June - 1 July 2022},
    editor = {Gogioso, Stefano and Hoban, Matty},
    series = {Electronic Proceedings in Theoretical Computer Science},
    volume = {394},
    pages = {116-140},
    publisher = {Open Publishing Association},
    doi = {10.4204/EPTCS.394.8},
    urldate = {2020-04-13},
    link = {http://arxiv.org/abs/2004.06052},
    keywords = {Phase gadgets, Optimisation, Applied, ZX-Supported},
    abstract = {We propose a new algorithm to synthesise quantum circuits for phase polynomials, which takes into account the qubit connectivity of the quantum computer. We focus on the architectures of currently available NISQ devices. Our algorithm generates circuits with a smaller CNOT depth than the algorithms currently used in Staq and t$|$ket$\rangle$, while improving the runtime with respect the former.},
    video = {https://www.youtube.com/watch?v=uOAA0nbh9MI}
}

Copy to Clipboard

Hopf-Frobenius Algebras and a Simpler Drinfeld Double
Joseph Collins and Ross Duncan
Show abstract ⇲ Show bibdata ⇲

Proceedings 16th International Conference on Quantum Physics and Logic, Chapman University, Orange, CA, USA., 10-14 June 2019
Keywords: Frobenius algebras, Category Theory.

The zx-calculus and related theories are based on so-called interacting Frobenius algebras, where a pair of

$\dagger$ -special commutative Frobenius algebras jointly form a pair of Hopf algebras. In this setting we introduce a generalisation of this structure, Hopf-Frobenius algebras, starting from a single Hopf algebra which is not necessarily commutative or cocommutative. We provide the necessary and sufficient condition for a Hopf algebra to be a Hopf-Frobenius algebra, and show that every Hopf algebra in

$\textbf{FVect}_\text{k}$ is a Hopf-Frobenius algebra. Hopf-Frobenius algebras provide a notion of duality, and give us a "dual" Hopf algebra that is isomorphic to the usual dual Hopf algebra in a compact closed category. We use this isomorphism to construct a Hopf algebra isomorphic to the Drinfeld double that is defined on

$H\otimes H$ rather than

$H\otimes H^*$ .

@inproceedings{Collins2020HopfFrobenius,
    author = {Collins, Joseph and Duncan, Ross},
    title = {{Hopf-Frobenius Algebras and a Simpler Drinfeld Double}},
    year = {2020},
    booktitle = {Proceedings 16th International Conference on Quantum Physics and Logic, Chapman University, Orange, CA, USA., 10-14 June 2019},
    editor = {Coecke, Bob and Leifer, Matthew},
    series = {Electronic Proceedings in Theoretical Computer Science},
    volume = {318},
    pages = {150-180},
    publisher = {Open Publishing Association},
    doi = {10.4204/EPTCS.318.10},
    urldate = {2019-05-02},
    link = {https://arxiv.org/abs/1905.00797},
    keywords = {Frobenius algebras, Category Theory},
    abstract = {The zx-calculus and related theories are based on so-called interacting Frobenius algebras, where a pair of $\dagger$-special commutative Frobenius algebras jointly form a pair of Hopf algebras. In this setting we introduce a generalisation of this structure, Hopf-Frobenius algebras, starting from a single Hopf algebra which is not necessarily commutative or cocommutative. We provide the necessary and sufficient condition for a Hopf algebra to be a Hopf-Frobenius algebra, and show that every Hopf algebra in $\textbf{FVect}_\text{k}$ is a Hopf-Frobenius algebra. Hopf-Frobenius algebras provide a notion of duality, and give us a "dual" Hopf algebra that is isomorphic to the usual dual Hopf algebra in a compact closed category. We use this isomorphism to construct a Hopf algebra isomorphic to the Drinfeld double that is defined on $H\otimes H$ rather than $H\otimes H^*$.}
}

Copy to Clipboard

Completeness of the Phase-free ZH-calculus
John van de Wetering and Sal Wolffs
Show abstract ⇲ Show bibdata ⇲

arXiv:1904.07545
Keywords: ZH-Calculus, Completeness, Triangle.

The ZH-calculus is a graphical calculus for linear maps between qubits that allows a natural representation of the Toffoli+Hadamard gate set. The original version of the calculus, which allows every generator to be labelled by an arbitrary complex number, was shown to be complete by Backens and Kissinger. Even though the calculus is complete, this does not mean it allows one to easily reason in restricted settings such as is the case in quantum computing. In this paper we study the fragment of the ZH-calculus that is phase-free, and thus is closer aligned to physically implementable maps. We present a modified rule-set for the phase-free ZH-calculus and show that it is complete. We further discuss the minimality of this rule-set and we give an intuitive interpretation of the rules. Our completeness result follows by reducing to Vilmart's rule-set for the phase-free

$\Delta$ ZX-calculus.

@article{PhasefreeZH2019,
    author = {van de Wetering, John and Wolffs, Sal},
    title = {{Completeness of the Phase-free ZH-calculus}},
    year = {2019},
    journal = {arXiv preprint arXiv:1904.07545},
    urldate = {2019-04-16},
    link = {https://arxiv.org/abs/1904.07545},
    keywords = {ZH-Calculus, Completeness, Triangle},
    abstract = {The ZH-calculus is a graphical calculus for linear maps between qubits that allows a natural representation of the Toffoli+Hadamard gate set. The original version of the calculus, which allows every generator to be labelled by an arbitrary complex number, was shown to be complete by Backens and Kissinger. Even though the calculus is complete, this does not mean it allows one to easily reason in restricted settings such as is the case in quantum computing. In this paper we study the fragment of the ZH-calculus that is phase-free, and thus is closer aligned to physically implementable maps. We present a modified rule-set for the phase-free ZH-calculus and show that it is complete. We further discuss the minimality of this rule-set and we give an intuitive interpretation of the rules. Our completeness result follows by reducing to Vilmart's rule-set for the phase-free $\Delta$ZX-calculus. }
}

Copy to Clipboard

Efficient magic state factories with a catalyzed $|CCZångle$ to $2|T\n̊gle$ transformation
Craig Gidney and Austin G. Fowler
Show abstract ⇲ Show bibdata ⇲

Quantum
Keywords: ZX-calculus, Lattice Surgery, Surface Code, Optimisation, CCZ, Applied.

We present magic state factory constructions for producing |CCZ⟩ states and |T⟩ states. For the |CCZ⟩ factory we apply the surface code lattice surgery construction techniques described by Fowler et al. to the fault-tolerant Toffoli. The resulting factory has a footprint of

$12d\times 6d$ (where

$d$ is the code distance) and produces one |CCZ⟩ every 5.5d surface code cycles. Our |T⟩ state factory uses the |CCZ⟩ factory's output and a catalyst |T⟩ state to exactly transform one |CCZ⟩ state into two |T⟩ states. It has a footprint

$25\%$ smaller than the factory of Fowler et al. but outputs |T⟩ states twice as quickly. We show how to generalize the catalyzed transformation to arbitrary phase angles, and note that the case

$θ=22.5^a$ produces a particularly efficient circuit for producing |

$\sqrt{T}$ ⟩ states. Compared to using the

$12d\times 8d\times 6.5d$ |T⟩ factory of Fowler et al., our |CCZ⟩ factory can quintuple the speed of algorithms that are dominated by the cost of applying Toffoli gates, including Shor's algorithm and the chemistry algorithm of Babbush et al.. Assuming a physical gate error rate of

$10^{−3}$ , our CCZ factory can produce

$∼10^{10}$ states on average before an error occurs. This is sufficient for classically intractable instantiations of the chemistry algorithm, but for more demanding algorithms such as Shor's algorithm the mean number of states until failure can be increased to

$∼10^{12}$ by increasing the factory footprint

$~20\%$ .

@article{magicFactories,
    author = {Gidney, Craig and Fowler, Austin G.},
    title = {{Efficient magic state factories with a catalyzed {$|CCZ\rangle$} to {$2|T\rangle$} transformation}},
    year = {2019},
    journal = {{Quantum}},
    volume = {3},
    month = {4},
    pages = {135},
    publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
    issn = {2521-327X},
    doi = {10.22331/q-2019-04-30-135},
    urldate = {2018-12-04},
    link = {https://arxiv.org/abs/1812.01238},
    url = {https://doi.org/10.22331/q-2019-04-30-135},
    keywords = {ZX-calculus, Lattice Surgery, Surface Code, Optimisation, CCZ, Applied},
    abstract = {We present magic state factory constructions for producing |CCZ⟩ states and |T⟩ states. For the |CCZ⟩ factory we apply the surface code lattice surgery construction techniques described by Fowler et al. to the fault-tolerant Toffoli. The resulting factory has a footprint of $12d\times 6d$ (where $d$ is the code distance) and produces one |CCZ⟩ every 5.5d surface code cycles. Our |T⟩ state factory uses the |CCZ⟩ factory's output and a catalyst |T⟩ state to exactly transform one |CCZ⟩ state into two |T⟩ states. It has a footprint $25\%$ smaller than the factory of Fowler et al. but outputs |T⟩ states twice as quickly. We show how to generalize the catalyzed transformation to arbitrary phase angles, and note that the case $θ=22.5^a$ produces a particularly efficient circuit for producing |$\sqrt{T}$⟩ states. Compared to using the $12d\times 8d\times 6.5d$ |T⟩ factory of Fowler et al., our |CCZ⟩ factory can quintuple the speed of algorithms that are dominated by the cost of applying Toffoli gates, including Shor's algorithm and the chemistry algorithm of Babbush et al.. Assuming a physical gate error rate of $10^{−3}$, our CCZ factory can produce $∼10^{10}$ states on average before an error occurs. This is sufficient for classically intractable instantiations of the chemistry algorithm, but for more demanding algorithms such as Shor's algorithm the mean number of states until failure can be increased to $∼10^{12}$ by increasing the factory footprint $~20\%$.}
}

Copy to Clipboard

Completeness of the ZX-calculus
Quanlong Wang
Show abstract ⇲ Show bibdata ⇲

University of Oxford PhD Thesis
Keywords: ZX-calculus, ZW-calculus, triangle, Completeness, PhD Thesis.

The ZX-calculus is an intuitive but also mathematically strict graphical language for quantum computing, which is especially powerful for the framework of quantum circuits. Completeness of the ZX-calculus means any equality of matrices with size powers of

$n$ can be derived purely diagrammatically. In this thesis, we give the first complete axiomatisation the ZX-calculus for the overall pure qubit quantum mechanics, via a translation from the completeness result of another graphical language for quantum computing -- the ZW-calculus. This paves the way for automated pictorial quantum computing, with the aid of some software like Quantomatic. Based on this universal completeness, we directly obtain a complete axiomatisation of the ZX-calculus for the Clifford+T quantum mechanics, which is approximatively universal for quantum computing, by restricting the ring of complex numbers to its subring corresponding to the Clifford+T fragment resting on the completeness theorem of the ZW-calculus for arbitrary commutative ring. Furthermore, we prove the completeness of the ZX-calculus (with just 9 rules) for 2-qubit Clifford+T circuits by verifying the complete set of 17 circuit relations in diagrammatic rewriting. This is an important step towards efficient simplification of general n-qubit Clifford+T circuits, considering that we now have all the necessary rules for diagrammatical quantum reasoning and a very simple construction of Toffoli gate within our axiomatisation framework, which is approximately universal for quantum computation together with the Hadamard gate. In addition to completeness results within the qubit related formalism, we extend the completeness of the ZX-calculus for qubit stabilizer quantum mechanics to the qutrit stabilizer system. Finally, we show with some examples the application of the ZX-calculus to the proof of generalised supplementarity, the representation of entanglement classification and Toffoli gate, as well as equivalence-checking for the UMA gate.

@phdthesis{wang_completeness_2018,
    author = {Wang, Quanlong},
    title = {{Completeness of the ZX-calculus}},
    year = {2018},
    school = {University of Oxford},
    urldate = {2018-02-27},
    link = {http://www.cs.ox.ac.uk/people/bob.coecke/Harny.pdf},
    keywords = {ZX-calculus, ZW-calculus, triangle, Completeness, PhD Thesis},
    abstract = {The ZX-calculus is an intuitive but also mathematically strict graphical language for quantum computing, which is especially powerful for the framework of quantum circuits. Completeness of the ZX-calculus means any equality of matrices with size powers of $n$ can be derived purely diagrammatically. In this thesis, we give the first complete axiomatisation the ZX-calculus for the overall pure qubit quantum mechanics, via a translation from the completeness result of another graphical language for quantum computing -- the ZW-calculus. This paves the way for automated pictorial quantum computing, with the aid of some software like Quantomatic.

Based on this universal completeness, we directly obtain a complete axiomatisation of the ZX-calculus for the Clifford+T quantum mechanics, which is approximatively universal for quantum computing, by restricting the ring of complex numbers to its subring corresponding to the Clifford+T fragment resting on the completeness theorem of the ZW-calculus for arbitrary commutative ring.

Furthermore, we prove the completeness of the ZX-calculus (with just 9 rules) for 2-qubit Clifford+T circuits by verifying the complete set of 17 circuit relations in diagrammatic rewriting. This is an important step towards efficient simplification of general n-qubit Clifford+T circuits, considering that we now have all the necessary rules for diagrammatical quantum reasoning and a very simple construction of Toffoli gate within our axiomatisation framework, which is approximately universal for quantum computation together with the Hadamard gate.

In addition to completeness results within the qubit related formalism, we extend the completeness of the ZX-calculus for qubit stabilizer quantum mechanics to the qutrit stabilizer system.

Finally, we show with some examples the application of the ZX-calculus to the proof of generalised supplementarity, the representation of entanglement classification and Toffoli gate, as well as equivalence-checking for the UMA gate.}
}

Copy to Clipboard

Universal MBQC with generalised parity-phase interactions and Pauli measurements
Aleks Kissinger and John van de Wetering
Show abstract ⇲ Show bibdata ⇲

Quantum
Keywords: ZX-calculus, Clifford+T, MBQC, Phase Gadgets, Applied.

We introduce a new family of models for measurement-based quantum computation which are deterministic and approximately universal. The resource states which play the role of graph states are prepared via 2-qubit gates of the form

$\exp(−i\pi 2nZ\otimes Z)$ . When

$n=2$ , these are equivalent, up to local Clifford unitaries, to graph states. However, when

$n>2$ , their behaviour diverges in two important ways. First, multiple applications of the entangling gate to a single pair of qubits produces non-trivial entanglement, and hence multiple parallel edges between nodes play an important role in these generalised graph states. Second, such a state can be used to realise deterministic, approximately universal computation using only Pauli Z and X measurements and feed-forward. Even though, for

$n>2$ , the relevant resource states are no longer stabiliser states, they admit a straightforward, graphical representation using the ZX-calculus. Using this representation, we are able to provide a simple, graphical proof of universality. We furthermore show that for every

$n>2$ this family is capable of producing all Clifford gates and all diagonal gates in the

$n$ -th level of the Clifford hierarchy.

@article{kissinger2017MBQC,
    author = {Kissinger, Aleks and van de Wetering, John},
    title = {{Universal MBQC with generalised parity-phase interactions and Pauli measurements}},
    year = {2019},
    journal = {Quantum},
    volume = {3},
    issue = {134},
    doi = {10.22331/q-2019-04-26-134},
    urldate = {2017-04-21},
    link = {https://arxiv.org/abs/1704.06504},
    keywords = {ZX-calculus, Clifford+T, MBQC, Phase Gadgets, Applied},
    abstract = {We introduce a new family of models for measurement-based quantum computation which are deterministic and approximately universal. The resource states which play the role of graph states are prepared via 2-qubit gates of the form $\exp(−i\pi 2nZ\otimes Z)$. When $n=2$, these are equivalent, up to local Clifford unitaries, to graph states. However, when $n>2$, their behaviour diverges in two important ways. First, multiple applications of the entangling gate to a single pair of qubits produces non-trivial entanglement, and hence multiple parallel edges between nodes play an important role in these generalised graph states. Second, such a state can be used to realise deterministic, approximately universal computation using only Pauli Z and X measurements and feed-forward. Even though, for $n>2$, the relevant resource states are no longer stabiliser states, they admit a straightforward, graphical representation using the ZX-calculus. Using this representation, we are able to provide a simple, graphical proof of universality. We furthermore show that for every $n>2$ this family is capable of producing all Clifford gates and all diagonal gates in the $n$-th level of the Clifford hierarchy.}
}

Copy to Clipboard

Equivalence of Local Complementation and Euler Decomposition in the Qutrit ZX-calculus
Xiaoyan Gong and Quanlong Wang
Show abstract ⇲ Show bibdata ⇲

arXiv:1704.05955 [quant-ph]
Keywords: ZX-calculus, Qutrits, Local Complementation.

In this paper, we give a modified version of the qutrit ZX-calculus, by which we represent qutrit graph states as diagrams and prove that the qutrit version of local complementation property is true if and only if the qutrit Hadamard gate H has an Euler decomposition into

$4\pi/3$ -green and red rotations. This paves the way for studying the completeness of qutrit ZX-calculus for qutrit stabilizer quantum mechanics.

@article{gong_equivalence_2017,
    author = {Gong, Xiaoyan and Wang, Quanlong},
    title = {{Equivalence of Local Complementation and Euler Decomposition in the Qutrit ZX-calculus}},
    year = {2017},
    journal = {arXiv:1704.05955 [quant-ph]},
    month = {apr},
    urldate = {2017-04-19},
    link = {http://arxiv.org/abs/1704.05955},
    keywords = {ZX-calculus, Qutrits, Local Complementation},
    abstract = {In this paper, we give a modified version of the qutrit ZX-calculus, by which we represent qutrit graph states as diagrams and prove that the qutrit version of local complementation property is true if and only if the qutrit Hadamard gate H has an Euler decomposition into $4\pi/3$-green and red rotations. This paves the way for studying the completeness of qutrit ZX-calculus for qutrit stabilizer quantum mechanics.}
}

Copy to Clipboard

Graphical structures for design and verification of quantum error correction
Nicholas Chancellor, Aleks Kissinger, Stefan Zohren, Joschka Roffe and Dominic Horsman
Show abstract ⇲ Show bibdata ⇲

Quantum Science and Technology
Keywords: ZX-Calculus, Quantomatic, Error correcting codes, Applied.

@article{chancellor2016coherent,
    author = {Chancellor, Nicholas and Kissinger, Aleks and Zohren, Stefan and Roffe, Joschka and Horsman, Dominic},
    title = {Graphical structures for design and verification of quantum error correction},
    year = {2023},
    journal = {Quantum Science and Technology},
    doi = {10.1088/2058-9565/acf157},
    urldate = {2016-11-23},
    link = {https://arxiv.org/abs/1611.08012},
    url = {http://iopscience.iop.org/article/10.1088/2058-9565/acf157},
    keywords = {ZX-Calculus, Quantomatic, Error correcting codes, Applied},
    abstract = {We introduce a high-level graphical framework for designing and analysing quantum error correcting codes, centred on what we term the coherent parity check (CPC). The graphical formulation is based on the diagrammatic tools of the ZX-calculus of quantum observables. The resulting framework leads to a construction for stabilizer codes that allows us to design and verify a broad range of quantum codes based on classical ones, and that gives a means of discovering large classes of codes using both analytical and numerical methods. We focus in particular on the smaller codes that will be the first used by near-term devices. We show how CSS codes form a subset of CPC codes and, more generally, how to compute stabilizers for a CPC code. As an explicit example of this framework, we give a method for turning almost any pair of classical [n,k,3] codes into a [[2n - k + 2, k, 3]] CPC code. Further, we give a simple technique for machine search which yields thousands of potential codes, and demonstrate its operation for distance 3 and 5 codes. Finally, we use the graphical tools to demonstrate how Clifford computation can be performed within CPC codes. As our framework gives a new tool for constructing small- to medium-sized codes with relatively high code rates, it provides a new source for codes that could be suitable for emerging devices, while its ZX-calculus foundations enable natural integration of error correction with graphical compiler toolchains. It also provides a powerful framework for reasoning about all stabilizer quantum error correction codes of any size.}
}

Copy to Clipboard

Categorical Quantum Dynamics
Stefano Gogioso
Show abstract ⇲ Show bibdata ⇲

University of Oxford PhD Thesis
Keywords: Strong Complementarity, Category Theory, Qudits, Foundations, PhD Thesis.

@phdthesis{Gogioso2016phd,
    author = {Gogioso, Stefano},
    title = {{Categorical Quantum Dynamics}},
    year = {2016},
    school = {University of Oxford},
    address = {Oxford},
    language = {English},
    urldate = {2016-10-15},
    link = {https://arxiv.org/abs/1709.09772},
    keywords = {Strong Complementarity, Category Theory, Qudits, Foundations, PhD Thesis},
    abstract = {Graphical languages offer intuitive and rigorous formalisms for quantum physics. They can be used to simplify expressions, derive equalities, and do computations. Yet in order to replace conventional formalisms, rigour alone is not sufficient: the new formalisms also need to have equivalent deductive power. This requirement is captured by the property of completeness, which means that any equality that can be derived using some standard formalism can also be derived graphically. In this thesis, I consider the ZX-calculus, a graphical language for pure state qubit quantum mechanics. I show that it is complete for pure state stabilizer quantum mechanics, so any problem within this fragment of quantum theory can be fully analysed using graphical methods. This includes questions of central importance in areas such as error-correcting codes or measurement-based quantum computation. Furthermore, I show that the ZX-calculus is complete for the single-qubit Clifford+T group, which is approximately universal: any single-qubit unitary can be approximated to arbitrary accuracy using only Clifford gates and the T-gate. Lastly, I extend the use of rigorous graphical languages outside quantum theory to Spekkens' toy theory, a local hidden variable model that nevertheless exhibits some features commonly associated with quantum mechanics. I develop a graphical calculus similar to the ZX-calculus that fully describes Spekkens' toy theory, and show that it is complete. Hence, stabilizer quantum mechanics and Spekkens' toy theory can be fully analysed and compared using graphical formalisms. Intuitive graphical languages can replace conventional formalisms for the analysis of many questions in quantum computation and foundations without loss of mathematical rigour or deductive power.}
}

Copy to Clipboard

Alternative theories in quantum foundations
Andre Ranchin
Show abstract ⇲ Show bibdata ⇲

Imperial College London PhD Thesis
Keywords: ZX-calculus, Spekkens Toy Model, Qudits, Phd Thesis.

@phdthesis{Ranchin2016phd,
    author = {Ranchin, Andre},
    title = {{Alternative theories in quantum foundations}},
    year = {2016},
    school = {Imperial College London},
    urldate = {2016-08-01},
    link = {https://spiral.imperial.ac.uk/handle/10044/1/52462},
    keywords = {ZX-calculus, Spekkens Toy Model, Qudits, Phd Thesis},
    abstract = {Abstraction is an important driving force in theoretical physics. New insights often accompany the creation of physical frameworks which are both comprehensive and parsimonious. In particular, the analysis of alternative sets of theories which exhibit similar structural features as quantum theory has yielded important new results and physical understanding. An important task is to undertake a thorough analysis and classification of quantum-like theories. In this thesis, we take a step in this direction, moving towards a synthetic description of alternative theories in quantum foundations. After a brief philosophical introduction, we give a presentation of the mathematical concepts underpinning the foundations of physics, followed by an introduction to the foundations of quantum mechanics. The core of the thesis consists of three results chapters based on the articles in the author’s publications page. Chapter 4 analyses the logic of stabilizer quantum mechanics and provides a complete set of circuit equations for this sub-theory of quantum mechanics. Chapter 5 describes how quantum-like theories can be classified in a periodic table of theories. A pictorial calculus for alternative physical theories, called the ZX calculus for qudits, is then introduced and used as a tool to depict particular examples of quantum-like theories, including qudit stabilizer quantum mechanics and the SpekkensSchreiber toy theory. Chapter 6 presents an alternative set of quantum-like theories, called quantum collapse models. A novel quantum collapse model, where the rate of collapse depends on the Quantum Integrated Information of a physical system, is introduced and discussed in some detail. We then conclude with a brief summary of the main results.}
}

Copy to Clipboard

Completeness and the ZX-calculus
Miriam Backens
Show abstract ⇲ Show bibdata ⇲

University of Oxford PhD Thesis
Keywords: ZX-Calculus, Completeness, PhD Thesis.

@phdthesis{backens_completeness_2016,
    author = {Backens, Miriam},
    title = {{Completeness and the ZX-calculus}},
    year = {2016},
    school = {University of Oxford},
    address = {Oxford},
    language = {English},
    urldate = {2016-02-29},
    link = {http://arxiv.org/abs/1602.08954},
    keywords = {ZX-Calculus, Completeness, PhD Thesis},
    abstract = {Graphical languages offer intuitive and rigorous formalisms for quantum physics. They can be used to simplify expressions, derive equalities, and do computations. Yet in order to replace conventional formalisms, rigour alone is not sufficient: the new formalisms also need to have equivalent deductive power. This requirement is captured by the property of completeness, which means that any equality that can be derived using some standard formalism can also be derived graphically. In this thesis, I consider the ZX-calculus, a graphical language for pure state qubit quantum mechanics. I show that it is complete for pure state stabilizer quantum mechanics, so any problem within this fragment of quantum theory can be fully analysed using graphical methods. This includes questions of central importance in areas such as error-correcting codes or measurement-based quantum computation. Furthermore, I show that the ZX-calculus is complete for the single-qubit Clifford+T group, which is approximately universal: any single-qubit unitary can be approximated to arbitrary accuracy using only Clifford gates and the T-gate. Lastly, I extend the use of rigorous graphical languages outside quantum theory to Spekkens' toy theory, a local hidden variable model that nevertheless exhibits some features commonly associated with quantum mechanics. I develop a graphical calculus similar to the ZX-calculus that fully describes Spekkens' toy theory, and show that it is complete. Hence, stabilizer quantum mechanics and Spekkens' toy theory can be fully analysed and compared using graphical formalisms. Intuitive graphical languages can replace conventional formalisms for the analysis of many questions in quantum computation and foundations without loss of mathematical rigour or deductive power.}
}

Copy to Clipboard

A Simplified Stabilizer ZX-calculus
Miriam Backens, Simon Perdrix and Quanlong Wang
Show abstract ⇲ Show bibdata ⇲ Video 🎥

Proceedings 13th International Conference on Quantum Physics and Logic, Glasgow, Scotland, 6-10 June 2016
Keywords: ZX-Calculus, Completeness, Clifford Fragment, Scalars.

@inproceedings{BackensSimplified,
    author = {Backens, Miriam and Perdrix, Simon and Wang, Quanlong},
    title = {{A Simplified Stabilizer ZX-calculus}},
    year = {2017},
    booktitle = {Proceedings 13th International Conference on Quantum Physics and Logic, Glasgow, Scotland, 6-10 June 2016},
    editor = {Duncan, Ross and Heunen, Chris},
    series = {Electronic Proceedings in Theoretical Computer Science},
    volume = {236},
    pages = {1-20},
    publisher = {Open Publishing Association},
    doi = {10.4204/EPTCS.236.1},
    urldate = {2016-02-15},
    link = {https://arxiv.org/abs/1602.04744},
    keywords = {ZX-Calculus, Completeness, Clifford Fragment, Scalars},
    abstract = {The stabilizer ZX-calculus is a rigorous graphical language for reasoning about quantum mechanics.The language is sound and complete: a stabilizer ZX-diagram can be transformed into another one if and only if these two diagrams represent the same quantum evolution or quantum state. We show that the stabilizer ZX-calculus can be simplified, removing unnecessary equations while keeping only the essential axioms which potentially capture fundamental structures of quantum mechanics. We thus give a significantly smaller set of axioms and prove that meta-rules like 'colour symmetry' and 'upside-down symmetry', which were considered as axioms in previous versions of the language, can in fact be derived. In particular, we show that the additional symbol and one of the rules which had been recently introduced to keep track of scalars (diagrams with no inputs or outputs) are not necessary.},
    video = {https://www.youtube.com/watch?v=aAAaKKbDi9w}
}

Copy to Clipboard

Interacting Frobenius Algebras are Hopf
Ross Duncan and Kevin Dunne
Show abstract ⇲ Show bibdata ⇲

2016 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Keywords: Frobenius algebras, Category Theory, Foundational.

@inproceedings{duncan2016interacting,
    author = {Duncan, Ross and Dunne, Kevin},
    title = {{Interacting Frobenius Algebras are Hopf}},
    year = {2016},
    booktitle = {2016 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)},
    pages = {1--10},
    organization = {IEEE},
    doi = {10.1145/2933575.2934550},
    urldate = {2016-01-19},
    link = {http://arxiv.org/abs/1601.04964},
    keywords = {Frobenius algebras, Category Theory, Foundational},
    abstract = {Theories featuring the interaction between a Frobenius algebra and a Hopf algebra have recently appeared in several areas in computer science: concurrent programming, control theory, and quantum computing, among others. Bonchi, Sobocinski, and Zanasi (2014) have shown that, given a suitable distributive law, a pair of Hopf algebras forms two Frobenius algebras. Here we take the opposite approach, and show that interacting Frobenius algebras form Hopf algebras. We generalise (BSZ 2014) by including non-trivial dynamics of the underlying object---the so-called phase group---and investigate the effects of finite dimensionality of the underlying model. We recover the system of Bonchi et al as a subtheory in the prime power dimensional case, but the more general theory does not arise from a distributive law.}
}

Copy to Clipboard

Making the stabilizer ZX-calculus complete for scalars
Miriam Backens
Show abstract ⇲ Show bibdata ⇲ Video 🎥

Proceedings of the 12th International Workshop on Quantum Physics and Logic (QPL 2015)
Keywords: ZX-Calculus, Completeness, Scalars.

@inproceedings{Backens:2015aa,
    author = {Miriam Backens},
    title = {{Making the stabilizer ZX-calculus complete for scalars}},
    year = {2015},
    booktitle = {Proceedings of the 12th International Workshop on Quantum Physics and Logic (QPL 2015)},
    editor = {Chris Heunen and Peter Selinger and Jamie Vicary},
    series = {Electronic Proceedings in Theoretical Computer Science},
    volume = {195},
    pages = {17--32},
    doi = {10.4204/EPTCS.195.2},
    urldate = {2015-07-14},
    link = {https://arxiv.org/abs/1507.03854},
    keywords = {ZX-Calculus, Completeness, Scalars},
    abstract = {The ZX-calculus is a graphical language for quantum processes with built-in rewrite rules. The rewrite rules allow equalities to be derived entirely graphically, leading to the question of completeness: can any equality that is derivable using matrices also be derived graphically? The ZX-calculus is known to be complete for scalar-free pure qubit stabilizer quantum mechanics, meaning any equality between two pure stabilizer operators that is true up to a non-zero scalar factor can be derived using the graphical rewrite rules. Here, we replace those scalar-free rewrite rules with correctly scaled ones and show that, by adding one new diagram element and a new rewrite rule, the calculus can be made complete for pure qubit stabilizer quantum mechanics with scalars. This completeness property allows amplitudes and probabilities to be calculated entirely graphically. We also explicitly consider stabilizer zero diagrams, i.e. diagrams that represent a zero matrix, and show that two new rewrite rules suffice to make the calculus complete for those.},
    video = {https://www.youtube.com/watch?v=vETJbZUicKE}
}

Copy to Clipboard

Generalised Compositional Theories and Diagrammatic Reasoning
Bob Coecke, Ross Duncan, Aleks Kissinger and Quanlong Wang
Show abstract ⇲ Show bibdata ⇲

Quantum Theory: Informational Foundations and Foils
Keywords: Foundational, Foundations, Strong complementarity.

@inbook{coecke2015generalised,
    author = {Coecke, Bob and Duncan, Ross and Kissinger, Aleks and Wang, Quanlong},
    title = {{Generalised Compositional Theories and Diagrammatic Reasoning}},
    year = {2016},
    booktitle = {Quantum Theory: Informational Foundations and Foils},
    editor = {Chiribella, Giulio and Spekkens, Robert W.},
    pages = {309--366},
    publisher = {Springer Netherlands},
    address = {Dordrecht},
    isbn = {978-94-017-7303-4},
    doi = {10.1007/978-94-017-7303-4_10},
    urldate = {2015-06-11},
    link = {http://arxiv.org/abs/1506.03632},
    keywords = {Foundational, Foundations, Strong complementarity},
    abstract = {This chapter provides an introduction to the use of diagrammatic language, or perhaps more accurately, diagrammatic calculus, in quantum information and quantum foundations. We illustrate the use of diagrammatic calculus in one particular case, namely the study of complementarity and non-locality, two fundamental concepts of quantum theory whose relationship we explore in later part of this chapter.   The diagrammatic calculus that we are concerned with here is not merely an illustrative tool, but it has both (i) a conceptual physical backbone, which allows it to act as a foundation for diverse physical theories, and (ii) a genuine mathematical underpinning, permitting one to relate it to standard mathematical structures.}
}

Copy to Clipboard

Supplementarity is Necessary for Quantum Diagram Reasoning
Simon Perdrix and Quanlong Wang
Show abstract ⇲ Show bibdata ⇲

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Keywords: ZX-calculus, Completeness, Clifford+T.

The ZX-calculus is a powerful diagrammatic language for quantum mechanics and quantum information processing. We prove that its

$\pi/4$ -fragment is not complete, in other words the ZX-calculus is not complete for the so called "Clifford+T quantum mechanics". The completeness of this fragment was one of the main open problems in categorical quantum mechanics, a programme initiated by Abramsky and Coecke. The ZX-calculus was known to be incomplete for quantum mechanics. On the other hand, its

$\pi/2$ -fragment is known to be complete, i.e. the ZX-calculus is complete for the so called "stabilizer quantum mechanics". Deciding whether its

$\pi/4$ -fragment is complete is a crucial step in the development of the ZX-calculus since this fragment is approximately universal for quantum mechanics, contrary to the

$\pi/2$ -fragment. To establish our incompleteness result, we consider a fairly simple property of quantum states called supplementarity. We show that supplementarity can be derived in the ZX-calculus if and only if the angles involved in this equation are multiples of

$\pi/2$ . In particular, the impossibility to derive supplementarity for

$\pi/4$ implies the incompleteness of the ZX-calculus for Clifford+T quantum mechanics. As a consequence, we propose to add the supplementarity to the set of rules of the ZX-calculus. We also show that if a ZX-diagram involves antiphase twins, they can be merged when the ZX-calculus is augmented with the supplementarity rule. Merging antiphase twins makes diagrammatic reasoning much easier and provides a purely graphical meaning to the supplementarity rule.

@inproceedings{supplementarity,
    author = {Perdrix, Simon and Wang, Quanlong},
    title = {{Supplementarity is Necessary for Quantum Diagram Reasoning}},
    year = {2016},
    booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
    series = {Leibniz International Proceedings in Informatics (LIPIcs)},
    volume = {58},
    pages = {76:1--76:14},
    address = {Krakow, Poland},
    doi = {10.4230/LIPIcs.MFCS.2016.76},
    urldate = {2015-06-09},
    link = {https://arxiv.org/abs/1506.03055},
    keywords = {ZX-calculus, Completeness, Clifford+T},
    abstract = {The ZX-calculus is a powerful diagrammatic language for quantum mechanics and quantum information processing. We prove that its $\pi/4$-fragment is not complete, in other words the ZX-calculus is not complete for the so called "Clifford+T quantum mechanics". The completeness of this fragment was one of the main open problems in categorical quantum mechanics, a programme initiated by Abramsky and Coecke. The ZX-calculus was known to be incomplete for quantum mechanics. On the other hand, its $\pi/2$-fragment is known to be complete, i.e. the ZX-calculus is complete for the so called "stabilizer quantum mechanics". Deciding whether its $\pi/4$-fragment is complete is a crucial step in the development of the ZX-calculus since this fragment is approximately universal for quantum mechanics, contrary to the $\pi/2$-fragment. To establish our incompleteness result, we consider a fairly simple property of quantum states called supplementarity. We show that supplementarity can be derived in the ZX-calculus if and only if the angles involved in this equation are multiples of $\pi/2$. In particular, the impossibility to derive supplementarity for $\pi/4$ implies the incompleteness of the ZX-calculus for Clifford+T quantum mechanics. As a consequence, we propose to add the supplementarity to the set of rules of the ZX-calculus. We also show that if a ZX-diagram involves antiphase twins, they can be merged when the ZX-calculus is augmented with the supplementarity rule. Merging antiphase twins makes diagrammatic reasoning much easier and provides a purely graphical meaning to the supplementarity rule.}
}

Copy to Clipboard

Mermin Non-Locality in Abstract Process Theories
Stefano Gogioso and William Zeng
Show abstract ⇲ Show bibdata ⇲

Proceedings of the 12th International Workshop on Quantum Physics and Logic (QPL 2015)
Keywords: Strong Complementarity, Category Theory, Foundations.

@inproceedings{gogioso2015mermin,
    author = {Gogioso, Stefano and Zeng, William},
    title = {{Mermin Non-Locality in Abstract Process Theories}},
    year = {2015},
    booktitle = {Proceedings of the 12th International Workshop on Quantum Physics and Logic (QPL 2015)},
    editor = {Chris Heunen and Peter Selinger and Jamie Vicary},
    series = {Electronic Proceedings in Theoretical Computer Science},
    volume = {195},
    pages = {228--246},
    doi = {10.4204/EPTCS.195.17},
    urldate = {2015-06-08},
    link = {http://arxiv.org/abs/1506.02675},
    keywords = {Strong Complementarity, Category Theory, Foundations},
    abstract = {The study of non-locality is fundamental to the understanding of quantum mechanics. The past 50 years have seen a number of non-locality proofs, but its fundamental building blocks, and the exact role it plays in quantum protocols, has remained elusive. In this paper, we focus on a particular flavour of non-locality, generalising Mermin's argument on the GHZ state. Using strongly complementary observables, we provide necessary and sufficient conditions for Mermin non-locality in abstract process theories. We show that the existence of more phases than classical points (aka eigenstates) is not sufficient, and that the key to Mermin non-locality lies in the presence of certain algebraically non-trivial phases. This allows us to show that fRel, a favourite toy model for categorical quantum mechanics, is Mermin local. We show Mermin non-locality to be the key resource ensuring the device-independent security of the HBB CQ (N,N) family of Quantum Secret Sharing protocols. Finally, we challenge the unspoken assumption that the measurements involved in Mermin-type scenarios should be complementary (like the pair X,Y), opening the doors to a much wider class of potential experimental setups than currently employed. In short, we give conditions for Mermin non-locality tests on any number of systems, where each party has an arbitrary number of measurement choices, where each measurement has an arbitrary number of outcomes and further, that works in any abstract process theory.}
}

Copy to Clipboard

Quantomatic: A proof assistant for diagrammatic reasoning
Aleks Kissinger and Vladimir Zamdzhiev
Show abstract ⇲ Show bibdata ⇲

International Conference on Automated Deduction
Keywords: Quantomatic, Automation.

@inproceedings{kissinger2015quantomatic,
    author = {Kissinger, Aleks and Zamdzhiev, Vladimir},
    title = {{Quantomatic: A proof assistant for diagrammatic reasoning}},
    year = {2015},
    booktitle = {International Conference on Automated Deduction},
    pages = {326--336},
    organization = {Springer},
    doi = {10.1007/978-3-319-21401-6\_22},
    urldate = {2015-03-03},
    link = {https://arxiv.org/abs/1503.01034},
    keywords = {Quantomatic, Automation},
    abstract = {Monoidal algebraic structures consist of operations that can have multiple outputs as well as multiple inputs, which have applications in many areas including categorical algebra, programming language semantics, representation theory, algebraic quantum information, and quantum groups. String diagrams provide a convenient graphical syntax for reasoning formally about such structures, while avoiding many of the technical challenges of a term-based approach. Quantomatic is a tool that supports the (semi-)automatic construction of equational proofs using string diagrams. We briefly outline the theoretical basis of Quantomatic's rewriting engine, then give an overview of the core features and architecture and give a simple example project that computes normal forms for commutative bialgebras.}
}

Copy to Clipboard

A diagrammatic axiomatisation for qubit entanglement
Amar Hadzihasanovic
Show abstract ⇲ Show bibdata ⇲ Video 🎥

2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science
Keywords: ZW-calculus, Completeness.

@inproceedings{hadzihasanovic2015diagrammatic,
    author = {Hadzihasanovic, Amar},
    title = {A diagrammatic axiomatisation for qubit entanglement},
    year = {2015},
    booktitle = {2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science},
    pages = {573--584},
    organization = {IEEE},
    doi = {10.1109/LICS.2015.59},
    urldate = {2015-01-28},
    link = {https://arxiv.org/abs/1501.07082},
    keywords = {ZW-calculus, Completeness},
    abstract = {Diagrammatic techniques for reasoning about monoidal categories provide an intuitive understanding of the symmetries and connections of interacting computational processes. In the context of categorical quantum mechanics, Coecke and Kissinger suggested that two 3-qubit states, GHZ and W, may be used as the building blocks of a new graphical calculus, aimed at a diagrammatic classification of multipartite qubit entanglement that would highlight the communicational properties of quantum states, and their potential uses in cryptographic schemes. 
In this paper, we present a full graphical axiomatisation of the relations between GHZ and W: the ZW calculus. This refines a version of the preexisting ZX calculus, while keeping its most desirable characteristics: undirectedness, a large degree of symmetry, and an algebraic underpinning. We prove that the ZW calculus is complete for the category of free abelian groups on a power of two generators - "qubits with integer coefficients" - and provide an explicit normalisation procedure.},
    video = {https://www.youtube.com/watch?v=5CfAb-EuML8}
}

Copy to Clipboard

The ZX-calculus is complete for the single-qubit Clifford+T group
Miriam Backens
Show abstract ⇲ Show bibdata ⇲ Video 🎥

Proceedings of the 11th workshop on Quantum Physics and Logic, Kyoto, Japan, 4-6th June 2014
Keywords: ZX-Calculus, Clifford+T, Completeness.

@inproceedings{backens2014zx,
    author = {Backens, Miriam},
    title = {The {ZX-calculus} is complete for the single-qubit {Clifford+T} group},
    year = {2014},
    booktitle = {Proceedings of the 11th workshop on Quantum Physics and Logic, Kyoto, Japan, 4-6th June 2014},
    editor = {Coecke, Bob and Hasuo, Ichiro and Panangaden, Prakash},
    series = {Electronic Proceedings in Theoretical Computer Science},
    volume = {172},
    pages = {293-303},
    publisher = {Open Publishing Association},
    doi = {10.4204/EPTCS.172.21},
    urldate = {2014-12-30},
    link = {https://arxiv.org/abs/1412.8553},
    keywords = {ZX-Calculus, Clifford+T, Completeness},
    abstract = {The ZX-calculus is a graphical calculus for reasoning about pure state qubit quantum mechanics. It is complete for pure qubit stabilizer quantum mechanics, meaning any equality involving only stabilizer operations that can be derived using matrices can also be derived pictorially. Stabilizer operations include the unitary Clifford group, as well as preparation of qubits in the state |0>, and measurements in the computational basis. For general pure state qubit quantum mechanics, the ZX-calculus is incomplete: there exist equalities involving non-stabilizer unitary operations on single qubits which cannot be derived from the current rule set for the ZX-calculus. Here, we show that the ZX-calculus for single qubits remains complete upon adding the operator T to the single-qubit stabilizer operations. This is particularly interesting as the resulting single-qubit Clifford+T group is approximately universal, i.e. any unitary single-qubit operator can be approximated to arbitrary accuracy using only Clifford operators and T.},
    video = {https://www.youtube.com/watch?v=6dEy6-mnweA}
}

Copy to Clipboard

A Complete Graphical Calculus for Spekkens’ Toy Bit Theory
Miriam Backens and Ali Nabi Duman
Show abstract ⇲ Show bibdata ⇲

Foundations of Physics
Keywords: ZX-Calculus, Spekkens Toy Model, Completeness.

While quantum theory cannot be described by a local hidden variable model, it is nevertheless possible to construct such models that exhibit features commonly associated with quantum mechanics. These models are also used to explore the question of

$\psi$ -ontic versus

$\psi$ -epistemic theories for quantum mechanics. Spekkens’ toy theory is one such model. It arises from classical probabilistic mechanics via a limit on the knowledge an observer may have about the state of a system. The toy theory for the simplest possible underlying system closely resembles stabilizer quantum mechanics, a fragment of quantum theory which is efficiently classically simulable but also non-local. Further analysis of the similarities and differences between those two theories can thus yield new insights into what distinguishes quantum theory from classical theories, and

$\psi$ -ontic from

$\psi$ -epistemic theories. In this paper, we develop a graphical language for Spekkens’ toy theory. Graphical languages offer intuitive and rigorous formalisms for the analysis of quantum mechanics and similar theories. To compare quantum mechanics and a toy model, it is useful to have similar formalisms for both. We show that our language fully describes Spekkens’ toy theory and in particular, that it is complete: meaning any equality that can be derived using other formalisms can also be derived entirely graphically. Our language is inspired by a similar graphical language for quantum mechanics called the ZX-calculus. Thus Spekkens’ toy bit theory and stabilizer quantum mechanics can be analysed and compared using analogous graphical formalisms.

@article{backens_complete_2015,
    author = {Backens, Miriam and Duman, Ali Nabi},
    title = {{A Complete Graphical Calculus for Spekkens’ Toy Bit Theory}},
    year = {2015},
    journal = {Foundations of Physics},
    volume = {46},
    number = {1},
    month = {oct},
    pages = {70--103},
    issn = {0015-9018, 1572-9516},
    language = {en},
    doi = {10.1007/s10701-015-9957-7},
    urldate = {2014-11-06},
    link = {https://arxiv.org/abs/1411.1618},
    url = {http://link.springer.com/article/10.1007/s10701-015-9957-7},
    keywords = {ZX-Calculus, Spekkens Toy Model, Completeness},
    abstract = {While quantum theory cannot be described by a local hidden variable model, it is nevertheless possible to construct such models that exhibit features commonly associated with quantum mechanics. These models are also used to explore the question of $\psi$-ontic versus $\psi$-epistemic theories for quantum mechanics. Spekkens’ toy theory is one such model. It arises from classical probabilistic mechanics via a limit on the knowledge an observer may have about the state of a system. The toy theory for the simplest possible underlying system closely resembles stabilizer quantum mechanics, a fragment of quantum theory which is efficiently classically simulable but also non-local. Further analysis of the similarities and differences between those two theories can thus yield new insights into what distinguishes quantum theory from classical theories, and $\psi$-ontic from $\psi$-epistemic theories. In this paper, we develop a graphical language for Spekkens’ toy theory. Graphical languages offer intuitive and rigorous formalisms for the analysis of quantum mechanics and similar theories. To compare quantum mechanics and a toy model, it is useful to have similar formalisms for both. We show that our language fully describes Spekkens’ toy theory and in particular, that it is complete: meaning any equality that can be derived using other formalisms can also be derived entirely graphically. Our language is inspired by a similar graphical language for quantum mechanics called the ZX-calculus. Thus Spekkens’ toy bit theory and stabilizer quantum mechanics can be analysed and compared using analogous graphical formalisms.}
}

Copy to Clipboard

Qutrit Dichromatic Calculus and Its Universality
Quanlong Wang and Xiaoning Bian
Show abstract ⇲ Show bibdata ⇲

Proceedings of the 11th workshop on Quantum Physics and Logic, Kyoto, Japan, 4-6th June 2014
Keywords: ZX-calculus, Qutrits, Qudits.

We introduce a dichromatic calculus (RG) for qutrit systems. We show that the decomposition of the qutrit Hadamard gate is non-unique and not derivable from the dichromatic calculus. As an application of the dichromatic calculus, we depict a quantum algorithm with a single qutrit. Since it is not easy to decompose an arbitrary

$d\times d$ unitary matrix into Z and X phase gates when

$d > 2$ , the proof of the universality of qudit ZX calculus for quantum mechanics is far from trivial. We construct counterexample to Ranchin’s universality proof, and give another proof by Lie theory that the qudit ZX calculus contains all single qudit unitary transformations, which implies that qudit ZX calculus, with qutrit dichromatic calculus as a special case, is universal for quantum mechanics.

@inproceedings{wang2014qutrit,
    author = {Wang, Quanlong and Bian, Xiaoning},
    title = {{Qutrit Dichromatic Calculus and Its Universality}},
    year = {2014},
    booktitle = {Proceedings of the 11th workshop on Quantum Physics and Logic,     Kyoto, Japan, 4-6th June 2014},
    editor = {Coecke, Bob and Hasuo, Ichiro and Panangaden, Prakash},
    series = {Electronic Proceedings in Theoretical Computer Science},
    volume = {172},
    pages = {92-101},
    publisher = {Open Publishing Association},
    doi = {10.4204/EPTCS.172.7},
    urldate = {2014-06-08},
    link = {https://arxiv.org/abs/1406.3056},
    keywords = {ZX-calculus, Qutrits, Qudits},
    abstract = {We introduce a dichromatic calculus (RG) for qutrit systems. We show that the decomposition of the qutrit Hadamard gate is non-unique and not derivable from the dichromatic calculus. As an application of the dichromatic calculus, we depict a quantum algorithm with a single qutrit. Since it is not easy to decompose an arbitrary $d\times d$ unitary matrix into Z and X phase gates when $d > 2$, the
proof of the universality of qudit ZX calculus for quantum mechanics is far from trivial. We construct counterexample to Ranchin’s universality proof, and give another proof by Lie theory that the qudit ZX calculus contains all single qudit unitary transformations, which implies that qudit ZX calculus, with qutrit dichromatic calculus as a special case, is universal for quantum mechanics.}
}

Copy to Clipboard

Depicting qudit quantum mechanics and mutually unbiased qudit theories
André Ranchin
Show abstract ⇲ Show bibdata ⇲

Proceedings of the 11th workshop on Quantum Physics and Logic, Kyoto, Japan, 4-6th June 2014
Keywords: ZX-calculus, Qudits, Spekkens Toy Model.

@inproceedings{1404.1288,
    author = {Andr{\'e} Ranchin},
    title = {Depicting qudit quantum mechanics and mutually unbiased qudit theories},
    year = {2014},
    booktitle = {Proceedings of the 11th workshop on Quantum Physics and Logic, Kyoto, Japan, 4-6th June 2014},
    editor = {Coecke, Bob and Hasuo, Ichiro and Panangaden, Prakash},
    series = {Electronic Proceedings in Theoretical Computer Science},
    volume = {172},
    pages = {68-91},
    publisher = {Open Publishing Association},
    doi = {10.4204/EPTCS.172.6},
    urldate = {2014-04-04},
    link = {https://arxiv.org/abs/1404.1288},
    keywords = {ZX-calculus, Qudits, Spekkens Toy Model},
    abstract = {We generalize the ZX calculus to quantum systems of dimension higher than two. The resulting calculus is sound and universal for quantum mechanics. We define the notion of a mutually unbiased qudit theory and study two particular instances of these theories in detail: qudit stabilizer quantum mechanics and Spekkens-Schreiber toy theory for dits. The calculus allows us to analyze the structure of qudit stabilizer quantum mechanics and provides a geometrical picture of qudit stabilizer theory using D-toruses, which generalizes the Bloch sphere picture for qubit stabilizer quantum mechanics.
We also use our framework to describe generalizations of Spekkens toy theory to higher dimensional systems. This gives a novel proof that qudit stabilizer quantum mechanics and Spekkens-Schreiber toy theory for dits are operationally equivalent in three dimensions. The qudit pictorial calculus is a useful tool to study quantum foundations, understand the relationship between qubit and qudit quantum mechanics, and provide a novel, high level description of quantum information protocols.}
}

Copy to Clipboard

Higher-order semantics for quantum programming languages with classical control
Philip Atzemoglou
Show abstract ⇲ Show bibdata ⇲

University of Oxford PhD Thesis
Keywords: ZX-Calculus, Category theory, PhD Thesis.

@phdthesis{Atzemoglou2013phd,
    author = {Atzemoglou, Philip},
    title = {{Higher-order semantics for quantum programming languages with classical control}},
    year = {2013},
    school = {University of Oxford},
    address = {Oxford},
    language = {English},
    urldate = {2013-11-26},
    link = {https://arxiv.org/abs/1311.6563},
    keywords = {ZX-Calculus, Category theory, PhD Thesis},
    abstract = {This thesis studies the categorical formalisation of quantum computing, through the prism of type theory, in a three-tier process. The first stage of our investigation involves the creation of the dagger lambda calculus, a lambda calculus for dagger compact categories. Our second contribution lifts the expressive power of the dagger lambda calculus, to that of a quantum programming language, by adding classical control in the form of complementary classical structures and dualisers. Finally, our third contribution demonstrates how our lambda calculus can be applied to various well known problems in quantum computation.}
}

Copy to Clipboard

Complete set of circuit equations for stabilizer quantum mechanics
André Ranchin and Bob Coecke
Show abstract ⇲ Show bibdata ⇲

Physical Review A
Keywords: ZX-calculus, Completeness, Clifford Fragment.

@article{ranchin_complete_2014,
    author = {Ranchin, André and Coecke, Bob},
    title = {Complete set of circuit equations for stabilizer quantum mechanics},
    year = {2014},
    journal = {Physical Review A},
    volume = {90},
    number = {1},
    month = {jul},
    doi = {10.1103/PhysRevA.90.012109},
    urldate = {2013-10-29},
    link = {https://arxiv.org/abs/1310.7932},
    url = {http://link.aps.org/doi/10.1103/PhysRevA.90.012109},
    keywords = {ZX-calculus, Completeness, Clifford Fragment},
    abstract = {We find a sufficient set of equations between quantum circuits from which we can derive any other equation between stabilizer quantum circuits. To establish this result, we rely upon existing work on the completeness of the graphical ZX language for quantum processes, a two-coloured logical calculus for multi-qubit systems. The complexity of the circuit equations, as opposed to the very intuitive reading of the much smaller number of ZX equations, advocates the latter for performing computations with quantum circuits.}
}

Copy to Clipboard

The ZX calculus is incomplete for non-stabilizer quantum mechanics
Christian Schröder de Witt
Show abstract ⇲ Show bibdata ⇲

University of Oxford Masters Thesis
Keywords: ZX-Calculus, Completeness, Master Thesis.

@mastersthesis{deWitt2013Master,
    author = {de Witt, Christian Schr{\"o}der},
    title = {{The ZX calculus is incomplete for non-stabilizer quantum mechanics}},
    year = {2013},
    school = {University of Oxford},
    urldate = {2013-09-06},
    link = {http://www.cs.ox.ac.uk/people/bob.coecke/Christian_thesis.pdf},
    keywords = {ZX-Calculus, Completeness, Master Thesis},
    abstract = {We prove that the ZX-calculus is incomplete for non-stabilizer quantum mechanics.   We suggest additional rules to be integrated with the graphical calculus and possible further incompleteness sources.  We express a simple quantum error correction circuit in Selinger's CPM construction in an attempt to obtain a graphical construction framework for general stabilizer error codes.  We also provide a simple framework for the integration of gate approximation errors into the ZX-calculus, including a simple way of propagating upper approximation bounds through quantum circuits.}
}

Copy to Clipboard

The ZX-calculus is complete for stabilizer quantum mechanics
Miriam Backens
Show abstract ⇲ Show bibdata ⇲

New Journal of Physics
Keywords: ZX-Calculus, Completeness, Clifford Fragment, Normal-form.

@article{Backens1,
    author = {Backens, Miriam},
    title = {{The ZX-calculus is complete for stabilizer quantum mechanics}},
    year = {2014},
    journal = {New Journal of Physics},
    volume = {16},
    number = {9},
    pages = {093021},
    publisher = {IOP Publishing},
    doi = {10.1088/1367-2630/16/9/093021},
    urldate = {2013-07-26},
    link = {https://arxiv.org/abs/1307.7025},
    keywords = {ZX-Calculus, Completeness, Clifford Fragment, Normal-form},
    abstract = {The ZX-calculus is a graphical calculus for reasoning about quantum systems and processes. It is known to be universal for pure state qubit quantum mechanics, meaning any pure state, unitary operation and post-selected pure projective measurement can be expressed in the ZX-calculus. The calculus is also sound, i.e. any equality that can be derived graphically can also be derived using matrix mechanics. Here, we show that the ZX-calculus is complete for pure qubit stabilizer quantum mechanics, meaning any equality that can be derived using matrices can also be derived pictorially. The proof relies on bringing diagrams into a normal form based on graph states and local Clifford operations.}
}

Copy to Clipboard

Pivoting makes the ZX-calculus complete for real stabilizers
Ross Duncan and Simon Perdrix
Show abstract ⇲ Show bibdata ⇲

Proceedings of the 10th International Workshop on Quantum Physics and Logic (QPL)
Keywords: ZX-Calculus, Clifford Fragment, Real Fragment, Completeness, Local Complementation.

@inproceedings{DP3,
    author = {Duncan, Ross and Perdrix, Simon},
    title = {{Pivoting makes the ZX-calculus complete for real stabilizers}},
    year = {2014},
    booktitle = {Proceedings of the 10th International Workshop on Quantum Physics and Logic (QPL)},
    series = {Electronic Proceedings in Theoretical Computer Science},
    volume = {171},
    pages = {50-62},
    publisher = {Open Publishing Association},
    doi = {10.4204/EPTCS.171.5},
    urldate = {2013-07-26},
    link = {https://arxiv.org/abs/1307.7048},
    keywords = {ZX-Calculus, Clifford Fragment, Real Fragment, Completeness, Local Complementation},
    abstract = {We show that pivoting property of graph states cannot be derived from the axioms of the ZX-calculus, and that pivoting does not imply local complementation of graph states. Therefore the ZX-calculus augmented with pivoting is strictly weaker than the calculus augmented with the Euler decomposition of the Hadamard gate. We derive an angle-free version of the ZX-calculus and show that it is complete for real stabilizer quantum mechanics.}
}

Copy to Clipboard

Superdense Coding with GHZ and Quantum Key Distribution with W in the ZX-calculus
Anne Hillebrand
Show abstract ⇲ Show bibdata ⇲ Video 🎥

Electronic Proceedings in Theoretical Computer Science
Keywords: ZX-calculus, Protocols.

@article{hillebrand_superdense_2012,
    author = {Hillebrand, Anne},
    title = {{Superdense Coding with GHZ and Quantum Key Distribution with W in the ZX-calculus}},
    year = {2012},
    journal = {Electronic Proceedings in Theoretical Computer Science},
    volume = {95},
    month = {oct},
    pages = {103--121},
    issn = {2075-2180},
    doi = {10.4204/EPTCS.95.10},
    urldate = {2012-10-02},
    link = {http://arxiv.org/abs/1210.0650},
    keywords = {ZX-calculus, Protocols},
    abstract = {Quantum entanglement is a key resource in many quantum protocols, such as quantum teleportation and quantum cryptography. Yet entanglement makes protocols presented in Dirac notation difficult to verify. This is why Coecke and Duncan have introduced a diagrammatic language for quantum protocols, called the ZX-calculus. This diagrammatic notation is both intuitive and formally rigorous. It is a simple, graphical, high level language that emphasises the composition of systems and naturally captures the essentials of quantum mechanics. In the author's MSc thesis it has been shown for over 25 quantum protocols that the ZX-calculus provides a relatively easy and more intuitive presentation. Moreover, the author embarked on the task to apply categorical quantum mechanics on quantum security; earlier works did not touch anything but Bennett and Brassard's quantum key distribution protocol, BB84. Superdense coding with the Greenberger-Horne-Zeilinger state and quantum key distribution with the W-state are presented in the ZX-calculus in this paper.},
    video = {https://www.youtube.com/watch?v=P5u-Qp_GQJY}
}

Copy to Clipboard

Topological Structure of Quantum Algorithms
Jamie Vicary
Show abstract ⇲ Show bibdata ⇲

Proceedings of the 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science
Keywords: Protocols, Category Theory.

@inproceedings{vicary2012topology,
    author = {Vicary, Jamie},
    title = {Topological Structure of Quantum Algorithms},
    year = {2013},
    booktitle = {Proceedings of the 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science},
    series = {LICS '13},
    pages = {93–102},
    numpages = {10},
    publisher = {IEEE Computer Society},
    address = {USA},
    isbn = {9780769550206},
    doi = {10.1109/LICS.2013.14},
    urldate = {2012-09-18},
    link = {http://arxiv.org/abs/1209.3917},
    keywords = {Protocols, Category Theory},
    abstract = {We use a categorical topological semantics to examine the Deutsch-Jozsa, hidden subgroup and single-shot Grover algorithms. This reveals important structures hidden by conventional algebraic presentations, and allows novel proofs of correctness via local topological operations, giving for the first time a satisfying high-level explanation for why these procedures work. We also investigate generalizations of these algorithms, providing improved analyses of those already in the literature, and a new generalization of the single-shot Grover algorithm.}
}

Copy to Clipboard

A graphical approach to measurement-based quantum computing
Ross Duncan
Show abstract ⇲ Show bibdata ⇲ Video 🎥

Quantum Physics and Linguistics: A Compositional, Diagrammatic Discourse
Keywords: ZX-calculus, MBQC, Applied.

@incollection{DuncanMBQC,
    author = {Duncan, Ross},
    title = {A graphical approach to measurement-based quantum computing},
    year = {2013},
    booktitle = {Quantum Physics and Linguistics: A Compositional, Diagrammatic Discourse},
    editor = {Chris Heunen, Mehrnoosh Sadrzadeh, and Edward Grefenstette},
    isbn = {9780199646296},
    doi = {10.1093/acprof:oso/9780199646296.001.0001},
    urldate = {2012-03-28},
    link = {https://arxiv.org/abs/1203.6242},
    keywords = {ZX-calculus, MBQC, Applied},
    abstract = {Quantum computations are easily represented in the graphical notation known as the ZX-calculus, a.k.a. the red-green calculus. We demonstrate its use in reasoning about measurement-based quantum computing, where the graphical syntax directly captures the structure of the entangled states used to represent computations, and show that the notion of information flow within the entangled states gives rise to rewriting strategies for proving the correctness of quantum programs.},
    video = {https://www.youtube.com/watch?v=RSU5jlpQJSo}
}

Copy to Clipboard

Strong complementarity and non-locality in categorical quantum mechanics
Bob Coecke, Ross Duncan, Aleks Kissinger and Quanlong Wang
Show abstract ⇲ Show bibdata ⇲ Video 🎥

Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science (LICS)
Keywords: Foundational, Strong Complementarity, Category Theory.

@inproceedings{CDKZ,
    author = {Coecke, Bob and Duncan, Ross and Kissinger, Aleks and Wang, Quanlong},
    title = {Strong complementarity and non-locality in categorical quantum mechanics},
    year = {2012},
    booktitle = {Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science (LICS)},
    doi = {10.1109/LICS.2012.35},
    urldate = {2012-03-22},
    link = {https://arxiv.org/abs/1203.4988},
    keywords = {Foundational, Strong Complementarity, Category Theory},
    abstract = {Categorical quantum mechanics studies quantum theory in the framework of dagger-compact closed categories. 
Using this framework, we establish a tight relationship between two key quantum theoretical notions: non-locality and complementarity. In particular, we establish a direct connection between Mermin-type non-locality scenarios, which we generalise to an arbitrary number of parties, using systems of arbitrary dimension, and performing arbitrary measurements, and a new stronger notion of complementarity which we introduce here. 
Our derivation of the fact that strong complementarity is a necessary condition for a Mermin scenario provides a crisp operational interpretation for strong complementarity. We also provide a complete classification of strongly complementary observables for quantum theory, something which has not yet been achieved for ordinary complementarity. 
Since our main results are expressed in the (diagrammatic) language of dagger-compact categories, they can be applied outside of quantum theory, in any setting which supports the purely algebraic notion of strongly complementary observables. We have therefore introduced a method for discussing non-locality in a wide variety of models in addition to quantum theory. 
The diagrammatic calculus substantially simplifies (and sometimes even trivialises) many of the derivations, and provides new insights. In particular, the diagrammatic computation of correlations clearly shows how local measurements interact to yield a global overall effect. In other words, we depict non-locality.},
    video = {https://www.youtube.com/watch?v=rHhdaQ3YtsI}
}

Copy to Clipboard

Pictures of Processes: Automated Graph Rewriting for Monoidal Categories and Applications to Quantum Computing
Aleks Kissinger
Show abstract ⇲ Show bibdata ⇲

University of Oxford PhD Thesis
Keywords: !-boxes, Automation, Quantomatic, ZX-calculus, Phd Thesis.

@phdthesis{kissinger2012pictures,
    author = {Kissinger, Aleks},
    title = {{Pictures of Processes: Automated Graph Rewriting for Monoidal Categories and Applications to Quantum Computing}},
    year = {2012},
    school = {University of Oxford},
    urldate = {2012-03-01},
    link = {http://arxiv.org/abs/1203.0202},
    keywords = {!-boxes, Automation, Quantomatic, ZX-calculus, Phd Thesis},
    abstract = {This work is about diagrammatic languages, how they can be represented, and what they in turn can be used to represent. More specifically, it focuses on representations and applications of string diagrams. String diagrams are used to represent a collection of processes, depicted as "boxes" with multiple (typed) inputs and outputs, depicted as "wires". If we allow plugging input and output wires together, we can intuitively represent complex compositions of processes, formalised as morphisms in a monoidal category.   [...] The first major contribution of this dissertation is the introduction of a discretised version of a string diagram called a string graph. String graphs form a partial adhesive category, so they can be manipulated using double-pushout graph rewriting. Furthermore, we show how string graphs modulo a rewrite system can be used to construct free symmetric traced and compact closed categories on a monoidal signature.   
The second contribution is in the application of graphical languages to quantum information theory. We use a mixture of diagrammatic and algebraic techniques to prove a new classification result for strongly complementary observables. [...] We also introduce a graphical language for multipartite entanglement and illustrate a simple graphical axiom that distinguishes the two maximally-entangled tripartite qubit states: GHZ and W. [...]   
The third contribution is a description of two software tools developed in part by the author to implement much of the theoretical content described here. The first tool is Quantomatic, a desktop application for building string graphs and graphical theories, as well as performing automated graph rewriting visually. The second is QuantoCoSy, which performs fully automated, model-driven theory creation using a procedure called conjecture synthesis.}
}

Copy to Clipboard

Trichromatic Open Digraphs for Understanding Qubits
Alex Lang and Bob Coecke
Show abstract ⇲ Show bibdata ⇲ Video 🎥

Proceedings 8th International Workshop on Quantum Physics and Logic, Nijmegen, Netherlands, October 27-29, 2011
Keywords: ZX-calculus.

@inproceedings{EPTCS95.14,
    author = {Lang, Alex and Coecke, Bob},
    title = {{Trichromatic Open Digraphs for Understanding Qubits}},
    year = {2012},
    booktitle = {Proceedings 8th International Workshop on Quantum Physics and Logic, Nijmegen, Netherlands, October 27-29, 2011},
    editor = {Jacobs, Bart and Selinger, Peter and Spitters, Bas},
    series = {Electronic Proceedings in Theoretical Computer Science},
    volume = {95},
    pages = {193-209},
    publisher = {Open Publishing Association},
    doi = {10.4204/EPTCS.95.14},
    urldate = {2011-10-12},
    link = {https://arxiv.org/abs/1110.2613},
    keywords = {ZX-calculus},
    abstract = {We introduce a trichromatic graphical calculus for quantum computing. The generators represent three complementary observables that are treated on equal footing, hence reflecting the symmetries of the Bloch sphere. We derive the Euler angle decomposition of the Hadamard gate within it as well as the so-called supplementary relationships, which are valid equations for qubits that were not derivable within Z/X-calculus of Coecke and Duncan. More specifically, we have: dichromatic Z/X-calculus + Euler angle decomposition of the Hadamard gate = trichromatic calculus.},
    video = {https://www.youtube.com/watch?v=7VV-mm3v_dM}
}

Copy to Clipboard

Implementing and Automating complex arithmetic in quantomatic
Benjamin Frot
Show abstract ⇲ Show bibdata ⇲

University of Oxford Masters Thesis
Keywords: ZW-Calculus, Quantomatic, Automation, Master Thesis.

@mastersthesis{Frot2011Master,
    author = {Frot, Benjamin},
    title = {{Implementing and Automating complex arithmetic in quantomatic}},
    year = {2011},
    school = {University of Oxford},
    urldate = {2011-09-01},
    link = {http://www.cs.ox.ac.uk/people/bob.coecke/Ben.pdf},
    keywords = {ZW-Calculus, Quantomatic, Automation, Master Thesis},
    abstract = {Much work has been done on trying to understand and classify multipartite entanglement. For the past few years Categorical Quantum Mechanics
[AC04], which introduces a formalism of quantum mechanics in terms of
Symmetric Monoidal Categories (SMCs), has been used successfully in describing quantum systems at a high level of abstraction. From this work
emerges a graphical calculus which is powerful enough to express any Nqubit entangled state and suitable for automated reasoning [CK10]. In
[CKMR11] the authors show that it is possible to encode rational arithmetic within the GHZ/W-calculus.
In this dissertation, we propose an extension of the encoding of rational
arithmetic to complex numbers and show how it is possible to approximate
the complex field with arbitrary precision. We also present the work done
on quantomatic [DD+] in order to support multiple theories. Finally, we
show how both rational and complex arithmetics were implemented in this
software.}
}

Copy to Clipboard

The GHZ/W-calculus contains rational arithmetic
Bob Coecke, Aleks Kissinger, Alex Merry and Shibdas Roy
Show abstract ⇲ Show bibdata ⇲

Electronic Proceedings in Theoretical Computer Science
Keywords: ZW-Calculus, Foundational.

@article{CKMR,
    author = {Coecke, Bob and Kissinger, Aleks and Merry, Alex and Roy, Shibdas},
    title = {{The GHZ/W-calculus contains rational arithmetic}},
    year = {2010},
    journal = {Electronic Proceedings in Theoretical Computer Science},
    volume = {52},
    pages = {34-48},
    doi = {10.4204/EPTCS.52.4},
    urldate = {2011-03-14},
    link = {https://arxiv.org/abs/1103.2812},
    keywords = {ZW-Calculus, Foundational},
    abstract = {Graphical calculi for representing interacting quantum systems serve a number of purposes: compositionally, intuitive graphical reasoning, and a logical underpinning for automation. The power of these calculi stems from the fact that they embody generalized symmetries of the structure of quantum operations, which, for example, stretch well beyond the Choi-Jamiolkowski isomorphism. One such calculus takes the GHZ and W states as its basic generators. Here we show that this language allows one to encode standard rational calculus, with the GHZ state as multiplication, the W state as addition, the Pauli X gate as multiplicative inversion, and the Pauli Z gate as additive inversion.}
}

Copy to Clipboard

Three qubit entanglement within graphical Z/X-calculus
Bob Coecke and Bill Edwards
Show abstract ⇲ Show bibdata ⇲

Proceedings CSR 2010 Workshop on High Productivity Computations, Kazan, Russia, June 21-22, 2010
Keywords: ZX-calculus, Entanglement, ZW-Calculus.

@inproceedings{EPTCS52.3,
    author = {Coecke, Bob and Edwards, Bill},
    title = {{Three qubit entanglement within graphical Z/X-calculus}},
    year = {2011},
    booktitle = {Proceedings CSR 2010 Workshop on High Productivity Computations,
Kazan, Russia, June 21-22, 2010},
    editor = {Ablayev, Farid and Coecke, Bob and Vasiliev, Alexander},
    series = {Electronic Proceedings in Theoretical Computer Science},
    volume = {52},
    pages = {22-33},
    publisher = {Open Publishing Association},
    doi = {10.4204/EPTCS.52.3},
    urldate = {2011-03-14},
    link = {https://arxiv.org/abs/1103.2811},
    keywords = {ZX-calculus, Entanglement, ZW-Calculus},
    abstract = {The compositional techniques of categorical quantum mechanics are applied to analyse 3-qubit quantum entanglement. In particular the graphical calculus of complementary observables and corresponding phases due to Duncan and one of the authors is used to construct representative members of the two genuinely tripartite SLOCC classes of 3-qubit entangled states, GHZ and W. This nicely illustrates the respectively pairwise and global tripartite entanglement found in the W- and GHZ-class states. A new concept of supplementarity allows us to characterise inhabitants of the W class within the abstract diagrammatic calculus; these method extends to more general multipartite qubit states.}
}

Copy to Clipboard

Graphical Calculus for Quantum Key Distribution (Extended Abstract)
Bob Coecke, Quanlong Wang, Baoshan Wang, Yongjun Wang and Qiye Zhang
Show abstract ⇲ Show bibdata ⇲

Electronic Notes in Theoretical Computer Science
Keywords: Protocols, ZX-calculus, Category Theory, Strong Complementarity.

@article{COECKE2011231,
    author = {Bob Coecke and Quanlong Wang and Baoshan Wang and Yongjun Wang and Qiye Zhang},
    title = {Graphical Calculus for Quantum Key Distribution (Extended Abstract)},
    year = {2011},
    journal = {Electronic Notes in Theoretical Computer Science},
    volume = {270},
    number = {2},
    pages = {231--249},
    issn = {1571-0661},
    doi = {https://doi.org/10.1016/j.entcs.2011.01.034},
    urldate = {2011-02-14},
    link = {https://www.sciencedirect.com/science/article/pii/S1571066111000351},
    keywords = {Protocols, ZX-calculus, Category Theory, Strong Complementarity},
    abstract = {Controlled complementary measurements are key to quantum key distribution protocols, among many other things. We axiomatize controlled complementary measurements within symmetric monoidal categories, which provides them with a corresponding graphical calculus. We study the BB84 and Ekert91 protocols within this calculus, including the case where there is an intercept-resend attack.},
    note = {Proceedings of the 6th International Workshop on Quantum Physics and Logic (QPL 2009)}
}

Copy to Clipboard

Quantum picturalism for topological cluster-state computing
Clare Horsman
Show abstract ⇲ Show bibdata ⇲

New Journal of Physics
Keywords: ZX-calculus, Surface Code, Applied.

@article{horsman2011quantum,
    author = {Horsman, Clare},
    title = {Quantum picturalism for topological cluster-state computing},
    year = {2011},
    journal = {New Journal of Physics},
    volume = {13},
    number = {9},
    pages = {095011},
    publisher = {IOP Publishing},
    doi = {10.1088/1367-2630/13/9/095011},
    urldate = {2011-01-25},
    link = {https://arxiv.org/abs/1101.4722},
    keywords = {ZX-calculus, Surface Code, Applied},
    abstract = {Topological quantum computing is a way of allowing precise quantum computations to run on noisy and imperfect hardware. One implementation uses surface codes created by forming defects in a highly-entangled cluster state. Such a method of computing is a leading candidate for large-scale quantum computing. However, there has been a lack of sufficiently powerful high-level languages to describe computing in this form without resorting to single-qubit operations, which quickly become prohibitively complex as the system size increases. In this paper we apply the category-theoretic work of Abramsky and Coecke to the topological cluster-state model of quantum computing to give a high-level graphical language that enables direct translation between quantum processes and physical patterns of measurement in a computer - a "compiler language". We give the equivalence between the graphical and topological information flows, and show the applicable rewrite algebra for this computing model. We show that this gives us a native graphical language for the design and analysis of topological quantum algorithms, and finish by discussing the possibilities for automating this process on a large scale.}
}

Copy to Clipboard

Quantum Protocols involving Multiparticle Entanglement and their Representations in the ZX-calculus
Anne Hillebrand
Show abstract ⇲ Show bibdata ⇲

University of Oxford Masters Thesis
Keywords: ZX-Calculus, Protocols, Master Thesis.

@mastersthesis{hillebrand2011masters,
    author = {Hillebrand, Anne},
    title = {{Quantum Protocols involving Multiparticle Entanglement and their Representations in the ZX-calculus}},
    year = {2011},
    school = {University of Oxford},
    urldate = {2011-01-01},
    link = {http://www.cs.ox.ac.uk/people/bob.coecke/Anne.pdf},
    keywords = {ZX-Calculus, Protocols, Master Thesis},
    abstract = {Quantum entanglement, described by Einstein as "spooky action at a distance", is a key resource in many quantum protocols, like quantum teleportation and quantum cryptography. Yet entanglement makes protocols presented in Dirac notation difficult to follow and check. This is why Coecke and Duncan have introduced a diagrammatic language for multi-qubit systems, called the red/green calculus or the ZX-calculus. This diagrammatic notation is both intuitive and formally rigorous. It is a simple, graphical, high level language that emphasises the composition of systems and naturally captures the essentials of quantum mechanics. One crucial feature that will be exploited here is the encoding of complementary observables and corresponding phase shifts. Reasoning is done by rewriting diagrams, i.e. locally replacing some part of a diagram. Diagrams are defined by their topology only; the number of inputs and outputs and the way they are connected. This exemplifies the 'flow' of information. For protocols involving multipartite entangled states, such as the GreenbergerHorne-Zeilinger and W-state, it will be shown that the zx-calculus provides a relatively easy and more intuitive presentation. Moreover, in this representation it is easier to check that protocols are correct. Protocols that will be discussed in detail are quantum teleportation, quantum cryptography, leader election, superdense coding and quantum direct communication with multipartite entangled states.}
}

Copy to Clipboard

Towards normal forms for GHZ/W calculus
Shibdas Roy
Show abstract ⇲ Show bibdata ⇲

AIP Conference Proceedings
Keywords: ZW-calculus, Normal-form.

@inproceedings{roy2011towards,
    author = {Roy, Shibdas},
    title = {Towards normal forms for {GHZ/W} calculus},
    year = {2011},
    booktitle = {AIP Conference Proceedings},
    volume = {1384},
    number = {1},
    pages = {112--119},
    organization = {AIP},
    doi = {10.1063/1.3635852},
    link = {https://aip.scitation.org/doi/abs/10.1063/1.3635852},
    keywords = {ZW-calculus, Normal-form},
    abstract = {Recently, a novel GHZ/W graphical calculus has been established to study and reason more intuitively about interacting quantum systems. The compositional structure of this calculus was shown to be well‐equipped to sufficiently express arbitrary mutlipartite quantum states equivalent under stochastic local operations and classical communication (SLOCC). However, it is still not clear how to explicitly identify which graphical properties lead to what states. This can be achieved if we have well‐behaved normal forms for arbitrary graphs within this calculus. This article lays down a first attempt at realizing such normal forms for a restricted class of such graphs, namely simple and regular graphs. These results should pave the way for the most general cases as part of future work.}
}

Copy to Clipboard

Models of Multipartite Entanglement
Michael Herrmann
Show abstract ⇲ Show bibdata ⇲

University of Oxford Masters Thesis
Keywords: ZW-Calculus, Entanglement, Master Thesis.

While multipartite entanglement is a crucial resource for many quantum algorithms and protocols, the abstract, structural rules governing it are still not fully understood. In their recent paper, Coecke and Kissinger propose a new language called GHZ/W-calculus that aims to give a structural axiomatization of multipartite entanglement in terms of interacting

special'' and

anti-special'' commutative Frobenius algebras (S/A-CFAs). These algebraic structures correspond precisely to the two different types of genuine entanglement between three qubits, as given by inter-convertability by stochastic local (quantum) operations and classical communication (SLOCC). An important feature of the language is that it lives in the framework of categorical quantum mechanics and thus comes with a Penrose-Joyal-Street graphical calulus. This thesis explores the expressive power of the GHZ/W-calculus. We prove a new result that demonstrates the canonicity of the recent concept of antispeciality for CFAs and use it to give a new classification of Frobenius Algebras on

$\mathbb{C}^2$ in FdHilb, the category of finite-dimensional Hilbert spaces and bounded linear maps. Next, we look at the non-standard model of categorical quantum mechanics given by FRel, the category of finite sets and binary relations. We classify all special CFAs in this category, prove some properties of anti-special ones and identify precisely which SCFAs/ACFAs are captured by the GHZ/W-language. Finally, we define a quantum AND gate in the graphical language and prove (or disprove) some of its properties. We come to the conclusion that the GHZ/W-calculus is unlikely to be the final answer to the structural entanglement problem in dimensions

$D > 2$ and identify intermediate ranks

$1 < rank < D$ as the notion it fails to explain.

@mastersthesis{HerrmannThesis,
    author = {Herrmann, Michael},
    title = {{Models of Multipartite Entanglement}},
    year = {2010},
    school = {University of Oxford},
    urldate = {2010-09-01},
    link = {http://www.cs.ox.ac.uk/people/bob.coecke/Michael.pdf},
    keywords = {ZW-Calculus, Entanglement, Master Thesis},
    abstract = {While multipartite entanglement is a crucial resource for many quantum algorithms and protocols, the abstract, structural rules governing it are still not fully understood. In their recent paper, Coecke and Kissinger propose a new language called GHZ/W-calculus that aims to give a structural axiomatization of multipartite entanglement in terms of interacting ``special'' and ``anti-special'' commutative Frobenius algebras (S/A-CFAs). These algebraic structures correspond precisely to the two different types of genuine entanglement between three qubits, as given by inter-convertability by stochastic local (quantum) operations and classical communication (SLOCC). An important feature of the language is that it lives in the framework of categorical quantum mechanics and thus comes with a Penrose-Joyal-Street graphical calulus. This thesis explores the expressive power of the GHZ/W-calculus. We prove a new result that demonstrates the canonicity of the recent concept of antispeciality for CFAs and use it to give a new classification of Frobenius Algebras on $\mathbb{C}^2$ in FdHilb, the category of finite-dimensional Hilbert spaces and bounded linear maps. Next, we look at the non-standard model of categorical quantum mechanics given by FRel, the category of finite sets and binary relations. We classify all special CFAs in this category, prove some properties of anti-special ones and identify precisely which SCFAs/ACFAs are captured by the GHZ/W-language. Finally, we define a quantum AND gate in the graphical language and prove (or disprove) some of its properties. We come to the conclusion that the GHZ/W-calculus is unlikely to be the final answer to the structural entanglement problem in dimensions $D > 2$ and identify intermediate ranks $1 < rank < D$ as the notion it fails to explain.}
}

Copy to Clipboard

Linking Form and Function: A geometric investigation of Multi-partite graph states
David Mack
Show abstract ⇲ Show bibdata ⇲

University of Oxford Masters Thesis
Keywords: ZX-calculus, ZW-calculus, Master Thesis, Graph States.

@mastersthesis{Mack2010Master,
    author = {Mack, David},
    title = {{Linking Form and Function: A geometric investigation of Multi-partite graph states}},
    year = {2010},
    school = {University of Oxford},
    urldate = {2010-09-01},
    link = {http://www.cs.ox.ac.uk/people/bob.coecke/David.pdf},
    keywords = {ZX-calculus, ZW-calculus, Master Thesis, Graph States},
    abstract = {Quantum Computing has quickly established itself as a paradigmshifting force, displaying properties that defy intuition. Its power has
produced revolutionary algorithms, yet we have no clear understanding of else is possible; we are still stumbling through a jungle rather
than mastering the field.
Bob Coecke et al. have produced a graphical calculus and algebraic
model that intuitively captures quantum’s essential features, allowing
one to manipulate complex structures easily on paper. Major algorithms can be verified in just a couple of steps. However, combining
the basic elements is still alchemy, no rules nor intuitions exist to
predict the results.
This dissertation seeks to investigate those dark corners and catalogue its findings, presenting any rules it encounters on the way. This
is prefaced by a thorough description of the advanced algebra and
calculus used, displaying key results and insights. The final chapter
presents interesting structures that warrant further investigation and
possible components for a higher-level quantum tool-set.}
}

Copy to Clipboard

Environment and classical channels in categorical quantum mechanics
Bob Coecke and Simon Perdrix
Show abstract ⇲ Show bibdata ⇲

Proceedings of the 19th EACSL Annual Conference on Computer Science Logic (CSL)
Keywords: ZX-Calculus, Category Theory, Foundational.

@inproceedings{CPer,
    author = {Coecke, Bob and Perdrix, Simon},
    title = {Environment and classical channels in categorical quantum mechanics},
    year = {2010},
    booktitle = {Proceedings of the 19th EACSL Annual Conference on Computer Science Logic (CSL)},
    series = {Lecture Notes in Computer Science},
    volume = {6247},
    pages = {230-244},
    doi = {10.1007/978-3-642-15205-4\_20},
    urldate = {2010-04-09},
    link = {https://arxiv.org/abs/1004.1598},
    keywords = {ZX-Calculus, Category Theory, Foundational},
    abstract = {We present a both simple and comprehensive graphical calculus for quantum computing. In particular, we axiomatize the notion of an environment, which together with the earlier introduced axiomatic notion of classical structure enables us to define classical channels, quantum measurements and classical control. If we moreover adjoin the earlier introduced axiomatic notion of complementarity, we obtain sufficient structural power for constructive representation and correctness derivation of typical quantum informatic protocols.}
}

Copy to Clipboard

Phase groups and the origin of non-locality for qubits
Bob Coecke, Bill Edwards and Rob Spekkens
Show abstract ⇲ Show bibdata ⇲

Electronic Notes in Theoretical Computer Science
Keywords: ZX-Calculus, Spekkens Toy Model.

@article{CES,
    author = {Coecke, Bob and Edwards, Bill and Spekkens, Rob},
    title = {Phase groups and the origin of non-locality for qubits},
    year = {2011},
    journal = {Electronic Notes in Theoretical Computer Science},
    volume = {270},
    number = {2},
    pages = {15-36},
    doi = {10.1016/j.entcs.2011.01.021},
    urldate = {2010-03-25},
    link = {https://arxiv.org/abs/1003.5005},
    keywords = {ZX-Calculus, Spekkens Toy Model},
    abstract = {We describe a general framework in which we can precisely compare the structures of quantum-like theories which may initially be formulated in quite different mathematical terms. We then use this framework to compare two theories: quantum mechanics restricted to qubit stabiliser states and operations, and Spekkens's toy theory. We discover that viewed within our framework these theories are very similar, but differ in one key aspect - a four element group we term the phase group which emerges naturally within our framework. In the case of the stabiliser theory this group is Z4 while for Spekkens's toy theory the group is Z2 x Z2. We further show that the structure of this group is intimately involved in a key physical difference between the theories: whether or not they can be modelled by a local hidden variable theory. This is done by establishing a connection between the phase group, and an abstract notion of GHZ state correlations. We go on to formulate precisely how the stabiliser theory and toy theory are `similar' by defining a notion of `mutually unbiased qubit theory', noting that all such theories have four element phase groups. Since Z4 and Z2 x Z2 are the only such groups we conclude that the GHZ correlations in this type of theory can only take two forms, exactly those appearing in the stabiliser theory and in Spekkens's toy theory. The results point at a classification of local/non-local behaviours by finite Abelian groups, extending beyond qubits to finitary theories whose observables are all mutually unbiased.}
}

Copy to Clipboard

The compositional structure of multipartite quantum entanglement
Bob Coecke and Aleks Kissinger
Show abstract ⇲ Show bibdata ⇲ Video 🎥

Automata, Languages and Programming
Keywords: ZW-Calculus, Foundations, Foundational.

@inproceedings{CK,
    author = {Coecke, Bob and Kissinger, Aleks},
    title = {The compositional structure of multipartite quantum entanglement},
    year = {2010},
    booktitle = {Automata, Languages and Programming},
    series = {Lecture Notes in Computer Science},
    pages = {297--308},
    publisher = {Springer},
    doi = {10.1007/978-3-642-14162-1\_25},
    urldate = {2010-02-12},
    link = {http://arxiv.org/abs/1002.2540},
    keywords = {ZW-Calculus, Foundations, Foundational},
    abstract = {While multipartite quantum states constitute a (if not the) key resource for quantum computations and protocols, obtaining a high-level, structural understanding of entanglement involving arbitrarily many qubits is a long-standing open problem in quantum computer science. In this paper we expose the algebraic and graphical structure of the GHZ-state and the W-state, as well as a purely graphical distinction that characterises the behaviours of these states. In turn, this structure yields a compositional graphical model for expressing general multipartite states. 
We identify those states, named Frobenius states, which canonically induce an algebraic structure, namely the structure of a commutative Frobenius algebra (CFA). We show that all SLOCC-maximal tripartite qubit states are locally equivalent to Frobenius states. Those that are SLOCC-equivalent to the GHZ-state induce special commutative Frobenius algebras, while those that are SLOCC-equivalent to the W-state induce what we call anti-special commutative Frobenius algebras. From the SLOCC-classification of tripartite qubit states follows a representation theorem for two dimensional CFAs. 
Together, a GHZ and a W Frobenius state form the primitives of a graphical calculus. This calculus is expressive enough to generate and reason about arbitrary multipartite states, which are obtained by "composing" the GHZ- and W-states, giving rise to a rich graphical paradigm for general multipartite entanglement.},
    video = {https://www.youtube.com/watch?v=7-QQj9akrrA}
}

Copy to Clipboard

Rewriting measurement-based quantum computations with generalised flow
Ross Duncan and Simon Perdrix
Show abstract ⇲ Show bibdata ⇲ Video 🎥

International Colloquium on Automata, Languages, and Programming
Keywords: ZX-Calculus, MBQC, Applied, Gflow.

@inproceedings{duncan2010rewriting,
    author = {Duncan, Ross and Perdrix, Simon},
    title = {Rewriting measurement-based quantum computations with generalised flow},
    year = {2010},
    booktitle = {International Colloquium on Automata, Languages, and Programming},
    pages = {285--296},
    organization = {Springer},
    doi = {10.1007/978-3-642-14162-1\_24},
    link = {http://personal.strath.ac.uk/ross.duncan/papers/gflow.pdf},
    keywords = {ZX-Calculus, MBQC, Applied, Gflow},
    abstract = {We present a method for verifying measurement-based quantum computations, by producing a quantum circuit equivalent to a given deterministic measurement pattern. We define a diagrammatic presentation of the pattern, and produce a circuit via a rewriting strategy based on the generalised flow of the pattern. Unlike other methods for translating measurement patterns with generalised flow to circuits, this method uses neither ancilla qubits nor acausal loops.},
    video = {https://www.youtube.com/watch?v=V-e4VXFBQBc}
}

Copy to Clipboard

Quantum picturalism
Bob Coecke
Show abstract ⇲ Show bibdata ⇲

Contemporary Physics
Keywords: ZX-Calculus, Foundational.
The quantum mechanical formalism doesn't support our intuition, nor does it elucidate the key concepts that govern the behaviour of the entities that are subject to the laws of quantum physics. The arrays of complex numbers are kin to the arrays of 0s and 1s of the early days of computer programming practice. In this review we present steps towards a diagrammatic $high-level' alternative for the Hilbert space formalism, one which appeals to our intuition. It allows for intuitive reasoning about interacting quantum systems, and trivialises many otherwise involved and tedious computations. It clearly exposes limitations such as the no-cloning theorem, and phenomena such as quantum teleportation. As a logic, it supports$ automation'. It allows for a wider variety of underlying theories, and can be easily modified, having the potential to provide the required step-stone towards a deeper conceptual understanding of quantum theory, as well as its unification with other physical theories. Specific applications discussed here are purely diagrammatic proofs of several quantum computational schemes, as well as an analysis of the structural origin of quantum non-locality. The underlying mathematical foundation of this high-level diagrammatic formalism relies on so-called monoidal categories, a product of a fairly recent development in mathematics. These monoidal categories do not only provide a natural foundation for physical theories, but also for proof theory, logic, programming languages, biology, cooking, ... The challenge is to discover the necessary additional pieces of structure that allow us to predict genuine quantum phenomena.
```
@article{ContPhys,
    author = {Coecke, Bob},
    title = {Quantum picturalism},
    year = {2009},
    journal = {Contemporary Physics},
    volume = {51},
    pages = {59-83},
    doi = {10.1080/00107510903257624},
    urldate = {2009-08-13},
    link = {http://arxiv.org/abs/0908.1787},
    keywords = {ZX-Calculus, Foundational},
    abstract = {The quantum mechanical formalism doesn't support our intuition, nor does it elucidate the key concepts that govern the behaviour of the entities that are subject to the laws of quantum physics. The arrays of complex numbers are kin to the arrays of 0s and 1s of the early days of computer programming practice. In this review we present steps towards a diagrammatic `high-level' alternative for the Hilbert space formalism, one which appeals to our intuition. It allows for intuitive reasoning about interacting quantum systems, and trivialises many otherwise involved and tedious computations. It clearly exposes limitations such as the no-cloning theorem, and phenomena such as quantum teleportation. As a logic, it supports `automation'. It allows for a wider variety of underlying theories, and can be easily modified, having the potential to provide the required step-stone towards a deeper conceptual understanding of quantum theory, as well as its unification with other physical theories. Specific applications discussed here are purely diagrammatic proofs of several quantum computational schemes, as well as an analysis of the structural origin of quantum non-locality. The underlying mathematical foundation of this high-level diagrammatic formalism relies on so-called monoidal categories, a product of a fairly recent development in mathematics. These monoidal categories do not only provide a natural foundation for physical theories, but also for proof theory, logic, programming languages, biology, cooking, ... The challenge is to discover the necessary additional pieces of structure that allow us to predict genuine quantum phenomena.}
}
```
Copy to Clipboard

Simulating quantum processes using classical structures
Manav Bhushan
Show abstract ⇲ Show bibdata ⇲

University of Oxford Masters Thesis
Keywords: ZX-calculus, Protocols, Master Thesis.

@mastersthesis{Manav2009Master,
    author = {Bhushan, Manav},
    title = {{Simulating quantum processes using classical structures}},
    year = {2009},
    school = {University of Oxford},
    urldate = {2009-06-30},
    link = {http://www.cs.ox.ac.uk/people/bob.coecke/Manav},
    keywords = {ZX-calculus, Protocols, Master Thesis},
    abstract = {In earlier work, it has been shown that Frobenius algebras with certain properties can
be used to simulate classical data. They are especially useful because in their deffnition itself they
incorporate the most major difference between classical and quantum data- which is the absence of
copying and deleting operations for arbitrary quantum states. In later work, it has been shown that a
special, commutative, dagger-Frobenius algebra (classical structure) corresponds to an orthonormal
basis for a finite-dimensional Hilbert Space. In this paper, we show how classical structures can be
used to axiomatize maximally entangled states for two qubits. We then go on explain how this new
representation of quantum informatic protocols using classical structures can be used to encode the
flow of quantum data. We explain how this process encodes all the possible observational branches
simultaneously, and thus has the ability to tell us the end result that can be achieved in any particular
protocol. We end with a summary of the results obtained, and suggestions for future work.}
}

Copy to Clipboard

Interacting quantum observables: categorical algebra and diagrammatics
Bob Coecke and Ross Duncan
Show abstract ⇲ Show bibdata ⇲

New Journal of Physics
Keywords: ZX-Calculus, Foundational.

@article{CD2,
    author = {Coecke, Bob and Duncan, Ross},
    title = {Interacting quantum observables: categorical algebra and diagrammatics},
    year = {2011},
    journal = {New Journal of Physics},
    volume = {13},
    pages = {043016},
    doi = {10.1088/1367-2630/13/4/043016},
    urldate = {2009-06-25},
    link = {https://arxiv.org/abs/0906.4725},
    keywords = {ZX-Calculus, Foundational},
    abstract = {This paper has two tightly intertwined aims: (i) To introduce an intuitive and universal graphical calculus for multi-qubit systems, the ZX-calculus, which greatly simplifies derivations in the area of quantum computation and information. (ii) To axiomatise complementarity of quantum observables within a general framework for physical theories in terms of dagger symmetric monoidal categories. We also axiomatize phase shifts within this framework. 
Using the well-studied canonical correspondence between graphical calculi and symmetric monoidal categories, our results provide a purely graphical formalisation of complementarity for quantum observables. Each individual observable, represented by a commutative special dagger Frobenius algebra, gives rise to an abelian group of phase shifts, which we call the phase group. We also identify a strong form of complementarity, satisfied by the Z and X spin observables, which yields a scaled variant of a bialgebra.}
}

Copy to Clipboard

Graph states and the necessity of Euler decomposition
Ross Duncan and Simon Perdrix
Show abstract ⇲ Show bibdata ⇲

Conference on Computability in Europe
Keywords: ZX-calculus, Clifford Fragment, Graph States, Local Complementation, Foundational.

@inproceedings{DuncanPerdrixGraphStates,
    author = {Duncan, Ross and Perdrix, Simon},
    title = {Graph states and the necessity of {Euler} decomposition},
    year = {2009},
    booktitle = {Conference on Computability in Europe},
    pages = {167--177},
    organization = {Springer},
    doi = {10.1007/978-3-642-03073-4\_18},
    urldate = {2009-02-03},
    link = {https://arxiv.org/abs/0902.0500},
    keywords = {ZX-calculus, Clifford Fragment, Graph States, Local Complementation, Foundational},
    abstract = {Coecke and Duncan recently introduced a categorical formalisation of the interaction of complementary quantum observables. In this paper we use their diagrammatic language to study graph states, a computationally interesting class of quantum states. We give a graphical proof of the fixpoint property of graph states. We then introduce a new equation, for the Euler decomposition of the Hadamard gate, and demonstrate that Van den Nest's theorem--locally equivalent graphs represent the same entanglement--is equivalent to this new axiom. Finally we prove that the Euler decomposition equation is not derivable from the existing axioms.}
}

Copy to Clipboard

Interacting quantum observables
Bob Coecke and Ross Duncan
Show abstract ⇲ Show bibdata ⇲ Video 🎥

Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP)
Keywords: ZX-Calculus, Foundational.

@inproceedings{CD1,
    author = {Coecke, Bob and Duncan, Ross},
    title = {Interacting quantum observables},
    year = {2008},
    booktitle = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP)},
    series = {Lecture Notes in Computer Science},
    doi = {10.1007/978-3-540-70583-3\_25},
    link = {https://ora.ox.ac.uk/objects/uuid:77175185-265b-4467-a81a-a9593ed329e7/download_file?file_format=pdf&safe_filename=Interacting%252520Quantum%252520Observables.pdf&type_of_work=Conference+item},
    keywords = {ZX-Calculus, Foundational},
    abstract = {We formalise the constructive content of an essential feature of quantum mechanics: the interaction of complementary quantum observables, and information flow mediated by them. Using a general categorical formulation, we show that pairs of mutually unbiased quantum observables form bialgebra-like structures. We also provide an abstract account on the quantum data encoded in complex phases, and prove a normal form theorem for it. Together these enable us to describe all observables of finite dimensional Hilbert space quantum mechanics. The resulting equations suffice to perform computations with elementary quantum gates, translate between distinct quantum computational models, establish the equivalence of entangled quantum states, and simulate quantum algorithms such as the quantum Fourier transform. All these computations moreover happen within an intuitive diagrammatic calculus.},
    video = {https://www.youtube.com/watch?v=UQTTJV0ejfw}
}

Copy to Clipboard