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 Richard East or John van de Wetering. If you want to keep up-to-date with additions, there is also an RSS feed.
Showing n items
@inproceedings{Simmons2021Measurement,
author = {Simmons, Will},
title = {{Relating Measurement Patterns to Circuits via Pauli Flow}},
year = {2021},
booktitle = {Proceedings 18th International Conference on Quantum Physics and Logic, Gdansk, Poland, and online, 7-11 June 2021},
editor = {Heunen, Chris and Backens, Miriam},
series = {Electronic Proceedings in Theoretical Computer Science},
volume = {343},
pages = {50-101},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.343.4},
urldate = {2021-09-13},
link = {https://arxiv.org/abs/2109.05654},
keywords = {ZX-calculus, MBQC, gflow, Circuit Extraction, Phase Gadgets},
abstract = {The one-way model of Measurement-Based Quantum Computing and the gate-based circuit model give two different presentations of how quantum computation can be performed. There are known methods for converting any gate-based quantum circuit into a one-way computation, whereas the reverse is only efficient given some constraints on the structure of the measurement pattern. Causal flow and generalised flow have already been shown as sufficient, with efficient algorithms for identifying these properties and performing the circuit extraction. Pauli flow is a weaker set of conditions that extends generalised flow to use the knowledge that some vertices are measured in a Pauli basis. In this paper, we show that Pauli flow can similarly be identified efficiently and that any measurement pattern whose underlying graph admits a Pauli flow can be efficiently transformed into a gate-based circuit without using ancilla qubits. We then use this relationship to derive simulation results for the effects of graph-theoretic rewrites in the ZX-calculus using a more circuit-like data structure we call the Pauli Dependency DAG.},
video = {https://www.youtube.com/watch?v=XcrD_Hc4zUY}
}
@article{kissinger2021simulating,
author = {Kissinger, Aleks and van de Wetering, John},
title = {{Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions}},
year = {2021},
journal = {arXiv preprint arXiv:2109.01076},
urldate = {2021-09-02},
link = {http://arxiv.org/abs/2109.01076},
keywords = {ZX-calculus, Classical Simulation, Applied, PyZX, Automation},
abstract = {We introduce an enhanced technique for strong classical simulation of quantum circuits which combines the `sum-of-stabilisers' method with an automated simplification strategy based on the ZX-calculus. Recently it was shown that quantum circuits can be classically simulated by expressing the non-stabiliser gates in a circuit as magic state injections and decomposing them in chunks of 2-6 states at a time, obtaining sums of (efficiently-simulable) stabiliser states with many fewer terms than the naive approach. We adapt these techniques from the original setting of Clifford circuits with magic state injection to generic ZX-diagrams and show that, by interleaving this "chunked" decomposition with a ZX-calculus-based simplification strategy, we can obtain stabiliser decompositions that are many orders of magnitude smaller than existing approaches. We illustrate this technique to perform exact norm calculations (and hence strong simulation) on the outputs of random 50- and 100-qubit Clifford+T circuits with up to 70 T-gates as well as a family of hidden shift circuits previously considered by Bravyi and Gosset with over 1000 T-gates.}
}
@article{vilmart2021quantum,
author = {Vilmart, Renaud},
title = {{Quantum Multiple-Valued Decision Diagrams in Graphical Calculi}},
year = {2021},
journal = {arXiv preprint arXiv:2107.01186},
urldate = {2021-07-02},
link = {http://arxiv.org/abs/2107.01186},
keywords = {ZH-calculus, Classical Simulation},
abstract = {Graphical calculi such as the ZH-calculus are powerful tools in the study and analysis of quantum processes, with links to other models of quantum computation such as quantum circuits, measurement-based computing, etc. A somewhat compact but systematic way to describe a quantum process is through the use of quantum multiple-valued decision diagrams (QMDDs), which have already been used for the synthesis of quantum circuits as well as for verification. We show in this paper how to turn a QMDD into an equivalent ZH-diagram, and vice-versa, and show how reducing a QMDD translates in the ZH-Calculus, hence allowing tools from one formalism to be used into the other.}
}
@article{cowtan2021quantum,
author = {Cowtan, Alexander and Majid, Shahn},
title = {{Quantum double aspects of surface code models}},
year = {2021},
journal = {arXiv preprint arXiv:2107.04411},
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.}
}
@mastersthesis{rasat2021masters,
author = {Rasat, Siti Aqilah Binti Muhamad},
title = {{The role of compositionality in constructing complementary classical structures within qubit systems}},
year = {2021},
school = {Universiti Putra Malaysia},
urldate = {2021-05-24},
link = {https://arxiv.org/abs/2105.11966},
keywords = {ZX-Calculus, Strong Complementarity, Master Thesis},
abstract = {Observables in a quantum system, represented by a Hilbert space, are given by the orthogonal bases of the aforementioned Hilbert space. Categorical Quantum Mechanics provides further abstraction of such observables, allowing for a diagrammatic representation of measurements that extends to quantum processes. Our research studies this abstraction of observables, which has been dubbed as classical structures, in a subtheory of quantum mechanics which focuses on qubit systems (or 2-dimensional quantum system and its composites). We have constructed a procedure that takes the complementary classical structures of a single qubit system and compose them separably via the Kronecker product or 'entangle' them via Bell states to obtain complementary classical structures in n-qubit systems. In this present work, we apply our procedure to two qubit and three qubit systems as examples. Then, using rewriting rules of ZX-calculus and tools in graph theory, we searched for maximal complete sets of mutually complementary classical structures (the categorical counterpart of mutually unbiased bases) among our constructed composite classical structures. For two qubits, we found 13 maximal complete sets of mutually complementary classical structures, and for three qubits, we found 32,448 maximal complete sets of mutually complementary classical structures.}
}
@article{comfort2021graphical,
author = {Comfort, Cole and Kissinger, Aleks},
title = {{A Graphical Calculus for Lagrangian Relations}},
year = {2021},
journal = {arXiv preprint arXiv:2105.06244},
urldate = {2021-05-13},
link = {http://arxiv.org/abs/2105.06244},
keywords = {Clifford fragment, Qudits, Spekkens Toy Model, Category Theory},
abstract = {Symplectic vector spaces are the phase space of linear mechanical systems. The symplectic form describes, for example, the relation between position and momentum as well as current and voltage. The category of linear Lagrangian relations between symplectic vector spaces is a symmetric monoidal subcategory of relations which gives a semantics for the evolution -- and more generally linear constraints on the evolution -- of various physical systems. We give a new presentation of the category of Lagrangian relations over an arbitrary field as a `doubled' category of linear relations. More precisely, we show that it arises as a variation of Selinger's CPM construction applied to linear relations, where the covariant orthogonal complement functor plays of the role of conjugation. Furthermore, for linear relations over prime fields, this corresponds exactly to the CPM construction for a suitable choice of dagger. We can furthermore extend this construction by a single affine shift operator to obtain a category of affine Lagrangian relations. Using this new presentation, we prove the equivalence of the prop of affine Lagrangian relations with the prop of qudit stabilizer theory in odd prime dimensions. We hence obtain a unified graphical language for several disparate process theories, including electrical circuits, Spekkens' toy theory, and odd-prime-dimensional stabilizer quantum circuits.}
}
@misc{Krueger2021Video,
author = {Krueger, Ryan},
title = {{Vanishing 2-qubit gates with non-simplification ZX-rules}},
year = {2021},
howpublished = {Master presentation},
urldate = {2021-04-23},
url = {https://www.youtube.com/watch?v=tUIcqXKEFhk},
keywords = {ZX-calculus, Applied, Automation, PyZX, Optimisation, Local Complementation},
abstract = {Traditional quantum circuit optimization is performed directly at the circuit level. Alternatively, a quantum circuit can be translated to a ZX-diagram which can be simplified using the rules of the ZX-calculus, after which a simplified circuit can be extracted. However, the best-known extraction procedures can drastically increase the number of 2-qubit gates. In this work, we take advantage of the fact that local changes in a ZX-diagram can drastically affect the complexity of the extracted circuit. We use a pair of congruences (i.e., non-simplification rewrite rules) based on the graph-theoretic notions of local complementation and pivoting to generate local variants of a simplified ZX-diagram. We explore the space of equivalent ZX-diagrams generated by these congruences using simulated annealing and genetic algorithms to obtain a simplified circuit with fewer 2-qubit gates.
Our method can reliably outperform state-of-the-art optimization techniques for low-qubit, less than 10 qubit, circuits and serves as a proof-of-concept for a new circuit optimization strategy in the ZX-calculus.
}
}
@article{wang2021qufinite,
author = {Wang, Quanlong},
title = {{Qufinite ZX-calculus: a unified framework of qudit ZX-calculi}},
year = {2021},
journal = {arXiv preprint arXiv:2104.06429},
urldate = {2021-04-13},
link = {http://arxiv.org/abs/2104.06429},
keywords = {Algebraic ZX, Completeness, Triangle, Qudits},
abstract = {ZX-calculus is graphical language for quantum computing which usually focuses on qubits. In this paper, we generalise qubit ZX-calculus to qudit ZX-calculus in any finite dimension by introducing suitable generators, especially a carefully chosen triangle node. As a consequence we obtain a set of rewriting rules which can be seen as a direct generalisation of qubit rules, and a normal form for any qudit vectors. Based on the qudit ZX-calculi, we propose a graphical formalism called qufinite ZX-calculus as a unified framework for all qudit ZX-calculi, which is universal for finite quantum theory due to a normal form for matrix of any finite size. We would expect a reconstruction of finite quantum theory within the framework of qufinite ZX-calculus which focuses on compositionality without resorting to any probability theory or sum structures.},
video = {https://www.youtube.com/watch?v=5DmlLbxGNlU}
}
@inproceedings{Carette2021quantum,
author = {Carette, Titouan and D'Anello, Yohann and Perdrix, Simon},
title = {{Quantum Algorithms and Oracles with the Scalable ZX-calculus}},
year = {2021},
booktitle = {Proceedings 18th International Conference on Quantum Physics and Logic, Gdansk, Poland, and online, 7-11 June 2021},
editor = {Heunen, Chris and Backens, Miriam},
series = {Electronic Proceedings in Theoretical Computer Science},
volume = {343},
pages = {193-209},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.343.10},
urldate = {2021-04-02},
link = {http://arxiv.org/abs/2104.01043},
keywords = {ZX-calculus, Scalable ZX, Tempered, Protocols},
abstract = {The ZX-calculus was introduced as a graphical language able to represent specific quantum primitives in an intuitive way. The recent completeness results have shown the theoretical possibility of a purely graphical description of quantum processes. However, in practice, such approaches are limited by the intrinsic low level nature of ZX calculus. The scalable notations have been proposed as an attempt to recover an higher level point of view while maintaining the topological rewriting rules of a graphical language. We demonstrate that the scalable ZX-calculus provides a formal, intuitive, and compact framework to describe and prove quantum algorithms. As a proof of concept, we consider the standard oracle-based quantum algorithms: Deutsch-Jozsa, Bernstein-Vazirani, Simon, and Grover algorithms, and we show they can be described and proved graphically.},
video = {https://www.youtube.com/watch?v=8J0Ll8RXyz0}
}
@article{gorard2021zxcalculus,
author = {Gorard, Jonathan and Namuduri, Manojna and D. Arsiwalla, Xerxes},
title = {{ZX-Calculus and Extended Wolfram Model Systems II: Fast Diagrammatic Reasoning with an Application to Quantum Circuit Simplification}},
year = {2021},
journal = {arXiv preprint arXiv:2103.15820},
urldate = {2021-03-29},
link = {http://arxiv.org/abs/2103.15820},
keywords = {ZX-calculus, Category Theory, Optimisation, Applied},
abstract = {This article presents a novel algorithmic methodology for performing automated diagrammatic deductions over combinatorial structures, using a combination of modified equational theorem-proving techniques and the extended Wolfram model hypergraph rewriting formalism developed by the authors in previous work. We focus especially upon the application of this new algorithm to the problem of automated circuit simplification in quantum information theory, using Wolfram model multiway operator systems combined with the ZX-calculus formalism for enacting fast diagrammatic reasoning over linear transformations between qubits. We show how to construct a generalization of the deductive inference rules for Knuth-Bendix completion in which equation matches are selected on the basis of causal edge density in the associated multiway system, before proceeding to demonstrate how to embed the higher-order logic of the ZX-calculus rules within this first-order equational framework. After showing explicitly how the (hyper)graph rewritings of both Wolfram model systems and the ZX-calculus can be effectively realized within this formalism, we proceed to exhibit comparisons of time complexity vs. proof complexity for this new algorithmic approach when simplifying randomly-generated Clifford circuits down to pseudo-normal form, as well as when reducing the number of T-gates in randomly-generated non-Clifford circuits, with circuit sizes ranging up to 3000 gates, illustrating that the method performs favorably in comparison with existing circuit simplification frameworks, and also exhibiting the approximately quadratic speedup obtained by employing the causal edge density optimization. Finally, we present a worked example of an automated proof of correctness for a simple quantum teleportation protocol, in order to demonstrate more clearly the internal operations of the theorem-proving procedure.}
}
@inproceedings{toumi2021diagrammatic,
author = {Toumi, Alexis and Yeung, Richie and de Felice, Giovanni},
title = {{Diagrammatic Differentiation for Quantum Machine Learning}},
year = {2021},
booktitle = {Proceedings 18th International Conference on Quantum Physics and Logic, Gdansk, Poland, and online, 7-11 June 2021},
editor = {Heunen, Chris and Backens, Miriam},
series = {Electronic Proceedings in Theoretical Computer Science},
volume = {343},
pages = {132-144},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.343.7},
urldate = {2021-03-14},
link = {http://arxiv.org/abs/2103.07960},
keywords = {ZX-calculus, Applied, PyZX, NLP},
abstract = {We introduce diagrammatic differentiation for tensor calculus by generalising the dual number construction from rigs to monoidal categories. Applying this to ZX diagrams, we show how to calculate diagrammatically the gradient of a linear map with respect to a phase parameter. For diagrams of parametrised quantum circuits, we get the well-known parameter-shift rule at the basis of many variational quantum algorithms. We then extend our method to the automatic differentation of hybrid classical-quantum circuits, using diagrams with bubbles to encode arbitrary non-linear operators. Moreover, diagrammatic differentiation comes with an open-source implementation in DisCoPy, the Python library for monoidal categories. Diagrammatic gradients of classical-quantum circuits can then be simplified using the PyZX library and executed on quantum hardware via the tket compiler. This opens the door to many practical applications harnessing both the structure of string diagrams and the computational power of quantum machine learning.},
video = {https://www.youtube.com/watch?v=HOB3r44-pGw}
}
@article{backens2021completeness,
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 = {2021},
journal = {arXiv preprint arXiv:2103.06610},
urldate = {2021-03-11},
link = {http://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}
}
@article{townsend-teague2021classifying,
author = {Townsend-Teague, Alex and Meichanetzidis, Konstantinos},
title = {{Classifying Complexity with the ZX-Calculus: Jones Polynomials and Potts Partition Functions}},
year = {2021},
journal = {arXiv preprint arXiv:2103.06914},
urldate = {2021-03-11},
link = {http://arxiv.org/abs/2103.06914},
keywords = {ZX-calculus, Tensor networks, Applied},
abstract = {The ZX-calculus is a graphical language which allows for reasoning about suitably represented tensor networks - namely ZX-diagrams - in terms of rewrite rules. Here, we focus on problems which amount to exactly computing a scalar encoded as a closed tensor network. In general, such problems are #P-hard. However, there are families of such problems which are known to be in P when the dimension is below a certain value. By expressing problem instances from these families as ZX-diagrams, we see that the easy instances belong to the stabilizer fragment of the ZX-calculus. Building on previous work on efficient simplification of qubit stabilizer diagrams, we present simplifying rewrites for the case of qutrits, which are of independent interest in the field of quantum circuit optimisation. Finally, we look at the specific examples of evaluating the Jones polynomial and of counting graph-colourings. Our exposition further champions the ZX-calculus as a suitable and unifying language for studying the complexity of a broad range of classical and quantum problems.},
video = {https://www.youtube.com/watch?v=fUxbUQkeaMQ}
}
@article{majid2021quantum,
author = {Majid, Shahn},
title = {{Quantum and braided ZX calculus}},
year = {2021},
journal = {arXiv preprint arXiv:2103.07264},
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}
}
@misc{Cowtan2021Video,
author = {Cowtan, Alex},
title = {{String Diagrams for the Surface Code}},
year = {2021},
howpublished = {ZX seminar},
urldate = {2021-03-01},
url = {https://www.youtube.com/watch?v=OYDpEo8yP40},
keywords = {ZX-calculus, Surface Code, Braids, Applied},
abstract = {We briefly review modular tensor categories, a formalism for modelling anyonic theories. By considering the modular tensor category for the toric code and a functor to FdHilb, we give the semantics of surface code string diagrams in terms of circuits and the ZX-calculus. We use these tools to compile circuits to the surface code.}
}
@article{kostia2021geometry,
author = {Chardonnet, Kostia and Valiron, Benoit and Vilmart, Renaud},
title = {{Geometry of Interaction for ZX-Diagrams}},
year = {2021},
journal = {HAL preprint: hal-03154573},
urldate = {2021-03-01},
link = {https://hal.archives-ouvertes.fr/hal-03154573/},
keywords = {ZX-calculus},
abstract = {ZX-Calculus is a versatile graphical language for quantum computation equipped with an equational theory. Getting inspiration from Geometry of Interaction, in this paper we propose a token-machine based asynchronous model of both pure ZX-Calculus and its extension to mixed processes. We also show how to connect this new semantics to the usual standard interpretation of ZX-diagrams. This model allows us to have a new look at what ZX-diagrams compute, and give a more local, operational view of the semantics of ZX-diagrams.}
}
@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 = {2021},
journal = {arXiv preprint arXiv:2102.10984},
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.}
}
@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}
}
@inproceedings{rasat2021construction,
author = {Rasat, Aqilah},
title = {Construction of classical structures on N qubits by composing diagrammatic eigenbases of Pauli operators},
year = {2021},
booktitle = {AIP Conference Proceedings},
volume = {2319},
number = {1},
pages = {120001},
organization = {AIP Publishing LLC},
doi = {10.1063/5.0036992},
urldate = {2021-02-05},
link = {https://doi.org/10.1063/5.0036992},
keywords = {ZX-calculus, Strong Complementarity},
abstract = {Within the framework of Categorical Quantum Mechanics, it was found that orthogonal bases are subsumed by the so called classical structures. So, there must be classical structures which have the eigenbases of the Pauli X,Y and Z operators as their underlying bases. In this article, we propose a procedure for composing these classical structures on a single qubit which produces classical structures on multiple qubits. As a result, we can present orthogonal bases within a multiple qubit system as diagrams which makes explicit the entanglement structure of those bases.}
}
@article{carette2021graphical,
author = {Carette, Titouan and de Visme, Marc and Perdrix, Simon},
title = {{Graphical Language with Delayed Trace: Picturing Quantum Computing with Finite Memory}},
year = {2021},
journal = {arXiv preprint arXiv:2102.03133},
urldate = {2021-02-05},
link = {http://arxiv.org/abs/2102.03133},
keywords = {Completeness, Category Theory, Mixed States},
abstract = {Graphical languages, like quantum circuits or ZX-calculus, have been successfully designed to represent (memoryless) quantum computations acting on a finite number of qubits. Meanwhile, delayed traces have been used as a graphical way to represent finite-memory computations on streams, in a classical setting (cartesian data types). We merge those two approaches and describe a general construction that extends any graphical language, equipped with a notion of discarding, to a graphical language of finite memory computations. In order to handle cases like the ZX-calculus, which is complete for post-selected quantum mechanics, we extend the delayed trace formalism beyond the causal case, refining the notion of causality for stream transformers. We design a stream semantics based on stateful morphism sequences and, under some assumptions, show universality and completeness results. Finally, we investigate the links of our framework with previous works on cartesian data types, signal flow graphs, and quantum channels with memories.},
video = {https://www.youtube.com/watch?v=zdPeKaDZCJs}
}
@article{carette2021when,
author = {Carette, Titouan},
title = {{When Only Topology Matters}},
year = {2021},
journal = {arXiv preprint arXiv:2102.03178},
urldate = {2021-02-04},
link = {http://arxiv.org/abs/2102.03178},
keywords = {Category Theory},
abstract = {Graphical languages are symmetric monoidal categories presented by generators and equations. The string diagrams notation allows to transform numerous axioms into low dimension topological rules we are comfortable with as three dimensional space citizens. This aspect is often referred to by the Only Topology Matters paradigm (OTM). However OTM remains quite informal and its exact meaning in terms of rewriting rules is ambiguous. In this paper we define three precise aspects of the OTM paradigm, namely flexsymmetry, flexcyclicity and flexibility of Frobenius algebras. We investigate how this new framework can simplify the presentation of known graphical languages based on Frobenius algebras.},
video = {https://www.youtube.com/watch?v=oZv_SLClh0M}
}
@article{zhao2021analyzing,
author = {Zhao, Chen and Gao, Xiao-Shan},
title = {{Analyzing the barren plateau phenomenon in training quantum neural network with the ZX-calculus}},
year = {2021},
journal = {arXiv preprint arXiv:2102.01828},
urldate = {2021-02-03},
link = {http://arxiv.org/abs/2102.01828},
keywords = {Variational Circuits, ZX-calculus, Applied},
abstract = {In this paper, we propose a general scheme to analyze the barren plateau phenomenon in training quantum neural networks with the ZX-calculus. More precisely, we extend the barren plateaus theorem from unitary 2-design circuits to any parameterized quantum circuits under certain reasonable assumptions. The main technical contribution of this paper is representing certain integrations as ZX-diagrams and computing them with the ZX-calculus. The method is used to analyze four concrete quantum neural networks with different structures. It is shown that, for the hardware efficient ansatz and the MPS-inspired ansatz, there exist barren plateaus, while for the QCNN and the tree tensor network ansatz, there exists no barren plateau.},
video = {https://www.youtube.com/watch?v=dFryJQIV0-k}
}
@article{abbaszadeh2021parametrized,
author = {Abbaszadeh, Mina and Shahin Mousavi, S. and Salari, Vahid},
title = {{Parametrized Quantum Circuits of Synonymous Sentences in Quantum Natural Language Processing}},
year = {2021},
journal = {arXiv preprint arXiv:2102.02204},
urldate = {2021-02-02},
link = {http://arxiv.org/abs/2102.02204},
keywords = {NLP, ZX-calculus, Applied},
abstract = {In this paper, we develop a compositional vector-based semantics of positive transitive sentences in quantum natural language processing for a non-English language, i.e. Persian, to compare the parametrized quantum circuits of two synonymous sentences in two languages, English and Persian. By considering grammar+meaning of a transitive sentence, we translate DisCoCat diagram via ZX-calculus into quantum circuit form. Also, we use a bigraph method to rewrite DisCoCat diagram and turn into quantum circuit in the semantic side.}
}
@phdthesis{wetering2021thesis,
author = {van de Wetering, John},
title = {{Quantum Theory from Principles, Quantum Software from Diagrams}},
year = {2021},
school = {Radboud University Nijmegen},
urldate = {2021-01-10},
link = {https://arxiv.org/abs/2101.03608},
keywords = {ZX-calculus, Optimisation, MBQC, Phase Gadgets, Local Complementation},
abstract = {This thesis consists of two parts. The first part is about how quantum theory can be recovered from first principles, while the second part is about the application of diagrammatic reasoning, specifically the ZX-calculus, to practical problems in quantum computing. The main results of the first part include a reconstruction of quantum theory from principles related to properties of sequential measurement and a reconstruction based on properties of pure maps and the mathematics of effectus theory. It also includes a detailed study of JBW-algebras, a type of infinite-dimensional Jordan algebra motivated by von Neumann algebras. In the second part we find a new model for measurement-based quantum computing, study how measurement patterns in the one-way model can be simplified and find a new algorithm for extracting a unitary circuit from such patterns. We use these results to develop a circuit optimisation strategy that leads to a new normal form for Clifford circuits and reductions in the T-count of Clifford+T circuits.}
}
@article{vandewetering2020zxcalculus,
author = {van de Wetering, John},
title = {{ZX-calculus for the working quantum computer scientist}},
year = {2020},
journal = {arXiv preprint arXiv:2012.13966},
urldate = {2020-12-27},
link = {http://arxiv.org/abs/2012.13966},
keywords = {ZX-calculus, ZH-calculus, ZW-calculus, MBQC, Completeness, Applied, Category Theory, Mixed States, Clifford Fragment},
abstract = {The ZX-calculus is a graphical language for reasoning about quantum computation that has recently seen an increased usage in a variety of areas such as quantum circuit optimisation, surface codes and lattice surgery, measurement-based quantum computation, and quantum foundations. The first half of this review gives a gentle introduction to the ZX-calculus suitable for those familiar with the basics of quantum computing. The aim here is to make the reader comfortable enough with the ZX-calculus that they could use it in their daily work for small computations on quantum circuits and states. The latter sections give a condensed overview of the literature on the ZX-calculus. We discuss Clifford computation and graphically prove the Gottesman-Knill theorem, we discuss a recently introduced extension of the ZX-calculus that allows for convenient reasoning about Toffoli gates, and we discuss the recent completeness theorems for the ZX-calculus that show that, in principle, all reasoning about quantum computation can be done using ZX-diagrams. Additionally, we discuss the categorical and algebraic origins of the ZX-calculus and we discuss several extensions of the language which can represent mixed states, measurement, classical control and higher-dimensional qudits.}
}
@article{carette2020note,
author = {Carette, Titouan},
title = {{A note on diagonal gates in SZX-calculus}},
year = {2020},
journal = {arXiv preprint arXiv:2012.09540},
urldate = {2020-12-17},
link = {http://arxiv.org/abs/2012.09540},
keywords = {Scalable ZX, Phase Gadgets, Fourier, ZH-calculus, Hypergraph, Tempered, Graph States},
abstract = {This note describes how the scalable ZXH calculus can be used to represent in a compact way the quantum gates that are diagonal in the computational basis. This includes controlled and multi-controlled Z gates, their generalizations, respectively graph and hypergraph operators, and also phase gadgets.}
}
@article{vandewetering2020constructing,
author = {van de Wetering, John},
title = {{Constructing quantum circuits with global gates}},
year = {2021},
journal = {New Journal of Physics},
volume = {23},
number = {4},
month = {4},
pages = {043015},
publisher = {{IOP Publishing}},
doi = {10.1088/1367-2630/abf1b3},
urldate = {2020-12-16},
link = {http://arxiv.org/abs/2012.09061},
keywords = {Optimisation, Phase Gadgets, ZX-supported, Applied},
abstract = {There are various gate sets that can be used to describe a quantum computation. A particularly popular gate set in the literature on quantum computing consists of arbitrary single-qubit gates and 2-qubit CNOT gates. A CNOT gate is however not always the natural multi-qubit interaction that can be implemented on a given physical quantum computer, necessitating a compilation step that transforms these CNOT gates to the native gate set. A particularly interesting case where compilation is necessary is for ion trap quantum computers, where the natural entangling operation can act on more than 2 qubits and can even act globally on all qubits at once. This calls for an entirely different approach to constructing efficient circuits. In this paper we study the problem of converting a given circuit that uses 2-qubit gates to one that uses global gates. Our three main contributions are as follows. First, we find an efficient algorithm for transforming an arbitrary circuit consisting of Clifford gates and arbitrary phase gates into a circuit consisting of single-qubit gates and a number of global interactions proportional to the number of non-Clifford phases present in the original circuit. Second, we find a general strategy to transform a global gate that targets all qubits into one that targets only a subset of the qubits. This approach scales linearly with the number of qubits that are not targeted, in contrast to the exponential scaling reported in (Maslov & Nam, N. J. Phys. 2018). Third, we improve on the number of global gates required to synthesise an arbitrary n-qubit Clifford circuit from the 12n-18 reported in (Maslov & Nam, N. J. Phys. 2018) to 6n-8.},
video = {https://www.youtube.com/watch?v=M2RI1dYC214}
}
@misc{Coecke2020Video,
author = {Coecke, Bob},
title = {{Quantum Natural Language Processing}},
year = {2020},
howpublished = {Q2B 2020},
urldate = {2020-12-10},
url = {https://www.youtube.com/watch?v=wqDzn_kzQTc},
keywords = {ZX-calculus, NLP, Applied, Automation},
abstract = {Bob Coecke, Professor at the University of Oxford and Senior Scientific Advisor at Cambridge Quantum Computing, presents to attendees on December 10, 2020 at Q2B20 - Practical Quantum Computing, an annual conference hosted by QC Ware.}
}
@misc{Duncan2020Video,
author = {Duncan, Ross},
title = {{Algorithm Development on Honeywell’s Quantum Computer}},
year = {2020},
howpublished = {Q2B 2020},
urldate = {2020-12-08},
url = {https://www.youtube.com/watch?v=chZ8QhTNJXo},
keywords = {ZX-calculus, MBQC, Applied, Optimisation, Automation},
abstract = {Ross Duncan, Head of Quantum Software of Cambridge Quantum Computing, presents to attendees on December 8, 2020 at Q2B20 - Practical Quantum Computing, an annual conference hosted by QC Ware.}
}
@article{coecke2020foundations,
author = {Coecke, Bob and de Felice, Giovanni and Meichanetzidis, Konstantinos and Toumi, Alexis},
title = {{Foundations for Near-Term Quantum Natural Language Processing}},
year = {2020},
journal = {arXiv preprint arXiv:2012.03755},
urldate = {2020-12-07},
link = {http://arxiv.org/abs/2012.03755},
keywords = {NLP, ZX-calculus, Applied},
abstract = {We provide conceptual and mathematical foundations for near-term quantum natural language processing (QNLP), and do so in quantum computer scientist friendly terms. We opted for an expository presentation style, and provide references for supporting empirical evidence and formal statements concerning mathematical generality. We recall how the quantum model for natural language that we employ canonically combines linguistic meanings with rich linguistic structure, most notably grammar. In particular, the fact that it takes a quantum-like model to combine meaning and structure, establishes QNLP as quantum-native, on par with simulation of quantum systems. Moreover, the now leading Noisy Intermediate-Scale Quantum (NISQ) paradigm for encoding classical data on quantum hardware, variational quantum circuits, makes NISQ exceptionally QNLP-friendly: linguistic structure can be encoded as a free lunch, in contrast to the apparently exponentially expensive classical encoding of grammar. Quantum speed-up for QNLP tasks has already been established in previous work with Will Zeng. Here we provide a broader range of tasks which all enjoy the same advantage. Diagrammatic reasoning is at the heart of QNLP. Firstly, the quantum model interprets language as quantum processes via the diagrammatic formalism of categorical quantum mechanics. Secondly, these diagrams are via ZX-calculus translated into quantum circuits. Parameterisations of meanings then become the circuit variables to be learned. Our encoding of linguistic structure within quantum circuits also embodies a novel approach for establishing word-meanings that goes beyond the current standards in mainstream AI, by placing linguistic structure at the heart of Wittgenstein's meaning-is-context.},
video = {https://www.youtube.com/watch?v=dXGnsCKLXrE}
}
@article{east2020akltstates,
author = {D. P. East, Richard and van de Wetering, John and Chancellor, Nicholas and G. Grushin, Adolfo},
title = {{AKLT-states as ZX-diagrams: diagrammatic reasoning for quantum states}},
year = {2020},
journal = {arXiv preprint arXiv:2012.01219},
urldate = {2020-12-02},
link = {http://arxiv.org/abs/2012.01219},
keywords = {Condensed Matter, ZH-calculus, PyZX, Tensor Networks, Applied},
abstract = {From Feynman diagrams to tensor networks, diagrammatic representations of computations in quantum mechanics have catalysed progress in physics. These diagrams represent the underlying mathematical operations and aid physical interpretation, but cannot generally be computed with directly. In this paper we introduce the ZXH-calculus, a graphical language based on the ZX-calculus, that we use to represent and reason about many-body states entirely graphically. As a demonstration, we express the 1D AKLT state, a symmetry protected topological state, in the ZXH-calculus by developing a representation of spins higher than 1/2 within the calculus. By exploiting the simplifying power of the ZXH-calculus rules we show how this representation straightforwardly recovers two important properties, the existence of topologically protected edge states, and the non-vanishing of a string order parameter. We furthermore show how the AKLT matrix-product state representation can be recovered from our diagrams. In addition, we provide an alternative proof that the 2D AKLT state on a hexagonal lattice can be reduced to a graph state, demonstrating that it is a universal quantum computing resource. Our results show that the ZXH-calculus is a powerful language for representing and computing with physical states entirely graphically, paving the way to develop more efficient many-body algorithms.},
video = {https://www.youtube.com/watch?v=vi-ndkgKgQY}
}
@misc{Borgna2020Video,
author = {Borgna, Agustín},
title = {{Mixed quantum-classical circuit optimization using grounds}},
year = {2020},
howpublished = {ZX seminar},
urldate = {2020-10-19},
url = {https://www.youtube.com/watch?v=-Frd8w-hTD0},
keywords = {ZX-calculus, PyZX, Optimisation, Mixed States, Applied},
abstract = {In this talk I show an extension to "Graph-theoretic simplification using ZX" (arXiv:1902.03178) to support mixed circuits with measurement and classical wires, using the ZX-ground calculus. I will present new gFlow-preserving rewrite rules that can be used with the ground generators, the extended optimization algorithm, and the extraction particularities that produce circuits with classical controls.}
}
@phdthesis{millerbakewell2020thesis,
author = {Miller-Bakewell, Hector},
title = {{Graphical calculi and their conjecture synthesis}},
year = {2020},
school = {University of Oxford},
urldate = {2020-10-08},
link = {https://arxiv.org/abs/2010.03914},
keywords = {ZX-calculus, ZQ-calculus, Automation, Quantomatic, PhD Thesis},
abstract = {Categorical Quantum Mechanics, and graphical calculi in particular, has proven to be an intuitive and powerful way to reason about quantum computing. This work continues the exploration of graphical calculi, inside and outside of the quantum computing setting, by investigating the algebraic structures with which we label diagrams. The initial aim for this was Conjecture Synthesis; the algorithmic process of creating theorems. To this process we introduce a generalisation step, which itself requires the ability to infer and then verify parameterised families of theorems. This thesis introduces such inference and verification frameworks, in doing so forging novel links between graphical calculi and fields such as Algebraic Geometry and Galois Theory. These frameworks inspired further research into the design of graphical calculi, and we introduce two important new calculi here. First is the calculus RING, which is initial among ring-based qubit graphical calculi, and in turn inspired the introduction and classification of phase homomorphism pairs also presented here. The second is the calculus ZQ, an edge-decorated calculus which naturally expresses arbitrary qubit rotations, eliminating the need for non-linear rules such as (EU) of ZX. It is expected that these results will be of use to those creating optimisation schemes and intermediate representations for quantum computing, to those creating new graphical calculi, and for those performing conjecture synthesis.}
}
@article{gorard2020zxcalculus,
author = {Gorard, Jonathan and Namuduri, Manojna and D. Arsiwalla, Xerxes},
title = {{ZX-Calculus and Extended Hypergraph Rewriting Systems I: A Multiway Approach to Categorical Quantum Information Theory}},
year = {2020},
journal = {arXiv preprint arXiv:2010.02752},
urldate = {2020-10-05},
link = {http://arxiv.org/abs/2010.02752},
keywords = {ZX-calculus, Category Theory},
abstract = {Categorical quantum mechanics and the Wolfram model offer distinct but complementary approaches to studying the relationship between diagrammatic rewriting systems over combinatorial structures and the foundations of physics; the objective of the present article is to begin elucidating the formal correspondence between the two methodologies in the context of the ZX-calculus formalism of Coecke and Duncan for reasoning diagrammatically about linear maps between qubits. After briefly summarizing the relevant formalisms, and presenting a categorical formulation of the Wolfram model in terms of adhesive categories and double-pushout rewriting systems, we illustrate how the diagrammatic rewritings of the ZX-calculus can be embedded and realized within the broader context of Wolfram model multiway systems, and illustrate some of the capabilities of the software framework (ZXMultiwaySystem) that we have developed specifically for this purpose. Finally, we present a proof (along with an explicitly computed example) based on the methods of Dixon and Kissinger that the multiway evolution graphs and branchial graphs of the Wolfram model are naturally endowed with a monoidal structure based on rulial composition that is, furthermore, compatible with the monoidal product of ZX-diagrams.}
}
@misc{Kissinger2020Video,
author = {Kissinger, Aleks},
title = {{Sparsifying ZX-diagrams for CNOT count}},
year = {2020},
howpublished = {ZX seminar},
urldate = {2020-10-05},
url = {https://www.youtube.com/watch?v=twtCQ-XF9f8},
keywords = {ZX-calculus, PyZX, Optimisation, Applied},
abstract = {Reducing ZX-diagrams using the technique from "Graph-theoretic simplification" (arXiv:1902.03178) does not result in unique normal forms, but rather one of many equivalent diagrams modulo local complementation and pivoting. The particular choice of normal form can then have a big effect on the CNOT count of the resulting diagram. In this talk, I will show some preliminary efforts to explore this space and use simulated annealing to get the CNOT count down.}
}
@misc{Chen2020Video,
author = {Chen, Zhao},
title = {{ZXCalculus.jl - A Julia package for ZX Calculus for Yao.jl}},
year = {2020},
howpublished = {ZX seminar},
urldate = {2020-09-21},
url = {https://www.youtube.com/watch?v=LnzEf0pWQcs},
keywords = {ZX-calculus, Automation, Optimisation, Applied},
abstract = {ZXCalculus.jl is a Google Summer of Code (GSoC) 2020 project developed this summer to enable Yao's newly developed compiler to be able to simplify quantum circuits using ZX calculus. It is highly inspired by the python project pyzx, and with some custom tweaks. In this talk, we will briefly introduce the Yao's ecosystem in the Julia programming language and give people a tutorial on how to use this ZXCalculus package.}
}
@inproceedings{carette2020recipe,
author = {Carette, Titouan and Jeandel, Emmanuel},
title = {{A Recipe for Quantum Graphical Languages}},
year = {2020},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {168},
pages = {118:1--118:17},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
isbn = {978-3-95977-138-2},
issn = {1868-8969},
doi = {10.4230/LIPIcs.ICALP.2020.118},
urldate = {2020-08-10},
link = {http://arxiv.org/abs/2008.04193},
url = {https://drops.dagstuhl.de/opus/volltexte/2020/12525},
keywords = {ZX-calculus, ZW-calculus, ZH-calculus, Foundations},
abstract = {Different graphical calculi have been proposed to represent quantum computation. First the ZX- calculus [4], followed by the ZW-calculus [12] and then the ZH-calculus [1]. We can wonder if new Z*-calculi will continue to be proposed forever. This article answers negatively. All those language share a common core structure we call Z*-algebras. We classify Z*-algebras up to isomorphism in two dimensional Hilbert spaces and show that they are all variations of the aforementioned calculi. We do the same for linear relations and show that the calculus of [2] is essentially the unique one.}
}
@misc{Gidney2020Video,
author = {Gidney, Craig},
title = {{A Rosetta Stone for the ZX Calculus and the Surface Code}},
year = {2020},
howpublished = {ZX seminar},
urldate = {2020-08-03},
url = {https://www.youtube.com/watch?v=1ojXEEm_JiI},
keywords = {ZX-calculus, Lattice Surgery, Surface Code, Applied},
abstract = {This is a talk I gave to a ZX calculus reading group, about thinking tools for translating surface code constructions into ZX graphs.}
}
@article{miguelsignorelli2020compositional,
author = {Miguel Signorelli, Camilo and Wang, Quanlong and Khan, Ilyas},
title = {{A Compositional Model of Consciousness based on Consciousness-Only}},
year = {2020},
journal = {arXiv preprint arXiv:2007.16138},
urldate = {2020-07-31},
link = {http://arxiv.org/abs/2007.16138},
keywords = {Qudits, Algebraic ZX, Foundations},
abstract = {Scientific studies of consciousness rely on objects whose existence is independent of any consciousness. This theoretical-assumption leads to the "hard problem" of consciousness. We avoid this problem by assuming consciousness to be fundamental, and the main feature of consciousness is characterized as being other-dependent. We set up a framework which naturally subsumes the other-dependent feature by defining a compact closed category where morphisms represent conscious processes. These morphisms are a composition of a set of generators, each being specified by their relations with other generators, and therefore other-dependent. The framework is general enough, i.e. parameters in the morphisms take values in arbitrary commutative semi-rings, from which any finitely dimensional system can be dealt with. Our proposal fits well into a compositional model of consciousness and is an important step forward that addresses both the hard problem of consciousness and the combination problem of (proto)-panpsychism.}
}
@article{wang2020algebraic,
author = {Wang, Quanlong},
title = {{Algebraic complete axiomatisation of ZX-calculus with a normal form via elementary matrix operations}},
year = {2020},
journal = {arXiv preprint arXiv:2007.13739},
urldate = {2020-07-26},
link = {http://arxiv.org/abs/2007.13739},
keywords = {ZX-calculus, Completeness, Algebraic ZX},
abstract = {In this paper we give a complete axiomatisation of qubit ZX-calculus via elementary transformations which are basic operations in linear algebra. This formalism has two main advantages. First, all the operations of the phases are algebraic ones without trigonometry functions involved, thus paved the way for generalising complete axiomatisation of qubit ZX-calculus to qudit ZX-calculus and ZX-calculus over commutative semirings. Second, we characterise elementary transformations in terms of ZX diagrams, so a lot of linear algebra stuff can be done purely diagrammatically.},
video = {https://www.youtube.com/watch?v=9V6up7hpqZw}
}
@article{cowtan2020generic,
author = {Cowtan, Alexander and Simmons, Will and Duncan, Ross},
title = {{A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz}},
year = {2020},
journal = {arXiv preprint arXiv:2007.10515},
urldate = {2020-07-20},
link = {http://arxiv.org/abs/2007.10515},
keywords = {Optimisation, Phase gadgets, Applied, ZX-supported},
abstract = {We describe a compilation strategy for Variational Quantum Eigensolver (VQE) algorithms which use the Unitary Coupled Cluster (UCC) ansatz, designed to reduce circuit depth and gate count. This is achieved by partitioning Pauli exponential terms into mutually commuting sets. These sets are then diagonalised using Clifford circuits and synthesised using the phase polynomial formalism. This strategy reduces cx depth by 75.4\% on average, and by up to 89.9\%, compared to naive synthesis for a variety of molecules, qubit encodings and basis sets.}
}
@article{kumarbishwas2020parts,
author = {Kumar Bishwas, Arit and Mani, Ashish and Palade, Vasile},
title = {{Parts of Speech Tagging in NLP: Runtime Optimization with Quantum Formulation and ZX Calculus}},
year = {2020},
journal = {arXiv preprint arXiv:2007.10328},
urldate = {2020-07-19},
link = {http://arxiv.org/abs/2007.10328},
keywords = {Optimisation, NLP, Applied, ZX-Supported},
abstract = {This paper proposes an optimized formulation of the parts of speech tagging in Natural Language Processing with a quantum computing approach and further demonstrates the quantum gate-level runnable optimization with ZX-calculus, keeping the implementation target in the context of Noisy Intermediate Scale Quantum Systems (NISQ). Our quantum formulation exhibits quadratic speed up over the classical counterpart and further demonstrates the implementable optimization with the help of ZX calculus postulates.}
}
@article{carette2020colored,
author = {Carette, Titouan and Perdrix, Simon},
title = {{Colored props for large scale graphical reasoning}},
year = {2020},
journal = {arXiv preprint arXiv:2007.03564},
urldate = {2020-07-07},
link = {http://arxiv.org/abs/2007.03564},
keywords = {Completeness, Scalable ZX, Category Theory},
abstract = {The prop formalism allows representation of processes withstring diagrams and has been successfully applied in various areas such as quantum computing, electric circuits and control flow graphs. However, these graphical approaches suffer from scalability problems when it comes to writing large diagrams. A proposal to tackle this issue has been investigated for ZX-calculus using colored props. This paper extends the approach to any prop, making it a general tool for graphical languages manipulation.}
}
@misc{Backens2020Video,
author = {Backens, Miriam},
title = {{Measurement-based quantum computing (MBQC) in the ZX-calculus}},
year = {2020},
howpublished = {ZX seminar},
urldate = {2020-06-29},
url = {https://www.youtube.com/watch?v=0KYkTWdvNmo},
keywords = {ZX-calculus, MBQC, Applied},
abstract = {}
}
@misc{Wang2020Video,
author = {Wang, Quanglong},
title = {{Enter a visual era: process theory embodied in ZX-calculus}},
year = {2020},
howpublished = {QPL 2020},
urldate = {2020-06-06},
url = {https://www.youtube.com/watch?v=cZ4CSkTJ8vA},
keywords = {ZX-calculus, Triangle, Algebraic ZX, Completeness},
abstract = {}
}
@inproceedings{debeaudrap2020welltempered,
author = {de Beaudrap, Niel},
title = {{Well-tempered ZX and ZH Calculi}},
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 = {13-45},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.340.2},
urldate = {2020-06-03},
link = {http://arxiv.org/abs/2006.02557},
keywords = {ZX-calculus,ZH-Calculus,Tempered, Scalars},
abstract = {The ZX calculus is a mathematical tool to represent and analyse quantum operations by manipulating diagrams which in effect represent tensor networks. Two families of nodes of these networks are ones which commute with either Z rotations or X rotations, usually called "green nodes" and "red nodes" respectively. The original formulation of the ZX calculus was motivated in part by properties of the algebras formed by the green and red nodes: notably, that they form a bialgebra -- but only up to scalar factors. As a consequence, the diagram transformations and notation for certain unitary operations involve "scalar gadgets" which denote contributions to a normalising factor. We present renormalised generators for the ZX calculus, which form a bialgebra precisely. As a result, no scalar gadgets are required to represent the most common unitary transformations, and the corresponding diagram transformations are generally simpler. We also present a similar renormalised version of the ZH calculus. We obtain these results by an analysis of conditions under which various "idealised" rewrites are sound, leveraging the existing presentations of the ZX and ZH calculi.},
video = {https://www.youtube.com/watch?v=3qivz98DhA8}
}
@inproceedings{meichanetzidis2020quantum,
author = {Meichanetzidis, Konstantinos and Gogioso, Stefano and de Felice, Giovanni and Chiappori, Nicol\`o and Toumi, Alexis and Coecke, Bob},
title = {{Quantum Natural Language Processing on Near-Term Quantum Computers}},
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 = {213-229},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.340.11},
urldate = {2020-05-08},
link = {http://arxiv.org/abs/2005.04147},
keywords = {ZX-calculus, NLP, Applied},
abstract = {In this work, we describe a full-stack pipeline for natural language processing on near-term quantum computers, aka QNLP. The language modelling framework we employ is that of compositional distributional semantics (DisCoCat), which extends and complements the compositional structure of pregroup grammars. Within this model, the grammatical reduction of a sentence is interpreted as a diagram, encoding a specific interaction of words according to the grammar. It is this interaction which, together with a specific choice of word embedding, realises the meaning (or "semantics") of a sentence. Building on the formal quantum-like nature of such interactions, we present a method for mapping DisCoCat diagrams to quantum circuits. Our methodology is compatible both with NISQ devices and with established Quantum Machine Learning techniques, paving the way to near-term applications of quantum technology to natural language processing.},
video = {https://www.youtube.com/watch?v=4Tw7BO7PyV4}
}
@article{yeh2021benchmarking,
author = {Yeh, Lia and Dasgupta, Emma and Winston, Erick},
title = {{Benchmarking ZX-Calculus Circuit Optimization Against Qiskit Transpilation}},
year = {2020},
journal = {ACM SRC Grand Finals Candidates},
urldate = {2020-05-01},
link = {https://src.acm.org/binaries/content/assets/src/2020/lia-yeh.pdf},
keywords = {ZX-calculus, PyZX, Optimisation, Applied},
abstract = {Quantum hardware and algorithms researchers alike have expressed the critical need for and shortage of expertise in quantum programming languages, compilation, and computer architecture. We design, implement, and benchmark quantum compilation and visualization in PyZX, a Python tool for the ZX-calculus, applied to Qiskit, the most widely-used quantum programming language. We demonstrate correct circuit optimization by our Qiskit transpiler pass on 1000 two qubit Randomized Benchmarking circuits, reducing gate count of 29% of the circuits further than Qiskit’s default transpiler.}
}
@inproceedings{Cole2020ZXand,
author = {Comfort, Cole},
title = {{The ZX\&-calculus: A complete graphical calculus for classical circuits using spiders}},
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 = {60-90},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.340.4},
urldate = {2020-04-29},
link = {https://arxiv.org/abs/2004.05287},
keywords = { ZX\&, AND gates, Classical circuits, Completeness},
abstract = {We give a complete presentation for the fragment, ZX\&, of the ZX-calculus generated by the Z and X spiders (corresponding to copying and addition) along with the not gate and the and gate. To prove completeness, we freely add units and counits to the category TOF generated by the Toffoli gate and ancillary bits, showing that this yields the strictification of spans of powers of the two element set; and then perform a two way translation between this category and ZX\&. A translation to some extension of TOF, as opposed to some fragment of the ZX-calculus, is a natural choice because of the multiplicative nature of the Toffoli gate. To this end, we show that freely adding counits to the semi-Frobenius algebra of a discrete inverse category is the same as computing the "environment structure" of the classical structures of the base discrete inverse category. We show that in this setting, the classical channels and the discrete Cartesian completion are the same constructions. Therefore, in the case of TOF, freely adding a counit, constructing the category of quantum channels, and computing the discrete Cartesian completion are all equivalent to partial functions between powers of the two element set. By glueing together the free counit completion and the free unit completion, this yields the strictification of spans between powers of the two element set. },
video = {https://www.youtube.com/watch?v=UwAd-3louBU}
}
@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}
}
@article{meijer-vandegriend2020architectureaware,
author = {Meijer-van de Griend, Arianne and Duncan, Ross},
title = {{Architecture-aware synthesis of phase polynomials for NISQ devices}},
year = {2020},
journal = {arXiv preprint arXiv:2004.06052},
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}
}
@article{deBeaudrap2020Tcount,
author = {de Beaudrap,Niel and Bian,Xiaoning and Wang,Quanlong},
title = {{Fast and effective techniques for T-count reduction via spider nest identities}},
year = {2020},
journal = {arXiv preprint arXiv:2004.05164},
urldate = {2020-04-10},
link = {https://arxiv.org/abs/2004.05164},
keywords = {T-count, Optimisation, Applied, ZX-Supported},
abstract = {In fault-tolerant quantum computing systems, realising (approximately) universal quantum computation is usually described in terms of realising Clifford+T operations, which is to say a circuit of CNOT, Hadamard, and π/2-phase rotations, together with T operations (π/4-phase rotations). For many error correcting codes, fault-tolerant realisations of Clifford operations are significantly less resource-intensive than those of T gates, which motivates finding ways to realise the same transformation involving T-count (the number of T gates involved) which is as low as possible. Investigations into this problem [arXiv:1206.0758, 1303.2042, 1308.4134, 1601.07363, 1606.01904, 1701.00140] has led to observations that this problem is closely related to NP-hard tensor decomposition problems [arXiv:1712.01557] and is tantamount to the difficult problem of decoding exponentially long Reed-Muller codes [arXiv:1601.07363]. This problem then presents itself as one for which must be content in practise with approximate optimisation, in which one develops an array of tactics to be deployed through some pragmatic strategy. In this vein, we describe techniques to reduce the T-count, based on the effective application of "spider nest identities": easily recognised products of parity-phase operations which are equivalent to the identity operation. We demonstrate the effectiveness of such techniques by obtaining improvements in the T-counts of a number of circuits, in run-times which are typically less than the time required to make a fresh cup of coffee. }
}
@inproceedings{Lemonnier2020Hypergraph,
author = {Lemonnier, Louis and van de Wetering, John and Kissinger, Aleks},
title = {{Hypergraph Simplification: Linking the Path-sum Approach to the ZH-calculus}},
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 = {188-212},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.340.10},
urldate = {2020-03-30},
link = {https://arxiv.org/abs/2003.13564},
keywords = {ZH-calculus, Fourier, Sum-Over-Paths, Hypergraph, Local Complementation},
abstract = {The ZH-calculus is a complete graphical calculus for linear maps between qubits that admits, for example, a straightforward encoding of hypergraph states and circuits arising from the Toffoli+Hadamard gate set. In this paper, we establish a correspondence between the ZH-calculus and the path-sum formalism, a technique recently introduced by Amy to verify quantum circuits. In particular, we find a bijection between certain canonical forms of ZH-diagrams and path-sum expressions. We then introduce and prove several new simplification rules for the ZH-calculus, which are in direct correspondence to the simplification rules of the path-sum formalism. The relatively opaque path-sum rules are shown to arise naturally as the convergence of two consequences of the ZH-calculus. The first is the extension of the familiar graph-theoretic simplifications based on local complementation and pivoting to their hypergraph-theoretic analogues: hyper-local complementation and hyper-pivoting. The second is the graphical Fourier transform introduced by Kuijpers et al., which enables effective simplification of ZH-diagrams encoding multi-linear phase polynomials with arbitrary real coefficients.},
video = {https://www.youtube.com/watch?v=YVKup5ppqSU}
}
@article{MillerBakewell2020ZQ,
author = {Hector Miller-Bakewell},
title = {{Entanglement and Quaternions: The graphical calculus ZQ}},
year = {2020},
journal = {arXiv preprint arXiv:2003.09999},
urldate = {2020-03-22},
link = {https://arxiv.org/abs/2003.09999},
keywords = {ZQ-Calculus,Quaternions, Completeness},
abstract = {Graphical calculi are vital tools for representing and reasoning about quantum circuits and processes. Some are not only graphically intuitive but also logically complete. The best known of these is the ZX-calculus, which is an industry candidate for an Intermediate Representation; a language that sits between the algorithm designer's intent and the quantum hardware's gate instructions. The ZX calculus, built from generalised Z and X rotations, has difficulty reasoning about arbitrary rotations. This contrasts with the cross-hardware compiler TriQ which uses these arbitrary rotations to exploit hardware efficiencies. In this paper we introduce the graphical calculus ZQ, which uses quaternions to represent these arbitrary rotations, similar to TriQ, and the phase-free Z spider to represent entanglement, similar to ZX. We show that this calculus is sound and complete for qubit quantum computing, while also showing that a fully spider-based representation would have been impossible. This new calculus extends the zoo of qubit graphical calculi, each with different strengths, and we hope it will provide a common language for the optimisation procedures of both ZX and TriQ.}
}
@inproceedings{pathsRenaud,
author = {Renaud Vilmart},
title = {{The Structure of Sum-Over-Paths, its Consequences, and Completeness for Clifford}},
year = {2021},
booktitle = {Foundations of Software Science and Computation Structures},
editor = {Kiefer, Stefan and Tasson, Christine},
pages = {531--550},
publisher = {Springer International Publishing},
address = {Cham},
isbn = {978-3-030-71995-1},
doi = {10.1007/978-3-030-71995-1_27},
urldate = {2020-03-12},
link = {https://arxiv.org/abs/2003.05678},
keywords = {ZH-Calculus,Clifford Fragment,Sum-Over-Paths },
abstract = {We show that the formalism of "Sum-Over-Path" (SOP), used for symbolically representing linear maps or quantum operators, together with a proper rewrite system, has a structure of dagger-compact PROP. Several consequences arise from this observation: 1) Morphisms of SOP are very close to the diagrams of the graphical calculus called ZH-Calculus, so we give a system of interpretation between the two; 2) A construction, called the discard construction, can be applied to enrich the formalism so that, in particular, it can represent the quantum measurement. We also enrich the rewrite system so as to get the completeness of the Clifford fragments of both the initial formalism and its enriched version.}
}
@article{Backens2020extraction,
author = {Backens, Miriam and Miller-Bakewell, Hector and de Felice, Giovanni and Lobski, Leo and van de Wetering, John},
title = {{There and back again: A circuit extraction tale}},
year = {2021},
journal = {{Quantum}},
volume = {5},
month = {3},
pages = {421},
publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
issn = {2521-327X},
doi = {10.22331/q-2021-03-25-421},
urldate = {2020-03-03},
link = {https://arxiv.org/abs/2003.01664},
keywords = {ZX-Calculus, circuit extraction, MBQC, gflow, Optimisation, Graph States, Phase Gadgets, Applied},
abstract = {We give the first circuit-extraction algorithm to work for one-way computations containing measurements in all three planes and having gflow. The algorithm is efficient and the resulting circuits do not contain ancillae. One-way computations are represented using the ZX-calculus, hence the algorithm also represents the most general known procedure for extracting circuits from ZX-diagrams. In developing this algorithm, we generalise several concepts and results previously known for computations containing only XY-plane measurements. We bring together several known rewrite rules for measurement patterns and formalise them in a unified notation using the ZX-calculus. These rules are used to simplify measurement patterns by reducing the number of qubits while preserving both the semantics and the existence of gflow. The results can be applied to circuit optimisation by translating circuits to patterns and back again.},
video = {https://www.youtube.com/watch?v=Orilw6ujWag}
}
@mastersthesis{KupperThesis,
author = {Kupper, Mateusz},
title = {{Analysis of quantum hypergraph states in the ZH-calculus}},
year = {2019},
school = {University of Edinburgh},
urldate = {2020-01-01},
link = {https://www.researchgate.net/publication/339377025_Analysis_of_quantum_hypergraph_states_in_the_ZH-calculus},
keywords = {ZH-Calculus, MBQC, Hypergraph, Graph States, Master Thesis},
abstract = {In this dissertation, we prove the known quantum hypergraph state manipulation rules, and introduce metarules for showing the correctness of measurement-based quantum computing (MBQC) resource states and measurement patterns in the ZH-calculus. In particular, we study the action of local Pauli operators on quantum hypergraph states, prove the generalisation of local complementation laws for hypergraph states and derive hypergraph transformation rules for local measurements, which have never been studied in the graphical calculus before. We then apply the derived metarules to study the two hypergraph-based MBQC states: the Union Jack state and the Takeuchi-Morimae-Hayashi state. Our examples show that the use of graphical calculus yields simple and intuitive proofs; in particular the metarules provide a formal and straightforward way of validating MBQC measurement patterns.}
}
@article{hanks2019effective,
author = {Hanks, Michael and P. Estarellas, Marta and J. Munro, William and Nemoto, Kae},
title = {{Effective Compression of Quantum Braided Circuits Aided by ZX-Calculus}},
year = {2020},
journal = {Physical Review X},
volume = {10},
issue = {4},
pages = {041030},
doi = {10.1103/PhysRevX.10.041030},
urldate = {2019-12-24},
link = {http://arxiv.org/abs/1912.11503},
keywords = {Lattice surgery, Surface Code, Optimisation, Applied},
abstract = {Mapping a quantum algorithm to any practical large-scale quantum computer will require a sequence of compilations and optimizations. At the level of fault-tolerant encoding, one likely requirement of this process is the translation into a topological circuit, for which braided circuits represent one candidate model. Given the large overhead associated with encoded circuits, it is paramount to reduce their size in terms of computation time and qubit number through circuit compression. While these optimizations have typically been performed in the language of three-dimensional diagrams, such a representation does not allow an efficient, general, and scalable approach to reduction or verification. We propose the use of the ZX-calculus as an intermediate language for braided circuit compression, demonstrating advantage by comparing results using this approach with those previously obtained for the compression of A- and Y-state distillation circuits. We then provide a benchmark of our method against a small set of Clifford+T circuits, yielding compression percentages of 77%. Our results suggest that the overheads of braided, defect-based circuits are comparable to those of their lattice-surgery counterparts, restoring the potential of this model for surface-code quantum computation.}
}
@article{ringZX,
author = {Wang, Quanlong},
title = {{On completeness of algebraic ZX-calculus over arbitrary commutative rings and semirings}},
year = {2019},
journal = {arXiv preprint arXiv:1912.01003},
urldate = {2019-12-02},
link = {https://arxiv.org/abs/1912.01003},
keywords = {ZX-calculus, Completeness, Rings},
abstract = {ZX-calculus is a strict mathematical formalism for graphical quantum computing which is based on the field of complex numbers. In this paper, we extend its power by generalising ZX-calculus to such an extent that it both in an arbitrary commutative ring and an arbitrary commutative semiring. We follow the framework of arXiv:2007.13739 to prove that the proposed ZX-calculus over an arbitrary commutative ring is complete for matrices over the same ring, via a normal form inspired from matrix elementary operations such as row addition and row multiplication. This work paves the way for doing elementary number theory in string diagrams. The proof of completeness for ZX-calculus over arbitrary commutative semirings is quite similar, whose details will be provided in a forthcoming version.}
}
@mastersthesis{borghans2019masters,
author = {Borghans, Coen},
title = {{ZX-Calculus and Quantum Stabilizer Theory}},
year = {2019},
school = {Radboud University},
urldate = {2019-11-20},
link = {https://www.cs.ox.ac.uk/people/aleks.kissinger/papers/borghans-thesis.pdf},
keywords = {ZX-Calculus, Clifford Fragment, Master Thesis},
abstract = {We will look at how we can convert between ZX-Calculus and stabilizer theory. This means that we develop a procedure to find stabilizers for a given state in the ZX-Calculus as well as a method to create a ZX-state for a given set of stabilizers. These are then presented as algorithms that can be efficiently implemented.}
}
@inproceedings{deBeaudrap2020Techniques,
author = {de Beaudrap, Niel and Bian, Xiaoning and Wang, Quanlong},
title = {{Techniques to Reduce $\pi/4$-Parity-Phase Circuits, Motivated by the ZX Calculus}},
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 = {131-149},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.318.9},
urldate = {2019-11-20},
link = {https://arxiv.org/abs/1911.09039},
keywords = {Optimisation, T-count, Clifford+T, ZX-calculus, Applied, ZX-Supported},
abstract = {To approximate arbitrary unitary transformations on one or more qubits, one must perform transformations which are outside of the Clifford group. The gate most commonly considered for this purpose is the T=diag(1,exp(i\pi/4)) gate. As T gates are computationally expensive to perform fault-tolerantly in the most promising error-correction technologies, minimising the "T-count" (the number of T gates) required to realise a given unitary in a Clifford+T circuit is of great interest. We describe techniques to find circuits with reduced T-count in unitary circuits, which develop on the ideas of Heyfron and Campbell [arXiv:1712.01557] with the help of the ZX calculus. Following [arXiv:1712.01557], we reduce the problem to that of minimising the T count of a CNOT+T circuit. The ZX calculus motivates a further reduction to simplifying a product of commuting "\pi/4-parity-phase" operations: diagonal unitary transformations which induce a relative phase of exp(i\pi/4) depending on the outcome of a parity computation on the standard basis (which motivated Kissinger and van de Wetering [1903.10477] to introduce "phase gadgets"). For a number of standard benchmark circuits, we show that these techniques --- in some cases supplemented by the TODD subroutine of Heyfron and Campbell [arXiv:1712.01557] --- yield T-counts comparable to or better than the best previously known results.}
}
@inproceedings{Wang2019Algebraic,
author = {Wang, Quanlong},
title = {{An Algebraic Axiomatisation of ZX-calculus}},
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 = {303-332},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.340.16},
urldate = {2019-11-15},
link = {https://arxiv.org/abs/1911.06752},
keywords = {ZX-calculus, ZH-calculus, Completeness, Algebraic ZX},
abstract = {In this paper we give an algebraic complete axiomatisation of ZX-calculus in the sense that there are only ring operations involved for phases, without any need of trigonometry functions such as sin and cos, in contrast to previous universally complete axiomatisations of ZX-calculus. With this algebraic axiomatisation of ZX-calculus, we are able to establish an invertible translation from ZH-calculus to ZX-calculus and to derive all the ZX-translated rules of ZH-calculus. As a consequence, we have a great benefit that all techniques obtained in ZH-calculus can be transplanted to ZX-calculus. }
}
@inproceedings{Munson2019ANDgates,
author = {Munson, Anthony and Coecke, Bob and Wang, Quanlong},
title = {{AND-gates in ZX-calculus: Spider Nest Identities and QBC-completeness}},
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 = {230-255},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.340.12},
urldate = {2019-10-15},
link = {https://arxiv.org/abs/1910.06818},
keywords = {Phase Gadgets, Completeness, ZX-calculus, AND gates},
abstract = {In this note we exploit the utility of the triangle symbol in ZX-calculus, and its role within the ZX-representation of AND-gates in particular. First, we derive a decomposition theorem for large phase gadgets, something that is of key importance to recent developments in quantum circuit optimisation and T-count reduction in particular. Then, using the same rule set, we prove a completeness theorem for quantum Boolean circuits (QBCs), which adds to the plethora of complete reasoning systems under the umbrella of ZX-calculus. }
}
@phdthesis{vilmart2019thesis,
author = {Vilmart, Renaud},
title = {{ZX-Calculi for Quantum Computing and their Completeness}},
year = {2019},
school = {Loria, Universit\'e de Lorraine},
urldate = {2019-09-19},
link = {https://hal.archives-ouvertes.fr/tel-02395443/document},
keywords = {ZX-calculus, ZW-calculus, Completeness, triangle, PhD Thesis},
abstract = {The ZX-Calculus is a powerful and intuitive graphical language, based on category theory, that allows for quantum reasoning and computing. Quantum evolutions are seen in this formalism as open graphs, or diagrams, that can be transformed locally according to a set of axioms that preserve the result of the computation. One of the most important aspects of language is its completeness: Given two diagrams that represent the same quantum evolution, can I transform one into the other using only the graphical rules allowed by the language? If this is the case, it means that the graphical language captures quantum mechanics entirely. The language is known to be complete for a particular subclass (or fragment) of quantum evolutions, called Clifford. Unfortunately, this one is not universal: we cannot represent, or even approach, certain quantum evolutions. In this thesis, we propose to extend the set of axioms to obtain completeness for larger fragments of the language, which in particular are approximately universal, or even universal. To do this, we first use the completeness of another graphical language and transport this result to the ZX-Calculus. In order to simplify this tedious step, we introduce an intermediate language, interesting in itself as it captures a particular but universal fragment of quantum mechanics: Toffoli-Hadamard. We then define the notion of a linear diagram, which provides a uniform proof for some sets of equations. We also define the notion of singular value decomposition of a diagram, which allows us to avoid a large number of calculations. In a second step, we define a normal form that exists for an infinite number of...}
}
@mastersthesis{comfort2019masters,
author = {Comfort, Cole},
title = {{Classifying reversible logic gates with ancillary bits}},
year = {2019},
school = {University of Calgary},
urldate = {2019-07-25},
link = {https://prism.ucalgary.ca/handle/1880/110665},
keywords = {Toffoli, Clifford Fragment, Completeness, Real Fragment, Master Thesis},
abstract = {In this thesis, two models of reversible computing are classified, and the relation of reversible computing to quantum computing is explored. First, a finite, complete set of identities is given for the symmetric monoidal category generated by the computational ancillary bits along with the controlled-not gate. In doing so, it is proven that this category is equivalent to the category of partial isomorphisms between non-empty finitely-generated commutative torsors of characteristic 2. Next, a finite, complete set of identities is given for the symmetric monoidal category generated by the computational ancillary bits along with the Toffoli gate. In doing so, it is proven that this category is equivalent to the category of partial isomorphisms between finite powers of the two element set. The relation between reversible and quantum computing is also explored. In particular, the category with the controlled-not gate as a generator is extended to be complete for the real stabilizer fragment of quantum mechanics. This is performed by translating the identities to and from the angle-free fragment of the ZX-calculus, and showing that these translations are inverse to each other.}
}
@inproceedings{Cowtan2020phasegadget,
author = {Cowtan, Alexander and Dilkes, Silas and Duncan, Ross and Simmons, Will and Sivarajah, Seyon},
title = {{Phase Gadget Synthesis for Shallow Circuits}},
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 = {213-228},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.318.13},
urldate = {2019-06-04},
link = {https://arxiv.org/abs/1906.01734},
keywords = {Phase Gadgets, Optimisation, ZX-calculus, Applied, ZX-Supported},
abstract = {We give an overview of the circuit optimisation methods used by tket, a compiler system for quantum software developed by Cambridge Quantum Computing Ltd. We focus on a novel technique based around phase gadgets, a family of multi-qubit quantum operations which occur naturally in a wide range of quantum circuits of practical interest. The phase gadgets have a simple presentation in the ZX-calculus, which makes it easy to reason about them. Taking advantage of this, we present an efficient method to translate the phase gadgets back to CNOT gates and single qubit operations suitable for execution on a quantum computer with significant reductions in gate count and circuit depth. We demonstrate the effectiveness of these methods on a quantum chemistry benchmarking set based on variational circuits for ground state estimation of small molecules.}
}
@inproceedings{gogioso2019diagrammatic,
author = {Stefano Gogioso},
title = {{A Diagrammatic Approach to Quantum Dynamics}},
year = {2019},
booktitle = {8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)},
editor = {Markus Roggenbach and Ana Sokolova},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {139},
pages = {19:1--19:23},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
isbn = {978-3-95977-120-7},
issn = {1868-8969},
doi = {10.4230/LIPIcs.CALCO.2019.19},
urldate = {2019-05-30},
link = {http://arxiv.org/abs/1905.13111},
keywords = {Strong Complementarity, Foundations},
abstract = {We present a diagrammatic approach to quantum dynamics based on the categorical algebraic structure of strongly complementary observables. We provide physical semantics to our approach in terms of quantum clocks and quantisation of time. We show that quantum dynamical systems arise naturally as the algebras of a certain dagger Frobenius monad, with the morphisms and tensor product of the category of algebras playing the role, respectively, of equivariant transformations and synchronised parallel composition of dynamical systems. We show that the Weyl Canonical Commutation Relations between time and energy are an incarnation of the bialgebra law and we derive Schr\"{o}dinger's equation from a process-theoretic perspective. Finally, we use diagrammatic symmetry-observable duality to prove Stone's proposition and von Neumann's Mean Ergodic proposition, recasting the results as two faces of the very same coin.}
}
@article{autoCCZ,
author = {Gidney, Craig and Fowler, Austin G.},
title = {{Flexible layout of surface code computations using AutoCCZ states}},
year = {2019},
journal = {arXiv preprint arXiv:1905.08916},
urldate = {2019-05-22},
link = {https://arxiv.org/abs/1905.08916},
keywords = {CCZ, Surface code, ZX-calculus, Toffoli, Lattice Surgery, Applied},
abstract = {We construct a self-correcting CCZ state (the "AutoCCZ") with embedded delayed choice CZs for completing gate teleportations. Using the AutoCCZ state we create efficient surface code spacetime layouts for both a depth-limited circuit (a ripply-carry addition) and a Clifford-limited circuit (a QROM read). Our layouts account for distillation and routing, are based on plausible physical assumptions for a large-scale superconducting qubit platform, and suggest that circuit-level Toffoli parallelism (e.g. using a carry-lookahead adder instead of a ripple-carry adder) will not reduce the execution time of computations involving fewer than five million physical qubits. We reduce the spacetime volume of delayed choice CZs by a factor of 4 compared to techniques from previous work (Fowler 2012), and make several improvements to the CCZ magic state factory from (Gidney 2019). }
}
@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^*$.}
}
@inproceedings{SZXCalculus,
author = {Titouan Carette and Dominic Horsman and Simon Perdrix},
title = {{SZX-Calculus: Scalable Graphical Quantum Reasoning}},
year = {2019},
booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
editor = {Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {138},
pages = {55:1--55:15},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
isbn = {978-3-95977-117-7},
issn = {1868-8969},
doi = {10.4230/LIPIcs.MFCS.2019.55},
urldate = {2019-04-30},
link = {https://arxiv.org/abs/1905.00041},
url = {http://drops.dagstuhl.de/opus/volltexte/2019/10999},
keywords = {ZX-calculus, Scalable ZX, Error correcting codes},
abstract = {We introduce the Scalable ZX-calculus (SZX-calculus for short), a formal and compact graphical language for the design and verification of quantum computations. The SZX-calculus is an extension of the ZX-calculus, a powerful framework that captures graphically the fundamental properties of quantum mechanics through its complete set of rewrite rules. The ZX-calculus is, however, a low level language, with each wire representing a single qubit. This limits its ability to handle large and elaborate quantum evolutions. We extend the ZX-calculus to registers of qubits and allow compact representation of sub-diagrams via binary matrices. We show soundness and completeness of the SZX-calculus and provide two examples of applications, for graph states and error correcting codes.},
urn = {urn:nbn:de:0030-drops-109999},
video = {https://www.youtube.com/watch?v=rVPPV356X4I}
}
@inproceedings{deBeaudrap2020Paulifusion,
author = {de Beaudrap, Niel and Duncan, Ross and Horsman, Dominic and Perdrix, Simon},
title = {{Pauli Fusion: a Computational Model to Realise Quantum Transformations from ZX Terms}},
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 = {85-105},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.318.6},
urldate = {2019-04-29},
link = {https://arxiv.org/abs/1904.12817},
keywords = {ZX-calculus, Lattice Surgery, Pauli Fusion, Surface Code, gflow},
abstract = {We present an abstract model of quantum computation, the Pauli Fusion model, whose primitive operations correspond closely to generators of the ZX calculus (a formal graphical language for quantum computing). The fundamental operations of Pauli Fusion are also straightforward abstractions of basic processes in some leading proposed quantum technologies. These operations have non-deterministic heralded effects, similarly to measurement-based quantum computation. We describe sufficient conditions for Pauli Fusion procedures to be deterministically realisable, so that it performs a given transformation independently of its non-deterministic outcomes. This provides an operational model to realise ZX terms beyond the circuit model.}
}
@article{comfort2019circuit,
author = {Comfort, Cole},
title = {{Circuit Relations for Real Stabilizers: Towards TOF+H}},
year = {2019},
journal = {arXiv preprint arXiv:1904.10614},
urldate = {2019-04-24},
link = {http://arxiv.org/abs/1904.10614},
keywords = {Completeness, Clifford Fragment, ZX-calculus, Toffoli, Real Fragment},
abstract = {The real stabilizer fragment of quantum mechanics was shown to have a complete axiomatization in terms of the angle-free fragment of the ZX-calculus. This fragment of the ZX-calculus---although abstractly elegant---is stated in terms of identities, such as spider fusion which generally do not have interpretations as circuit transformations. We complete the category CNOT generated by the controlled not gate and the computational ancillary bits, presented by circuit relations, to the real stabilizer fragment of quantum mechanics. This is performed first, by adding the Hadamard gate and the scalar sqrt 2 as generators. We then construct translations to and from the angle-free fragment of the ZX-calculus, showing that they are inverses. We then discuss how this could potentially lead to a complete axiomatization, in terms of circuit relations, for the approximately universal fragment of quantum mechanics generated by the Toffoli gate, Hadamard gate and computational ancillary bits.}
}
@article{GraphicalFourier2019,
author = {Kuijpers, Stach and van de Wetering, John and Kissinger, Aleks},
title = {{Graphical Fourier Theory and the Cost of Quantum Addition}},
year = {2019},
journal = {arXiv preprint arXiv:1904.07551},
urldate = {2019-04-16},
link = {https://arxiv.org/abs/1904.07551},
keywords = {ZH-calculus, ZX-calculus, Fourier, Toffoli, Phase gadgets},
abstract = {The ZX-calculus is a convenient formalism for expressing and reasoning about quantum circuits at a low level, whereas the recently-proposed ZH-calculus yields convenient expressions of mid-level quantum gates such as Toffoli and CCZ. In this paper, we will show that the two calculi are linked by Fourier transform. In particular, we will derive new Fourier expansion rules using the ZH-calculus, and show that we can straightforwardly pass between ZH- and ZX-diagrams using them. Furthermore, we demonstrate that the graphical Fourier expansion of a ZH normal-form corresponds to the standard Fourier transform of a semi-Boolean function. As an illustration of the calculational power of this technique, we then show that several tricks for reducing the T-gate cost of Toffoli circuits, which include for instance quantum adders, can be derived using graphical Fourier theory and straightforwardly generalized to more qubits.}
}
@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. }
}
@inproceedings{kissinger2019Pyzx,
author = {Kissinger, Aleks and van de Wetering, John},
title = {{PyZX: Large Scale Automated Diagrammatic Reasoning}},
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 = {229-241},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.318.14},
urldate = {2019-04-09},
link = {https://arxiv.org/abs/1904.04735},
keywords = {ZX-calculus, Optimisation, PyZX, Automation},
abstract = {The ZX-calculus is a graphical language for reasoning about ZX-diagrams, a tensor network-like language that can represent arbitrary linear maps between qubits. Using the ZX-calculus, we can intuitively reason about quantum mechanics, and optimise and validate quantum circuits. In this paper we introduce PyZX, an open source library for automated reasoning with large ZX-diagrams. We give a brief introduction to the ZX-calculus, then show how PyZX implements methods for circuit optimisation, equality validation, and visualisation and how it can be used in tandem with other software. We end with a set of challenges that when solved would expand the power of automated diagrammatic reasoning.},
video = {https://www.youtube.com/watch?v=JafI_LZts2g}
}
@article{Kissinger2020CNOT,
author = { Kissinger, Aleks and Meijer-van de Griend, Arianne },
title = {{CNOT circuit extraction for topologically-constrained quantum memories}},
year = {2020},
journal = {Quantum Information and Computation},
volume = {20},
issue = {7--8},
pages = {581--596},
doi = {10.26421/QIC20.7-8},
urldate = {2019-04-01},
link = {https://arxiv.org/abs/1904.00633},
keywords = {Optimisation, Circuit extraction, Applied, ZX-Supported},
abstract = {Many physical implementations of quantum computers impose stringent memory constraints in which 2-qubit operations can only be performed between qubits which are nearest neighbours in a lattice or graph structure. Hence, before a computation can be run on such a device, it must be mapped onto the physical architecture. That is, logical qubits must be assigned physical locations in the quantum memory, and the circuit must be replaced by an equivalent one containing only operations between nearest neighbours. In this paper, we give a new technique for quantum circuit mapping (a.k.a. routing), based on Gaussian elimination constrained to certain optimal spanning trees called Steiner trees. We give a reference implementation of the technique for CNOT circuits and show that it significantly out-performs general-purpose routines on CNOT circuits. We then comment on how the technique can be extended straightforwardly to the synthesis of CNOT+Rz circuits and as a modification to a recently-proposed circuit simplification/extraction procedure for generic circuits based on the ZX-calculus. }
}
@inproceedings{MillerBakewell2020finite,
author = {Miller-Bakewell, Hector},
title = {{Finite Verification of Infinite Families of Diagram Equations}},
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 = {27-52},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.318.3},
urldate = {2019-04-01},
link = {https://arxiv.org/abs/1904.00706},
keywords = {ZX-calculus, !-Boxes, ZH-calculus, ZW-calculus, Automation},
abstract = {The ZX, ZW and ZH calculi are all complete graphical calculi for reasoning about pure state qubit quantum mechanics. All of these languages use certain diagrammatic decorations, called !-boxes and phase variables, to indicate not just one diagram but an infinite family of diagrams. In this same manner one can express infinite families of equations between diagrams, and these decorations are powerful enough to allow for complete rulesets expressing any equivalence in pure state qubit quantum mechanics. We present here results that show that equations between separable infinite families of diagrams are finitely verifiable; that is to say that to verify these infinite families of equations it suffices to check a finite subset of that family, provided a condition we call separability is met. The results we present in this paper not only construct such a verifying subfamily directly, but also generalise to any diagrammatic calculus that satisfies certain simple conditions.}
}
@article{kissinger2019tcount,
author = {Kissinger, Aleks and van de Wetering, John},
title = {{Reducing T-count with the ZX-calculus}},
year = {2020},
journal = {Physical Review A},
volume = {102},
issue = {2},
month = {8},
pages = {022406},
numpages = {10},
publisher = {American Physical Society},
doi = {10.1103/PhysRevA.102.022406},
urldate = {2019-03-25},
link = {https://arxiv.org/abs/1903.10477},
keywords = {ZX-calculus, Clifford+T, T-count, Optimisation, PyZX, Automation, Phase Gadgets, Applied},
abstract = {Reducing the number of non-Clifford quantum gates present in a circuit is an important task for efficiently implementing quantum computations, especially in the fault-tolerant regime. We present a new method for reducing the number of T-gates in a quantum circuit based on the ZX-calculus, which matches or beats previous approaches to T-count reduction on the majority of our benchmark circuits in the ancilla-free case, in some cases yielding up to 50\% improvement. Our method begins by representing the quantum circuit as a ZX-diagram, a tensor network-like structure that can be transformed and simplified according to the rules of the ZX-calculus. We then show that a recently-proposed simplification strategy can be extended to reduce T-count using a new technique called phase teleportation. This technique allows non-Clifford phases to combine and cancel by propagating non-locally through a generic quantum circuit. Phase teleportation does not change the number or location of non-phase gates and the method also applies to arbitrary non-Clifford phase gates as well as gates with unknown phase parameters in parametrised circuits. Furthermore, the simplification strategy we use is powerful enough to validate equality of many circuits. In particular, we use it to show that our optimised circuits are indeed equal to the original ones. We have implemented the routines of this paper in the open-source library PyZX.}
}
@article{jeandel2019completeness,
author = {Jeandel, Emmanuel and Perdrix, Simon and Vilmart, Renaud},
title = {{Completeness of the ZX-Calculus}},
year = {2020},
journal = {Logical Methods in Computer Science},
month = {6},
doi = {10.23638/LMCS-16(2:11)2020},
urldate = {2019-03-13},
link = {https://arxiv.org/abs/1903.06035},
keywords = {ZX-calculus, Completeness, Triangle, Clifford+T, Universal Fragment},
abstract = {The ZX-Calculus is a graphical language for diagrammatic reasoning in quantum mechanics and quantum information theory. It comes equipped with an equational presentation. We focus here on a very important property of the language: completeness, which roughly ensures the equational theory captures all of quantum mechanics. We first improve on the known-to-be-complete presentation or the so-called Clifford fragment of the language - a restriction that is not universal - by adding some axioms. Thanks to a system of back-and-forth translation between the ZX-Calculus and a third-party complete graphical language, we prove that the provided axiomatisation is complete for the first approximately universal fragment of the language, namely Clifford+T. We then prove that the expressive power of this presentation, though aimed at achieving completeness for the aforementioned restriction, extends beyond Clifford+T, to a class of diagrams that we call linear with Clifford+T constants. We use another version of the third-party language - and an adapted system of back-and-forth translation - to complete the language for the ZX-Calculus as a whole, that is, with no restriction. We briefly discuss the added axioms, and finally, we provide a complete axiomatisation for an altered version of the language which involves an additional generator, making the presentation simpler.}
}
@inproceedings{carette_completeness_2019,
author = {Titouan Carette and Emmanuel Jeandel and Simon Perdrix and Renaud Vilmart},
title = {{Completeness of Graphical Languages for Mixed States Quantum Mechanics}},
year = {2019},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {132},
pages = {108:1--108:15},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
isbn = {978-3-95977-109-2},
issn = {1868-8969},
doi = {10.4230/LIPIcs.ICALP.2019.108},
urldate = {2019-02-19},
link = {http://arxiv.org/abs/1902.07143},
keywords = {Completeness, Category Theory, Mixed States},
abstract = {There exist several graphical languages for quantum information processing, like quantum circuits, ZX-Calculus, ZW-Calculus, etc. Each of these languages forms a dagger-symmetric monoidal category (dagger-SMC) and comes with an interpretation functor to the dagger-SMC of (finite dimension) Hilbert spaces. In the recent years, one of the main achievements of the categorical approach to quantum mechanics has been to provide several equational theories for most of these graphical languages, making them complete for various fragments of pure quantum mechanics. We address the question of the extension of these languages beyond pure quantum mechanics, in order to reason on mixed states and general quantum operations, i.e. completely positive maps. Intuitively, such an extension relies on the axiomatisation of a discard map which allows one to get rid of a quantum system, operation which is not allowed in pure quantum mechanics. We introduce a new construction, the discard construction, which transforms any dagger-symmetric monoidal category into a symmetric monoidal category equipped with a discard map. Roughly speaking this construction consists in making any isometry causal. Using this construction we provide an extension for several graphical languages that we prove to be complete for general quantum operations. However this construction fails for some fringe cases like the Clifford+T quantum mechanics, as the category does not have enough isometries.}
}
@article{duncan2019graph,
author = {Duncan, Ross and Kissinger, Aleks and Pedrix, Simon and van de Wetering, John},
title = {{Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus}},
year = {2020},
journal = {{Quantum}},
volume = {4},
month = {6},
pages = {279},
publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
issn = {2521-327X},
doi = {10.22331/q-2020-06-04-279},
urldate = {2019-02-08},
link = {https://arxiv.org/abs/1902.03178},
keywords = {ZX-calculus, Optimisation, PyZX, Automation, Local Complementation, Gflow, Applied},
abstract = {We present a completely new approach to quantum circuit optimisation, based on the ZX-calculus. We first interpret quantum circuits as ZX-diagrams, which provide a flexible, lower-level language for describing quantum computations graphically. Then, using the rules of the ZX-calculus, we give a simplification strategy for ZX-diagrams based on the two graph transformations of local complementation and pivoting and show that the resulting reduced diagram can be transformed back into a quantum circuit. While little is known about extracting circuits from arbitrary ZX-diagrams, we show that the underlying graph of our simplified ZX-diagram always has a graph-theoretic property called generalised flow, which in turn yields a deterministic circuit extraction procedure. For Clifford circuits, this extraction procedure yields a new normal form that is both asymptotically optimal in size and gives a new, smaller upper bound on gate depth for nearest-neighbour architectures. For Clifford+T and more general circuits, our technique enables us to to 'see around' gates that obstruct the Clifford structure and produce smaller circuits than naive 'cut-and-resynthesise' methods.},
video = {https://www.youtube.com/watch?v=Gt3sQgickn8}
}
@inproceedings{pinzani2019categorical,
author = {N. {Pinzani} and S. {Gogioso} and B. {Coecke}},
title = {{Categorical Semantics for Time Travel}},
year = {2019},
booktitle = {2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)},
volume = {},
number = {},
pages = {1-20},
doi = {10.1109/LICS.2019.8785664},
urldate = {2019-01-31},
link = {http://arxiv.org/abs/1902.00032},
keywords = {Category Theory, Foundations},
abstract = {We introduce a general categorical framework to reason about quantum theory and other process theories living in spacetimes where Closed Timelike Curves (CTCs) are available, allowing resources to travel back in time and provide computational speedups. Our framework is based on a weakening of the definition of traced symmetric monoidal categories, obtained by dropping the yanking axiom and the requirement that the trace be defined on all morphisms. We show that the two leading models for quantum theory with closed timelike curves---namely the P-CTC model of Lloyd et al. and the D-CTC model of Deutsch---are captured by our framework, and in doing so we provide the first compositional description of the D-CTC model. Our description of the D-CTC model results in a process theory which respects the constraints of relativistic causality: this is in direct contrast to the P-CTC model, where CTCs are implemented by a trace and allow post-selection to be performed deterministically.}
}
@inproceedings{FaganDuncan,
author = {Fagan, Andrew and Duncan, Ross},
title = {{Optimising Clifford Circuits with Quantomatic}},
year = {2019},
booktitle = {Proceedings of the 15th International Conference on Quantum Physics and Logic (QPL)},
series = {Electronic Proceedings in Theoretical Computer Science},
volume = {287},
pages = {85-105},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.287.5},
urldate = {2019-01-29},
link = {https://arxiv.org/abs/1901.10114},
keywords = {ZX-calculus, Quantomatic, Clifford Fragment, Optimisation, Automation, Applied},
abstract = {We present a system of equations between Clifford circuits, all derivable in the ZX-calculus, and formalised as rewrite rules in the Quantomatic proof assistant. By combining these rules with some non-trivial simplification procedures defined in the Quantomatic tactic language, we demonstrate the use of Quantomatic as a circuit optimisation tool. We prove that the system always reduces Clifford circuits of one or two qubits to their minimal form, and give numerical results demonstrating its performance on larger Clifford circuits.}
}
@misc{Vilmart2019Video,
author = {Vilmart, Renaud},
title = {{Completeness of the ZX-calculus}},
year = {2019},
howpublished = {QIP 2019},
urldate = {2019-01-15},
url = {https://www.youtube.com/watch?v=K59n-JE6Alc},
keywords = {ZX-calculus, Completeness, Clifford+T, Universal Fragment},
abstract = {}
}
@inproceedings{vilmarteulercompleteness,
author = {Vilmart, Renaud},
title = {{A Near-Minimal Axiomatisation of ZX-Calculus for Pure Qubit Quantum Mechanics}},
year = {2019},
booktitle = {2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)},
volume = {},
number = {},
pages = {1-10},
doi = {10.1109/LICS.2019.8785765},
urldate = {2018-12-21},
link = {https://arxiv.org/abs/1812.09114},
keywords = {ZX-calculus, Completeness, Universal Fragment, Minimality},
abstract = {Recent developments in the ZX-Calculus have resulted in complete axiomatisations first for an approximately universal restriction of the language, and then for the whole language. The main drawbacks were that the axioms that were added to achieve completeness were numerous, tedious to manipulate and lacked a physical interpretation. We present in this paper two complete axiomatisations for the general ZX-Calculus, that we believe are optimal, in that all their equations are necessary and moreover have a nice physical interpretation.}
}
@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\%$.}
}
@article{jeandel_rational_2018,
author = {Jeandel, Emmanuel},
title = {{The rational fragment of the ZX-calculus}},
year = {2018},
journal = {arXiv:1810.05377 [quant-ph]},
month = {oct},
urldate = {2018-10-12},
link = {http://arxiv.org/abs/1810.05377},
keywords = {ZX-calculus, Rational Fragment, Triangle, Completeness},
abstract = {We introduce here a new axiomatisation of the rational fragment of the ZX-calculus, a diagrammatic language for quantum mechanics. Compared to the previous axiomatisation introduced in [8], our axiomatisation does not use any metarule , but relies instead on a more natural rule, called the cyclotomic supplementarity rule, that was introduced previously in the literature. Our axiomatisation is only complete for diagrams using rational angles , and is not complete in the general case. Using results on diophantine geometry, we characterize precisely which diagram equality involving arbitrary angles are provable in our framework without any new axioms, and we show that our axiomatisation is continuous, in the sense that a diagram equality involving arbitrary angles is provable iff it is a limit of diagram equalities involving rational angles. We use this result to give a complete characterization of all Euler equations that are provable in this axiomatisation.}
}
@mastersthesis{Borun,
author = {Shi, Borun},
title = {{Towards Minimality of Clifford+T ZX-Calculus}},
year = {2018},
school = {University of Oxford},
urldate = {2018-06-30},
link = {http://www.cs.ox.ac.uk/people/bob.coecke/Borun},
keywords = {ZX-Calculus, Minimality, Master Thesis},
abstract = {ZX-calculus is a high-level graphical language used for quantum computation. A complete set of axioms for ZX-calculus has been found very recently. This thesis works towards minimizing axioms of ZX-calculus for Clifford+T quantum mechanics, a fragment consisting of an approximately universal gate set. Similar work has been done for the smaller fragment, stabilizer quantum mechanics, which motivates many of our proofs. We derive some singleton axioms and instances of axiom schemes. We establish the necessity and some weaker independence results of several axioms, by considering a variety of models. As a further step towards simplification we also consider alternative presentations of axioms that are equivalent and discuss their uses.}
}
@inproceedings{ZXNormalForm,
author = {Jeandel, Emmanuel and Perdrix, Simon and Vilmart, Renaud},
title = {{A Generic Normal Form for ZX-Diagrams and Application to the Rational Angle Completeness}},
year = {2019},
booktitle = {34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)},
series = {LICS '19},
volume = {},
number = {},
pages = {1-10},
publisher = {ACM},
doi = {10.1109/LICS.2019.8785754},
urldate = {2018-05-14},
link = {https://arxiv.org/abs/1805.05296},
keywords = {ZX-calculus, Normal-form, Rational Fragment, Completeness},
abstract = {Recent completeness results on the ZX-Calculus used a third-party language, namely the ZW-Calculus. As a consequence, these proofs are elegant, but sadly non-constructive. We address this issue in the following. To do so, we first describe a generic normal form for ZX-diagrams in any fragment that contains Clifford+T quantum mechanics. We give sufficient conditions for an axiomatisation to be complete, and an algorithm to reach the normal form. Finally, we apply these results to the Clifford+T fragment and the general ZX-Calculus -- for which we already know the completeness--, but also for any fragment of rational angles: we show that the axiomatisation for Clifford+T is also complete for any fragment of dyadic angles, and that a simple new rule (called cancellation) is necessary and sufficient otherwise.}
}
@inproceedings{EPTCS287.2,
author = {Backens, Miriam and Kissinger, Aleks},
title = {{ZH: A Complete Graphical Calculus for Quantum Computations Involving Classical Non-linearity}},
year = {2019},
booktitle = {Proceedings of the 15th International Conference on
Quantum Physics and Logic,
Halifax, Canada, 3-7th June 2018},
editor = {Selinger, Peter and Chiribella, Giulio},
series = {Electronic Proceedings in Theoretical Computer Science},
volume = {287},
pages = {23-42},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.287.2},
urldate = {2018-05-06},
link = {https://arxiv.org/abs/1805.02175},
keywords = {ZH-calculus, Completeness},
abstract = {We present a new graphical calculus that is sound and complete for a universal family of quantum circuits, which can be seen as the natural string-diagrammatic extension of the approximately (real-valued) universal family of Hadamard+CCZ circuits. The diagrammatic language is generated by two kinds of nodes: the so-called 'spider' associated with the computational basis, as well as a new arity-N generalisation of the Hadamard gate, which satisfies a variation of the spider fusion law. Unlike previous graphical calculi, this admits compact encodings of non-linear classical functions. For example, the AND gate can be depicted as a diagram of just 2 generators, compared to ~25 in the ZX-calculus. Consequently, N-controlled gates, hypergraph states, Hadamard+Toffoli circuits, and diagonal circuits at arbitrary levels of the Clifford hierarchy also enjoy encodings with low constant overhead. This suggests that this calculus will be significantly more convenient for reasoning about the interplay between classical non-linear behaviour (e.g. in an oracle) and purely quantum operations. After presenting the calculus, we will prove it is sound and complete for universal quantum computation by demonstrating the reduction of any diagram to an easily describable normal form.}
}
@inproceedings{coecke2018zx,
author = {Coecke, Bob and Wang, Quanlong},
title = {{ZX-rules for 2-qubit Clifford+ T quantum circuits}},
year = {2018},
booktitle = {International Conference on Reversible Computation},
pages = {144--161},
organization = {Springer},
doi = {10.1007/978-3-319-99498-7\_10},
urldate = {2018-04-15},
link = {https://arxiv.org/abs/1804.05356},
keywords = {ZX-Calculus, Completeness, Clifford+T},
abstract = {ZX-calculus is a high-level graphical formalism for qubit computation. In this paper we give the ZX-rules that enable one to derive all equations between 2-qubit Clifford+T quantum circuits. Our rule set is only a small extension of the rules of stabilizer ZX-calculus, and substantially less than those needed for the recently achieved universal completeness. One of our rules is new, and we expect it to also have other utilities.
These ZX-rules are much simpler than the complete of set Clifford+T circuit equations due to Selinger and Bian, which indicates that ZX-calculus provides a more convenient arena for quantum circuit rewriting than restricting oneself to circuit equations. The reason for this is that ZX-calculus is not constrained by a fixed unitary gate set for performing intermediate computations.}
}
@inproceedings{EPTCS287.18,
author = {Vilmart, Renaud},
title = {{A ZX-Calculus with Triangles for Toffoli-Hadamard, Clifford+T, and Beyond}},
year = {2019},
booktitle = {Proceedings of the 15th International Conference on
Quantum Physics and Logic,
Halifax, Canada, 3-7th June 2018},
editor = {Selinger, Peter and Chiribella, Giulio},
series = {Electronic Proceedings in Theoretical Computer Science},
volume = {287},
pages = {313-344},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.287.18},
urldate = {2018-04-09},
link = {https://arxiv.org/abs/1804.03084},
keywords = {ZX-calculus, Completeness, Toffoli, Triangle},
abstract = {We consider a ZX-calculus augmented with triangle nodes which is well-suited to reason on the so-called Toffoli-Hadamard fragment of quantum mechanics. We precisely show the form of the matrices it represents, and we provide an axiomatisation which makes the language complete for the Toffoli-Hadamard quantum mechanics. We extend the language with arbitrary angles and show that any true equation involving linear diagrams which constant angles are multiple of Pi are derivable. We show that a single axiom is then necessary and sufficient to make the language equivalent to the ZX-calculus which is known to be complete for Clifford+T quantum mechanics. As a by-product, it leads to a new and simple complete axiomatisation for Clifford+T quantum mechanics.}
}
@inproceedings{EPTCS266.3,
author = {Wang, Quanlong},
title = {{Qutrit ZX-calculus is Complete for Stabilizer Quantum Mechanics}},
year = {2018},
booktitle = {Proceedings 14th International Conference on
Quantum Physics and Logic,
Nijmegen, The Netherlands, 3-7 July 2017},
editor = {Coecke, Bob and Kissinger, Aleks},
series = {Electronic Proceedings in Theoretical Computer Science},
volume = {266},
pages = {58-70},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.266.3},
urldate = {2018-03-02},
link = {https://arxiv.org/abs/1803.00696},
keywords = {ZX-calculus, Qutrits, Clifford Fragment},
abstract = {In this paper, we show that a qutrit version of ZX-calculus, with rules significantly different from that of the qubit version, is complete for pure qutrit stabilizer quantum mechanics, where state preparations and measurements are based on the three dimensional computational basis, and unitary operations are required to be in the generalized Clifford group. This means that any equation of diagrams that holds true under the standard interpretation in Hilbert spaces can be derived diagrammatically. In contrast to the qubit case, the situation here is more complicated due to the richer structure of this qutrit ZX-calculus.},
video = {https://www.youtube.com/watch?v=eXyuV6G8800}
}
@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.}
}
@phdthesis{ng2018thesis,
author = {Ng, Kang Feng},
title = {{Completeness of the ZW and ZX calculi}},
year = {2018},
school = {University of Oxford},
urldate = {2018-02-26},
link = {http://www.cs.ox.ac.uk/people/bob.coecke/KangFeng.pdf},
keywords = {ZX-calculus, ZW-calculus, Completeness, triangle, qudits, qutrits, PhD Thesis},
abstract = {The quantum circuit formalism is good as it abstracts quantum processes while keeping in mind what are the allowed processes in laboratories. However, because of this, it is kind of restricting. It will be desirable to have a higher level language which provides further abstraction. This is where ZX and ZW calculus comes in. These two calculi are diagrammatic abstraction of quantum operations, similar to quantum circuits, but is more liberal than the circuit formalism.
Abstraction may be good, but it is, after all, not the actual thing; there are
limitations to how much the abstraction can reason about the systems. This is the
concept of completeness. If an abstraction can capture all of the system’s dynamics, then we say that it is complete. The circuit formalism and the ZX calculus are known to be incomplete, and it greatly limits their ability to reason quantum operations. This thesis is about completeness, but we won’t explore the completeness of the quantum circuit formalism; we will present a ZX calculus that is complete. The ZW calculus is complete, but it is hard to make connections to the implementable quantum operations. We could modify the calculus to obtain a calculus that is closely related to what is called fermionic circuits, but then this calculus is not known to be complete. In this thesis, we will complete it. As a bonus, we will show an even more restricted version, that may have connections to the understanding of the universe, which is complete. This may be an useful abstraction for the study of the fundamental properties of fermions.
The gist of the thesis is not about the complete ZW and ZX calculi; it is the
formula to produce a complete diagrammatic calculus.}
}
@inproceedings{JPV-universal,
author = {Jeandel, Emmanuel and Perdrix, Simon and Vilmart, Renaud},
title = {{Diagrammatic Reasoning Beyond Clifford+T Quantum Mechanics}},
year = {2018},
booktitle = {Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science},
series = {LICS '18},
pages = {569--578},
numpages = {10},
publisher = {ACM},
acmid = {3209139},
address = {New York, NY, USA},
isbn = {978-1-4503-5583-4},
location = {Oxford, United Kingdom},
doi = {10.1145/3209108.3209139},
urldate = {2018-01-30},
link = {https://arxiv.org/abs/1801.10142},
keywords = {ZX-calculus, Completeness, Triangle, Universal Fragment},
abstract = {The ZX-Calculus is a graphical language for quantum mechanics. An axiomatisation has recently been proven to be complete for an approximatively universal fragment of quantum mechanics, the so-called Clifford+T fragment. We focus here on the expressive power of this axiomatisation beyond Clifford+T Quantum mechanics. We consider the full pure qubit quantum mechanics, and mainly prove two results: (i) First, the axiomatisation for Clifford+T quantum mechanics is also complete for all equations involving some kind of linear diagrams. The linearity of the diagrams reflects the phase group structure, an essential feature of the ZX-calculus. In particular all the axioms of the ZX-calculus are involving linear diagrams. (ii) We also show that the axiomatisation for Clifford+T is not complete in general but can be completed by adding a single (non linear) axiom, providing a simpler axiomatisation of the ZX-calculus for pure quantum mechanics than the one recently introduced by Ng&Wang.}
}
@article{ng_completeness_2018,
author = {Ng, Kang Feng and Wang, Quanlong},
title = {{Completeness of the ZX-calculus for Pure Qubit Clifford+T Quantum Mechanics}},
year = {2018},
journal = {arXiv:1801.07993},
month = {1},
urldate = {2018-01-22},
link = {http://arxiv.org/abs/1801.07993},
keywords = {ZX-calculus, Completeness, Clifford+T},
abstract = {Recently, we gave a complete axiomatisation of the ZX-calculus for the overall pure qubit quantum mechanics. Based on this result, here we also obtain a complete axiomatisation of the ZX-calculus for the Clifford+T quantum mechanics 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. In contrast to the first complete axiomatisation of the ZX-calculus for the Clifford+T fragment, we have two new generators as features rather than novelties: the triangle can be employed as an essential component to construct a Toffoli gate in a very simple form, while the lambda box can be slightly extended to a generalised phase so that the generalised supplementarity (cyclotomic supplementarity ) is naturally seen as a special case of the generalised spider rule.}
}
@article{hadzihasanovic2018diagrammatic,
author = {Hadzihasanovic, Amar and de Felice, Giovanni and Ng, Kang Feng},
title = {A diagrammatic calculus of fermionic quantum circuits},
year = {2019},
journal = {Logical Methods in Computer Science},
volume = {15},
publisher = {Episciences. org},
doi = {10.23638/LMCS-15(3:26)2019},
urldate = {2018-01-04},
link = {https://arxiv.org/abs/1801.01231},
keywords = {ZW-Calculus, Completeness, Fermionic quantum computing},
abstract = {We introduce the fermionic ZW calculus, a string-diagrammatic language for fermionic quantum computing (FQC). After defining a fermionic circuit model, we present the basic components of the calculus, together with their interpretation, and show how the main physical gates of interest in FQC can be represented in our language. We then list our axioms, and derive some additional equations. We prove that the axioms provide a complete equational axiomatisation of the monoidal category whose objects are systems of finitely many local fermionic modes (LFMs), with maps that preserve or reverse the parity of states, and the tensor product as monoidal product. We achieve this through a procedure that rewrites any diagram in a normal form. As an example, we show how the statistics of a fermionic Mach-Zehnder interferometer can be calculated in the diagrammatic language. We conclude by giving a diagrammatic treatment of the dual-rail encoding, a standard method in optical quantum computing used to perform universal quantum computation.}
}
@inproceedings{HarnyAmarCompleteness,
author = {Hadzihasanovic, Amar and Ng, Kang Feng and Wang, Quanlong},
title = {{Two Complete Axiomatisations of Pure-state Qubit Quantum Computing}},
year = {2018},
booktitle = {Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science},
series = {LICS '18},
pages = {502--511},
numpages = {10},
publisher = {ACM},
acmid = {3209128},
address = {New York, NY, USA},
isbn = {978-1-4503-5583-4},
location = {Oxford, United Kingdom},
doi = {10.1145/3209108.3209128},
link = {https://dl.acm.org/citation.cfm?id=3209128},
keywords = {ZW-Calculus, Completeness, Universal Fragment, Normal-form},
abstract = {Categorical quantum mechanics places finite-dimensional quantum theory in the context of compact closed categories, with an emphasis on diagrammatic reasoning. In this framework, two equational diagrammatic calculi have been proposed for pure-state qubit quantum computing: the ZW calculus, developed by Coecke, Kissinger and the first author for the purpose of qubit entanglement classification, and the ZX calculus, introduced by Coecke and Duncan to give an abstract description of complementary observables. Neither calculus, however, provided a complete axiomatisation of their model.
In this paper, we present extended versions of ZW and ZX, and show their completeness for pure-state qubit theory, thus solving two major open problems in categorical quantum mechanics. First, we extend the original ZW calculus to represent states and linear maps with coefficients in an arbitrary commutative ring, and prove completeness by a strategy that rewrites all diagrams into a normal form. We then extend the language and axioms of the original ZX calculus, and show their completeness for pure-state qubit theory through a translation between ZX and ZW specialised to the field of complex numbers. This translation expands the one used by Jeandel, Perdrix, and Vilmart to derive an axiomatisation of the approximately universal Clifford+T fragment; restricting the field of complex numbers to a suitable subring, we obtain an alternative axiomatisation of the same theory.}
}
@article{backens2017minimal,
author = {Backens, Miriam and Perdrix, Simon and Wang, Quanlong},
title = {{Towards a Minimal Stabilizer ZX-calculus}},
year = {2020},
journal = {Logical Methods in Computer Science},
volume = {16},
issue = {4},
month = {12},
urldate = {2017-09-26},
link = {http://arxiv.org/abs/1709.08903},
keywords = {ZX-calculus, Clifford Fragment, Minimality, Completeness, Scalars},
abstract = {The stabilizer ZX-calculus is a rigorous graphical language for reasoning about quantum mechanics. The language is sound and complete: one can transform a stabilizer ZX-diagram into another one using the graphical rewrite rules if and only if these two diagrams represent the same quantum evolution or quantum state. We previously showed that the stabilizer ZX-calculus can be simplified by reducing the number of rewrite rules, without losing the property of completeness [Backens, Perdrix & Wang, EPTCS 236:1--20, 2017]. Here, we show that most of the remaining rules of the language are indeed necessary. We do however leave as an open question the necessity of two rules. These include, surprisingly, the bialgebra rule, which is an axiomatisation of complementarity, the cornerstone of the ZX-calculus. Furthermore, we show that a weaker ambient category -- a braided autonomous category instead of the usual compact closed category -- is sufficient to recover the meta rule 'only connectivity matters', even without assuming any symmetries of the generators.}
}
@phdthesis{hadzihasanovic2017algebra,
author = {Hadzihasanovic, Amar},
title = {The algebra of entanglement and the geometry of composition},
year = {2017},
school = {University of Oxford},
urldate = {2017-09-23},
link = {https://arxiv.org/abs/1709.08086},
keywords = {ZW-Calculus, Completeness, Rings, PhD Thesis},
abstract = {String diagrams turn algebraic equations into topological moves that have recurring shapes, involving the sliding of one diagram past another. We individuate, at the root of this fact, the dual nature of polygraphs as presentations of higher algebraic theories, and as combinatorial descriptions of "directed spaces". Operations of polygraphs modelled on operations of topological spaces are used as the foundation of a compositional universal algebra, where sliding moves arise from tensor products of polygraphs. We reconstruct several higher algebraic theories in this framework.
In this regard, the standard formalism of polygraphs has some technical problems. We propose a notion of regular polygraph, barring cell boundaries that are not homeomorphic to a disk of the appropriate dimension. We define a category of non-degenerate shapes, and show how to calculate their tensor products. Then, we introduce a notion of weak unit to recover weakly degenerate boundaries in low dimensions, and prove that the existence of weak units is equivalent to a representability property.
We then turn to applications of diagrammatic algebra to quantum theory. We re-evaluate the category of Hilbert spaces from the perspective of categorical universal algebra, which leads to a bicategorical refinement. Then, we focus on the axiomatics of fragments of quantum theory, and present the ZW calculus, the first complete diagrammatic axiomatisation of the theory of qubits.
The ZW calculus has several advantages over ZX calculi, including a computationally meaningful normal form, and a fragment whose diagrams can be read as setups of fermionic oscillators. Moreover, its generators reflect an operational classification of entangled states of 3 qubits. We conclude with generalisations of the ZW calculus to higher-dimensional systems, including the definition of a universal set of generators in each dimension.}
}
@article{ng2017universal,
author = {Ng, Kang Feng and Wang, Quanlong},
title = {{A universal completion of the ZX-calculus}},
year = {2017},
journal = {arXiv preprint arXiv:1706.09877},
urldate = {2017-06-29},
link = {https://arxiv.org/abs/1706.09877},
keywords = {ZX-calculus, Completeness, Universal Fragment},
abstract = {In this paper, we give a universal completion of the ZX-calculus for the whole of pure qubit quantum mechanics. This proof is based on the completeness of another graphical language: the ZW-calculus, with direct translations between these two graphical systems.}
}
@inproceedings{EPTCS266.10,
author = {Garvie, Liam and Duncan, Ross},
title = {{Verifying the Smallest Interesting Colour Code with Quantomatic}},
year = {2018},
booktitle = {Proceedings 14th International Conference on
Quantum Physics and Logic,
Nijmegen, The Netherlands, 3-7 July 2017},
editor = {Coecke, Bob and Kissinger, Aleks},
series = {Electronic Proceedings in Theoretical Computer Science},
volume = {266},
pages = {147-163},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.266.10},
urldate = {2017-06-08},
link = {https://arxiv.org/abs/1706.02717},
keywords = {ZX-calculus, Quantomatic, Error correcting codes, Automation, Applied},
abstract = {In this paper we present a Quantomatic case study, verifying the basic properties of the Smallest Interesting Colour Code error detecting code.}
}
@inproceedings{SimonCompleteness,
author = {Jeandel, Emmanuel and Perdrix, Simon and Vilmart, Renaud},
title = {{A Complete Axiomatisation of the ZX-Calculus for Clifford+T Quantum Mechanics}},
year = {2018},
booktitle = {Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science},
series = {LICS '18},
pages = {559--568},
numpages = {10},
publisher = {ACM},
acmid = {3209131},
address = {New York, NY, USA},
isbn = {978-1-4503-5583-4},
location = {Oxford, United Kingdom},
doi = {10.1145/3209108.3209131},
urldate = {2017-05-31},
link = {https://arxiv.org/abs/1705.11151},
keywords = {Clifford+T, Completeness, triangle, ZX-calculus},
abstract = {We introduce the first complete and approximatively universal diagrammatic language for quantum mechanics. We make the ZX-Calculus, a diagrammatic language introduced by Coecke and Duncan, complete for the so-called Clifford+T quantum mechanics by adding four new axioms to the language. The completeness of the ZX-Calculus for Clifford+T quantum mechanics was one of the main open questions in categorical quantum mechanics. We prove the completeness of the Clifford+T fragment of the ZX-Calculus using the recently studied ZW-Calculus, a calculus dealing with integer matrices. We also prove that the Clifford+T fragment of the ZX-Calculus represents exactly all the matrices over some finite dimensional extension of the ring of dyadic rationals.}
}
@article{horsman2017surgery,
author = {de Beaudrap, Niel and Horsman, Dominic},
title = {{The ZX calculus is a language for surface code lattice surgery}},
year = {2020},
journal = {Quantum},
volume = {4},
doi = {10.22331/q-2020-01-09-218},
urldate = {2017-04-27},
link = {https://arxiv.org/abs/1704.08670},
keywords = {ZX-calculus, Lattice Surgery, Surface Code, Applied},
abstract = {Quantum computing is moving rapidly to the point of deployment of technology. Functional quantum devices will require the ability to correct error in order to be scalable and effective. A leading choice of error correction, in particular for modular or distributed architectures, is the surface code with logical two-qubit operations realised via "lattice surgery". These operations consist of "merges" and "splits" acting non-unitarily on the logical states and are not easily captured by standard circuit notation. This raises the question of how best to reason about lattice surgery in order efficiently to use quantum states and operations in architectures with complex resource management issues. In this paper we demonstrate that the operations of the ZX calculus, a form of quantum diagrammatic reasoning designed using category theory, match exactly the operations of lattice surgery. Red and green "spider" nodes match rough and smooth merges and splits, and follow the axioms of a dagger special associative Frobenius algebra. Some lattice surgery operations can require non-trivial correction operations, which are captured natively in the use of the ZX calculus in the form of ensembles of diagrams. We give a first taste of the power of the calculus as a language for surgery by considering two operations (magic state use and producing a CNOT) and show how ZX diagram re-write rules give lattice surgery procedures for these operations that are novel, efficient, and highly configurable.},
video = {https://www.youtube.com/watch?v=Ce2Hou5u8N4}
}
@inproceedings{cicala_categorifying_2018,
author = {Cicala, Daniel},
title = {Categorifying the {ZX-calculus}},
year = {2018},
booktitle = {{\rm Proceedings 14th International Conference on}
Quantum Physics and Logic,
{\rm Nijmegen, The Netherlands, 3-7 July 2017}},
editor = {Coecke, Bob and Kissinger, Aleks},
series = {Electronic Proceedings in Theoretical Computer Science},
volume = {266},
pages = {294-314},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.266.19},
urldate = {2017-04-24},
link = {http://arxiv.org/abs/1704.07034},
keywords = {ZX-Calculus, Category Theory},
abstract = {We build a symmetric monoidal and compact closed bicategory by combining spans and cospans inside a topos. This can be used as a framework in which to study open networks and diagrammatic languages. We illustrate this framework with Coecke and Duncan's zx-calculus by constructing a bicategory with the natural numbers for 0-cells, the zx-calculus diagrams for 1-cells, and rewrite rules for 2-cells.}
}
@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.}
}
@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.}
}
@inproceedings{cyclo,
author = {Emmanuel Jeandel and Simon Perdrix and Renaud Vilmart and Quanlong Wang},
title = {{ZX-Calculus: Cyclotomic Supplementarity and Incompleteness for Clifford+T Quantum Mechanics}},
year = {2017},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
editor = {Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {83},
pages = {11:1--11:13},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
isbn = {978-3-95977-046-0},
issn = {1868-8969},
doi = {10.4230/LIPIcs.MFCS.2017.11},
urldate = {2017-02-07},
link = {https://arxiv.org/abs/1702.01945},
keywords = {ZX-Calculus, Completeness, Rational Fragment},
abstract = {The ZX-Calculus is a powerful graphical language for quantum mechanics and quantum information processing. The completeness of the language -- i.e. the ability to derive any true equation -- is a crucial question. In the quest of a complete ZX-calculus, supplementarity has been recently proved to be necessary for quantum diagram reasoning (MFCS 2016). Roughly speaking, supplementarity consists in merging two subdiagrams when they are parameterized by antipodal angles. We introduce a generalised supplementarity -- called cyclotomic supplementarity -- which consists in merging n subdiagrams at once, when the n angles divide the circle into equal parts. We show that when n is an odd prime number, the cyclotomic supplementarity cannot be derived, leading to a countable family of new axioms for diagrammatic quantum reasoning.We exhibit another new simple axiom that cannot be derived from the existing rules of the ZX-Calculus, implying in particular the incompleteness of the language for the so-called Clifford+T quantum mechanics. We end up with a new axiomatisation of an extended ZX-Calculus, including an axiom schema for the cyclotomic supplementarity.}
}
@article{gogioso2017generalised,
author = {Gogioso, Stefano and Zeng, William},
title = {{Generalised Mermin-type non-locality arguments}},
year = {2019},
journal = {Logical Methods in Computer Science},
volume = {15},
issue = {2},
month = {4},
doi = {10.23638/LMCS-15(2:3)2019},
urldate = {2017-02-06},
link = {http://arxiv.org/abs/1702.01772},
keywords = {Strong Complementarity, Category Theory, Foundations, Applied},
abstract = {We broadly generalise Mermin-type arguments on GHZ states, and we provide exact group-theoretic conditions for non-locality to be achieved. Our results are of interest in quantum foundations, where they yield a new hierarchy of quantum-realisable All-vs-Nothing arguments. They are also of interest to quantum protocols, where they find immediate application to a non-trivial extension of the hybrid quantum-classical secret sharing scheme of Hillery, Bu\v{z}ek and Berthiaume (HBB). Our proofs are carried out in the graphical language of string diagrams for dagger compact categories, and their validity extends beyond quantum theory to any theory featuring the relevant algebraic structures.}
}
@inproceedings{EPTCS266.2,
author = {Jeandel, Emmanuel and Perdrix, Simon and Vilmart, Renaud},
title = {{Y-Calculus: A Language for Real Matrices Derived from the ZX-Calculus}},
year = {2018},
booktitle = {Proceedings 14th International Conference on
Quantum Physics and Logic,
Nijmegen, The Netherlands, 3-7 July 2017},
editor = {Coecke, Bob and Kissinger, Aleks},
series = {Electronic Proceedings in Theoretical Computer Science},
volume = {266},
pages = {23-57},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.266.2},
urldate = {2017-02-03},
link = {https://arxiv.org/abs/1702.00934},
keywords = {Y-Calculus, Completeness, Real Fragment},
abstract = {We introduce a ZX-like diagrammatic language devoted to manipulating real matrices - and rebits -, with its own set of axioms. We prove the necessity of some non trivial axioms of these. We show that some restriction of the language is complete. We exhibit two interpretations to and from the ZX-Calculus, thus showing the consistency between the two languages. Finally, we derive from our work a way to extract the real or imaginary part of a ZX-diagram, and prove that a restriction of our language is complete if the equivalent restriction of the ZX-calculus is complete.}
}
@book{CKbook,
author = {Coecke, Bob and Kissinger, Aleks},
title = {{Picturing Quantum Processes}},
year = {2017},
journal = {Cambridge University Press},
publisher = {Cambridge University Press},
doi = {10.1007/978-3-319-91376-6\_6},
link = {https://www.amazon.com/Picturing-Quantum-Processes-Diagrammatic-Reasoning/dp/110710422X},
keywords = {ZX-calculus, Mixed States, Foundations, Qudits, MBQC, Graph States, Spekkens Toy Model, Protocols, Strong Complementarity, Triangle, ZW-calculus},
abstract = {The unique features of the quantum world are explained in this book through the language of diagrams, setting out an innovative visual method for presenting complex theories. Requiring only basic mathematical literacy, this book employs a unique formalism that builds an intuitive understanding of quantum features while eliminating the need for complex calculations. This entirely diagrammatic presentation of quantum theory represents the culmination of ten years of research, uniting classical techniques in linear algebra and Hilbert spaces with cutting-edge developments in quantum computation and foundations. Written in an entertaining and user-friendly style and including more than one hundred exercises, this book is an ideal first course in quantum theory, foundations, and computation for students from undergraduate to PhD level, as well as an opportunity for researchers from a broad range of fields, from physics to biology, linguistics, and cognitive science, to discover a new set of tools for studying processes and interaction.}
}
@misc{Duncan2016Video,
author = {Duncan, Ross},
title = {{Compositionality in Categorical Quantum Computing}},
year = {2016},
howpublished = {Compositionality 2016},
urldate = {2016-12-7},
url = {https://www.youtube.com/watch?v=KIYT1NYCtdM},
keywords = {ZX-calculus, MBQC},
abstract = {}
}
@article{chancellor2016coherent,
author = {Chancellor, Nicholas and Kissinger, Aleks and Roffe, Joschka and Zohren, Stefan and Horsman, Dominic},
title = {{Graphical Structures for Design and Verification of Quantum Error Correction}},
year = {2016},
journal = {arXiv preprint arXiv:1611.08012},
urldate = {2016-11-23},
link = {https://arxiv.org/abs/1611.08012},
keywords = {ZX-Calculus, Quantomatic, Error correcting codes, Applied},
abstract = {We introduce a high-level graphical framework for the design, analysis, and verification of quantum error correcting codes. The coherent parity check construction for stabilizer codes allows us to construct a broad range of quantum codes based on classical codes, and gives a framework in which large classes of such codes can be both analytically and numerically discovered. Using graphical tools based on the \zx calculus, we explicitly construct small distance 3 and 5 codes with high code rates using this framework. We also show how this framework can be used to represent CSS codes and conversely how to compute stabilisers for a CPC code. We give a construction turns (almost) any pair of classical [n,k,3] codes into a [[2n - k + 2, k, 3]] CPC code, and give a straightforward 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 we introduce to demonstrate how Clifford computation can be performed within CPC codes.}
}
@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.}
}
@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.}
}
@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.}
}
@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}
}
@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.}
}
@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}
}
@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.}
}
@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.}
}
@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.}
}
@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.}
}
@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}
}
@inproceedings{backens2014zx,
author = {Backens, Miriam},
title = {The {ZX-calculus} is complete for the single-qubit {Clifford+T} group},
year = {2014},
booktitle = {{\rm Proceedings of the 11th workshop on}
Quantum Physics and Logic,
{\rm 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}
}
@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.}
}
@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.}
}
@inproceedings{Witt:2014aa,
author = {Schr\"oder de Witt, Christian and Zamdzhiev, Vladimir},
title = {The {ZX}-calculus is incomplete for quantum mechanics},
year = {2014},
booktitle = {{\rm Proceedings of the 11th workshop on}
Quantum Physics and Logic,
{\rm 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 = {285-292},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.172.20},
urldate = {2014-04-14},
link = {https://arxiv.org/abs/1404.3633},
keywords = {ZX-calculus, Completeness},
abstract = {We prove that the ZX-calculus is incomplete for quantum mechanics. We suggest the addition of a new 'color-swap' rule, of which currently no analytical formulation is known and which we suspect may be necessary, but not sufficient to make the ZX-calculus complete.},
video = {https://www.youtube.com/watch?v=XH9gXGXcSKg}
}
@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.}
}
@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.}
}
@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.}
}
@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.}
}
@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.}
}
@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.}
}
@inproceedings{duncan2013verifying,
author = {Duncan, Ross and Lucas, Maxime},
title = {Verifying the {Steane} code with {Quantomatic}},
year = {2014},
booktitle = {{\rm Proceedings of the 10th International Workshop on}
Quantum Physics and Logic,
{\rm Castelldefels (Barcelona), Spain, 17th to 19th July 2013}},
editor = {Coecke, Bob and Hoban, Matty},
series = {Electronic Proceedings in Theoretical Computer Science},
volume = {171},
pages = {33-49},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.171.4},
urldate = {2013-06-19},
link = {https://arxiv.org/abs/1306.4532},
keywords = {ZX-calculus, Quantomatic, Automation, Error correcting codes, Applied},
abstract = {In this paper we give a partially mechanized proof of the correctness of Steane's 7-qubit error correcting code, using the tool Quantomatic. To the best of our knowledge, this represents the largest and most complicated verification task yet carried out using Quantomatic.}
}
@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}
}
@mastersthesis{Zamdzhiev2012masters,
author = {Zamdzhiev, Vladimir},
title = {{An Abstract Approach towards Quantum Secret Sharing}},
year = {2012},
school = {University of Oxford},
urldate = {2012-08-31},
link = {http://www.cs.ox.ac.uk/people/bob.coecke/VladimirZamdzhievThesis.pdf},
keywords = {ZX-Calculus, Protocols, Master Thesis},
abstract = {In this thesis we prove in a formal and rigorous way the correctness of some aspects of quantum secret sharing protocols. We do not use the traditional Hilbert space formalism to reason about quantum computation, but we instead approach the problem from another, more abstract perspective. All of our proofs are written in the ZX calculus [10] - a diagrammatic language developed from the study of categorical quantum mechanics [4].}
}
@mastersthesis{Bar2012Master,
author = {Bar, Krzysztof},
title = {{Design and Analysis of Quantum Protocols and Algorithms}},
year = {2012},
school = {University of Oxford},
urldate = {2012-05-20},
link = {http://www.cs.ox.ac.uk/people/bob.coecke/Krzysztof_Bar.pdf},
keywords = {ZX-calculus, Protocols, Master Thesis},
abstract = {Categorical axiomatisation of Quantum Theory leads to an intuitive language for describing quantum computation - graphical calculi. The subject of this dissertation is to
explore its capabilities within different branches of the field of Quantum Computing.}
}
@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}
}
@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}
}
@misc{Coecke2012Video,
author = {Coecke, Bob},
title = {{Graphical and Automated Reasoning for Quantum Algorithms and Protocols}},
year = {2012},
howpublished = {QISW 2012},
urldate = {2012-03-04},
url = {https://www.youtube.com/watch?v=-wLWqlBEyY4},
keywords = {ZX-calculus, NLP, ZW-calculus, Quantomatic, Automation},
abstract = {}
}
@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.}
}
@inproceedings{coecke2012tutorial,
author = {Coecke, Bob and Duncan, Ross},
title = {{Tutorial: Graphical calculus for quantum circuits}},
year = {2012},
booktitle = {International Workshop on Reversible Computation},
pages = {1--13},
organization = {Springer},
isbn = {978-3-642-36315-3},
doi = {10.1007/978-3-642-36315-3_1},
urldate = {2012-01-01},
link = {https://link.springer.com/chapter/10.1007/978-3-642-36315-3_1},
keywords = {ZX-calculus},
abstract = {We explain the graphical zx-calculus for reasoning about qubits without any reference to the underlying categorical semantics, and illustrate its use on quantum circuits.}
}
@inproceedings{EPTCS95.14,
author = {Lang, Alex and Coecke, Bob},
title = {{Trichromatic Open Digraphs for Understanding Qubits}},
year = {2012},
booktitle = {{\rm Proceedings 8th International Workshop on}
Quantum Physics and Logic,
{\rm 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}
}
@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.}
}
@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.}
}
@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.}
}
@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.}
}
@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.}
}
@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.}
}
@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.}
}
@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.}
}
@misc{Duncan2010Video,
author = {Duncan, Ross},
title = {{Introduction to monoidal categories and graphical calculus 5}},
year = {2010},
howpublished = {Course},
urldate = {2010-05-01},
url = {https://www.youtube.com/watch?v=7ZLFmCpA9oQ},
keywords = {Category Theory, ZX-calculus, MBQC, Foundational},
abstract = {}
}
@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.}
}
@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.}
}
@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}
}
@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}
}
@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.}
}
@misc{Kissinger2009Video,
author = {Kissinger, Aleks},
title = {{Entanglement classification with classical structures and graph rewriting}},
year = {2009},
howpublished = {Categories, Logic and Foundations of Physics V},
urldate = {2009-08-01},
url = {https://www.youtube.com/watch?v=kuTI6Xh0yUw},
keywords = {ZW-calculus, Strong Complementarity},
abstract = {}
}
@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.}
}
@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.}
}
@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.}
}
@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}
}
@article{Coecke2007graphicalcalculus,
author = {Coecke, Bob and Duncan, Ross},
title = {A graphical calculus for quantum observables},
year = {2007},
journal = {Preprint},
link = {http://www.cs.ox.ac.uk/people/bob.coecke/GreenRed.pdf},
keywords = {ZX-Calculus, Foundational},
abstract = {We present novel laws describing the interaction of a pair of mutually unbiased observables. These laws yield a diagrammatic calculus which enables matrix-free reasoning about quantum systems. To illustrate the elegance of this approach we establish some properties of standard quantum logic gates, compute the quantum Fourier transform and demonstrate equivalence between certain cluster state and quantum circuit computations.
Historical note: First paper containing ZX-diagrams. Rejected from QIP with reports like: ``nice pictures, so what?''.}
}