1,765 research outputs found
A Complete Dichotomy for Complex-Valued Holant^c
Full text linkHolant 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, i.e. functions which only depend on the Hamming weight of the input.
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. This full dichotomy for Holant^c answers a question that has been open for almost a decade
A New Holant Dichotomy Inspired by Quantum Computation
Full text linkHolant 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
Towards a Minimal Stabilizer ZX-calculus
Full text link13+15 pagesInternational audienceThe 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
Dr. Miriam McCormick – Faculty Author Interview
No full textDr. Miriam McCormick, Associate Professor of Philosophy and Philosophy, Politics, Economics and Law, discusses her new book, Believing Against the Evidence: Agency and the Ethics of Belief published recently by Routledge. In this book, Dr. McCormick argues that the standards used to evaluate beliefs are not isolated from other evaluative domains. The ultimate criteria for assessing beliefs are the same as those for assessing action because beliefs and actions are both products of agency
Informatique Fondamentale et ses Mathématiques : Une photographie en 2025
No full textInternational audienceL'informatique Fondamentale et ses Mathématiques (IFM) regroupe des thématiques relevant a priori de tous les domaines de l’informatique, pourvu que la démarche de recherche ou le point de vue adoptés soient « mathématisables ». Cet ouvrage réunit les cours proposés à l’édition 2025 de l’École des Jeunes Chercheuses et Chercheurs en Informatique Fondamentale et ses Mathématiques (EJCIFM), organisée à Caen du 16 au 20 juin 2025 dans le cadre du Groupe de recherche en Informatique Fondamentale et ses Mathématiques (GdR IFM) du CNRS. Présentant de manière équilibrée différentes thématiques du domaine IFM, cet ouvrage en propose une photographie.Cinq thèmes sont présentés par sept spécialistes du domaine : l’informatique quantique, la sémantique, la combinatoire énumérative, l’évaluationsymbolique numérique et la compilation de connaissances. Ces chapitres ont été écrits par Miriam Backens, Kostia Chardonnet, Pierre Clairambault,Julien Courtiel, Denis Arzelier, Mioara Joldes et Bruno Zanuttini
Informatique Fondamentale et ses Mathématiques : Une photographie en 2025
No full textInternational audienceL'informatique Fondamentale et ses Mathématiques (IFM) regroupe des thématiques relevant a priori de tous les domaines de l’informatique, pourvu que la démarche de recherche ou le point de vue adoptés soient « mathématisables ». Cet ouvrage réunit les cours proposés à l’édition 2025 de l’École des Jeunes Chercheuses et Chercheurs en Informatique Fondamentale et ses Mathématiques (EJCIFM), organisée à Caen du 16 au 20 juin 2025 dans le cadre du Groupe de recherche en Informatique Fondamentale et ses Mathématiques (GdR IFM) du CNRS. Présentant de manière équilibrée différentes thématiques du domaine IFM, cet ouvrage en propose une photographie.Cinq thèmes sont présentés par sept spécialistes du domaine : l’informatique quantique, la sémantique, la combinatoire énumérative, l’évaluationsymbolique numérique et la compilation de connaissances. Ces chapitres ont été écrits par Miriam Backens, Kostia Chardonnet, Pierre Clairambault,Julien Courtiel, Denis Arzelier, Mioara Joldes et Bruno Zanuttini
Informatique Fondamentale et ses Mathématiques : Une photographie en 2025
No full textInternational audienceL'informatique Fondamentale et ses Mathématiques (IFM) regroupe des thématiques relevant a priori de tous les domaines de l’informatique, pourvu que la démarche de recherche ou le point de vue adoptés soient « mathématisables ». Cet ouvrage réunit les cours proposés à l’édition 2025 de l’École des Jeunes Chercheuses et Chercheurs en Informatique Fondamentale et ses Mathématiques (EJCIFM), organisée à Caen du 16 au 20 juin 2025 dans le cadre du Groupe de recherche en Informatique Fondamentale et ses Mathématiques (GdR IFM) du CNRS. Présentant de manière équilibrée différentes thématiques du domaine IFM, cet ouvrage en propose une photographie.Cinq thèmes sont présentés par sept spécialistes du domaine : l’informatique quantique, la sémantique, la combinatoire énumérative, l’évaluationsymbolique numérique et la compilation de connaissances. Ces chapitres ont été écrits par Miriam Backens, Kostia Chardonnet, Pierre Clairambault,Julien Courtiel, Denis Arzelier, Mioara Joldes et Bruno Zanuttini
Informatique Fondamentale et ses Mathématiques : Une photographie en 2025
No full textInternational audienceL'informatique Fondamentale et ses Mathématiques (IFM) regroupe des thématiques relevant a priori de tous les domaines de l’informatique, pourvu que la démarche de recherche ou le point de vue adoptés soient « mathématisables ». Cet ouvrage réunit les cours proposés à l’édition 2025 de l’École des Jeunes Chercheuses et Chercheurs en Informatique Fondamentale et ses Mathématiques (EJCIFM), organisée à Caen du 16 au 20 juin 2025 dans le cadre du Groupe de recherche en Informatique Fondamentale et ses Mathématiques (GdR IFM) du CNRS. Présentant de manière équilibrée différentes thématiques du domaine IFM, cet ouvrage en propose une photographie.Cinq thèmes sont présentés par sept spécialistes du domaine : l’informatique quantique, la sémantique, la combinatoire énumérative, l’évaluationsymbolique numérique et la compilation de connaissances. Ces chapitres ont été écrits par Miriam Backens, Kostia Chardonnet, Pierre Clairambault,Julien Courtiel, Denis Arzelier, Mioara Joldes et Bruno Zanuttini
Informatique Fondamentale et ses Mathématiques : Une photographie en 2025
No full textInternational audienceL'informatique Fondamentale et ses Mathématiques (IFM) regroupe des thématiques relevant a priori de tous les domaines de l’informatique, pourvu que la démarche de recherche ou le point de vue adoptés soient « mathématisables ». Cet ouvrage réunit les cours proposés à l’édition 2025 de l’École des Jeunes Chercheuses et Chercheurs en Informatique Fondamentale et ses Mathématiques (EJCIFM), organisée à Caen du 16 au 20 juin 2025 dans le cadre du Groupe de recherche en Informatique Fondamentale et ses Mathématiques (GdR IFM) du CNRS. Présentant de manière équilibrée différentes thématiques du domaine IFM, cet ouvrage en propose une photographie.Cinq thèmes sont présentés par sept spécialistes du domaine : l’informatique quantique, la sémantique, la combinatoire énumérative, l’évaluationsymbolique numérique et la compilation de connaissances. Ces chapitres ont été écrits par Miriam Backens, Kostia Chardonnet, Pierre Clairambault,Julien Courtiel, Denis Arzelier, Mioara Joldes et Bruno Zanuttini
Informatique Fondamentale et ses Mathématiques : Une photographie en 2025
No full textInternational audienceL'informatique Fondamentale et ses Mathématiques (IFM) regroupe des thématiques relevant a priori de tous les domaines de l’informatique, pourvu que la démarche de recherche ou le point de vue adoptés soient « mathématisables ». Cet ouvrage réunit les cours proposés à l’édition 2025 de l’École des Jeunes Chercheuses et Chercheurs en Informatique Fondamentale et ses Mathématiques (EJCIFM), organisée à Caen du 16 au 20 juin 2025 dans le cadre du Groupe de recherche en Informatique Fondamentale et ses Mathématiques (GdR IFM) du CNRS. Présentant de manière équilibrée différentes thématiques du domaine IFM, cet ouvrage en propose une photographie.Cinq thèmes sont présentés par sept spécialistes du domaine : l’informatique quantique, la sémantique, la combinatoire énumérative, l’évaluationsymbolique numérique et la compilation de connaissances. Ces chapitres ont été écrits par Miriam Backens, Kostia Chardonnet, Pierre Clairambault,Julien Courtiel, Denis Arzelier, Mioara Joldes et Bruno Zanuttini
- …
