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 wrote a book! Picturing Quantum Software, co-written with Aleks Kissinger, is now available for free as a pre-print, and teaches you everything you need to know about quantum compilation and the ZX-calculus.
I am currently looking for a PhD student! You can apply here. If you are still doing your Bachelors, consider applying to our Master programme in Quantum Computer Science at the UvA! If you are (or know) an interested Bachelor student looking for a world-class education in quantum computing, check it out.
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.
Parametrised quantum circuits contain phase gates whose phase is determined by a classical algorithm prior to running the circuit on a quantum device. Such circuits are used in variational algorithms like QAOA and VQE. In order for these algorithms to be as efficient as possible it is important that we use the fewest number of parameters. We show that, while the general problem of minimising the number of parameters is NP-hard, when we restrict to circuits that are Clifford apart from parametrised phase gates and where each parameter is used just once, we can efficiently find the optimal parameter count. We show that when parameter transformations are required to be sufficiently well-behaved that the only rewrites that reduce parameters correspond to simple 'fusions'. Using this we find that a previous circuit optimisation strategy by some of the authors [Kissinger, van de Wetering. PRA (2019)] finds the optimal number of parameters. Our proof uses the ZX-calculus. We also prove that the standard rewrite rules of the ZX-calculus suffice to prove any equality between parametrised Clifford circuits.
We present a complete set of rewrite rules for n-qutrit Clifford circuits where n is any non-negative integer. This is the first completeness result for any fragment of quantum circuits in odd prime dimensions. We first generalize Selinger's normal form for n-qubit Clifford circuits to the qutrit setting. Then, we present a rewrite system by which any Clifford circuit can be reduced to this normal form. We then simplify the rewrite rules in this procedure to a small natural set of rules, giving a clean presentation of the group of qutrit Clifford unitaries in terms of generators and relations.
A key challenge in realizing fault-tolerant quantum computers is circuit optimization. Focusing on the most expensive gates in fault-tolerant quantum computation (namely, the T gates), we address the problem of T-count optimization, i.e., minimizing the number of T gates that are needed to implement a given circuit. To achieve this, we develop AlphaTensor-Quantum, a method based on deep reinforcement learning that exploits the relationship between optimizing T-count and tensor decomposition. Unlike existing methods for T-count optimization, AlphaTensor-Quantum can incorporate domain-specific knowledge about quantum computation and leverage gadgets, which significantly reduces the T-count of the optimized circuits. AlphaTensor-Quantum outperforms the existing methods for T-count optimization on a set of arithmetic benchmarks (even when compared without making use of gadgets). Remarkably, it discovers an efficient algorithm akin to Karatsuba's method for multiplication in finite fields. AlphaTensor-Quantum also finds the best human-designed solutions for relevant arithmetic computations used in Shor's algorithm and for quantum chemistry simulation, thus demonstrating it can save hundreds of hours of research by optimizing relevant quantum circuits in a fully automated way.
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.
In order for quantum computations to be done as efficiently as possible it is important to optimise the number of gates used in the underlying quantum circuits. In this paper we find that many gate optimisation problems for approximately universal quantum circuits are NP-hard. In particular, we show that optimising the T-count or T-depth in Clifford+T circuits, which are important metrics for the computational cost of executing fault-tolerant quantum computations, is NP-hard by reducing the problem to Boolean satisfiability. With a similar argument we show that optimising the number of CNOT gates or Hadamard gates in a Clifford+T circuit is also NP-hard. Again varying the same argument we also establish the hardness of optimising the number of Toffoli gates in a reversible classical circuit. We find an upper bound to the problems of T-count and Toffoli-count of \(\text{NP}^{\text{NQP}}\). Finally, we also show that for any non-Clifford gate \(G\) it is NP-hard to optimise the \(G\)-count over the Clifford+\(G\) gate set, where we only have to match the target unitary within some small distance in the operator norm.
It is known that the matrices that can be exactly represented by a multiqubit circuit over the Toffoli+Hadamard, Clifford+\(T\), or, more generally, Clifford-cyclotomic gate set are precisely the unitary matrices with entries in the ring \(\mathbb{Z}[1/2, \zeta_k]\), where \(k\) is a positive integer that depends on the gate set and \(\zeta_k\) is a primitive \(2^k\)-th root of unity. In the present paper, we establish an analogous correspondence for qutrits. We define the multiqutrit Clifford-cyclotomic gate set of degree \(3^k\) by extending the classical qutrit gates \(X\), \(CX\), and \(CCX\) with the Hadamard gate \(H\) and the \(T_k\) gate \(T_k=\mathrm{diag}(1,\omega_k, \omega_k^2)\), where \(\omega_k\) is a primitive \(3^k\)-th root of unity. This gate set is equivalent to the qutrit Toffoli+Hadamard gate set when \(k=1\), and to the qutrit Clifford+\(T_k\) gate set when \(k>1\). We then prove that a \(3^n\times 3^n\) unitary matrix \(U\) can be represented by an \(n\)-qutrit circuit over the Clifford-cyclotomic gate set of degree \(3^k\) if and only if the entries of \(U\) lie in the ring \(\mathbb{Z}[1/3,\omega_k]\).
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.
This is the second in a series of "graphical grokking" papers in which we study how stabiliser codes can be understood using the ZX calculus. In this paper we show that certain complex rules involving ZX diagrams, called spider nest identities, can be captured succinctly using the scalable ZX calculus, and all such identities can be proved inductively from a single new rule using the Clifford ZX calculus. This can be combined with the ZX picture of CSS codes, developed in the first "grokking" paper, to give a simple characterisation of the set of all transversal diagonal gates at the third level of the Clifford hierarchy implementable in an arbitrary CSS code.
A catalysis state is a quantum state that is used to make some desired operation possible or more efficient, while not being consumed in the process. Recent years have seen catalysis used in state-of-the-art protocols for implementing magic state distillation or small angle phase rotations. In this paper we will see that we can also use catalysis to prove that certain gate sets are computationally universal, and to extend completeness results of graphical languages to larger fragments. In particular, we give a simple proof of the computational universality of the CS+Hadamard gate set using the catalysis of a \(T\) gate using a CS gate, which sidesteps the more complicated analytic arguments of the original proof by Kitaev. This then also gives us a simple self-contained proof of the computational universality of Toffoli+Hadamard. Additionally, we show that the phase-free ZH-calculus can be extended to a larger complete fragment, just by using a single catalysis rule (and one scalar rule).
We present a smorgasbord of results on the stabiliser ZX-calculus for odd prime-dimensional qudits (i.e. qupits). We derive a simplified rule set that closely resembles the original rules of qubit ZX-calculus. Using these rules, we demonstrate analogues of the spider-removing local complementation and pivoting rules. This allows for efficient reduction of diagrams to the affine with phases normal form. We also demonstrate a reduction to a unique form, providing an alternative and simpler proof of completeness. Furthermore, we introduce a different reduction to the graph state with local Cliffords normal form, which leads to a novel layered decomposition for qupit Clifford unitaries. Additionally, we propose a new approach to handle scalars formally, closely reflecting their practical usage. Finally, we have implemented many of these findings in DiZX, a new open-source Python library for qudit ZX-diagrammatic reasoning.
We introduce the qudit ZH-calculus and show how to generalise the phase-free qubit rules to qudits. We prove that for prime dimensions \(d\), the phase-free qudit ZH-calculus is universal for matrices over the ring \(\mathbb{Z}[e^{2\pi i/d}]\). For qubits, there is a strong connection between phase-free ZH-diagrams and Toffoli+Hadamard circuits, a computationally universal fragment of quantum circuits. We generalise this connection to qudits, by finding that the two-qudit \(|0\rangle\)-controlled \(X\) gate can be used to construct all classical reversible qudit logic circuits in any odd qudit dimension, which for qubits requires the three-qubit Toffoli gate. We prove that our construction is asymptotically optimal up to a logarithmic term. Twenty years after the celebrated result by Shi proving universality of Toffoli+Hadamard for qubits, we prove that circuits of \(|0\rangle\)-controlled \(X\) and Hadamard gates are approximately universal for qudit quantum computing for any odd prime \(d\), and moreover that phase-free ZH-diagrams correspond precisely to such circuits allowing postselections.
Counting the solutions to Boolean formulae defines the problem #SAT, which is complete for the complexity class #P. We use the ZH-calculus, a universal and complete graphical language for linear maps which naturally encodes counting problems in terms of diagrams, to give graphical reductions from #SAT to several related counting problems. Some of these graphical reductions, like to #2SAT, are substantially simpler than known reductions via the matrix permanent. Additionally, our approach allows us to consider the case of counting solutions modulo an integer on equal footing. Finally, since the ZH-calculus was originally introduced to reason about quantum computing, we show that the problem of evaluating ZH-diagrams in the fragment corresponding to the Clifford+T gateset, is in \(FP^{\#P}\). Our results show that graphical calculi represent an intuitive and useful framework for reasoning about counting problems.
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.
Among the many important geometric properties of quantum state space are: transitivity of the group of symmetries of the cone of unnormalized states on its interior (homogeneity), identification of this cone with its dual cone of effects via an inner product (self-duality), and transitivity of the group of symmetries of the normalized state space on the pure normalized states (pure transitivity). Koecher and Vinberg showed that homogeneity and self-duality characterize Jordan-algebraic state spaces: real, complex and quaternionic quantum theory, spin factors, 3-dimensional octonionic quantum state space and direct sums of these irreducible spaces. We show that self-duality follows from homogeneity and pure transitivity. These properties have a more direct physical and information-processing significance than self-duality. We show for instance (extending results of Barnum, Gaebeler, and Wilce) that homogeneity is closely related to the ability to steer quantum states. Our alternative to the Koecher-Vinberg theorem characterizes nearly the same set of state spaces: direct sums of isomorphic Jordan-algebraic ones, which may be viewed as composites of a classical system with an irreducible Jordan-algebraic one. There are various physically and informationally natural additional postulates that are known to single out complex quantum theory from among these Jordan-algebraic possibilities. We give various such reconstructions based on the additional property of local tomography.
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.
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.
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.
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 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.