We revisit Kapranov and Voevodsky's idea of spaces modelled on combinatorial pasting diagrams, now as a framework for higher-dimensional rewriting and the basis of a model of weak ω-categories. In the first part, we elaborate on Steiner's theory of directed complexes as a combinatorial foundation. We individuate convenient classes of directed complexes and develop the theory of diagrammatic sets relative to one such class. We study a notion of equivalence internal to a diagrammatic set, and single out as models of weak ω-categories those diagrammatic sets whose every composable diagram is connected by an equivalence to a single cell. We then define a semistrict model providing algebraic composites and study the embedding of strict ω-categories into this model. Finally, we prove a version of the homotopy hypothesis for the ∞-groupoids in the weak model, and exhibit a specific mistake in a proof by Kapranov and Voevodsky that had previously been refuted indirectly.
A. Hadzihasanovic. A combinatorial-topological shape category for polygraphs. 2020.
In Applied Categorical Structures, volume 28, issue 3, pages 419—476.
We introduce constructible directed complexes, a combinatorial presentation of higher categories inspired by constructible complexes in poset topology. Constructible directed complexes with a greatest element, called atoms, encompass common classes of higher-categorical cell shapes, including globes, cubes, oriented simplices, and a large sub-class of opetopes, and are closed under lax Gray products and joins. We define constructible polygraphs to be presheaves on a category of atoms and inclusions, and extend the monoidal structures.
We show that constructible directed complexes are a well-behaved subclass of Steiner's directed complexes, which we use to define a realisation functor from constructible polygraphs to omega-categories. We prove that the realisation of a constructible polygraph is a polygraph in restricted cases, and in all cases conditionally to a conjecture. Finally, we define the geometric realisation of a constructible polygraph, and prove that it is a CW complex with one cell for each of its elements.
A. Hadzihasanovic. Weak units, universal cells, and coherence via universality for bicategories. 2019.
In Theory and Applications of Categories, volume 34, number 29, pages 883—960.
Poly-bicategories generalise planar polycategories in the same way as bicategories generalise monoidal categories. In a poly-bicategory, the existence of enough 2-cells satisfying certain universal properties (representability) induces coherent algebraic structure on the 2-graph of single-input, single-output 2-cells. A special case of this theory was used by Hermida to produce a proof of strictification for bicategories. No full strictification is possible for higher-dimensional categories, seemingly due to problems with 2-cells that have degenerate boundaries; it was conjectured by C. Simpson that semi-strictification excluding units may be possible.
We study poly-bicategories where 2-cells with degenerate boundaries are barred, and show that we can recover the structure of a bicategory through a different construction of weak units. We prove that the existence of these units is equivalent to the existence of 1-cells satisfying lower-dimensional universal properties, and study the relation between preservation of units and universal cells.
Then, we introduce merge-bicategories, a variant of poly-bicategories with more composition operations, which admits a natural monoidal closed structure, giving access to higher morphisms. We derive equivalences between morphisms, transformations, and modifications of representable merge-bicategories and the corresponding notions for bicategories. Finally, we prove a semi-strictification theorem for representable merge-bicategories with a choice of composites and units.
G. de Felice, A. Hadzihasanovic, K. F. Ng. A diagrammatic calculus of fermionic quantum circuits. 2019.
In Logical Methods in Computer Science, volume 15, issue 3, pages 26:1—26:34.
We introduce the fermionic ZW calculus, a string-diagrammatic language for fermionic quantum computing (FQC). After defining a fermionic circuit model, we present the basic components of the calculus, together with their interpretation, and show how the main physical gates of interest in FQC can be represented in our language. We then list our axioms, and derive some additional equations. We prove that the axioms provide a complete equational axiomatisation of the monoidal category whose objects are systems of finitely many local fermionic modes (LFMs), with maps that preserve or reverse the parity of states, and the tensor product as monoidal product. We achieve this through a procedure that rewrites any diagram in a normal form. As an example, we show how the statistics of a fermionic Mach-Zehnder interferometer can be calculated in the diagrammatic language. We conclude by giving a diagrammatic treatment of the dual-rail encoding, a standard method in optical quantum computing used to perform universal quantum computation.
Extended version of A diagrammatic axiomatisation of fermionic quantum circuits, FSCD 2018.
A. Hadzihasanovic, K. F. Ng, Q. Wang. Two complete axiomatisations of pure-state qubit quantum computing. 2018.
In 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 2018, pages 502—511, ACM.
Categorical quantum mechanics places finite-dimensional quantum theory in the context of compact closed categories, with an emphasis on diagrammatic reasoning. In this framework, two equational diagrammatic calculi have been proposed for pure-state qubit quantum computing: the ZW calculus, developed by Coecke, Kissinger and the first author for the purpose of qubit entanglement classification, and the ZX calculus, introduced by Coecke and Duncan to give an abstract description of complementary observables. Neither calculus, however, provided a complete axiomatisation of their model.
In this paper, we present extended versions of ZW and ZX, and show their completeness for pure-state qubit theory, thus solving two major open problems in categorical quantum mechanics. First, we extend the original ZW calculus to represent states and linear maps with coefficients in an arbitrary commutative ring, and prove completeness by a strategy that rewrites all diagrams into a normal form. We then extend the language and axioms of the original ZX calculus, and show their completeness for pure-state qubit theory through a translation between ZX and ZW specialised to the field of complex numbers. This translation expands the one used by Jeandel, Perdrix, and Vilmart to derive an axiomatisation of the approximately universal Clifford+T fragment; restricting the field of complex numbers to a suitable subring, we obtain an alternative axiomatisation of the same theory.
A. Hadzihasanovic, G. de Felice, K. F. Ng. A diagrammatic axiomatisation of fermionic quantum circuits. 2018.
In 3rd International Conference on Formal Structures for Computation and Deduction (FSCD) 2018, volume 108 of LIPIcs, pages 17:1—17:20.
We introduce the fermionic ZW calculus, a string-diagrammatic language for fermionic quantum computing (FQC). After defining a fermionic circuit model, we present the basic components of the calculus, together with their interpretation, and show how the main physical gates of interest in FQC can be represented in the language. We then list our axioms, and derive some additional equations. We prove that the axioms provide a complete equational axiomatisation of the monoidal category whose objects are quantum systems of finitely many local fermionic modes, with operations that preserve or reverse the parity (number of particles mod 2) of states, and the tensor product, corresponding to the composition of two systems, as monoidal product. We achieve this through a procedure that rewrites any diagram in a normal form. We conclude by showing, as an example, how the statistics of a fermionic Mach-Zehnder interferometer can be calculated in the diagrammatic language.
A. Hadzihasanovic. A topological perspective on interacting algebraic theories. 2017.
In Proceedings 13th International Conference on Quantum Physics and Logic (QPL) 2016, volume 236 of EPTCS, pages 70—86.
Techniques from higher categories and higher-dimensional rewriting are becoming increasingly important for understanding the finer, computational properties of higher algebraic theories that arise, among other fields, in quantum computation. These theories have often the property of containing simpler sub-theories, whose interaction is regulated in a limited number of ways, which reveals a topological substrate when pictured by string diagrams. By exploring the double nature of computads as presentations of higher algebraic theories, and combinatorial descriptions of "directed spaces", we develop a basic language of directed topology for the compositional study of algebraic theories. We present constructions of computads, all with clear analogues in standard topology, that capture in great generality such notions as homomorphisms and actions, and the interactions of monoids and comonoids that lead to the theory of Frobenius algebras and of bialgebras. After a number of examples, we describe how a fragment of the ZX calculus can be reconstructed in this framework.
A. Hadzihasanovic, B. van den Berg. Nonstandard functional interpretations and categorical models. 2017.
In Notre Dame Journal of Formal Logic, volume 58, number 3, pages 343—380.
Recently, the second author, Briseid and Safarik introduced nonstandard Dialectica, a functional interpretation that is capable of eliminating instances of familiar principles of nonstandard arithmetic — including overspill, underspill, and generalisations to higher types — from proofs. We show that, under few metatheoretical assumptions, the properties of this interpretation are mirrored by first order logic in a constructive sheaf model of nonstandard arithmetic due to Moerdijk, later developed by Palmgren. In doing so, we also draw some new connections between nonstandard principles, and principles that are rejected by strict constructivism.
Furthermore, we introduce a variant of the Diller-Nahm interpretion with two different kinds of quantifiers (with and without computational meaning), similar to Hernest's light Dialectica interpretation, and show that one can obtain nonstandard Dialectica from this by weakening the computational content of the existential quantifiers — a process we call herbrandisation. We also define a constructive sheaf model mirroring this new functional interpretation and show that the process of herbrandisation has a clear meaning in terms of these sheaf models.
A. Hadzihasanovic. A diagrammatic axiomatisation for qubit entanglement. 2015.
In 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 2015, pages 573—584, IEEE.
Diagrammatic techniques for reasoning about monoidal categories provide an intuitive understanding of the symmetries and connections of interacting computational processes. In the context of categorical quantum mechanics, Coecke and Kissinger suggested that two 3-qubit states, GHZ and W, may be used as the building blocks of a new graphical calculus, aimed at a diagrammatic classification of multipartite qubit entanglement that would highlight the communicational properties of quantum states, and their potential uses in cryptographic schemes.
In this paper, we present a full graphical axiomatisation of the relations between GHZ and W: the ZW calculus. This refines a version of the preexisting ZX calculus, while keeping its most desirable characteristics: undirectedness, a large degree of symmetry, and an algebraic underpinning. We prove that the ZW calculus is complete for the category of free abelian groups on a power of two generators — "qubits with integer coefficients" — and provide an explicit normalisation procedure.
A. Hadzihasanovic. Representable diagrammatic sets as a model of weak higher categories. 2019.
Developing an idea of Kapranov and Voevodsky, we introduce a model of weak omega-categories based on directed complexes, combinatorial presentations of pasting diagrams. We propose this as a convenient framework for higher-dimensional rewriting.
We define diagrammatic sets to be presheaves on a category of directed complexes presenting pasting diagrams with spherical boundaries. Diagrammatic sets have structural face and degeneracy operations, but no structural composition. We define a notion of equivalence cell in a diagrammatic set, and say that a diagrammatic set is representable if all pasting diagrams with spherical boundaries are connected to individual cells — their weak composites — by a higher-dimensional equivalence cell. We develop the basic theory of representable diagrammatic sets (RDSs), and prove that equivalence cells satisfy the expected properties in an RDS. We study nerves of strict omega-categories as RDSs and prove that 2-truncated RDSs are equivalent to bicategories.
Finally, we connect the combinatorics of diagrammatic sets and simplicial sets, and prove a version of the homotopy hypothesis for “groupoidal” RDSs: there exists a geometric realisation functor for diagrammatic sets, inducing isomorphisms between combinatorial and classical homotopy groups, which has a homotopical right inverse.
A. Hadzihasanovic. The algebra of entanglement and the geometry of composition. University of Oxford. 2017.
String diagrams turn algebraic equations into topological moves that have recurring shapes, involving the sliding of one diagram past another. We individuate, at the root of this fact, the dual nature of polygraphs as presentations of higher algebraic theories, and as combinatorial descriptions of "directed spaces". Operations of polygraphs modelled on operations of topological spaces are used as the foundation of a compositional universal algebra, where sliding moves arise from tensor products of polygraphs. We reconstruct several higher algebraic theories in this framework.
In this regard, the standard formalism of polygraphs has some technical problems. We propose a notion of regular polygraph, barring cell boundaries that are not homeomorphic to a disk of the appropriate dimension. We define a category of non-degenerate shapes, and show how to calculate their tensor products. Then, we introduce a notion of weak unit to recover weakly degenerate boundaries in low dimensions, and prove that the existence of weak units is equivalent to a representability property.
We then turn to applications of diagrammatic algebra to quantum theory. We re-evaluate the category of Hilbert spaces from the perspective of categorical universal algebra, which leads to a bicategorical refinement. Then, we focus on the axiomatics of fragments of quantum theory, and present the ZW calculus, the first complete diagrammatic axiomatisation of the theory of qubits.
The ZW calculus has several advantages over ZX calculi, including a computationally meaningful normal form, and a fragment whose diagrams can be read as setups of fermionic oscillators. Moreover, its generators reflect an operational classification of entangled states of 3 qubits. We conclude with generalisations of the ZW calculus to higher-dimensional systems, including the definition of a universal set of generators in each dimension.