Abstract. This erratum adds a missing case to the proof of Lemma 5.8 in [ SIAM J. Comput., 50 (2021), pp. 1739–1799].

Computer science ? like other areas of science, engineering, technology and mathematics (STEM) - can be inhospitable to marginalised groups. Lesbian, gay, bisexual, trans, queer, intersex, asexual, and other minority sexual identity or minority gender (LGBTQIA+) people have often been ignored in STEM, even though research shows they find the field particularly unwelcoming. While there is a broad range of advice for improving equality, diversity and inclusivity (EDI) in higher education, it either does not apply to many areas of computer science, or is fairly vague.

Holant problems are a family of counting problems parameterized by sets of algebraic-complex-valued constraint functions and defined on graphs. They arise from the theory of holographic algorithms, which was originally inspired by concepts from quantum computation. Here, we employ quantum information theory to explain existing results about holant problems in a concise way and to derive two new dichotomies: one for a new family of problems, which we call ${{Holant}}^+$, and, building on this, a full dichotomy for ${{Holant}}^c$. These two families of holant problems assume the availability of certain unary constraint functions---the two pinning functions in the case of ${{Holant}}^c$, and four functions in the case of ${{Holant}}^+$---and allow arbitrary sets of algebraic-complex valued constraint functions otherwise. The dichotomy for ${{Holant}}^+$ also applies when inputs are restricted to instances defined on planar graphs. In proving these complexity classifications, we derive an original result about entangled quantum states.

The stabilizer ZX-calculus is a rigorous graphical language for reasoning about quantum mechanics. The language is sound and complete: one can transform a stabilizer ZX-diagram into another one using the graphical rewrite rules if and only if these two diagrams represent the same quantum evolution or quantum state. We previously showed that the stabilizer ZX-calculus can be simplified by reducing the number of rewrite rules, without losing the property of completeness [Backens, Perdrix & Wang, EPTCS 236:1--20, 2017]. Here, we show that most of the remaining rules of the language are indeed necessary. We do however leave as an open question the necessity of two rules. These include, surprisingly, the bialgebra rule, which is an axiomatisation of complementarity, the cornerstone of the ZX-calculus. Furthermore, we show that a weaker ambient category -- a braided autonomous category instead of the usual compact closed category -- is sufficient to recover the meta rule 'only connectivity matters', even without assuming any symmetries of the generators.

We construct a theory of holant clones to capture the notion of expressibility in the holant framework. Their role is analogous to the role played by functional clones in the study of weighted counting Constraint Satisfaction Problems. We explore the landscape of conservative holant clones and determine the situations in which a set F of functions is “universal in the conservative case,” which means that all functions are contained in the holant clone generated by F together with all unary functions. When F is not universal in the conservative case, we give concise generating sets for the clone. We demonstrate the usefulness of the holant clone theory by using it to give a complete complexity-theory classification for the problem of approximating the solution to conservative holant problems. We show that approximation is intractable exactly when F is universal in the conservative case.

Holant problems are a family of counting problems on graphs, parametrised by sets of complex-valued functions of Boolean inputs. Holant^c denotes a subfamily of those problems, where any function set considered must contain the two unary functions pinning inputs to values 0 or 1. The complexity classification of Holant problems usually takes the form of dichotomy theorems, showing that for any set of functions in the family, the problem is either #P-hard or it can be solved in polynomial time. Previous such results include a dichotomy for real-valued Holant^c and one for Holant^c with complex symmetric functions. Here, we derive a dichotomy theorem for Holant^c with complex-valued, not necessarily symmetric functions. The tractable cases are the complex-valued generalisations of the tractable cases of the real-valued Holant^c dichotomy. The proof uses results from quantum information theory, particularly about entanglement.

Holant problems are a framework for the analysis of counting complexity problems on graphs. This framework is simultaneously general enough to encompass many counting problems on graphs and specific enough to allow the derivation of dichotomy results, partitioning all problems into those which are in FP and those which are #P-hard. The Holant framework is based on the theory of holographic algorithms, which was originally inspired by concepts from quantum computation, but this connection appears not to have been explored before. Here, we employ quantum information theory to explain existing results in a concise way and to derive a dichotomy for a new family of problems, which we call Holant^+. This family sits in between the known families of Holant^*, for which a full dichotomy is known, and Holant^c, for which only a restricted dichotomy is known. Using knowledge from entanglement theory -- both previously existing work and new results of our own -- we prove a full dichotomy theorem for Holant^+, which is very similar to the restricted Holant^c dichotomy and may thus be a stepping stone to a full dichotomy for that family.