Theoretical Computer Science

Informatics Institute

University of Amsterdam

LAB42, Science Park 900

1098XH Amsterdam, The Netherlands

Email:

You can find me on Google Scholar, arXiv, github and ORCID. Here's my CV.

I am an assistant professor at the Theoretical Computer Science group of the Informatics Institute of the University of Amsterdam, working together with the QuSoft research center. I currently do not have any available PhD positions.

My research focuses on two areas. The first is the usage of diagrammatic techniques in quantum computation. In particular, figuring out how the ZX-calculus can be used to improve our reasoning about quantum processes in order to do better quantum circuit optimisation, classical simulation and verification. I am cocreator of the open source optimising quantum compiler PyZX, a Python tool for using the ZX-calculus on quantum circuits. Check out my review article on the ZX-calculus if you want to learn more.

My second area of research is in quantum foundations where I try to better understand the nature of quantum mechanics through algebraic and compositional methods. The guiding question here is *why* nature is described by the laws of quantum mechanics. I try to answer this question by showing that certain natural assumptions or restrictions on physical theories automatically lead one down the path of quantum theory.

- A computer scientist's reconstruction of quantum theory

Bas Westerbaan and John van de Wetering,*Journal of Physics A: Mathematical and Theoretical*(2021)**55**

Show abstract ⇲The rather unintuitive nature of quantum theory has led numerous people to develop sets of (physically motivated) principles that can be used to derive quantum mechanics from the ground up, in order to better understand where the structure of quantum systems comes from. From a computer scientist's perspective we would like to study quantum theory in a way that allows interesting transformations and compositions of systems and that also includes infinite-dimensional datatypes. Here we present such a compositional reconstruction of quantum theory that includes infinite-dimensional systems. This reconstruction is noteworthy for three reasons: it is only one of a few that includes no restrictions on the dimension of a system; it allows for both classical, quantum, and mixed systems; and it makes no a priori reference to the structure of the real (or complex) numbers. This last point is possible because we frame our results in the language of category theory, specifically the categorical framework of effectus theory.

- Classical Simulation of Quantum Circuits with Partial and Graphical Stabiliser Decompositions

Aleks Kissinger, John van de Wetering and Renaud Vilmart,*17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022) pp. 5:1–5:13*(2022)

Show abstract ⇲ video 🎥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.

- Qutrit Metaplectic Gates Are a Subset of Clifford+T

Andrew N. Glaudell, Neil J. Ross, John van de Wetering and Lia Yeh,*17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022) pp. 12:1–12:15*(2022)

Show 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 \mathbb{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.

- Circuit Extraction for ZX-Diagrams Can Be #P-Hard

Niel de Beaudrap, Aleks Kissinger and John van de Wetering,*49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) pp. 119:1–119:19*(2022)

Show abstract ⇲ video 🎥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.

- Phase gadget compilation for diagonal qutrit gates

John van de Wetering and Lia Yeh,*Accepted in QPL2022*(2022)

Show 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.

- Constructing all qutrit controlled Clifford+T gates in Clifford+T

Lia Yeh and John van de Wetering,*Reversible Computation pp. 28–50*(2022)

Show 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.

- Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions

Aleks Kissinger and John van de Wetering,*Quantum Science and Technology*(2022)**7**

Show abstract ⇲ video 🎥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.

- AKLT-states as ZX-diagrams: diagrammatic reasoning for quantum states

Richard D. P. East, John van de Wetering, Nicholas Chancellor and Adolfo G. Grushin,*PRX Quantum*(2022)**3**(1)

Show abstract ⇲ video 🎥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.

- Spin-networks in the ZX-calculus

Richard D. P. East, Pierre Martin-Dussaud and John van de Wetering,*arXiv preprint arXiv:2111.03114*(2021)

Show abstract ⇲ video 🎥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.

- A Categorical Construction of the Real Unit Interval

John van de Wetering,*Accepted in ACT2021*(2021)

Show abstract ⇲ video 🎥The real unit interval is the fundamental building block for many branches of mathematics like probability theory, measure theory, convex sets and homotopy theory. However, a priori the unit interval could be considered an arbitrary choice and one can wonder if there is some more canonical way in which the unit interval can be constructed. In this paper we find such a construction by using the theory of effect algebras. We show that the real unit interval is the unique non-initial, non-final irreducible algebra of a particular monad on the category of bounded posets. The algebras of this monad carry an order, multiplication, addition and complement, and as such model much of the operations we need to do on probabilities. On a technical level, we show that both the categories of omega-complete effect algebras as well as that of omega-complete effect monoids are monadic over the category of bounded posets using Beck's monadicity theorem. The characterisation of the real unit interval then follows easily using a recent representation theorem for omega-complete effect monoids.

- There and back again: A circuit extraction tale

Miriam Backens, Hector Miller-Bakewell, Giovanni de Felice, Leo Lobski and John van de Wetering,*Quantum*(2020)**5**(421)

Show abstract ⇲ video 🎥Translations between the quantum circuit model and the measurement-based one-way model are useful for verification and optimisation of quantum computations. They make crucial use of a property known as gflow. While gflow is defined for one-way computations allowing measurements in three different planes of the Bloch sphere, most research so far has focused on computations containing only measurements in the XY-plane. Here, 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.

- Constructing quantum circuits with global gates

John van de Wetering,*New Journal of Physics*(2021)

Show abstract ⇲ video 🎥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.

- Completeness of the ZH-calculus

Miriam Backens, Aleks Kissinger, Hector Miller-Bakewell, John van de Wetering and Sal Wolffs,*arXiv preprint arXiv:2103.06610*(2021)

Show abstract ⇲ video 🎥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.

- ZX-calculus for the working quantum computer scientist

John van de Wetering,*arXiv preprint arXiv:2012.13966*(2020)

Show abstract ⇲ video 🎥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.

- The three types of normal sequential effect algebras

Abraham Westerbaan, Bas Westerbaan and John van de Wetering,*Quantum*(2020)**4**(378)

Show abstract ⇲A sequential effect algebra (SEA) is an effect algebra equipped with a sequential product operation modeled after the L\"uders product \((a,b)\mapsto \sqrt{a}b\sqrt{a}\) on C*-algebras. A SEA is called normal when it has all suprema of directed sets, and the sequential product interacts suitably with these suprema. The effects on a Hilbert space and the unit interval of a von Neumann or JBW algebra are examples of normal SEAs that are in addition convex, i.e. possess a suitable action of the real unit interval on the algebra. Complete Boolean algebras form normal SEAs too, which are convex only when \(0=1\). We show that any normal SEA \(E\) splits as a direct sum \(Eâ‰¡E_b\oplus E_c\oplus E_{ac}\) of a complete Boolean algebra \(E_b\), a convex normal SEA \(E_c\), and a newly identified type of normal SEA \(E_{ac}\) we dub purely almost-convex. Along the way we show, among other things, that a SEA which contains only idempotents must be a Boolean algebra; and we establish a spectral theorem using which we settle for the class of normal SEAs a problem of Gudder regarding the uniqueness of square roots. After establishing our main result, we propose a simple extra axiom for normal SEAs that excludes the seemingly pathological a-convex SEAs. We conclude the paper by a study of SEAs with an associative sequential product. We find that associativity forces normal SEAs satisfying our new axiom to be commutative, shedding light on the question of why the sequential product in quantum theory should be non-associative.

- Reducing the number of non-Clifford gates in quantum circuits

Aleks Kissinger and John van de Wetering,*Physical Review A*(2020)**102**(2)

Show abstract ⇲ video 🎥We present a method for reducing the number of non-Clifford quantum gates, in particularly T-gates, in a circuit, an important task for efficiently implementing fault-tolerant quantum computations. This method matches or beats previous approaches to ancillae-free T-count reduction on the majority of our benchmark circuits, in some cases yielding up to 50\% improvement. Our method begins by representing the quantum circuit as a ZX-diagram, a tensor networklike structure that can be transformed and simplified according to the rules of the ZX-calculus. We then extend a recent simplification strategy with a different ingredient, phase gadgetization, which we use to propagate non-Clifford phases through a ZX-diagram to find nonlocal cancellations. Our procedure extends unmodified to arbitrary phase angles and to parameter elimination for variational circuits. Finally, our optimization is self-checking, in the sense that the simplification strategy we propose is powerful enough to independently validate equality of the input circuit and the optimized output circuit. We have implemented the routines of this paper in the open-source library pyzx.

- A Characterisation of Ordered Abstract Probabilities

Abraham Westerbaan, Bas Westerbaan and John van de Wetering,*Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science pp. 944–957*(2020)

Show abstract ⇲ video 🎥In computer science, especially when dealing with quantum computing or other non-standard models of computation, basic notions in probability theory like "a predicate" vary wildly. There seems to be one constant: the only useful example of an algebra of probabilities is the real unit interval. In this paper we try to explain this phenomenon. We will show that the structure of the real unit interval naturally arises from a few reasonable assumptions. We do this by studying effect monoids, an abstraction of the algebraic structure of the real unit interval: it has an addition \(x+y\) which is only defined when \(x+y\leq 1\) and an involution \(x\mapsto 1-x\) which make it an effect algebra, in combination with an associative (possibly non-commutative) multiplication. Examples include the unit intervals of ordered rings and Boolean algebras. We present a structure theory for effect monoids that are \(\omega\)-complete, i.e. where every increasing sequence has a supremum. We show that any \(\omega\)-complete effect monoid embeds into the direct sum of a Boolean algebra and the unit interval of a commutative unital C*-algebra. This gives us from first principles a dichotomy between sharp logic, represented by the Boolean algebra part of the effect monoid, and probabilistic logic, represented by the commutative C*-algebra. Some consequences of this characterisation are that the multiplication must always be commutative, and that the unique \(\omega\)-complete effect monoid without zero divisors and more than 2 elements must be the real unit interval. Our results give an algebraic characterisation and motivation for why any physical or logical theory would represent probabilities by real numbers.

- Hypergraph Simplification: Linking the Path-sum Approach to the ZH-calculus

Louis Lemonnier, John van de Wetering and Aleks Kissinger,*Proceedings 17th International Conference on Quantum Physics and Logic, Paris, France, June 2 - 6, 2020 pp. 188-212*(2021)

Show abstract ⇲ video 🎥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.

- Dichotomy between Deterministic and Probabilistic Models in Countably Additive Effectus Theory

Kenta Cho, Bas Westerbaan and John van de Wetering,*Proceedings 17th International Conference on Quantum Physics and Logic, Paris, France, June 2 - 6, 2020 pp. 91-113*(2021)

Show abstract ⇲ video 🎥Effectus theory is a relatively new approach to categorical logic that can be seen as an abstract form of generalized probabilistic theories (GPTs). While the scalars of a GPT are always the real unit interval [0,1], in an effectus they can form any effect monoid. Hence, there are quite exotic effectuses resulting from more pathological effect monoids. In this paper we introduce \(\sigma\)-effectuses, where certain countable sums of morphisms are defined. We study in particular \(\sigma\)-effectuses where unnormalized states can be normalized. We show that a non-trivial \(\sigma\)-effectus with normalization has as scalars either the two-element effect monoid {0,1} or the real unit interval [0,1]. When states and/or predicates separate the morphisms we find that in the {0,1} case the category must embed into the category of sets and partial functions (and hence the category of Boolean algebras), showing that it implements a deterministic model, while in the [0,1] case we find it embeds into the category of Banach order-unit spaces and of Banach pre-base-norm spaces (satisfying additional properties), recovering the structure present in GPTs. Hence, from abstract categorical and operational considerations we find a dichotomy between deterministic and convex probabilistic models of physical theories.

- Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus

Ross Duncan, Aleks Kissinger, Simon Perdrix and John van de Wetering,*Quantum*(2020)**4**(279)

Show abstract ⇲ video 🎥We present the theoretical foundations for a new quantum circuit optimisation technique based on an equational theory called 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 derive a terminating simplification procedure for ZX-diagrams based on the two graph transformations of local complementation and pivoting. While little is known about extracting an equivalent quantum circuit from an arbitrary ZX-diagram, we show that our simplification procedure preserves a graph property called focused gFlow, and use this property to derive a deterministic strategy for circuit re-extraction. Hence, this approach enables us to temporarily break the rigid quantum circuit structure and 'see around' obstructions (namely non-Clifford quantum gates) to produce significant reductions, while still maintaining enough data to extract a reduced quantum circuit at the end.

- Commutativity in Jordan Operator Algebras

John van de Wetering,*Journal of Pure and Applied Algebra*(2020)**224**(11)

Show abstract ⇲While Jordan algebras are commutative, their non-associativity makes it so that the Jordan product operators do not necessarily commute. When the product operators of two elements commute, the elements are said to operator commute. In some Jordan algebras operator commutation can be badly behaved, for instance having elements \(a\) and \(b\) operator commute, while \(a^2\) and \(b\) do not operator commute. In this paper we study JB-algebras, real Jordan algebras which are also Banach spaces in a compatible manner, of which C*-algebras are examples. We show that elements \(a\) and \(b\) in a JB-algebra operator commute if and only if they span an associative sub-algebra of mutually operator commuting elements, and hence operator commutativity in JB-algebras is as well-behaved as it can be. Letting \(Q_a\) denote the quadratic operator of \(a\), we also show that positive \(a\) and \(b\) operator commute if and only if \(Q_ab^2=Q_ba^2\). We use this result to conclude that the unit interval of a JB-algebra is a sequential effect algebra as defined by Gudder and Greechie.

- PyZX: Large Scale Automated Diagrammatic Reasoning

Aleks Kissinger and John van de Wetering,*Proceedings 16th International Conference on Quantum Physics and Logic, Chapman University, Orange, CA, USA., 10-14 June 2019 pp. 229-241*(2020)

Show abstract ⇲ video 🎥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.

- An effect-theoretic reconstruction of quantum theory

John van de Wetering,*Compositionality*(2019)**1**(1)

Show abstract ⇲ video 🎥An often used model for quantum theory is to associate to every physical system a C*-algebra. From a physical point of view it is unclear why operator algebras would form a good description of nature. In this paper, we retrieve the category of finite-dimensional C*-algebras using concepts from effectus theory, a categorical logical framework generalizing classical and quantum logic. As these concepts have a physical interpretation, this motivates the usage of operator algebras as a model for quantum theory. In contrast to other reconstructions of quantum theory, we do not start with the framework of generalised probabilistic theories and instead use effect theories where no convex structure and no tensor product needs to be present. The lack of this structure in effectus theory has led to a different notion of pure maps. A map in an effectus is pure when it is a composition of a compression and a filter. These maps satisfy particular universal properties and respectively correspond to 'forgetting' and measuring the validity of an effect. We define a pure effect theory (PET) to be an effect theory where the pure maps form a dagger-category and filters and compressions are adjoint. We characterise the category of Euclidean Jordan algebras as the most general convex, finite-dimensional PET. If we in addition assume monoidal structure, then any such PET must embed into either the category of real or complex C*-algebras, which completes our reconstruction. As a PET must be quantum theory in the probabilistic convex setting, a PET without those properties can be viewed as a new type of generalisation of quantum theory.

- Sequential Product Spaces are Jordan Algebras

John van de Wetering,*Journal of Mathematical Physics*(2019)**60**(6)

Show abstract ⇲We show that finite-dimensional order unit spaces equipped with a continuous sequential product as defined by Gudder and Greechie are homogeneous and self-dual. As a consequence of the Koecher-Vinberg theorem, these spaces therefore correspond to Euclidean Jordan algebras. We remark on the significance of this result in the context of reconstructions of quantum theory. In particular, we show that sequential product spaces must be C*-algebras when their vector space tensor product is also a sequential product space (in the parlance of operational theories, when the space "allows a local composite"). We also show that sequential product spaces in infinite dimension correspond to JB-algebras when a few additional conditions are satisfied. Finally, we remark on how changing the axioms of the sequential product might lead to a new characterization of homogeneous cones.

- Universal MBQC with generalised parity-phase interactions and Pauli measurements

Aleks Kissinger and John van de Wetering,*Quantum*(2019)**3**(134)

Show 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.

- Graphical Fourier Theory and the Cost of Quantum Addition

Stach Kuijpers, John van de Wetering and Aleks Kissinger,*arXiv preprint arXiv:1904.07551*(2019)

Show 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.

- Completeness of the Phase-free ZH-calculus

John van de Wetering and Sal Wolffs,*arXiv preprint arXiv:1904.07545*(2019)

Show 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.

- Pure Maps between Euclidean Jordan Algebras

Abraham Westerbaan, Bas Westerbaan and John van de Wetering,*Proceedings of the 15th International Conference on Quantum Physics and Logic, Halifax, Canada, 3-7th June 2018 pp. 345-364*(2019)

Show abstract ⇲We propose a definition of purity for positive linear maps between Euclidean Jordan Algebras (EJA) that generalizes the notion of Kraus rank one channels (\(A\mapsto B^*AB\)). We show that this definition of purity is closed under composition and taking adjoints and thus that the pure maps form a dagger category. This dagger yields a notion of positivity: maps of the form \(f=g^\dagger\circ g\) are called \(\dagger\)-positive. We show that such a \(\dagger\)-positive map \(f\) is completely determined by \(f(1)\) and equal to \(Q_{\sqrt{f(1)}}\), the Jordan algebraic version of the sequential measurement map \(A\mapsto \sqrt{f(1)}A\sqrt{f(1)}\). The notion of \(\dagger\)-positivity therefore characterises the sequential product. These results hold for the general reason that the opposite category of EJAs with positive contractive linear maps is a \(\dagger\)-effectus. The notion of \(\dagger\)-effectus was introduced to prove similar results for the opposite category of normal completely positive contractive maps between von Neumann algebras.

- Ordering quantum states and channels based on positive Bayesian evidence

John van de Wetering,*Journal of Mathematical Physics*(2018)**59**(10)

Show abstract ⇲In this paper we introduce a new partial order on quantum states that considers which states can be achieved from others by updating on 'agreeing' Bayesian evidence. We prove that this order can also be interpreted in terms of minimising worst case distinguishability between states using the concept of quantum max-divergence. This order solves the problem of which states are optimal approximations to their more pure counterparts and it shows in an explicit way that a proposed quantum analogue of Bayes' rule leads to a Bayesian update that changes the state as little as possible when updating on positive evidence. We prove some structural properties of the order, specifically that the order preserves convex mixtures and tensor products of states and that it is a domain. The uniqueness of the order given these properties is discussed. Finally we extend this order on states to one on quantum channels using the Jamiolkowski isomorphism. This order turns the spaces of unital/non-unital trace-preserving quantum channels into domains that, unlike the regular order on channels, is not trivial for unital trace-preserving channels.

- Three characterisations of the sequential product

John van de Wetering,*Journal of Mathematical Physics*(2018)**59**(8)

Show abstract ⇲It has already been established that the properties required of an abstract sequential product as introduced by Gudder and Greechie are not enough to characterise the standard sequential product \(a\circ b = \sqrt{a}b\sqrt{b}\) on an operator algebra. We give three additional properties, each of which characterises the standard sequential product on either a von Neumann algebra or a Euclidean Jordan algebra. These properties are (1) invariance under application of unital order isomorphisms, (2) symmetry of the sequential product with respect to a certain inner product, and (3) preservation of invertibility of the effects. To give these characterisations we first have to study convex sigma-sequential effect algebras. We show that these objects correspond to unit intervals of spectral order unit spaces with a homogeneous positive cone.

- Quantum Theory is a Quasi-stochastic Process Theory

John van de Wetering,*Proceedings 14th International Conference on Quantum Physics and Logic, Nijmegen, The Netherlands, 3-7 July 2017 pp. 179-196*(2018)

Show abstract ⇲ video 🎥There is a long history of representing a quantum state using a quasi-probability distribution: a distribution allowing negative values. In this paper we extend such representations to deal with quantum channels. The result is a convex, strongly monoidal, functorial embedding of the category of trace preserving completely positive maps into the category of quasi-stochastic matrices. This establishes quantum theory as a subcategory of quasi-stochastic processes. Such an embedding is induced by a choice of minimal informationally complete POVM's. We show that any two such embeddings are naturally isomorphic. The embedding preserves the dagger structure of the categories if and only if the POVM's are symmetric, giving a new use of SIC-POVM's, objects that are of foundational interest in the QBism community. We also study general convex embeddings of quantum theory and prove a dichotomy that such an embedding is either trivial or faithful.

- Entailment Relations on Distributions

John van de Wetering,*Proceedings of the 2016 Workshop on Semantic Spaces at the Intersection of NLP, Physics and Cognitive Science, Glasgow, Scotland, 11th June 2016 pp. 58-66*(2016)

Show abstract ⇲ video 🎥In this paper we give an overview of partial orders on the space of probability distributions that carry a notion of information content and serve as a generalisation of the Bayesian order given in (Coecke and Martin, 2011). We investigate what constraints are necessary in order to get a unique notion of information content. These partial orders can be used to give an ordering on words in vector space models of natural language meaning relating to the contexts in which words are used, which is useful for a notion of entailment and word disambiguation. The construction used also points towards a way to create orderings on the space of density operators which allow a more fine-grained study of entailment. The partial orders in this paper are directed complete and form domains in the sense of domain theory.

- Classical simulation of quantum circuits with partial and graphical stabiliser decompositions (slides). Given at TQC2022.
- Supercharging classical simulation of quantum circuits with the ZX-calculus (slides). Given at QPL2022.
- Circuit Extraction for ZX-diagrams can be #P-hard (slides). Given at QPL2022.
- Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions (slides, video). Given at QCTIP 2020.
- Categorical approaches to reconstructing quantum theory (slides). Given at SYCO8.
- The algebraic structure of quantum effects (slides). Given at ENSPM2021.
- A Categorical Construction of the Real Unit Interval (slides, video). Given at ACT2021.
- Quantum compilation using the ZX-calculus (slides, video). Given at QRE2021 and PlanQC2021.
- The ZH-calculus: completeness and extensions (slides, video). Given at QPL2021.
- Constructing quantum circuits with global gates (slides, video). Given at QPL2021.
- There and back again: A circuit extraction tale (slides, video). Given at International Workshop on Quantum Compilation 2020.
- An effect-theoretic reconstruction of quantum theory (slides, video). Given at MIT Categories Seminar 2020.
- Quantum Theory from First Principles (lecture 1, lecture 2, lecture 3, lecture 4, video). Invited lecture series at L'Agape 2020.
- Dichotomy between deterministic and probabilistic models in countably additive effectus theory (slides, video). Given at QPL2020.
- Quantum Circuit Optimisation with the ZX-calculus (slides, video). Given at QCTIP 2020.
- Quantum circuit optimisation, verification, and simulation with PyZX (slides, video). Invited talk at FOSDEM 2020.
- Simulation of quantum circuits by ZX-diagram contraction (slides). Given at STRING2019.
- An effect-theoretic reconstruction of quantum theory (slides, video). Given at ACT2019.
- PyZX: Large Scale Automated Diagrammatic Reasoning (slides). Given at QPL2019.
- T-count optimization of quantum circuits using graph-theoretical rewriting of ZX-diagrams (slides). Given at EQTC2019.
- PyZX: Graph-theoretic optimization of quantum circuits (slides). Invited talk at FOSDEM 2019.
- PyZX: Quantum circuit optimization using the ZX-calculus (slides). Given at SYCO 2.
- Reconstruction of Quantum Theory from Universal Filters (slides). Given at Foundations 2018.
- Sequential Measurement characterises Quantum Theory (slides). Given at QPL 2018.
- Purity in Euclidean Jordan Algebras (slides). Given at QPL 2018.
- Quantum Theory is a Quasi-Stochastic Process Theory (slides, video). Given at QPL 2017.

- Together with Aleks Kissinger I co-lectured the Masters course Quantum Processes and Computation at the Radboud University, and the Master course Quantum Software in Oxford.
- Together with Hector Miller-Bakewell I developed the ZX-calculus website as a resource for understanding the ZX-calculus. In addition, together with Miriam Backens we wrote most of the current ZX-calculus Wikipedia page.
- I was part of the EU's Quantum Flagship Gender Equality Working group that raises awareness and promotes strategies for realising gender equality in the field of quantum technologies.