Publications.

You can:

Return to the homepage.

Preprints.

1. C. Chanavat, A. Hadzihasanovic. Model structures for diagrammatic (∞, n)-categories. 2024.
   arXiv 2410.19053 - Show abstract

   Diagrammatic sets admit a notion of internal equivalence in the sense of coinductive weak invertibility, with similar properties to its analogue in strict ω-categories. We construct a model structure whose fibrant objects are diagrammatic sets in which every round pasting diagram is equivalent to a single cell—its weak composite—and propose them as a model of (∞, ∞)-categories. For each n < ∞, we then construct a model structure whose fibrant objects are those (∞, ∞)-categories whose cells in dimension > n are all weakly invertible. We show that weak equivalences between fibrant objects are precisely morphisms that are essentially surjective on cells of all dimensions. On the way to this result, we also construct model structures for (∞, n)-categories on marked diagrammatic sets, which split into a coinductive and an inductive case when n = ∞, and prove that they are Quillen equivalent to the unmarked model structures when n < ∞ and in the coinductive case of n = ∞. Finally, we prove that the (∞, 0)-model structure is Quillen equivalent to the classical model structure on simplicial sets. This establishes the first proof of the homotopy hypothesis for a model of ∞-groupoids defined as (∞, ∞)-categories whose cells in dimension > 0 are all weakly invertible.

2. C. Chanavat, A. Hadzihasanovic. Equivalences in diagrammatic sets. 2024.
   arXiv 2410.00123 - Show abstract

   We show that diagrammatic sets, a topologically sound alternative to polygraphs and strict ω-categories, admit an internal notion of equivalence in the sense of coinductive weak invertibility. We prove that equivalences have the expected properties: they include all degenerate cells, are closed under 2-out-of-3, and satisfy an appropriate version of the "division lemma", which ensures that enwrapping a diagram with equivalences at all sides is an invertible operation up to higher equivalence. On the way to this result, we develop methods, such as an algebraic calculus of natural equivalences, for handling the weak units and unitors which set this framework apart from strict ω-categories.

3. C. Chanavat, A. Hadzihasanovic. Diagrammatic sets as a model of homotopy types. 2024.
   arXiv 2407.06285 - Show abstract

   Diagrammatic sets are presheaves on a rich category of shapes, whose definition is motivated by combinatorial topology and higher-dimensional diagram rewriting. These shapes include representatives of oriented simplices, cubes, and positive opetopes, and are stable under operations including Gray products, joins, suspensions, and duals. We exhibit a cofibrantly generated model structure on diagrammatic sets, as well as two separate Quillen equivalences with the classical model structure on simplicial sets. We construct explicit sets of generating cofibrations and acyclic cofibrations, and prove that the model structure is monoidal with the Gray product of diagrammatic sets.

4. A. Hadzihasanovic, F. Loubaton, V. Ozornova, M. Rovelli. A model for the coherent walking ω-equivalence. 2024.
   arXiv 2404.14509 - Show abstract

   We prove that a certain ω-category, which was constructed in previous work by the third and fourth author, is a model for the fully coherent walking ω-equivalence. Further, appropriate truncations of it give models for the fully coherent walking n-equivalence for each n ≥ 1.

5. A. Hadzihasanovic. Combinatorics of higher-categorical diagrams. 2024.
   arXiv 2404.07273 - Show abstract

   This is a book on higher-categorical diagrams, including pasting diagrams. It aims to provide a thorough and modern reference on the subject, collecting, revisiting and expanding results scattered across the literature, informed by recent advances and practical experience with higher-dimensional diagram rewriting.

   We approach the subject as a kind of directed combinatorial topology: a diagram is a map from a "directed cell complex", encoded combinatorially as a face poset together with orientation data. Unlike previous expositions, we adopt from the beginning a functorial viewpoint, focussing on morphisms and categorical constructions. We do not tie ourselves to a specific model of higher categories, and instead treat diagrams as independent combinatorial structures that admit functorial interpretations in various contexts.

   Topics covered include the theory of layerings of diagrams; acyclicity properties and their consequences; constructions including Gray products, suspensions, and joins; special shapes such as globes, oriented simplices, cubes, and positive opetopes; the interpretation of diagrams in strict ω-categories and their geometric realisation as simplicial and CW complexes; and Steiner's theory of directed chain complexes.

Refereed.

1. A. Hadzihasanovic, D. Kessler. Acyclicity conditions on pasting diagrams. 2024.
   In Applied Categorical Structures, volume 32, issue 6, article number 31.
   arXiv 2408.16775 - Show abstract

   We study various acyclicity conditions on higher-categorical pasting diagrams in the combinatorial framework of regular directed complexes. We present an apparently weakest acyclicity condition under which the ω-category presented by a diagram shape is freely generated in the sense of polygraphs. We then consider stronger conditions under which this ω-category is equivalent to one obtained from an augmented directed chain complex in the sense of Steiner, or consists only of subsets of cells in the diagram. Finally, we study the stability of these conditions under the operations of pasting, suspensions, Gray products, joins and duals.

2. C. Puca, A. Hadzihasanovic, F. Genovese, B. Coecke. Obstructions to compositionality. 2023.
   In 6th International Conference on Applied Category Theory (ACT) 2023, volume 397 of EPTCS, pages 226—245.
   arXiv 2307.14461 - Show abstract

   Compositionality is at the heart of computer science and several other areas of applied category theory such as computational linguistics, categorical quantum mechanics, interpretable AI, dynamical systems, compositional game theory, and Petri nets. However, the meaning of the term seems to vary across the many different applications. This work contributes to understanding, and in particular qualifying, different kinds of compositionality. Formally, we introduce invariants of categories that we call zeroth and first homotopy posets, generalising in a precise sense the π₀ and π₁ of a groupoid. These posets can be used to obtain a qualitative description of how far an object is from being terminal and a morphism is from being iso. In the context of applied category theory, this formal machinery gives us a way to qualitatively describe the "failures of compositionality", seen as failures of certain (op)lax functors to be strong, by classifying obstructions to the (op)laxators being isomorphisms. Failure of compositionality, for example for the interpretation of a categorical syntax in a semantic universe, can both be a bad thing and a good thing, which we illustrate by respective examples in graph theory and quantum theory.

3. A. Hadzihasanovic, D. Kessler. Higher-dimensional subdiagram matching. 2023.
   In 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 2023, pages 1—13, IEEE.
   arXiv 2304.09216 - Show abstract

   Higher-dimensional rewriting is founded on a duality of rewrite systems and cell complexes, connecting computational mathematics to higher categories and homotopy theory: the two sides of a rewrite rule are two halves of the boundary of an (n+1)-cell, which are diagrams of n-cells. We study higher-dimensional diagram rewriting as a mechanism of computation, focussing on the matching problem for rewritable subdiagrams within the combinatorial framework of diagrammatic sets. We provide an algorithm for subdiagram matching in arbitrary dimensions, based on new results on layerings of diagrams, and derive upper bounds on its time complexity. We show that these superpolynomial bounds can be improved to polynomial bounds under certain acyclicity conditions, and that these conditions hold in general for diagrams up to dimension 3. We discuss the challenges that arise in dimension 4.

4. A. Hadzihasanovic, D. Kessler. Data structures for topologically sound higher-dimensional diagram rewriting. 2022.
   In 5th International Conference on Applied Category Theory (ACT) 2022, volume 380 of EPTCS, pages 111—127.
   arXiv 2209.09509 - Show abstract

   We present a computational implementation of diagrammatic sets, a model of higher-dimensional diagram rewriting that is “topologically sound”: diagrams admit a functorial interpretation as homotopies in cell complexes. This has potential applications both in the formalisation of higher algebra and category theory and in computational algebraic topology. We describe data structures for well-formed shapes of diagrams of arbitrary dimensions and provide a solution to their isomorphism problem in time O(n³ log n). On top of this, we define a type theory for rewriting in diagrammatic sets and provide a semantic characterisation of its syntactic category. All data structures and algorithms are implemented in the Python library rewalt, which also supports various visualisations of diagrams.

5. A. Hadzihasanovic. The smash product of monoidal theories. 2021.
   In 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 2021, pages 1—13, IEEE.
   arXiv 2101.10361 - Show abstract

   The tensor product of props was defined by Hackney and Robertson as an extension of the Boardman-Vogt product of operads to more general monoidal theories. Theories that factor as tensor products include the theory of commutative monoids and the theory of bialgebras. We give a topological interpretation (and vast generalisation) of this construction as a low-dimensional projection of a "smash product of pointed directed spaces". Here directed spaces are embodied by combinatorial structures called diagrammatic sets, while Gray products replace cartesian products. The correspondence is mediated by a web of adjunctions relating diagrammatic sets, pros, probs, props, and Gray-categories. The smash product applies to presentations of higher-dimensional theories and systematically produces higher-dimensional coherence cells.

6. A. Hadzihasanovic. A combinatorial-topological shape category for polygraphs. 2020.
   In Applied Categorical Structures, volume 28, issue 3, pages 419—476.
   arXiv 1806.10353 - Show abstract

   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.

7. 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.
   arXiv 1803.06086 - Show abstract

   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.

8. 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.
   arXiv 1801.01231 - Show abstract

   We introduce the fermionic ZW calculus, a string-diagrammatic language for fermionic quantum computing (FQC). After defining a fermionic circuit model, we present the basic components of the calculus, together with their interpretation, and show how the main physical gates of interest in FQC can be represented in our language. We then list our axioms, and derive some additional equations. We prove that the axioms provide a complete equational axiomatisation of the monoidal category whose objects are systems of finitely many local fermionic modes (LFMs), with maps that preserve or reverse the parity of states, and the tensor product as monoidal product. We achieve this through a procedure that rewrites any diagram in a normal form. As an example, we show how the statistics of a fermionic Mach-Zehnder interferometer can be calculated in the diagrammatic language. We conclude by giving a diagrammatic treatment of the dual-rail encoding, a standard method in optical quantum computing used to perform universal quantum computation.

   Extended version of A diagrammatic axiomatisation of fermionic quantum circuits, FSCD 2018.

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

   Categorical quantum mechanics places finite-dimensional quantum theory in the context of compact closed categories, with an emphasis on diagrammatic reasoning. In this framework, two equational diagrammatic calculi have been proposed for pure-state qubit quantum computing: the ZW calculus, developed by Coecke, Kissinger and the first author for the purpose of qubit entanglement classification, and the ZX calculus, introduced by Coecke and Duncan to give an abstract description of complementary observables. Neither calculus, however, provided a complete axiomatisation of their model.

   In this paper, we present extended versions of ZW and ZX, and show their completeness for pure-state qubit theory, thus solving two major open problems in categorical quantum mechanics. First, we extend the original ZW calculus to represent states and linear maps with coefficients in an arbitrary commutative ring, and prove completeness by a strategy that rewrites all diagrams into a normal form. We then extend the language and axioms of the original ZX calculus, and show their completeness for pure-state qubit theory through a translation between ZX and ZW specialised to the field of complex numbers. This translation expands the one used by Jeandel, Perdrix, and Vilmart to derive an axiomatisation of the approximately universal Clifford+T fragment; restricting the field of complex numbers to a suitable subring, we obtain an alternative axiomatisation of the same theory.

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

    We introduce the fermionic ZW calculus, a string-diagrammatic language for fermionic quantum computing (FQC). After defining a fermionic circuit model, we present the basic components of the calculus, together with their interpretation, and show how the main physical gates of interest in FQC can be represented in 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.

11. 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.
    arXiv 1701.00658 - Show abstract

    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.

12. 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.
    arXiv 1402.0784 - Show abstract

    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.

13. 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.
    arXiv 1501.07082 - Show abstract

    Diagrammatic techniques for reasoning about monoidal categories provide an intuitive understanding of the symmetries and connections of interacting computational processes. In the context of categorical quantum mechanics, Coecke and Kissinger suggested that two 3-qubit states, GHZ and W, may be used as the building blocks of a new graphical calculus, aimed at a diagrammatic classification of multipartite qubit entanglement that would highlight the communicational properties of quantum states, and their potential uses in cryptographic schemes.

    In this paper, we present a full graphical axiomatisation of the relations between GHZ and W: the ZW calculus. This refines a version of the preexisting ZX calculus, while keeping its most desirable characteristics: undirectedness, a large degree of symmetry, and an algebraic underpinning. We prove that the ZW calculus is complete for the category of free abelian groups on a power of two generators — "qubits with integer coefficients" — and provide an explicit normalisation procedure.

Unpublished.

1. A. Hadzihasanovic. Diagrammatic sets and rewriting in weak higher categories. 2020.
   arXiv 2007.14505 - Show abstract

   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.

2. A. Hadzihasanovic. Representable diagrammatic sets as a model of weak higher categories. 2019.
   arXiv 1909.07639 - Show abstract

   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.

Doctoral thesis.

• A. Hadzihasanovic. The algebra of entanglement and the geometry of composition. University of Oxford. 2017.
  arXiv 1709.08086 - Show abstract

  String diagrams turn algebraic equations into topological moves that have recurring shapes, involving the sliding of one diagram past another. We individuate, at the root of this fact, the dual nature of polygraphs as presentations of higher algebraic theories, and as combinatorial descriptions of "directed spaces". Operations of polygraphs modelled on operations of topological spaces are used as the foundation of a compositional universal algebra, where sliding moves arise from tensor products of polygraphs. We reconstruct several higher algebraic theories in this framework.

  In this regard, the standard formalism of polygraphs has some technical problems. We propose a notion of regular polygraph, barring cell boundaries that are not homeomorphic to a disk of the appropriate dimension. We define a category of non-degenerate shapes, and show how to calculate their tensor products. Then, we introduce a notion of weak unit to recover weakly degenerate boundaries in low dimensions, and prove that the existence of weak units is equivalent to a representability property.

  We then turn to applications of diagrammatic algebra to quantum theory. We re-evaluate the category of Hilbert spaces from the perspective of categorical universal algebra, which leads to a bicategorical refinement. Then, we focus on the axiomatics of fragments of quantum theory, and present the ZW calculus, the first complete diagrammatic axiomatisation of the theory of qubits. The ZW calculus has several advantages over ZX calculi, including a computationally meaningful normal form, and a fragment whose diagrams can be read as setups of fermionic oscillators. Moreover, its generators reflect an operational classification of entangled states of 3 qubits. We conclude with generalisations of the ZW calculus to higher-dimensional systems, including the definition of a universal set of generators in each dimension.