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
@article{bombin2023unifying,
author = {Bombin, Hector and Litinski, Daniel and Nickerson, Naomi and Pastawski, Fernando and Roberts, Sam},
title = {{Unifying flavors of fault tolerance with the ZX calculus}},
year = {2023},
journal = {arXiv preprint arXiv:2303.08829},
urldate = {2023-03-15},
link = {http://arxiv.org/abs/2303.08829},
keywords = {Surface Code, Lattice Surgery, Error Correcting Codes, Pauli Fusion, ZX-calculus},
abstract = {There are several models of quantum computation which exhibit shared fundamental fault-tolerance properties. This article makes commonalities explicit by presenting these different models in a unifying framework based on the ZX calculus. We focus on models of topological fault tolerance - specifically surface codes - including circuit-based, measurement-based and fusion-based quantum computation, as well as the recently introduced model of Floquet codes. We find that all of these models can be viewed as different flavors of the same underlying stabilizer fault-tolerance structure, and sustain this through a set of local equivalence transformations which allow mapping between flavors. We anticipate that this unifying perspective will pave the way to transferring progress among the different views of stabilizer fault-tolerance and help researchers familiar with one model easily understand others.}
}
@article{bombin2023modular,
author = {Bomb{\'i}n, H{\'e}ctor and Dawson, Chris and Liu, Ye-Hua and Nickerson, Naomi and Pastawski, Fernando and Roberts, Sam},
title = {{Modular decoding: parallelizable real-time decoding for quantum computers}},
year = {2023},
journal = {arXiv preprint arXiv:2303.04846},
urldate = {2023-03-08},
link = {http://arxiv.org/abs/2303.04846},
keywords = {Surface Code, Lattice Surgery, Error Correcting Codes, Applied, ZX-calculus},
abstract = {Universal fault-tolerant quantum computation will require real-time decoding algorithms capable of quickly extracting logical outcomes from the stream of data generated by noisy quantum hardware. We propose modular decoding, an approach capable of addressing this challenge with minimal additional communication and without sacrificing decoding accuracy. We introduce the edge-vertex decomposition, a concrete instance of modular decoding for lattice-surgery style fault-tolerant blocks which is remarkably effective. This decomposition of the global decoding problem into sub-tasks mirrors the logical-block-network structure of a fault-tolerant quantum circuit. We identify the buffering condition as a key requirement controlling decoder quality; it demands a sufficiently large separation (buffer) between a correction committed by a decoding sub-task and the data unavailable to it. We prove that the fault distance of the protocol is preserved if the buffering condition is satisfied. Finally, we implement edge-vertex modular decoding and apply it on a variety of quantum circuits, including the Clifford component of the 15-to-1 magic-state distillation protocol. Monte Carlo simulations on a range of buffer sizes provide quantitative evidence that buffers are both necessary and sufficient to guarantee decoder accuracy. Our results show that modular decoding meets all the practical requirements necessary to support real-world fault-tolerant quantum computers.}
}
@article{cl?ent2023simple,
author = {Cl{\'e}ment, Alexandre and Delorme, No{\'e} and Perdrix, Simon and Vilmart, Renaud},
title = {{Simple Complete Equational Theories for Quantum Circuits with Ancillae or Partial Trace}},
year = {2023},
journal = {arXiv preprint arXiv:2303.03117},
urldate = {2023-03-06},
link = {http://arxiv.org/abs/2303.03117},
keywords = {Completeness, Mixed States, Universal Fragment, Toffoli, ZX-Supported},
abstract = {Although quantum circuits have been ubiquitous for decades in quantum computing, the first complete equational theory for quantum circuits has only recently been introduced. Completeness guarantees that any true equation on quantum circuits can be derived from the equational theory. Our contribution is twofold: (i) We simplify this equational theory by proving that several rules can be derived from the remaining ones. In particular, two out of the three most intricate rules are removed, the third one being slightly simplified. (ii) We extend the complete equational theory to quantum circuits with ancillae or qubit discarding, to represent respectively quantum computations using an additional workspace, and hybrid quantum computations. We show that the remaining intricate rule can be greatly simplified in these more expressive settings. The development of simple and complete equational theories for expressive quantum circuit models opens new avenues for reasoning about quantum circuits. It provides strong formal foundations for various compiling tasks such as circuit optimisation, hardware constraint satisfaction and verification.}
}
@article{coecke2023basic,
author = {Coecke, Bob},
title = {{Basic ZX-calculus for students and professionals}},
year = {2023},
journal = {arXiv preprint arXiv:2303.03163},
urldate = {2023-03-06},
link = {http://arxiv.org/abs/2303.03163},
keywords = {ZX-calculus, MBQC, Graph States, Protocols},
abstract = {These are the lecture notes of guest lectures for Artur Ekert's course Introduction to Quantum Information at the Mathematical Institute of Oxford University, Hilary Term 2023. Some basic familiarity with Dirac notation is assumed. For the readers of Quantum in Pictures (QiP) who have some basic quantum background, these notes also constitute the shortest path to an explanation of how what they learn in QIP relates to the traditional quantum formalism.}
}
@article{kristjuhan2023resource,
author = {Kristjuhan, Kaur and Nicholas Jones, Mark},
title = {{Resource efficient method for representation and measurement of constrained electronic structure states with a quantum computer}},
year = {2023},
journal = {arXiv preprint arXiv:2303.01122},
urldate = {2023-03-02},
link = {http://arxiv.org/abs/2303.01122},
keywords = {ZX-Supported, Chemistry, Applied},
abstract = {We present a novel method for improving the quantum simulation of the ground state energy of molecules. We perform a pre-processing step classically, which reduces the dimensionality of the problem by generating a custom mapping which excludes states which violate problem constraints. Subsequently, a specialized measurement scheme is used to extract the expectation value of the problem Hamiltonian through this mapping. We demonstrate that this method reduces the amount of quantum resources needed to run a Variational Quantum Eigensolver (VQE) algorithm without making any approximations to the physics of the quantum chemistry problem.}
}
@article{colisson2023oblivious,
author = {Colisson, L{\'e}o and Muguruza, Garazi and Speelman, Florian},
title = {{Oblivious Transfer from Zero-Knowledge Proofs, or How to Achieve Round-Optimal Quantum Oblivious Transfer and Zero-Knowledge Proofs on Quantum States}},
year = {2023},
journal = {arXiv preprint arXiv:2303.01476},
urldate = {2023-03-02},
link = {http://arxiv.org/abs/2303.01476},
keywords = {ZX-Supported, Cryptography, Applied},
abstract = {We provide a generic construction to turn any classical Zero-Knowledge (ZK) protocol into a composable (quantum) oblivious transfer (OT) protocol, mostly lifting the round-complexity properties and security guarantees (plain-model/statistical security/unstructured functions...) of the ZK protocol to the resulting OT protocol. Such a construction is unlikely to exist classically as Cryptomania is believed to be different from Minicrypt. In particular, by instantiating our construction using Non-Interactive ZK (NIZK), we provide the first round-optimal (2-message) quantum OT protocol secure in the random oracle model, and round-optimal extensions to string and k-out-of-n OT. At the heart of our construction lies a new method that allows us to prove properties on a received quantum state without revealing (too much) information on it, even in a non-interactive way and/or with statistical guarantees when using an appropriate classical ZK protocol. We can notably prove that a state has been partially measured (with arbitrary constraints on the set of measured qubits), without revealing any additional information on this set. This notion can be seen as an analog of ZK to quantum states, and we expect it to be of independent interest as it extends complexity theory to quantum languages, as illustrated by the two new complexity classes we introduce, ZKstateQIP and ZKstateQMA.}
}
@article{poor2023completeness,
author = {Po{\'o}r, Boldizs{\'a}r and Wang, Quanlong and Shaikh A., Razin and Yeh, Lia and Yeung, Richie and Coecke, Bob},
title = {{Completeness for arbitrary finite dimensions of ZXW-calculus, a unifying calculus}},
year = {2023},
journal = {arXiv preprint arXiv:2302.12135},
urldate = {2023-02-23},
link = {http://arxiv.org/abs/2302.12135},
keywords = {ZW-calculus, Completeness, ZX-calculus, Qudits},
abstract = {The ZX-calculus is a universal graphical language for qubit quantum computation, meaning that every linear map between qubits can be expressed in the ZX-calculus. Furthermore, it is a complete graphical rewrite system: any equation involving linear maps that is derivable in the Hilbert space formalism for quantum theory can also be derived in the calculus by rewriting. It has widespread usage within quantum industry and academia for a variety of tasks such as quantum circuit optimisation, error-correction, and education. The ZW-calculus is an alternative universal graphical language that is also complete for qubit quantum computing. In fact, its completeness was used to prove that the ZX-calculus is universally complete. This calculus has advanced how quantum circuits are compiled into photonic hardware architectures in the industry. Recently, by combining these two calculi, a new calculus has emerged for qubit quantum computation, the ZXW-calculus. Using this calculus, graphical-differentiation, -integration, and -exponentiation were made possible, thus enabling the development of novel techniques in the domains of quantum machine learning and quantum chemistry. Here, we generalise the ZXW-calculus to arbitrary finite dimensions, that is, to qudits. Moreover, we prove that this graphical rewrite system is complete for any finite dimension. This is the first completeness result for any universal graphical language beyond qubits.}
}
@article{carette2023compositionality,
author = {Carette, Titouan and Moutot, Etienne and Perez, Thomas and Vilmart, Renaud},
title = {{Compositionality of planar perfect matchings}},
year = {2023},
journal = {arXiv preprint arXiv:2302.08767},
urldate = {2023-02-17},
link = {http://arxiv.org/abs/2302.08767},
keywords = {ZW-calculus, Classical Simulation, Applied},
abstract = {We exhibit a strong connection between the matchgate formalism introduced by Valiant and the ZW-calculus of Coecke and Kissinger. This connection provides a natural compositional framework for matchgate theory as well as a direct combinatorial interpretation of the diagrams of ZW-calculus through the perfect matchings of their underlying graphs. We identify a precise fragment of ZW-calculus, the planar W-calculus, that we prove to be complete and universal for matchgates, that are linear maps satisfying the matchgate identities. Computing scalars of the planar W-calculus corresponds to counting perfect matchings of planar graphs, and so can be carried in polynomial time using the FKT algorithm, making the planar W-calculus an efficiently simulable fragment of the ZW-calculus, in a similar way that the Clifford fragment is for ZX-calculus. This work opens new directions for the investigation of the combinatorial properties of ZW-calculus as well as the study of perfect matching counting through compositional diagrammatical technics.}
}
@article{carette2023complete,
author = {Carette, Titouan and Hoffreumon, Timoth\'ee and Larroque, Emile and Vilmart, Renaud},
title = {{Complete Graphical Language for Hermiticity-Preserving Superoperators}},
year = {2023},
journal = {arXiv preprint arXiv:2302.04212},
urldate = {2023-02-08},
link = {http://arxiv.org/abs/2302.04212},
keywords = {ZW-calculus, Completeness, Category Theory, Mixed States},
abstract = {Universal and complete graphical languages have been successfully designed for pure state quantum mechanics, corresponding to linear maps between Hilbert spaces, and mixed states quantum mechanics, corresponding to completely positive superoperators. In this paper, we go one step further and present a universal and complete graphical language for Hermiticity-preserving superoperators. Such a language opens the possibility of diagrammatic compositional investigations of antilinear transformations featured in various physical situations, such as the Choi-Jamio{\l}kowski isomorphism, spin-flip, or entanglement witnesses. Our construction relies on an extension of the ZW-calculus exhibiting a normal form for Hermitian matrices.}
}
@article{ufrecht2023cutting,
author = {Ufrecht, Christian and Periyasamy, Maniraman and Rietsch, Sebastian and D. Scherer, Daniel and Plinge, Axel and Mutschler, Christopher},
title = {{Cutting multi-control quantum gates with ZX calculus}},
year = {2023},
journal = {arXiv preprint arXiv:2302.00387},
urldate = {2023-02-01},
link = {http://arxiv.org/abs/2302.00387},
keywords = {ZH-calculus, Classical Simulation, Applied},
abstract = {Circuit cutting, the decomposition of a quantum circuit into independent partitions, has become a promising avenue towards experiments with larger quantum circuits in the noisy-intermediate scale quantum (NISQ) era. While previous work focused on cutting qubit wires or two-qubit gates, in this work we introduce a method for cutting multi-controlled Z gates. We construct a decomposition and prove the upper bound $\mathcal{O}(6^{2K})$ on the associated sampling overhead, where $K$ is the number of cuts in the circuit. This bound is independent of the number of control qubits but can be further reduced to $\mathcal{O}(4.5^{2K})$ for the special case of CCZ gates. Furthermore, we evaluate our proposal on IBM hardware and experimentally show noise resilience due to the strong reduction of CNOT gates in the cut circuits.}
}
@article{cowtan2023css,
author = {Cowtan, Alexander and Burton, Simon},
title = {{CSS code surgery as a universal construction}},
year = {2023},
journal = {arXiv preprint arXiv:2301.13738},
urldate = {2023-01-31},
link = {http://arxiv.org/abs/2301.13738},
keywords = {Error Correcting Codes, Category Theory, ZX-Supported},
abstract = {We define code maps between Calderbank-Shor-Steane (CSS) codes using maps between chain complexes, and describe code surgery between such codes using a specific colimit in the category of chain complexes. As well as describing a surgery operation, this gives a general recipe for new codes. As an application we describe how to `merge' and `split' along a shared $\overline{X}$ or $\overline{Z}$ operator between arbitrary CSS codes in a fault-tolerant manner, so long as the participating qubits satisfy a technical condition related to gauge fixing. We prove that such merges and splits on LDPC codes yield codes which are themselves LDPC.}
}
@phdthesis{Chardonnet2023thesis,
author = {Chardonnet, Kostia},
title = {{Towards a Curry-Howard Correspondence for Quantum Computation}},
year = {2023},
school = {Universit\'e Paris-Saclay},
urldate = {2023-01-27},
link = {https://theses.hal.science/tel-03959403/document},
keywords = {ZX-calculus, Category Theory, Completeness, Verification, PhD Thesis},
abstract = {In this thesis, we are interested in the development of a Curry-Howard correspondence for quantum computing, allowing to represent quantum types and quantum control-flow. In the standard model of Quantum Computation, a classical computer is linked to a quantum coprocessor. The classical computer can then send instructions to allocate, update, or read quantum registers. The programs executed by the coprocessor are represented by a quantum circuit: a sequence of instructions that applies unitary operations to the input quantum bits. While the model is universal, in the sense that it can represent any unitary operations, it stays limited: it lacks of proper representation of non-causal execution flow. Normally, to represent branching, one can use a type system featuring a coproduct, allowing for the choice between two possible executions, but quantum circuits only feature qubits and tensors thereof. On the other hand, types and strongly related to logic via the Curry-Howard correspondence which states that types of programs correspond to formulas and programs to proofs, while the program evaluation is matched with the proof simplification. While this correspondence has been extended to multiple setting in classical computer, it has yet to emerge in quantum computing. To address those problems we follow two different approaches: the first one, through the development of a linear and reversible programming language, capturing a subset of quantum computing, along with a Curry-Howard correspondence with the logic µMALL. The language comes in two versions: one representing exactly complete, reversible functions while the other one can represent partial functions. Both version comes with an expressivity result: in the former, one can capture the whole class of Primitive Recursive Functions, while in the later any Turing Machine we show how to capture any Turing Machine. The second approach follows the development of token-based semantics, inspired by Girard’s Geometry of Interaction, for graphical language for quantum computation. In this approach, a token-based semantics was given for the ZX-Calculus: a graphical language for quantum computation capable of representing any linear operators. We show how the token-based semantics matches the denotational one. We extend the ZX-Calculus with a coproduct and an explicit tensor in the development of the Many-Worlds Calculus. This new languages comes with a token-based semantics and an equational theory. We show how quantum control can be represented in this system. Finally, the programming language is modified to be able to realize pure quantum computation and the graphical language is then used as a denotational model for it. }
}
@article{mernyei2023equivariant,
author = {Mernyei, P{\'e}ter and Meichanetzidis, Konstantinos and Ceylan, {\.I}smail {\.I}lkan},
title = {Equivariant quantum graph circuits: constructions for universal approximation over graphs},
year = {2023},
journal = {Quantum Machine Intelligence},
volume = {5},
number = {1},
pages = {6},
publisher = {Springer},
doi = {10.1007/s42484-022-00086-w},
urldate = {2023-01-24},
link = {https://link.springer.com/article/10.1007/s42484-022-00086-w},
keywords = {ZX-calculus, Variational Circuits, Graph States, Applied},
abstract = {We investigate quantum circuits for graph representation learning, and propose equivariant quantum graph circuits (EQGCs), as a class of parameterized quantum circuits with strong relational inductive bias for learning over graph-structured data. Conceptually, EQGCs serve as a unifying framework for quantum graph representation learning, allowing us to define several interesting subclasses subsuming existing proposals. In terms of the representation power, we prove that the subclasses of interest are universal approximators for functions over the bounded graph domain. This theoretical perspective on quantum graph machine learning methods opens many directions for further work, and could lead to models with capabilities beyond those of classical approaches. We also provide experimental evidence, and observe that the performance of EQGCs scales well with the depth of the model.}
}
@phdthesis{Borgna2023thesis,
author = {Borgna, Agust\'in},
title = {{Towards a compiler toolchain for quantum programs}},
year = {2023},
school = {Loria, Universit\'e de Lorraine},
urldate = {2023-01-13},
link = {https://lmf.cnrs.fr/downloads/Perso/thesis-aborgna.pdf},
keywords = {ZX-calculus, Scalable ZX, Mixed States, Protocols, PyZX, Automation, Optimisation, Category Theory, Circuit Extraction, Applied, PhD Thesis},
abstract = {In this thesis, we present various contributions to the different stages of a quantum compiler toolchain. Our first contribution is the definition of a new intermediate representation for quantum programs based on an extension of the ZX calculus called Scalable ZX (SZX), which allows us to compactly represent quantum circuits repeated structure. We introduce a non-trivial fragment of the Proto-Quipper-D language and present its encoding into families of such SZX-diagrams, that can be used to optimize recurrent segments of the program in a single optimization pass. This intermediate representation can then be transformed into a ZX diagram or a quantum circuit to continue the compilation process. This work was first presented at the International Workshop on Programming Languages for Quantum Computing (PLanQC 2022), and a full version was published in the proceedings of the Quantum Physics and Logic Conference (QPL 2022). A second contribution of this work is the definition of a new optimization procedure for quantum circuits containing both quantum and classical segments, based on the method by Duncan et al. We are able to use an extension of the ZX calculus called ZX Ground to represent such hybrid programs, and optimize programs that encode some communication between the quantum and classical components. A preliminary version of this work was first presented in the proceedings of the International Workshop on Quantum Compilation (IWQC 2020), and finally published at the Asian Symposium on Programming Languages and Systems (APLAS 2021). We have implemented our optimization procedure as an extension of the ZX-diagram manipulation tool pyzx, and upstreamed some of the changes to the main repository. Finally, our last contribution pertains to the detection of classical segments in a hybrid quantum-classical circuit. Some automated optimization processes such as the one we present may produce circuits that computes quantumly some operations that could be performed classically using fewer resources. We formalise the classicalisation problem and present an efficient heuristic to detect such segments. This work was developed jointly with the optimization procedure for hybrid quantum-classical circuits, and a succinct version was published along it at APLAS 2021.}
}
@article{boriskhesin2023graphical,
author = {Boris Khesin, Andrey and Z. Lu, Jonathan and W. Shor, Peter},
title = {{Graphical quantum Clifford-encoder compilers from the ZX calculus}},
year = {2023},
journal = {arXiv preprint arXiv:2301.02356},
urldate = {2023-01-06},
link = {http://arxiv.org/abs/2301.02356},
keywords = {Error Correcting Codes, ZX-calculus, Applied},
abstract = {We present a quantum compilation algorithm that maps Clifford encoders, an equivalence class of quantum circuits that arise universally in quantum error correction, into a representation in the ZX calculus. In particular, we develop a canonical form in the ZX calculus and prove canonicity as well as efficient reducibility of any Clifford encoder into the canonical form. The diagrams produced by our compiler explicitly visualize information propagation and entanglement structure of the encoder, revealing properties that may be obscured in the circuit or stabilizer-tableau representation.}
}
@article{codsi2022classically,
author = {Codsi, Julien and van de Wetering, John},
title = {{Classically Simulating Quantum Supremacy IQP Circuits trough a Random Graph Approach}},
year = {2022},
journal = {arXiv preprint arXiv:2212.08609},
urldate = {2022-12-16},
link = {http://arxiv.org/abs/2212.08609},
keywords = {Classical Simulation, ZX-calculus, Applied},
abstract = {Quantum Supremacy is a demonstration of a computation by a quantum computer that can not be performed by the best classical computer in a reasonable time. A well-studied approach to demonstrating this on near-term quantum computers is to use random circuit sampling. It has been suggested that a good candidate for demonstrating quantum supremacy with random circuit sampling is to use \emph{IQP circuits}. These are quantum circuits where the unitary it implements is diagonal. In this paper we introduce improved techniques for classically simulating random IQP circuits. We find a simple algorithm to calculate an amplitude of an $n$-qubit IQP circuit with dense random two-qubit interactions in time $O(\frac{\log^2 n}{n} 2^n )$, which for sparse circuits (where each qubit interacts with $O(\log n)$ other qubits) runs in $o(2^n/\text{poly}(n))$ for any given polynomial. Using a more complicated stabiliser decomposition approach we improve the algorithm for dense circuits to $O\left(\frac{(\log n)^{4-\beta}}{n^{2-\beta}} 2^n \right)$ where $\beta \approx 0.396$. We benchmarked our algorithm and found that we can simulate up to 50-qubit circuits in a couple of minutes on a laptop. We estimate that 70-qubit circuits are within reach for a large computing cluster.}
}
@article{laakkonen2022graphical,
author = {Laakkonen, Tuomas and Meichanetzidis, Konstantinos and van de Wetering, John},
title = {{A Graphical \#SAT Algorithm for Formulae with Small Clause Density}},
year = {2022},
journal = {arXiv preprint arXiv:2212.08048},
urldate = {2022-12-15},
link = {http://arxiv.org/abs/2212.08048},
keywords = {Classical Simulation, ZH-calculus, SAT, Applied},
abstract = {We study the counting version of the Boolean satisfiability problem \#SAT using the ZH-calculus, a graphical language originally introduced to reason about quantum circuits. Using this we find a natural extension of \#SAT which we call $\#SAT_\pm$, where variables are additionally labeled by phases, which is GapP-complete. Using graphical reasoning, we find a reduction from \#SAT to $\#2SAT_\pm$ in the ZH-calculus. We observe that the DPLL algorithm for #2SAT can be adapted to $\#2SAT_\pm$ directly and hence that Wahlstrom's $O^*(1.2377^n)$ upper bound applies to $\#2SAT_\pm$ as well. Combining this with our reduction from \#SAT to $\#2SAT_\pm$ gives us novel upper bounds in terms of clauses and variables that are better than $O^*(2^n)$ for small clause densities of $\frac{m}{n} < 2.25$. This is to our knowledge the first non-trivial upper bound for \#SAT that is independent of clause size. Our algorithm improves on Dubois' upper bound for $\#kSAT$ whenever $\frac{m}{n} < 1.85$ and $k \geq 4$, and the Williams' average-case analysis whenever $\frac{m}{n} < 1.21$ and $k \geq 6$. We also obtain an unconditional upper bound of $O^*(1.88^m)$ for $\#4SAT$ in terms of clauses only, and find an improved bound on $\#3SAT$ for $1.2577 < \frac{m}{n} \leq \frac{7}{3}$. Our results demonstrate that graphical reasoning can lead to new algorithmic insights, even outside the domain of quantum computing that the calculus was intended for.}
}
@phdthesis{toumi2022thesis,
author = {Toumi, Alexis},
title = {{Category Theory for Quantum Natural Language Processing}},
year = {2022},
school = {University of Oxford},
urldate = {2022-12-13},
link = {http://arxiv.org/abs/2212.06615},
keywords = {NLP, Category Theory, PhD Thesis, Applied},
abstract = {This thesis introduces quantum natural language processing (QNLP) models based on a simple yet powerful analogy between computational linguistics and quantum mechanics: grammar as entanglement. The grammatical structure of text and sentences connects the meaning of words in the same way that entanglement structure connects the states of quantum systems. Category theory allows to make this language-to-qubit analogy formal: it is a monoidal functor from grammar to vector spaces. We turn this abstract analogy into a concrete algorithm that translates the grammatical structure onto the architecture of parameterised quantum circuits. We then use a hybrid classical-quantum algorithm to train the model so that evaluating the circuits computes the meaning of sentences in data-driven tasks. The implementation of QNLP models motivated the development of DisCoPy (Distributional Compositional Python), the toolkit for applied category theory of which the first chapter gives a comprehensive overview. String diagrams are the core data structure of DisCoPy, they allow to reason about computation at a high level of abstraction. We show how they can encode both grammatical structures and quantum circuits, but also logical formulae, neural networks or arbitrary Python code. Monoidal functors allow to translate these abstract diagrams into concrete computation, interfacing with optimised task-specific libraries. The second chapter uses DisCopy to implement QNLP models as parameterised functors from grammar to quantum circuits. It gives a first proof-of-concept for the more general concept of functorial learning: generalising machine learning from functions to functors by learning from diagram-like data. In order to learn optimal functor parameters via gradient descent, we introduce the notion of diagrammatic differentiation: a graphical calculus for computing the gradients of parameterised diagrams.}
}
@article{shaikh2022sum,
author = {Shaikh, Razin A. and Wang, Quanlong and Yeung, Richie},
title = {{How to sum and exponentiate Hamiltonians in ZXW calculus}},
year = {2022},
journal = {arXiv preprint arXiv:2212.04462},
urldate = {2022-12-08},
link = {http://arxiv.org/abs/2212.04462},
keywords = {ZW-calculus, Algebraic ZX, Variational Circuits, Chemistry, Triangle},
abstract = {This paper develops practical summation techniques in ZXW calculus to reason about quantum dynamics, such as unitary time evolution. First we give a direct representation of a wide class of sums of linear operators, including arbitrary qubits Hamiltonians, in ZXW calculus. As an application, we demonstrate the linearity of the Schr\"odinger equation and give a diagrammatic representation of the Hamiltonian in Greene-Diniz et al (Gabriel, 2022), which is the first paper that models carbon capture using quantum computing. We then use the Cayley-Hamilton theorem to show in principle how to exponentiate arbitrary qubits Hamiltonians in ZXW calculus. Finally, we develop practical techniques and show how to do Taylor expansion and Trotterization diagrammatically for Hamiltonian simulation. This sets up the framework for using ZXW calculus to the problems in quantum chemistry and condensed matter physics.},
video = {https://youtu.be/_s2pOcrdmig?t=1347}
}
@article{shaw2022quantum,
author = {Shaw, Alexis and Bremner, Michael and Paler, Alexandru and Herr, Daniel and Devitt, Simon J.},
title = {{Quantum computation on a 19-qubit wide 2d nearest neighbour qubit array}},
year = {2022},
journal = {arXiv preprint arXiv:2212.01550},
urldate = {2022-12-03},
link = {http://arxiv.org/abs/2212.01550},
keywords = {Surface Code, Lattice Surgery, Applied, Error Correcting Codes, ZX-calculus},
abstract = {In this paper, we explore the relationship between the width of a qubit lattice constrained in one dimension and physical thresholds for scalable, fault-tolerant quantum computation. To circumvent the traditionally low thresholds of small fixed-width arrays, we deliberately engineer an error bias at the lowest level of encoding using the surface code. We then address this engineered bias at a higher level of encoding using a lattice-surgery surface code bus that exploits this bias, or a repetition code to make logical qubits with unbiased errors out of biased surface code qubits. Arbitrarily low error rates can then be reached by further concatenating with other codes, such as Steane [[7,1,3]] code and the [[15,7,3]] CSS code. This enables a scalable fixed-width quantum computing architecture on a square qubit lattice that is only 19 qubits wide, given physical qubits with an error rate of $8.0\times 10^{-4}$. This potentially eases engineering issues in systems with fine qubit pitches, such as quantum dots in silicon or gallium arsenide.}
}
@article{litinski2022active,
author = {Litinski, Daniel and Nickerson, Naomi},
title = {{Active volume: An architecture for efficient fault-tolerant quantum computers with limited non-local connections}},
year = {2022},
journal = {arXiv preprint arXiv:2211.15465},
urldate = {2022-11-28},
link = {http://arxiv.org/abs/2211.15465},
keywords = {Surface Code, Lattice Surgery, Applied, ZX-calculus},
abstract = {In existing general-purpose architectures for surface-code-based fault-tolerant quantum computers, the cost of a quantum computation is determined by the circuit volume, i.e., the number of qubits multiplied by the number of non-Clifford gates. We introduce an architecture using non-2D-local connections in which the cost does not scale with the number of qubits, and instead only with the number of logical operations. Each logical operation has an associated active volume, such that the cost of a quantum computation can be quantified as a sum of active volumes of all operations. For quantum computations with thousands of logical qubits, the active volume can be orders of magnitude lower than the circuit volume. Importantly, the architecture does not require all-to-all connectivity between N logical qubits. Instead, each logical qubit is connected to O(log N) other sites. As an example, we show that, using the same number of logical qubits, a 2048-bit factoring algorithm can be executed 44 times faster than on a general-purpose architecture without non-local connections. With photonic qubits, long-range connections are available and we show how photonic components can be used to construct a fusion-based active-volume quantum computer.}
}
@mastersthesis{Roy2022Masters,
author = {Roy, Patrick},
title = {{Qudit ZH-calculus}},
year = {2022},
school = {University of Oxford},
urldate = {2022-11-24},
link = {https://www.cs.ox.ac.uk/people/aleks.kissinger/theses/roy-thesis.pdf},
keywords = {ZH-Calculus, Qudits, Completeness, Master Thesis},
abstract = {The use of quantum graphical calculi, such as the ZX-calculus, has lead to great advances in fields such as quantum circuit optimization. Particularly the ZH-calculus has proven useful for reasoning about higher-level quantum operations, such as Toffoli and Hadamard gates, which form an approximately universal set of gates, for which the qubit ZH-calculus is complete. More recently, quantum computing based on d-ary basis states has gained traction, with the ZX- and ZW-calculi having been generalized to higher dimensions. However, no generalization of the ZH-calculus is known. Such a generalization might lead to new insights about higher-dimensional equivalents of the Toffoli-gate. In this dissertation, we provide this generalization of the qubit ZH-calculus to qudits by generalizing a classification of qubit quantum graphical calculi due to Carette and Jeandel by relaxing a condition that would have excluded a qudit ZH-calculus from being constructed. We then use this generalization to reduce the ruleset of the qubit ZH-calculus by one rule. Additionally, we give a first-of-its-kind algorithm for constructing ZH-diagrams from the matrix representation of linear maps, and use this algorithm to show that, for prime dimension, ZH-calculus is universal.}
}
@mastersthesis{Raj2022Masters,
author = {Raj, Snehal},
title = {{Graphical calculus for Tensor Network Contractions}},
year = {2022},
school = {University of Oxford},
urldate = {2022-11-23},
link = {https://www.cs.ox.ac.uk/people/aleks.kissinger/theses/raj-thesis.pdf},
keywords = {ZX-Calculus, Classical Simulation, Tensor Networks, Applied, Master Thesis},
abstract = {Quantum computing is an emerging field of research that harnesses the laws of quantum mechanics to solve computationally hard problems. In addition to developing better and bigger quantum computers, a significant challenge is developing techniques to benchmark these devices. Thus, pushing the barrier of classical simulation goes hand in hand with the development of quantum computers. In this dissertation, we hope to leverage the existing work on quantum graphical languages such as the ZX-calculus to aid one of the most prominent classical simulation tools, tensor network methods. By their very nature, graphical languages have a more modular representation of quantum circuits, which could be optimized using the associated rewrite rules of the calculi. We investigate how effective the existing procedures are at enhancing tensor network contractions and propose new strategies based on our observations. Furthermore, we evaluate our strategies using a variety of circuits, including the Sycamore circuits used by Google to demonstrate quantum supremacy in 2019.}
}
@article{ritaahmadi2022topological,
author = {Ahmadi, Fatimah Rita and Kissinger, Aleks},
title = {{Topological Quantum Computation Through the Lens of Categorical Quantum Mechanics}},
year = {2022},
journal = {arXiv preprint arXiv:2211.03855},
urldate = {2022-11-07},
link = {http://arxiv.org/abs/2211.03855},
keywords = {Braids, ZX-calculus, Applied},
abstract = {Unitary fusion categories formalise the algebraic theory of topological quantum computation. We rectify confusion around a category describing an anyonic theory and a category describing topological quantum computation. We show that the latter is a subcategory of Hilb. We represent elements of the Fibonacci and Ising models, namely the encoding of qubits and the associated braid group representations, with the ZX-calculus and show that in both cases, the Yang-Baxter equation is directly connected to an instance of the P-rule of the ZX-calculus. In the Ising case, this reduces to a familiar rule relating two distinct Euler decompositions of the Hadamard gate as $\pi/2$ phase rotations, whereas in the Fibonacci case, we give a previously unconsidered exact solution of the P-rule involving the Golden ratio. We demonstrate the utility of these representations by giving graphical derivations of the single-qubit braid equations for Fibonacci anyons and the single- and two-qubit braid equations for Ising anyons.}
}
@mastersthesis{Codsi2022Masters,
author = {Codsi, Julien},
title = {{Cutting-Edge Graphical Stabiliser Decompositions for Classical Simulation of Quantum Circuits}},
year = {2022},
school = {University of Oxford},
urldate = {2022-10-19},
link = {https://www.cs.ox.ac.uk/people/aleks.kissinger/theses/codsi-thesis.pdf},
keywords = {ZX-Calculus, Classical Simulation, Phase Gadgets, Applied, Master Thesis},
abstract = {The aim of this thesis is to study and improve classical simulation of quan tum circuits with stabiliser decompositions by using the ZX-calculus. We propose more efficient decompositions for a large family of states in addi- tion to integrating graphs cuts to make use of potential low connectivity of ZX-diagrams. We also discovered different heuristics to speed up the simulations. Finally, we implemented our method and compared it with the state-of-the-art on different families of circuits to asses the improvements achieved by our approach.}
}
@mastersthesis{Koch2022Masters,
author = {Koch, Mark},
title = {{Quantum Machine Learning using the ZXW-Calculus}},
year = {2022},
school = {University of Oxford},
urldate = {2022-10-18},
link = {https://www.cs.ox.ac.uk/people/aleks.kissinger/theses/koch-thesis.pdf},
keywords = {ZX-Calculus, ZW-Calculus, Variational Circuits, Chemistry, Applied, Master Thesis},
abstract = {The field of quantum machine learning (QML) explores how quantum computers can be used to more efficiently solve machine learning problems. As an application of hybrid quantum-classical algorithms, it promises a potential quantum advantages in the near term. In this thesis, we use the ZXW-calculus to diagrammatically analyse two key problems that QML applications face. First, we discuss algorithms to compute gradients on quantum hardware that are needed to perform gradient-based optimisation for QML. Concretely, we give new diagrammatic proofs of the common 2- and 4-term parameter shift rules used in the literature. Additionally, we derive a novel, generalised parameter shift rule with 2n terms that is applicable to gates that can be represented with n parametrised spiders in the ZXW-calculus. Furthermore, to the best of our knowledge, we give the first proof of a conjecture by Anselmetti et al. by proving a no-go theorem ruling out more efficient alternatives to the 4-term shift rule. Secondly, we analyse the gradient landscape of quantum ans\"atze for barren plateaus using both empirical and analytical techniques. Concretely, we develop a tool that automatically calculates the variance of gradients and use it to detect likely barren plateaus in commonly used quantum ans¨atze. Furthermore, we formally prove the existence or absence of barren plateaus for a selection of ans\"{a}tze using diagrammatic techniques from the ZXW-calculus.}
}
@mastersthesis{Khatri2022Masters,
author = {Khatri, Nikhil},
title = {{ Experimental Comparison of Ansatze for Quantum Natural Language Processing}},
year = {2022},
school = {University of Oxford},
urldate = {2022-10-17},
link = {https://www.cs.ox.ac.uk/people/aleks.kissinger/theses/khatri-thesis.pdf},
keywords = {ZX-Calculus, Optimisation, NLP, Variational Circuits, Applied, Master Thesis},
abstract = {The DisCoCat model of natural language is a framework which serves as the foundation for several contemporary experiments in Quantum Natural Language Processing (QNLP). In this model, sentences are represented as string diagrams which compose the meaning of the entire sentence from the meaning of each word. An essential step in performing QNLP tasks is converting DisCoCat string diagrams into quantum circuits, through a mapping known as an ansatz. While several ans\"{a}tze have been studied in the broader quantum machine learning literature, no comparative study of ans\"{a}tze exists for the specific case of QNLP models. In this work, we implement multiple ans\"{a}tze and compare their performance on a variety of QNLP tasks. In doing so, the first experimental results for a QNLP model applied to the paraphrase identification task are presented. We propose a novel approach to overcome the out-of-vocabulary problem faced by contemporary QNLP models, and demonstrate that our proposed method outperforms naive approaches by a significant margin. Further, experimental results relating to the barren plateau phenomenon in quantum machine learning are provided. We present evidence suggesting that circuits derived from DisCoCat string diagrams for binary classification tasks are no more susceptible to the barren plateau problem than regular quantum machine learning circuits.}
}
@mastersthesis{Cole2022Masters,
author = {Cole, Oliver},
title = {{Quantum Circuit Optimisation Through Stabiliser Reduction of Pauli Exponentials}},
year = {2022},
school = {University of Oxford},
urldate = {2022-10-16},
link = {https://www.cs.ox.ac.uk/people/aleks.kissinger/theses/cole-thesis.pdf},
keywords = {ZX-Calculus, Optimisation, Phase Gadgets, Applied, Master Thesis},
abstract = {Quantum circuits require careful and in-depth optimisation to be run on existing quantum computers. This project investigates the application of the Product Rotation Lemma, introduced by Will Simmons in [32], as a tool for general circuit optimisation. These optimisations exploit the initial state information to identify redundancies in the circuit. This project delves into the lemma’s applications for the Clifford-Pauli-Exponential form and its synthesis alongside the practical applications of this theory. The main contributions from this project are (1) the Pauli DAG Merging Theorem and its surrounding theory that gives simple necessary, and sufficient conditions for applying the Product Rotation Lemma in a strictly beneficial way and (2) providing results strongly indicating the feasibility of the techniques presented here as tools to be used in generic compilation procedures. This report provides proof of the novel theory coming out of this project, alongside a design and implementation of an end-to-end QASM-to-QASM compiler using staq as the base [3]. This compiler is very efficient on large circuits and provides CX count, and depth reductions of up to 42\% after existing methods are applied.}
}
@mastersthesis{Laakkonen2022Masters,
author = {Laakkonen, Tuomas},
title = {{Graphical Stabilizer Decompositions For Counting Problems}},
year = {2022},
school = {University of Oxford},
urldate = {2022-10-15},
link = {https://www.cs.ox.ac.uk/people/aleks.kissinger/theses/laakkonen-thesis.pdf},
keywords = {ZX-Calculus, ZH-calculus, Classical Simulation, SAT, Applied, Master Thesis},
abstract = {Building on the work of de Beaudrap, Kissinger, and Meichanetzidis [dKM21], in this dissertation, we examine the relationship between #SAT and the ZH calculus. We outline their reduction from \#SAT to evaluating ZH diagrams, which shows that evaluating ZH diagrams is \#P-hard, and we extend this to show that evaluating diagrams in certain fragments of the ZH calculus, is $FP^{\#P}$-complete. In particular, we show this holds for diagrams where all H-boxes have labels in $\mathbb{Q}[i,\sqrt{2}]$, which includes both the Clifford+T and Toffoli-Hadamard fragments natively [BKM+21]. We show the action of the DPLL algorithm [DLL62] for SAT and its derivative CDP [BL99] for \#SAT in terms of ZH-diagrams, and use diagrammatic methods to extend CDP to treat variables and clauses equally. Combining this with an algorithm for \#2SAT by Wahlström [Wah08], we derive novel upper bounds in terms of clauses and variables for \#kSAT that are independent of $k$, and better than brute-force for small clause densities of $\frac{m}{n} < 2.25$.
This improves on the upper bound of Dubois [Dub91] whenever $\frac{m}{n} < 1.858$ and $k \geq 4$, and the average-case analysis by Williams [Wil04] whenever $\frac{m}{n} < 1.217$ and $k \geq 6$. We also obtain an unconditional upper bound of
$O∗(1.88m)$ for \#4SAT in terms of clauses only.
Finally, we find novel stabilizer decompositions of certain ZH-diagrams and use this to adapt the algorithm of Kissinger and van de Wetering [Kv21] [KvV22] for evaluating ZX-diagrams using stabilizer decompositions to evaluate \#2SAT instances. We examine the effect of different decomposition strategies on its runtime but conclude that the algorithm as given is not
effective, and suggest avenues for further improvement.}
}
@article{cerveromartín2022barren,
author = {Cervero Martín, Enrique and Plekhanov, Kirill and Lubasch, Michael},
title = {{Barren plateaus in quantum tensor network optimization}},
year = {2022},
journal = {arXiv preprint arXiv:2209.00292},
urldate = {2022-09-01},
link = {http://arxiv.org/abs/2209.00292},
keywords = {ZX-calculus, Variational Circuits, Applied, Tensor Networks},
abstract = {We analyze the barren plateau phenomenon in the variational optimization of quantum circuits inspired by matrix product states (qMPS), tree tensor networks (qTTN), and the multiscale entanglement renormalization ansatz (qMERA). We consider as the cost function the expectation value of a Hamiltonian that is a sum of local terms. For randomly chosen variational parameters we show that the variance of the cost function gradient decreases exponentially with the distance of a Hamiltonian term from the canonical centre in the quantum tensor network. Therefore, as a function of qubit count, for qMPS most gradient variances decrease exponentially and for qTTN as well as qMERA they decrease polynomially. We also show that the calculation of these gradients is exponentially more efficient on a classical computer than on a quantum computer.}
}
@article{9868772,
author = {Peham, Tom and Burgholzer, Lukas and Wille, Robert},
title = {Equivalence Checking of Quantum Circuits with the ZX-Calculus},
year = {2022},
journal = {IEEE Journal on Emerging and Selected Topics in Circuits and Systems},
volume = {},
number = {},
pages = {1-1},
doi = {10.1109/JETCAS.2022.3202204},
urldate = {2022-08-26},
link = {https://ieeexplore.ieee.org/document/9868772/authors#authors},
keywords = {ZX-calculus, Verification, Applied, Automation, Sum-Over-Paths},
abstract = {As state-of-the-art quantum computers are capable of running increasingly complex algorithms, the need for automated methods to design and test potential applications rises. Equivalence checking of quantum circuits is an important, yet hardly automated, task in the development of the quantum software stack. Recently, new methods have been proposed that tackle this problem from widely different perspectives. One of them is based on the ZX-calculus, a graphical rewriting system for quantum computing. However, the power and capability of this equivalence checking method has barely been explored. The aim of this work is to evaluate the ZX-calculus as a tool for equivalence checking of quantum circuits. To this end, it is demonstrated how the ZX-calculus based approach for equivalence checking can be expanded in order to verify the results of compilation flows and optimizations on quantum circuits. It is also shown that the ZX-calculus based method is not complete–especially for quantum circuits with ancillary qubits. In order to properly evaluate the proposed method, we conduct a detailed case study by comparing it to two other state-of-the-art methods for equivalence checking: one based on path-sums and another based on decision diagrams. The proposed methods have been integrated into the publicly available QCEC tool (https://github.com/cda-tum/qcec) which is part of the Munich Quantum Toolkit (MQT).}
}
@inproceedings{10.1145/3489517.3530480,
author = {Peham, Tom and Burgholzer, Lukas and Wille, Robert},
title = {Equivalence Checking Paradigms in Quantum Circuit Design: A Case Study},
year = {2022},
booktitle = {Proceedings of the 59th ACM/IEEE Design Automation Conference},
series = {DAC '22},
pages = {517–522},
numpages = {6},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
isbn = {9781450391429},
location = {San Francisco, California},
doi = {10.1145/3489517.3530480},
urldate = {2022-08-23},
link = {https://doi.org/10.1145/3489517.3530480},
keywords = {ZX-calculus, Verification, Applied},
abstract = {As state-of-the-art quantum computers are capable of running increasingly complex algorithms, the need for automated methods to design and test potential applications rises. Equivalence checking of quantum circuits is an important, yet hardly automated, task in the development of the quantum software stack. Recently, new methods have been proposed that tackle this problem from widely different perspectives. However, there is no established baseline on which to judge current and future progress in equivalence checking of quantum circuits. In order to close this gap, we conduct a detailed case study of two of the most promising equivalence checking methodologies---one based on decision diagrams and one based on the ZX-calculus---and compare their strengths and weaknesses.}
}
@phdthesis{East2022thesis,
author = {East, Richard},
title = {{Formal diagrammatic spin physics}},
year = {2022},
school = {Universit\'e Grenoble Alpes},
urldate = {2022-07-11},
link = {https://tel.archives-ouvertes.fr/tel-03719945},
keywords = {ZX-calculus, ZH-calculus, Tensor Networks, PyZX, Condensed Matter, Applied, PhD Thesis},
abstract = {Diagrams are ubiquitous in physics and have catalysed progress on numerous occasions. From
tensor networks and quantum circuits to Feynman diagrams, there are few areas of physics
that don’t employ some informal pictorial reasoning. These diagrams represent the underlying
mathematical operations and aid physical interpretation, but cannot generally be computed
with directly. In this thesis the ZXH-calculus, a graphical language based on the ZX-calculus,
is offered as a prototype for a formal diagrammatic calculational tool for theoretical physics
involving spin. This extends the ZXH-calculus (and more broadly the ZX family of calculi to
which it belongs) beyond its traditional domain which has largely been dominated by quantum
computing. In order to do this the spin lattices taken from condensed matter physics are studied.
It is also shown how spin-networks of the form often seen as the state-space of loop quantum
gravity (LQG) can diagrammatised along with operators acting on them.
To achieve this a diagrammatic form of SU(2) representation theory is outlined. Following this
in condensed matter a number of results are shown. The 1D AKLT state, a symmetry protected
topological state, is expressed 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 it
is shown how this representation straightforwardly recovers the AKLT matrix-product state
representation, the existence of topologically protected edge states, and the non-vanishing of a
string order parameter. Extending beyond these known properties, the diagrammatic approach
also allows one to analytically derive that the Berry phase of any finite-length 1D AKLT chain
is π. In addition, 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.
Continuing on the theme of condensed matter it is then shown how one can build 2D higher-order
topological phases diagrammatically, which is used to illustrate a symmetry-breaking phase
transition.
Turning to LQG the first step is the analysis of Yutsis diagrams, a standard graphical calculus
used in quantum chemistry and quantum gravity, which captures the main features of SU(2)
representation theory. Second, it is shown how it embeds within Penrose’s binor calculus. The
two are then rewritten as ZXH-diagrams. In the process we show how the SU(2) invariance
of Wigner symbols is trivially provable in the ZXH-calculus. Additionally, we show how we
can explicitly diagrammatically calculate 3jm, 4jm and 6j symbols. It has long been thought
that quantum gravity should be closely aligned to quantum information theory. In this paper,
we present a way in which this connection can be made exact, by writing the spin-networks
of loop quantum gravity in the ZX-diagrammatic language of quantum computation. Finally
after outlining the motivation for considering spin-networks as the quantisation of space, the
geometric operators are discussed, and in specific cases diagrammatic versions of the operators
are provided. More generally what is done here shows a route by which LQG can be interpreted
in quantum informational terms by rewriting its kinematical states as networks of qubits in
ZXH.
In total these results demonstrate that the ZXH-calculus is a powerful language for representing
quantum systems and even allows for the computation on physical states entirely graphically.
Within condensed matter it is hoped this will pave the way to develop more efficient many-body
algorithms and giving a novel diagrammatic perspective on quantum phase transitions. In
LQG it is hoped this re-imagining of its state space will spur further integration of quantum
information and gravity.}
}
@inproceedings{10.1145/3489517.3530627,
author = {Wille, Robert and Burgholzer, Lukas and Hillmich, Stefan and Grurl, Thomas and Ploier, Alexander and Peham, Tom},
title = {{The Basis of Design Tools for Quantum Computing: Arrays, Decision Diagrams, Tensor Networks, and ZX-Calculus}},
year = {2022},
booktitle = {Proceedings of the 59th ACM/IEEE Design Automation Conference},
series = {DAC '22},
pages = {1367–1370},
numpages = {4},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
isbn = {9781450391429},
location = {San Francisco, California},
doi = {10.1145/3489517.3530627},
urldate = {2022-07-01},
link = {https://doi.org/10.1145/3489517.3530627},
keywords = {ZX-calculus, Verification, Classical Simulation, Optimisation, Applied},
abstract = {Quantum computers promise to efficiently solve important problems classical computers never will. However, in order to capitalize on these prospects, a fully automated quantum software stack needs to be developed. This involves a multitude of complex tasks from the classical simulation of quantum circuits, over their compilation to specific devices, to the verification of the circuits to be executed as well as the obtained results. All of these tasks are highly non-trivial and necessitate efficient data structures to tackle the inherent complexity. Starting from rather straight-forward arrays over decision diagrams (inspired by the design automation community) to tensor networks and the ZX-calculus, various complementary approaches have been proposed. This work provides a look "under the hood" of today's tools and showcases how these means are utilized in them, e.g., for simulation, compilation, and verification of quantum circuits.}
}
@article{cao2022multiagent,
author = {Cao, Shuxiang},
title = {{Multi-agent blind quantum computation without universal cluster state}},
year = {2022},
journal = {arXiv preprint arXiv:2206.13330},
urldate = {2022-06-27},
link = {http://arxiv.org/abs/2206.13330},
keywords = {MBQC, gflow, Applied, Graph States},
abstract = {Blind quantum computation (BQC) protocols enable quantum algorithms to be executed on third-party quantum agents while keeping the data and algorithm confidential. The previous proposals for measurement-based BQC require preparing a highly entangled cluster state. In this paper, we show that such a requirement is not necessary. Our protocol only requires pre-shared bell pairs between delegated quantum agents, and there is no requirement of any classical or quantum information exchange between agents during the execution. Our proposal requires fewer quantum resources than previous proposals by removing the universal cluster state.}
}
@article{gidney2022pair,
author = {Gidney, Craig},
title = {{A Pair Measurement Surface Code on Pentagons}},
year = {2022},
journal = {arXiv preprint arXiv:2206.12780},
urldate = {2022-06-26},
link = {http://arxiv.org/abs/2206.12780},
keywords = {Surface Code, ZX-calculus, Applied},
abstract = {In this paper, I present a way to compile the surface code into two-body parity measurements ("pair measurements"), where the pair measurements run along the edges of a Cairo pentagonal tiling. The resulting circuit improves on prior work by Chao et al. by using fewer pair measurements per four-body stabilizer measurement (5 instead of 6) and fewer time steps per round of stabilizer measurement (6 instead of 10). Using Monte Carlo sampling, I show that these improvements increase the threshold of the surface code when compiling into pair measurements from $\approx 0.2\%$ to $\approx 0.4\%$, and also that they improve the teraquop footprint at a $0.1\%$ physical gate error rate from $\approx6000$ qubits to $\approx3000$ qubits. However, I also show that Chao et al's construction will have a smaller teraquop footprint for physical gate error rates below $\approx 0.03\%$ (due to bidirectional hook errors in my construction). I also compare to the planar honeycomb code, showing that although this work does noticeably reduce the gap between the surface code and the honeycomb code (when compiling into pair measurements), the honeycomb code is still more efficient (threshold $\approx 0.8\%$, teraquop footprint at $0.1\%$ of $\approx 1000$).}
}
@article{gogioso2022annealing,
author = {Gogioso, Stefano and Yeung, Richie},
title = {{Annealing optimisation of Mixed ZX Phase Circuits}},
year = {2022},
journal = {arXiv preprint arXiv:2206.11839},
urldate = {2022-06-23},
link = {http://arxiv.org/abs/2206.11839},
keywords = {ZX-calculus, Applied, Phase Gadgets, Optimisation, Variational Circuits},
abstract = {We present a topology-aware optimisation technique for circuits of mixed ZX phase gadgets, based on conjugation by CX gates and simulated annealing.},
video = {https://youtu.be/WZgDVPXo7WQ?t=2706}
}
@article{cl?ent2022complete,
author = {Cl{\'e}ment, Alexandre and Heurtel, Nicolas and Mansfield, Shane and Perdrix, Simon and Valiron, Beno{\^i}t},
title = {{A Complete Equational Theory for Quantum Circuits}},
year = {2022},
journal = {arXiv preprint arXiv:2206.10577},
urldate = {2022-06-21},
link = {http://arxiv.org/abs/2206.10577},
keywords = {Completeness, Universal Fragment, Toffoli, ZX-Supported},
abstract = {We introduce the first complete equational theory for quantum circuits. More precisely, we introduce a set of circuit equations that we prove to be sound and complete: two circuits represent the same unitary map if and only if they can be transformed one into the other using the equations. The proof is based on the properties of multi-controlled gates -- that are defined using elementary gates -- together with an encoding of quantum circuits into linear optical circuits, which have been proved to have a complete axiomatisation.}
}
@inproceedings{Staudacher2022reducing,
author = {Staudacher, Korbinian and Guggemos, Tobias and Grundner-Culemann, Sophia},
title = {{Reducing 2-qubit gate count for ZX-calculus based quantum circuit optimization}},
year = {2022},
booktitle = {Proceedings 19th International Conference on Quantum Physics and Logic, University of Oxford, United Kingdom, 27 June - 1 July 2022},
editor = {Gogioso, Stefano and Hoban, Matty},
series = {Electronic Proceedings in Theoretical Computer Science},
volume = {To appear},
pages = {TBD},
publisher = {Open Publishing Association},
urldate = {2022-06-20},
link = {https://www.qplconference.org/proceedings2022/QPL_2022_paper_10.pdf},
keywords = {Optimisation, ZX-calculus, Optimisation, PyZX, Applied, Local Complementation},
abstract = {In the near term, programming quantum computers will remain severely limited by low quantum volumes. Therefore, it is desirable to implement quantum circuits with the fewest resources possible. For the common Clifford+T circuits, most research is focused on reducing the number of T gates, since they are an order of magnitude more expensive than Clifford gates in quantum error corrected encoding schemes. However, this optimization sometimes leads to more 2-qubit gates, which, even though they are less expensive in terms of fault-tolerance, contribute significantly to the overall circuit cost. Approaches based on the ZX-calculus have recently gained some popularity in the field, but reduction of 2-qubit gates is not their focus. In this work, we present an alternative for improving 2-qubit gate count of a quantum circuit with the ZX-calculus by using heuristics in ZX-diagram simplification. Our approach maintains the good reduction of the T gate count provided by other strategies based on ZX-calculus, thus serving as an extension for other optimization algorithms. Our results show that combining the available ZX-calculus-based optimizations with our algorithms can reduce the number of 2-qubit gates by as much as 40\% compared to current approaches using ZXcalculus. Additionally, we improve the results of the best currently available optimization technique of Nam et. al [22] for some circuits by up to 15\%.}
}
@article{borgna2022encoding,
author = {Borgna, Agustín and Romero, Rafael},
title = {{Encoding High-level Quantum Programs as SZX-diagrams}},
year = {2022},
journal = {arXiv preprint arXiv:2206.09376},
urldate = {2022-06-19},
link = {http://arxiv.org/abs/2206.09376},
keywords = {Scalable ZX, ZX-calculus, Protocols},
abstract = {The Scalable ZX-calculus is a compact graphical language used to reason about linear maps between quantum states. These diagrams have multiple applications, but they frequently have to be constructed in a case-by-case basis. In this work we present a method to encode quantum programs implemented in a fragment of the linear dependently typed Proto-Quipper-D language as families of SZX-diagrams. We define a subset of translatable Proto-Quipper-D programs and show that our procedure is able to encode non-trivial algorithms as diagrams that grow linearly on the size of the program.},
video = {https://www.youtube.com/watch?v=umYCWcBtXhs}
}
@article{lehmann2022vyzx,
author = {Lehmann, Adrian and Caldwell, Ben and Rand, Robert},
title = {{VyZX : A Vision for Verifying the ZX Calculus}},
year = {2022},
journal = {arXiv preprint arXiv:2205.05781},
urldate = {2022-05-11},
link = {http://arxiv.org/abs/2205.05781},
keywords = {ZX-calculus, Automation, Applied, Verification},
abstract = {Optimizing quantum circuits is a key challenge for quantum computing. The PyZX compiler broke new ground by optimizing circuits via the ZX calculus, a powerful graphical alternative to the quantum circuit model. Still, it carries no guarantee of its correctness. To address this, we developed VyZX, a verified ZX-calculus in the Coq proof assistant. VyZX provides two distinct representations of ZX diagrams for ease of programming and proof: A graph-based representation for writing high-level functions on diagrams and a block-based representation for proving ZX diagrams equivalent. Through these two different views, VyZX provides the tools necessary to verify properties and transformations of ZX diagrams. This paper explores the proofs and design choices underlying VyZX and its application and the challenges of verifying a graphical programming language.},
video = {https://www.youtube.com/watch?v=sPv-ufgLr1E}
}
@article{mcelvanney2022complete,
author = {McElvanney, Tommy and Backens, Miriam},
title = {{Complete flow-preserving rewrite rules for MBQC patterns with Pauli measurements}},
year = {2022},
journal = {arXiv preprint arXiv:2205.02009},
urldate = {2022-05-04},
link = {http://arxiv.org/abs/2205.02009},
keywords = {ZX-calculus, Clifford Fragment, gflow, Circuit Extraction, Local Complementation},
abstract = {In the one-way model of measurement-based quantum computation (MBQC), computation proceeds via measurements on some standard resource state. So-called flow conditions ensure that the overall computation is deterministic in a suitable sense, with Pauli flow being the most general of these. Existing work on rewriting MBQC patterns while preserving the existence of flow has focused on rewrites that reduce the number of qubits. In this work, we show that introducing new $Z$-measured qubits, connected to any subset of the existing qubits, preserves the existence of Pauli flow. Furthermore, we give a unique canonical form for stabilizer ZX-diagrams inspired by recent work of Hu & Khesin [arXiv:2109.10210]. We prove that any MBQC-like stabilizer ZX-diagram with Pauli flow can be rewritten into this canonical form using only rules which preserve the existence of Pauli flow and that each of these rules can be reversed while also preserving the existence of Pauli flow. Hence we have complete graphical rewriting for MBQC-like stabilizer ZX-diagrams with Pauli flow.},
video = {https://www.youtube.com/watch?v=Hpk3JKdj4vo}
}
@article{kissinger2022phasefree,
author = {Kissinger, Aleks},
title = {{Phase-free ZX diagrams are CSS codes (...or how to graphically grok the surface code)}},
year = {2022},
journal = {arXiv preprint arXiv:2204.14038},
urldate = {2022-04-29},
link = {http://arxiv.org/abs/2204.14038},
keywords = {ZX-calculus, Surface Code, Lattice Surgery, Error correcting codes},
abstract = {In this paper, we demonstrate a direct correspondence between phase-free ZX diagrams, a graphical notation for representing and manipulating a certain class of linear maps on qubits, and Calderbank-Shor-Steane (CSS) codes, a large family of quantum error correcting codes constructed from classical codes, including for example the Steane code, surface codes, and colour codes. The stabilisers of a CSS code have an especially nice structure arising from a pair of orthogonal $\mathbb F_2$-linear subspaces, or in the case of maximal CSS codes, a single subspace and its orthocomplement. On the other hand, phase-free ZX diagrams can always be efficiently reduced to a normal form given by the basis elements of an $\mathbb F_2$-linear subspace. Here, we will show that these two ways of describing a quantum state by an $\mathbb F_2$-linear subspace $S$ are in fact the same. Namely, the maximal CSS code generated by $S$ fixes the quantum state whose ZX normal form is also given by $S$. This insight gives us an immediate translation from stabilisers of a maximal CSS code into a ZX diagram describing its associated state. We show that we can extend this translation to stabilisers and logical operators of any (possibly non-maximal) CSS code by "bending wires". To demonstrate the utility of this translation, we give a simple picture of the surface code and a fully graphical derivation of the action of physical lattice surgery operations on the space of logical qubits, completing the ZX presentation of lattice surgery initiated by de Beudrap and Horsman.},
video = {https://www.youtube.com/watch?v=VVhBGpCMlwA}
}
@article{Chardonnet2022ManyWorlds,
author = {Chardonnet, Kostia and de Visme, Marc and Valiron, Benoit and Vilmart, Renaud},
title = {{The Many-Worlds Calculus: Representing Quantum Control}},
year = {2022},
journal = {HAL preprint: hal-03654190},
urldate = {2022-04-28},
link = {https://hal.archives-ouvertes.fr/hal-03654190},
keywords = {ZX-calculus, Category Theory, Completeness},
abstract = {We propose a new typed graphical language for quantum computation, based on compact categories with biproducts. Our language generalizes existing approaches such as ZX-calculus and quantum circuits, while offering a natural framework to support quantum control: it natively supports "quantum tests". The language comes equipped with a denotational semantics based on linear applications, and an equational theory. Through the use of normal forms for the diagrams, we prove the language to be universal, and the equational theory to be complete with respect to the semantics.}
}
@article{vandewetering2022phase,
author = {van de Wetering, John and Yeh, Lia},
title = {{Phase gadget compilation for diagonal qutrit gates}},
year = {2022},
journal = {arXiv preprint arXiv:2204.13681},
urldate = {2022-04-28},
link = {http://arxiv.org/abs/2204.13681},
keywords = {ZX-calculus, Qutrits, Phase Gadgets, Applied, Clifford Fragment},
abstract = {Phase gadgets have proved to be an indispensable tool for reasoning about ZX-diagrams, being used in optimisation and simulation of quantum circuits and the theory of measurement-based quantum computation. In this paper we study phase gadgets for qutrits. We present the flexsymmetric variant of the original qutrit ZX-calculus, which allows for rewriting that is closer in spirit to the original (qubit) ZX-calculus. In this calculus phase gadgets look as you would expect, but there are non-trivial differences in their properties. We devise new qutrit-specific tricks to extend the graphical Fourier theory of qubits, resulting in a translation between the 'additive' phase gadgets and a 'multiplicative' counterpart we dub phase multipliers. This enables us to build different types of qutrit multiple-controlled phase gates. As an application of these results we find a construction for emulating arbitrary qubit diagonal unitaries, and specifically find an emulation for the qubit CCZ gate that only requires three single-qutrit non-Clifford gates to implement - provably lower than the four T gates needed using just qubit gates.},
video = {https://youtu.be/v_y8Wu6GLxc?t=2548}
}
@article{Vilmart2022Completeness,
author = {Vilmart, Renaud},
title = {{Completeness of Sum-Over-Paths for Toffoli-Hadamard and the Clifford Hierarchy}},
year = {2022},
journal = {HAL preprint: hal-03654438},
urldate = {2022-04-28},
link = {https://hal.archives-ouvertes.fr/hal-03654438},
keywords = {ZH-calculus, Completeness, Sum-Over-Paths},
abstract = {The "Sum-Over-Paths" formalism is a way to symbolically manipulate linear maps that describe quantum systems, and is a tool that is used in formal verification. We give here a new set of rewrite rules for the formalism, and show that it is complete for "Toffoli-Hadamard", the simplest approximately universal fragment of quantum mechanics. We show that the rewriting is terminating, but not confluent (which is expected from the universality of the fragment). We do so using the connection between Sum-over-Paths and graphical language ZH-Calculus, and also show how the axiomatization translates into the latter. Finally, we show how to enrich the rewrite system to reach completeness for the whole Clifford hierarchy.}
}
@article{defelice2022quantum,
author = {de Felice, Giovanni and Coecke, Bob},
title = {{Quantum Linear Optics via String Diagrams}},
year = {2022},
journal = {arXiv preprint arXiv:2204.12985},
urldate = {2022-04-27},
link = {http://arxiv.org/abs/2204.12985},
keywords = {ZX-calculus, Applied, Pauli Fusion, Completeness},
abstract = {We establish a formal bridge between qubit-based and photonic quantum computing. We do this by defining a functor from the ZX calculus to linear optical circuits. In the process we provide a compositional theory of quantum linear optics which allows to reason about events involving multiple photons such as those required to perform linear-optical and fusion-based quantum computing.},
video = {https://www.youtube.com/watch?v=BomcbwrJxvs}
}
@article{cowtan2022qudit,
author = {Cowtan, Alexander},
title = {{Qudit lattice surgery}},
year = {2022},
journal = {arXiv preprint arXiv:2204.13228},
urldate = {2022-04-27},
link = {http://arxiv.org/abs/2204.13228},
keywords = {ZX-calculus, Qudits, Lattice Surgery, Surface Code},
abstract = {We observe that lattice surgery, a model of fault-tolerant qubit computation, generalises straightforwardly to arbitrary finite-dimensional qudits. The generalised model is based on the group algebras $\mathbb{C}\mathbb{Z}_d$ for $d \geq 2$. It still requires magic state injection for universal quantum computation. We relate the model to the ZX-calculus, a diagrammatic language based on Hopf-Frobenius algebras.},
video = {https://youtu.be/eNCefHNnw0A?t=3623}
}
@article{booth2022complete,
author = {I. Booth, Robert and Carette, Titouan},
title = {{Complete ZX-calculi for the stabiliser fragment in odd prime dimensions}},
year = {2022},
journal = {arXiv preprint arXiv:2204.12531},
urldate = {2022-04-26},
link = {http://arxiv.org/abs/2204.12531},
keywords = {ZX-calculus, Completeness, Qudits, Clifford Fragment, Local Complementation, Graph States, Mixed States},
abstract = {We introduce a family of ZX-calculi which axiomatise the stabiliser fragment of quantum theory in odd prime dimensions. These calculi recover many of the nice features of the qubit ZX-calculus which were lost in previous proposals for higher-dimensional systems. We then prove that these calculi are complete, i.e. provide a set of rewrite rules which can be used to prove any equality of stabiliser quantum operations. Adding a discard construction, we obtain a calculus complete for mixed state stabiliser quantum mechanics in odd prime dimensions, and this furthermore gives a complete axiomatisation for the related diagrammatic language for affine co-isotropic relations.},
video = {https://www.youtube.com/watch?v=v_y8Wu6GLxc}
}
@article{carette2022largescale,
author = {Carette, Titouan and Lemonnier, Louis},
title = {{Large-scale quantum diagrammatic reasoning tools, !-boxes vs. scalable notations}},
year = {2022},
journal = {arXiv preprint arXiv:2204.11702},
urldate = {2022-04-25},
link = {http://arxiv.org/abs/2204.11702},
keywords = {Scalable ZX, ZH-calculus, !-boxes, Hypergraph, Local Complementation, Graph States},
abstract = {The application of diagrammatic reasoning techniques to large-scale quantum processes needs specific tools to describe families of diagrams of arbitrary size. For now, large-scale diagrammatic reasoning tools in ZH-calculus come in two flavours, !-boxes and scalable notations. This paper investigates the interactions between the two approaches by exhibiting correspondences through various examples from the literature, focusing on (hyper)graph states and diagrammatic transforms. In doing so, we set up a path toward a neat and tidy large-scale diagrammatic reasoning toolbox.},
video = {https://www.youtube.com/watch?v=9yXEoyt8YCA}
}
@article{Winderl2022ZXPolynomial,
author = {Winderl, David},
title = {{ZX Polynomial Synthesis}},
year = {2022},
journal = {Preprint},
urldate = {2022-04-23},
link = {https://mediatum.ub.tum.de/doc/1658567/0cqw8i7hoo3k7g3wsrbs0k51m.pdf},
keywords = {ZX-calculus, Optimisation, Applied, Phase Gadgets},
abstract = {The Noisy intermediate state quantum devices era (NISQ era) in quantum computing can be seen as the era of quantum devices with 50-100 qubits, which provide restricted connectivity between qubits and nosy qubits with a limited coherence time. This issue motivates efficient algorithms to reduce the number of gates applied to circuits in an automated way, similar to the simplification process of classical compilers. Various researchers have proposed methods that reduce the number of gates, and the depth of the quantum circuit. Nevertheless, providing a routed circuit, so a circuit that suffices the connectivity graph of the device was always considered a process that is done after optimization. Griend et al. has proposed a recursive algorithm for synthesizing so-called Z polynomials. Moreover, they showed that optimization and routing in combination are pretty effective for Z Polynomials. Hence they proposed the avenue of future work to extend their algorithm to Pauli gadgets. This guided research aims to analyze the problem of general phase gadget synthesis. Herefore we provide two extensions to the algorithm by Griend et al.. One extension focuses on splitting the ZX Polynomial into smaller commuting regions, while the other tries to identify blocking columns and resolve them beforehand. Next, we provide an algorithm based on the A* search heuristic. Finally, we compare our results to the Pauli-Gadet simplification-pass by tket combined with their internal routing strategy and our optimization strategy with pyzx concerning one qubit gates}
}
@article{stollenwerk2022diagrammatic,
author = {Stollenwerk, Tobias and Hadfield, Stuart},
title = {{Diagrammatic Analysis for Parameterized Quantum Circuits}},
year = {2022},
journal = {arXiv preprint arXiv:2204.01307},
urldate = {2022-04-04},
link = {http://arxiv.org/abs/2204.01307},
keywords = {ZX-calculus, Variational Circuits, Applied},
abstract = {Diagrammatic representations of quantum algorithms and circuits offer novel approaches to their design and analysis. In this work, we describe extensions of the ZX-calculus especially suitable for parameterized quantum circuits, in particular for computing observable expectation values as functions of or for fixed parameters, which are important algorithmic quantities in a variety of applications ranging from combinatorial optimization to quantum chemistry. We provide several new ZX-diagram rewrite rules and generalizations for this setting. In particular, we give formal rules for dealing with linear combinations of ZX-diagrams, where the relative complex-valued scale factors of each diagram must be kept track of, in contrast to most previously studied single-diagram realizations where these coefficients can be effectively ignored. This allows us to directly import a number useful relations from the operator analysis to ZX-calculus setting, including causal cone and quantum gate commutation rules. We demonstrate that the diagrammatic approach offers useful insights into algorithm structure and performance by considering several ans\"atze from the literature including realizations of hardware-efficient ans\"atze and QAOA. We find that by employing a diagrammatic representation, calculations across different ans\"atze can become more intuitive and potentially easier approach systematically than by alternative means. Finally, we outline how diagrammatic approaches may aid in the design and study of new and more effective quantum circuit ans\"atze.},
video = {https://youtu.be/0YJgSJvBZH0?t=2789}
}
@inproceedings{Yeh2022Constructing,
author = {Yeh, Lia and van de Wetering, John},
title = {{Constructing All Qutrit Controlled Clifford+T gates in Clifford+T}},
year = {2022},
booktitle = {Reversible Computation},
editor = {Mezzina, Claudio Antares and Podlaski, Krzysztof},
pages = {28--50},
publisher = {Springer International Publishing},
address = {Cham},
isbn = {978-3-031-09005-9},
doi = {10.1007/978-3-031-09005-9_3},
urldate = {2022-04-01},
link = {https://arxiv.org/abs/2204.00552},
keywords = {Qutrits, Optimisation, Clifford+T, ZX-Supported},
abstract = {For a number of useful quantum circuits, qudit constructions have been found which reduce resource requirements compared to the best known or best possible qubit construction. However, many of the necessary qutrit gates in these constructions have never been explicitly and efficiently constructed in a fault-tolerant manner. We show how to exactly and unitarily construct any qutrit multiple-controlled Clifford+T unitary using just Clifford+T gates and without using ancillae. The T-count to do so is polynomial in the number of controls k, scaling as $O(k^{3.585})$. With our results we can construct ancilla-free Clifford+T implementations of multiple-controlled T gates as well as all versions of the qutrit multiple-controlled Toffoli, while the analogous results for qubits are impossible. As an application of our results, we provide a procedure to implement any ternary classical reversible function on $n$ trits as an ancilla-free qutrit unitary using $O(3^n n^{3.585})$ T gates.}
}
@article{jeandel2022addition,
author = {Jeandel, Emmanuel and Perdrix, Simon and Veshchezerova, Margarita},
title = {{Addition and Differentiation of ZX-diagrams}},
year = {2022},
journal = {arXiv preprint arXiv:2202.11386},
urldate = {2022-02-23},
link = {http://arxiv.org/abs/2202.11386},
keywords = {ZX-calculus, Applied, Variational Circuits},
abstract = {The ZX-calculus is a powerful framework for reasoning in quantum computing. It provides in particular a compact representation of matrices of interests. A peculiar property of the ZX-calculus is the absence of a formal sum allowing the linear combinations of arbitrary ZX-diagrams. The universality of the formalism guarantees however that for any two ZX-diagrams, the sum of their interpretations can be represented by a ZX-diagram. We introduce a general, inductive definition of the addition of ZX-diagrams, relying on the construction of controlled diagrams. Based on this addition technique, we provide an inductive differentiation of ZX-diagrams. Indeed, given a ZX-diagram with variables in the description of its angles, one can differentiate the diagram according to one of these variables. Differentiation is ubiquitous in quantum mechanics and quantum computing (e.g. for solving optimization problems). Technically, differentiation of ZX-diagrams is strongly related to summation as witnessed by the product rules. We also introduce an alternative, non inductive, differentiation technique rather based on the isolation of the variables. Finally, we apply our results to deduce a diagram for an Ising Hamiltonian.},
video = {https://www.youtube.com/watch?v=_s2pOcrdmig}
}
@inproceedings{kissinger2022classical,
author = {Kissinger, Aleks and van de Wetering, John and Vilmart, Renaud},
title = {{Classical Simulation of Quantum Circuits with Partial and Graphical Stabiliser Decompositions}},
year = {2022},
booktitle = {17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)},
editor = {Le Gall, Fran\c{c}ois and Morimae, Tomoyuki},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {232},
pages = {5:1--5:13},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
isbn = {978-3-95977-237-2},
issn = {1868-8969},
doi = {10.4230/LIPIcs.TQC.2022.5},
urldate = {2022-02-18},
link = {http://arxiv.org/abs/2202.09202},
keywords = {ZX-calculus, Classical Simulation, Applied, PyZX, Automation},
abstract = {Recent developments in classical simulation of quantum circuits make use of clever decompositions of chunks of magic states into sums of efficiently simulable stabiliser states. We show here how, by considering certain non-stabiliser entangled states which have more favourable decompositions, we can speed up these simulations. This is made possible by using the ZX-calculus, which allows us to easily find instances of these entangled states in the simplified diagram representing the quantum circuit to be simulated. We additionally find a new technique of partial stabiliser decompositions that allow us to trade magic states for stabiliser terms. With this technique we require only $2^{\alpha t}$ stabiliser terms, where $\alpha\approx 0.396$, to simulate a circuit with T-count $t$. This matches the $\alpha$ found by Qassim et al., but whereas they only get this scaling in the asymptotic limit, ours applies for a circuit of any size. Our method builds upon a recently proposed scheme for simulation combining stabiliser decompositions and optimisation strategies implemented in the software QuiZX. With our techniques we manage to reliably simulate 50-qubit 1400 T-count hidden shift circuits in a couple of minutes on a consumer laptop.},
video = {https://youtu.be/y3LIDcgrc1k?t=1394}
}
@inproceedings{debeaudrap2022circuit,
author = {de Beaudrap, Niel and Kissinger, Aleks and van de Wetering, John},
title = {{Circuit Extraction for ZX-Diagrams Can Be #P-Hard}},
year = {2022},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {229},
pages = {119:1--119:19},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
isbn = {978-3-95977-235-8},
issn = {1868-8969},
doi = {10.4230/LIPIcs.ICALP.2022.119},
urldate = {2022-02-18},
link = {http://arxiv.org/abs/2202.09194},
keywords = {ZX-calculus, Circuit Extraction},
abstract = {The ZX-calculus is a graphical language for reasoning about quantum computation using ZX-diagrams, a certain flexible generalisation of quantum circuits that can be used to represent linear maps from $m$ to $n$ qubits for any $m,n \geq 0$. Some applications for the ZX-calculus, such as quantum circuit optimisation and synthesis, rely on being able to efficiently translate a ZX-diagram back into a quantum circuit of comparable size. While several sufficient conditions are known for describing families of ZX-diagrams that can be efficiently transformed back into circuits, it has previously been conjectured that the general problem of circuit extraction is hard. That is, that it should not be possible to efficiently convert an arbitrary ZX-diagram describing a unitary linear map into an equivalent quantum circuit. In this paper we prove this conjecture by showing that the circuit extraction problem is #P-hard, and so is itself at least as hard as strong simulation of quantum circuits. In addition to our main hardness result, which relies specifically on the circuit representation, we give a representation-agnostic hardness result. Namely, we show that any oracle that takes as input a ZX-diagram description of a unitary and produces samples of the output of the associated quantum computation enables efficient probabilistic solutions to NP-complete problems.},
video = {https://www.youtube.com/watch?v=d-2HSa9MHKY}
}
@inproceedings{glaudell2022Qutrit,
author = {Glaudell, Andrew N. and Ross, Neil J. and van de Wetering, John and Yeh, Lia},
title = {{Qutrit Metaplectic Gates Are a Subset of Clifford+T}},
year = {2022},
booktitle = {17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)},
editor = {Le Gall, Fran\c{c}ois and Morimae, Tomoyuki},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {232},
pages = {12:1--12:15},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
isbn = {978-3-95977-237-2},
issn = {1868-8969},
doi = {10.4230/LIPIcs.TQC.2022.12},
urldate = {2022-02-18},
link = {https://arxiv.org/abs/2202.09235},
keywords = {Qutrits, Optimisation, Clifford+T, ZX-Supported},
abstract = {A popular universal gate set for quantum computing with qubits is Clifford+T, as this can be readily implemented on many fault-tolerant architectures. For qutrits, there is an equivalent T gate, that, like its qubit analogue, makes Clifford+T approximately universal, is injectable by a magic state, and supports magic state distillation. However, it was claimed that a better gate set for qutrits might be Clifford+R, where R=diag(1,1,-1) is the metaplectic gate, as certain protocols and gates could more easily be implemented using the R gate than the T gate. In this paper we show that when we have at least two qutrits, the qutrit Clifford+R unitaries form a strict subset of the Clifford+T unitaries, by finding a direct decomposition of $R\otimes I$ as a Clifford+T circuit and proving that the T gate cannot be exactly synthesized in Clifford+R. This shows that in fact the T gate is at least as powerful as the R gate, up to a constant factor. Moreover, we additionally show that it is impossible to find a single-qutrit Clifford+T decomposition of the R gate, making our result tight.}
}
@mastersthesis{Peham2022masters,
author = {Peham, Tom},
title = {{Equivalence Checking of Quantum Circuits with the ZX-Calculus}},
year = {2022},
school = {Johannes Kepler Universit\"at Linz},
urldate = {2022-02-01},
link = {https://epub.jku.at/obvulihs/content/titleinfo/7683969},
keywords = {ZX-Calculus, Verification, Automation, Master Thesis},
abstract = {As state-of-the-art quantum computers are capable of running increasingly complex algorithms, the need for automated methods to design and test potential applications rises. Equivalence checking of quantum circuits is an important, yet hardly automated, task in the development of the quantum software stack. Recently, new methods have been proposed that tackle this problem from widely different perspectives. One of them is based on the ZX-calculus, a graphical rewriting system for quantum computing. However, the power and capability of this equivalence checking method has barely been explored. The aim of this work is to evaluate the ZX-calculus as a tool for equivalence checking of quantum circuits. To this end, it is demonstrated how the ZX-calculus-based approach to equivalence checking can be expanded in order to verify the results of compilation flows and optimizations on quantum circuits. It is also shown that the ZX-calculus based method is not complete — especially for quantum circuits with ancillary qubits. In order to properly evaluate the proposed method we conduct a detailed case study by comparing it to a prominent method in equivalence checking based on decision diagrams.}
}
@article{wang2022differentiating,
author = {Wang, Quanlong and Yeung, Richie},
title = {{Differentiating and Integrating ZX Diagrams}},
year = {2022},
journal = {arXiv preprint arXiv:2201.13250},
urldate = {2022-01-31},
link = {http://arxiv.org/abs/2201.13250},
keywords = {ZX-calculus, Applied, Variational Circuits},
abstract = {ZX-calculus has proved to be a useful tool for quantum technology with a wide range of successful applications. Most of these applications are of an algebraic nature. However, other tasks that involve differentiation and integration remain unreachable with current ZX techniques. Here we elevate ZX to an analytical perspective by realising differentiation and integration entirely within the framework of ZX-calculus. We explicitly illustrate the new analytic framework of ZX-calculus by applying it in context of quantum machine learning.},
video = {https://youtu.be/_s2pOcrdmig?t=2514}
}
@article{10.1145/3579367,
author = {Cuomo, Daniele and Caleffi, Marcello and Krsulich, Kevin and Tramonto, Filippo and Agliardi, Gabriele and Prati, Enrico and Cacciapuoti, Angela Sara},
title = {Optimized Compiler for Distributed Quantum Computing},
year = {2023},
journal = {ACM Transactions on Quantum Computing},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
issn = {2643-6809},
doi = {10.1145/3579367},
urldate = {2021-12-28},
link = {https://arxiv.org/abs/2112.14139},
keywords = {ZX-Supported, Applied, PyZX, Clifford Fragment},
abstract = {Practical distributed quantum computing requires the development of efficient compilers, able to make quantum circuits compatible with some given hardware constraints. This problem is known to be tough, even for local computing. Here, we address it on distributed architectures. As generally assumed in this scenario, telegates represent the fundamental remote (inter-processor) operations. Each telegate consists of several tasks: i) entanglement generation and distribution, ii) local operations, and iii) classical communications. Entanglement generations and distribution is an expensive resource, as it is time-consuming. To mitigate its impact, we model an optimization problem that combines running-time minimization with the usage of distributed entangled states. Specifically, we formulated the distributed compilation problem as a dynamic network flow. To enhance the solution space, we extend the formulation, by introducing a predicate that manipulates the circuit given in input and parallelizes telegate tasks. To evaluate our framework, we split the problem into three sub-problems, and solve it by means of an approximation routine. Experiments demonstrate that the run-time is resistant to the problem size scaling. Moreover, we apply the proposed algorithm to compile circuits under different topologies, showing that topologies with a higher ratio between edges and nodes give rise to shallower circuits}
}
@phdthesis{carette2021thesis,
author = {Carette, Titouan},
title = {{Wielding the ZX-calculus, Flexsymmetry, Mixed States, and Scalable Notations}},
year = {2021},
school = {Loria, Universit\'e de Lorraine},
urldate = {2021-12-06},
link = {https://hal.archives-ouvertes.fr/tel-03468027/document},
keywords = {ZX-calculus, Category Theory, Scalable ZX, Mixed States, ZH-calculus, ZW-calculus, Protocols, PhD Thesis},
abstract = {My first contribution is to propose a formalisation of this property through the notion of flexsymmetry in Chapter 5, it relies on the notion of paradigm introduced in Chapter 4. This equation called the bialgebra rule and making two spiders interact is the key ingredient in the definition of Z*-algebras in Chapter 6 where it is shown that the red and green spiders are not the only ones following this pattern. The introduction of Z*-algebras and the classification of all their models in qubits is the second contribution of this thesis. There are essentially three such structures for qubits, corresponding to the ZX-calculus, ZH-calculus, and ZW-calculus. Similar behaviour can also appear in other settings, as in the graphical linear algebra introduced in Chapter 7. All those calculi can then be used to represent quantum algorithms. But there are two obstacles. First, those algorithms can involve interactions with the non-quantum world that require a broader model of computation allowing classical behaviours alongside quantum ones.
This is called mixed state quantum mechanics and a way to extend quantum graphical languages to this setting is presented in Chapter 8. The extension of ZX-calculus to mixed-state quantum mechanics is the third contribution presented in this thesis. A second obstacle is the fact that a quantum algorithm is defined by a uniform family of circuits, one for each possible size of the input. The scalable notations presented in Chapter 9 allow to handle such families, completing the toolbox necessary to calmly approach quantum algorithm graphically. The scalable notations are the fourth and last theoretical contribution of this thesis.
All those methods can be used to graphically prove the correction of quantum algorithms. Examples are provided in Chapter 10, which concludes the thesis.}
}
@article{d.p.east2021spinnetworks,
author = {East, Richard D. P. and Martin-Dussaud, Pierre and van de Wetering, John},
title = {{Spin-networks in the ZX-calculus}},
year = {2021},
journal = {arXiv preprint arXiv:2111.03114},
urldate = {2021-11-04},
link = {http://arxiv.org/abs/2111.03114},
keywords = {ZH-calculus, Tensor Networks, Applied, PyZX},
abstract = {The ZX-calculus, and the variant we consider in this paper (ZXH-calculus), are formal diagrammatic languages for qubit quantum computing. We show that it can also be used to describe SU(2) representation theory. To achieve this, we first recall the definition of Yutsis diagrams, a standard graphical calculus used in quantum chemistry and quantum gravity, which captures the main features of SU(2) representation theory. Second, we show precisely how it embed within Penrose's binor calculus. Third, we subsume both calculus into ZXH-diagrams. In the process we show how the SU(2) invariance of Wigner symbols is trivially provable in the ZXH-calculus. Additionally, we show how we can explicitly diagrammatically calculate 3jm, 4jm and 6j symbols. It has long been thought that quantum gravity should be closely aligned to quantum information theory. In this paper, we present a way in which this connection can be made exact, by writing the spin-networks of loop quantum gravity (LQG) in the ZX-diagrammatic language of quantum computation.},
video = {https://www.youtube.com/watch?v=QLnW4h_UpT4}
}
@mastersthesis{Domitrz2022Masters,
author = {Domitrz, Witalis},
title = {{On the Verge to Improve Technique of T-count Reduction via Spider Nest Identities}},
year = {2021},
school = {University of Oxford},
urldate = {2021-10-22},
link = {https://www.cs.ox.ac.uk/people/aleks.kissinger/theses/domitrz-thesis.pdf},
keywords = {ZX-Calculus, Optimisation, T-count, Clifford+T, Phase Gadgets, Applied, Master Thesis},
abstract = {Approximate, universal quantum computation is most commonly described by circuits consisting of Clifford+T gates. The T gate, except being crucial for the universality, is the one which is, in real-world implementations, the most resource-intensive, and the least fault-tolerant of all operations. Because of that, a natural question emerges – how to reduce the number of T gates (or T-count) in a given circuit. The known methods used to reduce the T-count to an optimal value have an exponential running time [24, 2], which motivates the search for an efficient heuristic algorithm. The importance of this problem, along with proposed solutions were discussed in multiple publications including [6, 18, 16, 15, 7, 23]. Spider nest identities, introduced in [16], together with the decomposition of the circuit inspired by [18], were combined in [15] to provide an effective algorithm for T-count reduction. This approach was tested and compared with previous results, and, in some cases, it resulted in a significant improvement of the state of the art. Another advantage of this algorithm was, in contrast to the other results, a significant improvement of the execution time. In this dissertation, we discuss several modifications of the algorithm in order to gain partial outperformance without a significant increase of the running time, which include analysis of the influence of the order of applying the identities, efficient usage of identities generated from small and big spider nests, combining the results obtained in [25] with spider nest identities, and others. Some of these modifications improve or achieve the current state of the art for various circuits. We also provide a quantitative comparison of results, verified using [3] – a tool created alongside [4], on numerous benchmark circuits obtained from [9, 26, 3]. Moreover, we present abstract formulations of considered problem, pose a question of completeness of spider nest identities with respect to T-count reduction, and present different, possibly more elegant, way of phrasing the spider nest identities, as dense spider nest identities.}
}
@article{wang2021representing,
author = {Wang, Quanlong},
title = {{Representing Matrices Using Algebraic ZX-calculus}},
year = {2021},
journal = {arXiv preprint arXiv:2110.06898},
urldate = {2021-10-13},
link = {http://arxiv.org/abs/2110.06898},
keywords = {Algebraic ZX, Normal-Form},
abstract = {Elementary matrices play an important role in linear algebra applications. In this paper, we represent all the elementary matrices of size 2^m\times 2^m using algebraic ZX-calculus. Then we show their properties on inverses and transpose using rewriting rules of ZX-calculus. As a consequence, we are able to depict any matrices of size 2^m\times 2^n by string diagrams without resort to a diagrammatic normal form for matrices as shown in [Wang 2020]. By doing so we pave the way towards visualising by string diagrams important matrix technologies deployed in AI especially machine learning.},
video = {https://www.youtube.com/watch?v=E9BJZ2uAVOM}
}
@mastersthesis{staudacher2021masters,
author = {Staudacher, Korbinian},
title = {{Optimization Approaches for Quantum Circuits using ZX-calculus}},
year = {2021},
school = {Ludwig-Maximilians-Universit\"at M\"unchen},
urldate = {2021-09-30},
link = {https://www.mnm-team.org/pub/Diplomarbeiten/stau21/PDF-Version/stau21.pdf},
keywords = {ZX-Calculus, Optimisation, Automation, PyZX, Circuit Extraction, Master Thesis},
abstract = {This work focuses on quantum circuit optimization using the ZX-calculus, a recently developed graphical language designed to simplify reasoning about quantum systems. Quantum circuits can be optimized in an intuitive and efficient way by transforming them to equivalent ZX-diagrams and using rules of the ZX-calculus for diagram simplification. However, some rules can modify ZX-diagrams in such a way that the re-extraction of a quantum circuit is no longer possible. Moreover, rules that simplify ZX-diagrams can still increase the size of the underlying circuits. Due to these problems, most of the existing ZXcalculus based optimization approaches become inefficient with increasing quantum circuit complexity. In our work we develop different strategies to improve those approaches. In particular, we introduce heuristics to estimate the optimization benefit gained by certain ZX-rules. This allows treating ZX-diagram simplification as a classical search problem where heuristics can be applied to guide the sequence of rule applications towards minimal circuits. We implement different heuristic-based algorithms like greedy search, random search and simulated annealing in the open-source library PyZX where we test them against existing strategies on circuits of variant size. The results show that using heuristics in diagram simplification often leads to better overall optimization results, especially when optimizing large and complex quantum circuits. Our algorithms can be further improved in several aspects like runtime or consideration of hardware topology.
},
video = {https://youtu.be/WZgDVPXo7WQ?t=3805}
}
@article{wang2021nonanyonic,
author = {Wang, Quanlong},
title = {{A non-anyonic qudit ZW-calculus}},
year = {2021},
journal = {arXiv preprint arXiv:2109.11285},
urldate = {2021-09-23},
link = {http://arxiv.org/abs/2109.11285},
keywords = {ZW-calculus, Qudits, Algebraic ZX},
abstract = {ZW-calculus is a useful graphical language for pure qubit quantum computing. It is via the translation of the completeness of ZW-calculus that the first proof of completeness of ZX-calculus was obtained. A d-level generalisation of qubit ZW-calculus (anyonic qudit ZW-calculus) has been given in \cite{amar} which is universal for pure qudit quantum computing. However, the interpretation of the W spider in this type of ZW-calculus has so-called q-binomial coefficients involved, thus makes computation quite complicated. In this paper, we give a new type of qudit ZW-calculus which has generators and rewriting rules similar to that of the qubit ZW-calculus. Especially, the Z spider is exactly the same as that of the qudit ZX-calculus as given in \cite{wangqufinite}, and the new W spider has much simpler interpretation as a linear map. Furthermore, we establish a translation between this qudit ZW-calculus and the qudit ZX-calculus which is universal as shown in \cite{wangqufinite}, therefore this qudit ZW-calculus is also universal for pure qudit quantum computing.},
video = {https://www.youtube.com/watch?v=DjUn5llp0OE}
}
@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}
}
@inproceedings{borgna2021hybrid,
author = {Borgna, Agust{\'i}n and Perdrix, Simon and Valiron, Beno{\^i}t},
title = {{Hybrid quantum-classical circuit simplification with the ZX-calculus}},
year = {2021},
booktitle = {Programming Languages and Systems},
editor = {Oh, Hakjoo},
pages = {121--139},
publisher = {Springer International Publishing},
address = {Cham},
doi = {10.1007/978-3-030-89051-3_8},
urldate = {2021-09-13},
link = {http://arxiv.org/abs/2109.06071},
keywords = {ZX-calculus, Mixed States, Optimisation, Automation, PyZX, Applied},
abstract = {We present a complete optimization procedure for hybrid quantum-classical circuits with classical parity logic. While common optimization techniques for quantum algorithms focus on rewriting solely the pure quantum segments, there is interest in applying a global optimization process for applications such as quantum error correction and quantum assertions. This work, based on the pure-quantum circuit optimization procedure by Duncan et al., uses an extension of the formal graphical ZX-calculus called ZX-ground as an intermediary representation of the hybrid circuits to allow for granular optimizations below the quantum-gate level. We define a translation from hybrid circuits into diagrams that admit the graph-theoretical focused-gFlow property, needed for the final extraction back into a circuit. We then derive a number of gFlow-preserving optimization rules for ZX-ground diagrams that reduce the size of the graph, and devise an strategy to find optimization opportunities by rewriting the diagram guided by a Gauss elimination process. Then, after extracting the circuit, we present a general procedure for detecting segments of circuit-like ZX-ground diagrams which can be implemented with classical gates in the extracted circuit. We have implemented our optimization procedure as an extension to the open-source python library PyZX.},
video = {https://www.youtube.com/watch?v=-Frd8w-hTD0}
}
@article{kissinger2021simulating,
author = {Kissinger, Aleks and van de Wetering, John},
title = {{Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions}},
year = {2022},
journal = {Quantum Science and Technology},
volume = {7},
number = {4},
pages = {044001},
publisher = {IOP Publishing},
doi = {10.1088/2058-9565/ac5d20},
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.},
video = {https://www.youtube.com/watch?v=0C9i0sUkQgk}
}
@inproceedings{vilmart2021quantum,
author = {Vilmart, Renaud},
title = {{Quantum Multiple-Valued Decision Diagrams in Graphical Calculi}},
year = {2021},
booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
editor = {Bonchi, Filippo and Puglisi, Simon J.},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {202},
pages = {89:1--89:15},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
isbn = {978-3-95977-201-3},
issn = {1868-8969},
doi = {10.4230/LIPIcs.MFCS.2021.89},
urldate = {2021-07-02},
link = {http://arxiv.org/abs/2107.01186},
keywords = {ZH-calculus, Classical Simulation, Verification},
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.},
urn = {urn:nbn:de:0030-drops-145295},
video = {https://www.youtube.com/watch?v=HTPU-XqW2gM}
}
@article{cowtan2021quantum,
author = {Cowtan, Alexander and Majid, Shahn},
title = {{Quantum double aspects of surface code models}},
year = {2022},
journal = {Journal of Mathematical Physics},
volume = {63},
doi = {10.1063/5.0063768},
urldate = {2021-06-25},
link = {http://arxiv.org/abs/2107.04411},
keywords = {Braids, Surface Code},
abstract = {We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry, where $G$ is a finite group. We provide projection operators for its quasiparticles content as irreducible representations of $D(G)$ and combine this with $D(G)$-bimodule properties of open ribbon excitation spaces $L(s_0,s_1)$ to show how open ribbons can be used to teleport information between their endpoints $s_0,s_1$. We give a self-contained account that builds on earlier work but emphasises applications to quantum computing as surface code theory, including gates on $D(S_3)$. We show how the theory reduces to a simpler theory for toric codes in the case of $D( \Bbb Z_n)\cong \Bbb C\Bbb Z_n^2$, including toric ribbon operators and their braiding. In the other direction, we show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$, including site actions of $D(H)$ and partial results on ribbon equivariance even when the Hopf algebra is not semisimple.}
}
@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.}
}
@inproceedings{comfort2021graphical,
author = {Comfort, Cole and Kissinger, Aleks},
title = {{A Graphical Calculus for Lagrangian Relations}},
year = {2022},
booktitle = {{\rm Proceedings of the Fourth International Conference on}
Applied Category Theory,
{\rm Cambridge, United Kingdom, 12-16th July 2021}},
editor = {Kishida, Kohei},
series = {Electronic Proceedings in Theoretical Computer Science},
volume = {372},
pages = {338-351},
publisher = {Open Publishing Association},
doi = {10.4204/EPTCS.372.24},
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.},
video = {https://www.youtube.com/watch?v=Xbxv3FiCIAA}
}
@mastersthesis{krueger2021Masters,
author = {Krueger, Ryan},
title = {{Vanishing 2-Qubit Gates with Non-Simplification ZX-Rules}},
year = {2021},
school = {University of Oxford},
urldate = {2021-04-23},
link = {http://arxiv.org/abs/2209.06874},
keywords = {ZX-calculus, Optimisation, PyZX, Automation, Applied, 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. On randomly generated circuits, our method can outperform state-of-the-art optimization techniques for low-qubit (<10) circuits. On a set of previously reported benchmark circuits with <=14 qubits, our method outperforms off-the-shelf methods in 87% of cases, consistently reducing overall circuit complexity by an additional ~15-30% and eliminating up to 46% of 2-qubit gates. These preliminary results serve as a proof-of-concept for a new circuit optimization strategy in the ZX-calculus.},
video = {https://www.youtube.com/watch?v=tUIcqXKEFhk}
}
@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 Arsiwalla, Xerxes D.},
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://youtu.be/v_y8Wu6GLxc?t=1558}
}
@article{majid2021quantum,
author = {Majid, Shahn},
title = {{Quantum and braided ZX calculus}},
year = {2022},
journal = {Journal of Physics A: Mathematical and Theoretical},
doi = {10.1088/1751-8121/ac631f},
urldate = {2021-03-11},
link = {http://arxiv.org/abs/2103.07264},
keywords = {Braids, Frobenius algebras},
abstract = {We revisit the notion of interacting Frobenius Hopf algebras for ZX-calculus in quantum computing, with focus on allowing the algebras to be noncommutative and coalgebras to be noncocommutative. We introduce the notion of *-structures in ZX-calculus at this algebraic level and construct examples based on the quantum group $u_q(sl_2)$ at a root of unity. We provide an abstract formulation of the Hadamard gate at this level and clarify its relationship to Hopf algebra self-duality. We then solve the problem of extending the notion of interacting Hopf algebras and ZX-calculus to take place in a braided tensor category. In the ribbon case, the Hadamard gate coming from braided self-duality obeys a modular identity. We give the example of $b_q(sl_2)$, the self-dual braided version of $u_q(sl_2)$.},
video = {https://www.youtube.com/watch?v=sXpT8Xhpwuw}
}
@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.}
}
@inproceedings{kostia2021geometry,
author = {Chardonnet, Kostia and Valiron, Beno\^{i}t and Vilmart, Renaud},
title = {{Geometry of Interaction for ZX-Diagrams}},
year = {2021},
booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
editor = {Bonchi, Filippo and Puglisi, Simon J.},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {202},
pages = {30:1--30:16},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
isbn = {978-3-95977-201-3},
issn = {1868-8969},
doi = {10.4230/LIPIcs.MFCS.2021.30},
urldate = {2021-03-01},
link = {https://hal.archives-ouvertes.fr/hal-03154573/},
keywords = {ZX-calculus, Verification},
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.},
urn = {urn:nbn:de:0030-drops-144701},
video = {https://www.youtube.com/watch?v=C_to8pIfpmc}
}
@article{coecke2021kindergarden,
author = {Coecke, Bob and Horsman, Dominic and Kissinger, Aleks and Wang, Quanlong},
title = {{Kindergarden quantum mechanics graduates (...or how I learned to stop gluing LEGO together and love the ZX-calculus)}},
year = {2022},
journal = {Theoretical Computer Science},
volume = {897},
month = {1},
pages = {1--22},
doi = {10.1016/j.tcs.2021.07.024},
urldate = {2021-02-22},
link = {http://arxiv.org/abs/2102.10984},
keywords = {ZX-calculus, NLP, MBQC},
abstract = {This paper is a `spiritual child' of the 2005 lecture notes Kindergarten Quantum Mechanics, which showed how a simple, pictorial extension of Dirac notation allowed several quantum features to be easily expressed and derived, using language even a kindergartner can understand. Central to that approach was the use of pictures and pictorial transformation rules to understand and derive features of quantum theory and computation. However, this approach left many wondering `where's the beef?' In other words, was this new approach capable of producing new results, or was it simply an aesthetically pleasing way to restate stuff we already know? The aim of this sequel paper is to say `here's the beef!', and highlight some of the major results of the approach advocated in Kindergarten Quantum Mechanics, and how they are being applied to tackle practical problems on real quantum computers. We will focus mainly on what has become the Swiss army knife of the pictorial formalism: the ZX-calculus. First we look at some of the ideas behind the ZX-calculus, comparing and contrasting it with the usual quantum circuit formalism. We then survey results from the past 2 years falling into three categories: (1) completeness of the rules of the ZX-calculus, (2) state-of-the-art quantum circuit optimisation results in commercial and open-source quantum compilers relying on ZX, and (3) the use of ZX in translating real-world stuff like natural language into quantum circuits that can be run on today's (very limited) quantum hardware. We also take the title literally, and outline an ongoing experiment aiming to show that ZX-calculus enables children to do cutting-edge quantum computing stuff. If anything, this would truly confirm that `kindergarten quantum mechanics' wasn't just a joke.}
}
@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.}
}
@inproceedings{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},
booktitle = {2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)},
volume = {},
number = {},
pages = {1--13},
doi = {10.1109/LICS52264.2021.9470553},
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{Zhao2021analyzingbarren,
author = {Zhao, Chen and Gao, Xiao-Shan},
title = {Analyzing the barren plateau phenomenon in training quantum neural networks with the {ZX}-calculus},
year = {2021},
journal = {{Quantum}},
volume = {5},
month = {6},
pages = {466},
publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
issn = {2521-327X},
doi = {10.22331/q-2021-06-04-466},
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 = {East, Richard D. P. and van de Wetering, John and Chancellor, Nicholas and Grushin, Adolfo G.},
title = {{AKLT-states as ZX-diagrams: diagrammatic reasoning for quantum states}},
year = {2022},
journal = {PRX Quantum},
volume = {3},
issue = {1},
month = {Jan},
pages = {010302},
numpages = {31},
publisher = {American Physical Society},
doi = {10.1103/PRXQuantum.3.010302},
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}
}
@mastersthesis{yeung2020diagrammatic,
author = {Yeung, Richie},
title = {{Diagrammatic Design and Study of Ans\"{a}tze for Quantum Machine Learning}},
year = {2020},
school = {University of Oxford},
urldate = {2020-11-22},
link = {http://arxiv.org/abs/2011.11073},
keywords = {ZX-calculus, Applied, Variational Circuits, Chemistry, Master Thesis},
abstract = {Given the rising popularity of quantum machine learning (QML), it is important to develop techniques that effectively simplify commonly adopted families of parameterised quantum circuits (commonly known as ans\"{a}tze). This thesis pioneers the use of diagrammatic techniques to reason with QML ans\"{a}tze. We take commonly used QML ans\"{a}tze and convert them to diagrammatic form and give a full description of how these gates commute, making the circuits much easier to analyse and simplify. Furthermore, we leverage a combinatorial description of the interaction between CNOTs and phase gadgets to analyse a periodicity phenomenon in layered ans\"{a}tze and also to simplify a class of circuits commonly used in QML.}
}
@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 = {Entropy},
volume = {23},
number = {3},
article-number = {308},
issn = {1099-4300},
doi = {10.3390/e23030308},
urldate = {2020-07-31},
link = {http://arxiv.org/abs/2007.16138},
url = {https://www.mdpi.com/1099-4300/23/3/308},
keywords = {Qudits, Algebraic ZX, Foundations},
abstract = {Scientific studies of consciousness rely on objects whose existence is assumed to be independent of any consciousness. On the contrary, we assume consciousness to be fundamental, and that one of the main features of consciousness is characterized as being other-dependent. We set up a framework which naturally subsumes this 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 co-dependent. The framework is general enough and fits well into a compositional model of consciousness. Interestingly, we also show how our proposal may become a step towards avoiding the hard problem of consciousness, and thereby address the combination problem of conscious experiences.}
}
@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, Chemistry, 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}
}
@inproceedings{deBeaudrapN2020treducspidernest,
author = {Niel de Beaudrap and Xiaoning Bian and Quanlong Wang},
title = {{Fast and Effective Techniques for T-Count Reduction via Spider Nest Identities}},
year = {2020},
booktitle = {15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
editor = {Steven T. Flammia},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {158},
pages = {11:1--11:23},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
isbn = {978-3-95977-146-7},
issn = {1868-8969},
doi = {10.4230/LIPIcs.TQC.2020.11},
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. },
urn = {urn:nbn:de:0030-drops-120705}
}
@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, Verification, 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, Verification},
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 = {Pinzani, Nicola and Gogioso, Stefano and Coecke, Bob},
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},
doi = {10.23638/LMCS-16(4:19)2020},
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{COECKE2011231,
author = {Bob Coecke and Quanlong Wang and Baoshan Wang and Yongjun Wang and Qiye Zhang},
title = {Graphical Calculus for Quantum Key Distribution (Extended Abstract)},
year = {2011},
journal = {Electronic Notes in Theoretical Computer Science},
volume = {270},
number = {2},
pages = {231--249},
issn = {1571-0661},
doi = {https://doi.org/10.1016/j.entcs.2011.01.034},
urldate = {2011-02-14},
link = {https://www.sciencedirect.com/science/article/pii/S1571066111000351},
keywords = {Protocols, ZX-calculus, Category Theory, Strong Complementarity},
abstract = {Controlled complementary measurements are key to quantum key distribution protocols, among many other things. We axiomatize controlled complementary measurements within symmetric monoidal categories, which provides them with a corresponding graphical calculus. We study the BB84 and Ekert91 protocols within this calculus, including the case where there is an intercept-resend attack.},
note = {Proceedings of the 6th International Workshop on Quantum Physics and Logic (QPL 2009)}
}
@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?''.}
}