Publications

In accordance with the San Francisco Declaration on Research Assessment, all articles below are either open access or have an author version, with the exception of the published poster.

Preprints

  1. Pierre Guillon and Emmanuel Jeandel. Infinite Communication Complexity[DL]

    Suppose that Alice and Bob are given each an infinite string, and they want to decide whether their two strings are in a given relation. How much communication do they need? How can communication be even defined and measured for infinite strings? In this article, we propose a formalism for a notion of infinite communication complexity, prove that it satisfies some natural properties and coincides, for relevant applications, with the classical notion of amortized communication complexity. Moreover, an application is given for tackling some conjecture about tilings and multidimensional sofic shifts.

  2. Emmanuel Jeandel. Some Notes about Subshifts on Groups[DL]

    In this note we prove the following results: • If a finitely presented group G admits a strongly aperiodic SFT, then G has decidable word problem. • For a large class of group \(G\), \(Z \times G\) admits a strongly aperiodic SFT. In particular, this is true for the free group with 2 generators, Thompson’s groups \(T\) and \(V\) , \(PSL_2(\mathbb{ZZ})\) and any f.g. group of rational matrices which is bounded.

  3. Emmanuel Jeandel. Strong shift equivalence as a category notion[DL]

    In this paper, we present a completely radical way to investigate the main problem of symbolic dynamics, the conjugacy problem, by proving that this problem actually relates to a natural question in category theory regarding the theory of traced bialgebras. As a consequence of this theory, we obtain a systematic way of obtaining new invariants for the conjugacy problem by looking at existing bialgebras in the literature.

  4. Emmanuel Jeandel. Translation-like Actions and Aperiodic Subshifts on Groups[DL]

    It is well known that if \(G\) admits a f.g. subgroup \(H\) with a weakly aperiodic SFT (resp. an undecidable domino problem), then \(G\) itself has a weakly aperiodic SFT (resp. an undecidable domino problem). We prove that we can replace the property ‘\(H\) is a subgroup of \(G\)’ by ’ \(H\) acts translation-like on \(G\)’, provided \(H\) is finitely presented. In particular: * If \(G_1\) and \(G_2\) are f.g. infinite groups, then \(G_1\times G_2\) has a weakly aperiodic SFT (and actually an undecidable domino problem). In particular the Grigorchuk group has an undecidable domino problem. * Every infinite f.g. p-group admits a weakly aperiodic SFT.

Book Chapters

  1. Amaury Saint-Jore, Nazim Fatès, and Emmanuel Jeandel. Amoeba for Clustering: A Bio-inspired Cellular Automata Method for Data Classification. In Andrez Adamatzky, editor, Automata and Complexity, volume 42 of Emergence, Complexity and Computation, pages 417–432. Springer, 2022 [DOI][DL]

  2. Emmanuel Jeandel and Pascal Vanier. The Undecidability of the Domino Problem. In Substitution and Tiling Dynamics: Introduction to Self-inducing Structures, number 2273 in Lecture Notes in Mathematics, pages 293–356. Springer, 2020 [DOI][DL]

  3. Nathalie Aubrun, Sebastian Barbieri, and Emmanuel Jeandel. About the Domino Problem for Subshifts on Groups. In Valérie Berthé and Michel Rigo, editors, Sequences, Groups, and Number Theory, Trends in Mathematics, pages 331–389. Springer, 2018 [DOI][DL]

Papers

  1. Emmanuel Jeandel, Simon Perdrix, and Margarita Veshchezerova. Addition and Differentiation of ZX-diagrams. LMCS, 2024 . special issue pour FSCD 2022

  2. Emmanuel Jeandel and Michael Rao. An aperiodic set of 11 Wang tiles. Advances in Combinatorics, 1:1–37, January 2021[DOI][DL]

    A new aperiodic tile set containing 11 Wang tiles on 4 colors is presented. This tile set is minimal in the sense that no Wang set with less than 11 tiles is aperiodic, and no Wang set with less than 4 colors is aperiodic.

  3. Titouan Carette, Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. Completeness of Graphical Languages for Mixed States Quantum Mechanics. ACM Transactions on Quantum Computing, 2(4):1–28, 2021 [DOI][DL]

    There exist several graphical languages for quantum information processing, like quantum circuits, ZX-calculus, ZW-calculus, etc. Each of these languages forms a \(\dagger\)-symmetric monoidal category (\(\dagger\)-SMC) and comes with an interpretation functor to the \(\dagger\)-SMC of finite dimensional Hilbert spaces. In recent years, one of the main achievements of the categorical approach to quantum mechanics has been to provide several equational theories for most of these graphical languages, making them complete for various fragments of pure quantum mechanics. We address the question of how to extend these languages beyond pure quantum mechanics, in order to reason about mixed states and general quantum operations, i.e., completely positive maps. Intuitively, such an extension relies on the axiomatisation of a discard map which allows one to get rid of a quantum system, an operation which is not allowed in pure quantum mechanics. We introduce a new construction, the discard construction, which transforms any \(\dagger\)-symmetric monoidal category into a symmetric monoidal category equipped with a discard map. Roughly speaking this construction consists in making any isometry causal. Using this construction, we provide an extension for several graphical languages that we prove to be complete for general quantum operations. However, this construction fails for some fringe cases like Clifford+T quantum mechanics, as the category does not have enough isometries.

  4. Constantin Dalyac, Loïc Henriet, Emmanuel Jeandel, Wolfgang Lechner, Simon Perdrix, Marc Porcheron, and Margarita Veshchezerova. Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles. EPJ Quantum Technology, 8(12):1–27, 2021 [DOI]

    In order to qualify quantum algorithms for industrial NP-Hard problems, comparing them to available polynomial approximate classical algorithms and not only to exact exponential ones is necessary. This is a great challenge as, in many cases, bounds on the reachable approximation ratios exist according to some highly-trusted conjectures of Complexity Theory. An interesting setup for such qualification is thus to focus on particular instances of these problems known to be “less difficult” than the worst-case ones and for which the above bounds can be outperformed: quantum algorithms should perform at least as well as the conventional approximate ones on these instances, up to very large sizes. We present a case study of such a protocol for two industrial problems drawn from the strongly developing field of smart-charging of electric vehicles. Tailored implementations of the Quantum Approximate Optimization Algorithm (QAOA) have been developed for both problems, and tested numerically with classical resources either by emulation of Pasqal’s Rydberg atom based quantum device or using Atos Quantum Learning Machine. In both cases, quantum algorithms exhibit the same approximation ratios as conventional approximation algorithms or improve them. These are very encouraging results, although still for instances of limited size as allowed by studies on classical computing resources. The next step will be to confirm them on larger instances, on actual devices, and for more complex versions of the problems addressed.

  5. Emmanuel Jeandel, Etienne Moutot, and Pascal Vanier. Slopes of multi-dimensional subshifts. Theory of Computing Systems, 64:35–61, 2020 [DOI][DL]

    In this paper we study the directions of periodicity of multidimensional subshifts of finite type (SFTs) and of multidimensional effectively closed and sofic subshifts. A configuration of a subshift has a slope of periodicity if it is periodic in exactly one direction, the slope representing that direction. In this paper, we prove that \(\Sigma_1^0\) sets of non-commensurable \(\mathbb{Z}^2\) vectors are exactly the sets of slopes of 2D SFTs and that \(\Sigma_2^0\) sets of non-commensurable vectors are exactly the sets of slopes of 3D SFTs, and exactly the sets of slopes of 2D and 3D sofic and effectively closed subshifts.

  6. Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. Completeness of the ZX-Calculus. Logical Methods in Computer Science, 16(2):11:1–72, 2020 [DOI][DL]

    The ZX-Calculus is a graphical language for diagrammatic reasoning in quantum mechanics and quantum information theory. It comes equipped with an equational presentation. We focus here on a very important property of the language: completeness, which roughly ensures the equational theory captures all of quantum mechanics. We first improve on the known-to-be-complete presentation for the so-called Clifford fragment of the language — a restriction that is not universal — by adding some axioms. Thanks to a system of back-and-forth translation between the ZX-Calculus and a third-party complete graphical language, we prove that the provided axiomatisation is complete for the first approximately universal fragment of the language, namely Clifford+T. We then prove that the expressive power of this presentation, though aimed at achieving completeness for the aforementioned restriction, extends beyond Clifford+T, to a class of diagrams that we call linear with Clifford+T constants. We use another version of the third-party language — and an adapted system of back-and-forth translation — to complete the language for the ZX-Calculus as a whole, that is, with no restriction. We briefly discuss the added axioms, and finally, we provide a complete axiomatisation for an altered version of the language which involves an additional generator, making the presentation simpler.

  7. Emmanuel Jeandel and Pascal Vanier. Characterizations of periods of multidimensional shifts. Ergodic Theory and Dynamical Systems, 35(2):431–460, April 2015[DOI][DL]

    We show that the sets of periods of multi-dimensional shifts of finite type are precisely the sets of integers of the complexity class NP. We also show that the functions counting their number are the functions of #P. We also give characterizations of some other notions of periodicity in terms of space complexity. We finish the paper by giving some characterizations for sofic and effective subshifts.

  8. Emmanuel Jeandel and Pascal Vanier. Hardness of conjugacy, embedding and factorization of multidimensional subshifts. Journal of Computer and System Sciences, 81(8):1648–1664, 2015 [DOI][DL]

    Subshifts of finite type are sets of colorings of the plane defined by local constraints. They can be seen as a discretization of continuous dynamical systems. We investigate here the hardness of deciding factorization, conjugacy and embedding of subshifts in dimensions d>1 for subshifts of finite type and sofic shifts and in dimensions d>0 for effective shifts. In particular, we prove that the conjugacy, factorization and embedding problems are \(\Sigma_3^0\)-complete for sofic and effective subshifts and that they are \(\Sigma_1^0\)-complete for SFTs, except for factorization which is also \(\Sigma_3^0\)-complete.

  9. Emmanuel Jeandel and Guillaume Theyssier. Subshifts as models for MSO logic. Information and Computation, 225:1–15, 2013 [DOI][DL]

    We study the Monadic Second Order (MSO) Hierarchy over colorings of the discrete plane, and draw links between classes of formula and classes of subshifts. We give a characterization of existential MSO in terms of projections of tilings, and of universal sentences in terms of combinations of “pattern counting” subshifts. Conversely, we characterize logic fragments corresponding to various classes of subshifts (subshifts of finite type, sofic subshifts, all subshifts). Finally, we show by a separation result how the situation here is different from the case of tiling pictures studied earlier by Giammarresi et al.

  10. Emmanuel Jeandel and Pascal Vanier. Turing degrees of multidimensional SFTs. Theoretical Computer Science, 505:81–92, 2013 [DOI][DL]

    In this paper we are interested in computability aspects of subshifts and in particular Turing degrees of 2-dimensional SFTs (i.e. tilings). To be more precise, we prove that given any subset \(P\) of \(\{0,1\}^\mathbb{N}\) there is a SFT \(X\) such that \(P\times\mathbb{Z}^2\) is recursively homeomorphic to \(X\setminus U\) where \(U\) is a computable set of points. As a consequence, if \(P\) contains a recursive member, \(P\) and \(X\) have the exact same set of Turing degrees. On the other hand, we prove that if \(X\) contains only non-recursive members, some of its members always have different but comparable degrees. This gives a fairly complete study of Turing degrees of SFTs.

  11. Emmanuel Jeandel. The periodic domino problem revisited. Theoretical Computer Science, 411:4010–4016, 2010 [DOI][DL]

    In this article, we give a new proof of the undecidability of the periodic domino problem. Compared to previous proofs, the main difference is that this one does not start from a proof of the undecidability of the (general) domino problem but only from the existence of an aperiodic tileset.

  12. Pierre Charbit, Emmanuel Jeandel, Pascal Koiran, Sylvain Perifel, and Stéphan Thomassé. Finding a Vector Orthogonal to Roughly Half a Collection of Vectors. Journal of Complexity, 24(1):39–53, February 2008[DOI]

    Dimitri Grigoriev has shown that for any family of \(N\) vectors in the \(d\)-dimensional linear space \(E=(F_2)^d\), there exists a vector in \(E\) which is orthogonal to at least \(N/3\) and at most \(2N/3\) vectors of the family. We show that the range \([N/3,2N/3]\) can be replaced by the much smaller range \([N/2-\sqrt{N}/2,N/2+\sqrt{N}/2]\) and we give an efficient, deterministic parallel algorithm which finds a vector achieving this bound. The optimality of the bound is also investigated.

  13. Emmanuel Jeandel and Nicolas Ollinger. Playing with Conway’s Problem. Theoretical Computer Science, 409:557–564, 2008 [DOI]

    The centralizer of a language is the maximal language commuting with it. The question, raised by Conway in 1971, whether the centralizer of a rational language is always rational, recently received a lot of attention. In Kunc 2005, a strong negative answer to this problem was given by showing that even complete co-recursively enumerable centralizers exist for finite languages. Using a combinatorial game approach, we give here an incremental construction of rational languages embedding any recursive computation in their centralizers.

  14. Emmanuel Jeandel. Topological Automata. Theory of Computing Systems, 40(4):397–407, June 2007[DOI][DL]

    We give here a new, topological, definition of automata that extends previous definitions of probabilistic and quantum automata. We then prove in an unified framework that deterministic or non-deterministic probabilistic and quantum automata recognise only regular languages with an isolated threshold.

  15. Harm Derksen, Emmanuel Jeandel, and Pascal Koiran. Quantum automata and algebraic groups. Journal of Symbolic Computation, 39(3–4):357–371, March–April 2005[DOI]

    We show that several problems which are known to be undecidable for probabilistic automata become decidable for quantum finite automata. Our main tool is an algebraic result of independent interest: we give an algorithm which, given a finite number of invertible matrices, computes the Zariski closure of the group generated by these matrices.

  16. Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, and Natacha Portier. Decidable and Undecidable Problems about Quantum Automata. SIAM Journal on Computing, 34(6):1464–1473, 2005 [DOI]

    We study the following decision problem: is the language recognized by a quantum finite automaton empty or non-empty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or non-strict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata for which it is known that strict and non-strict thresholds both lead to undecidable problems.

Proceedings

  1. Liliane-Joy Dandy, Emmanuel Jeandel, and Vladimir Zamdzhiev. Type-safe Quantum Programming in Idris. In European Symposium on Programming (ESOP), 2023 [DOI]

    Variational Quantum Algorithms are hybrid classical-quantum algorithms where classical and quantum computation work in tandem to solve computational problems. These algorithms create interesting challenges for the design of suitable programming languages. In this paper we introduce Qimaera, which is a set of libraries for the Idris 2 programming language that enable the programmer to implement hybrid classical-quantum algorithms where the full power of the elegant Idris language works in synchrony with quantum programming primitives. The two key ingredients of Idris that make this possible are (1) dependent types which allow us to implement unitary quantum operations; and (2) linearity which allows us to enforce fine-grained control over the execution of quantum operations so that we may detect and reject many physically inadmissible programs. We also show that Qimaera is suitable for variational quantum programming by providing implementations of two prominent variational quantum algorithms – QAOA and VQE.

  2. Emmanuel Jeandel, Simon Perdrix, and Margarita Veshchezerova. Addition and Differentiation of ZX-diagrams. In International Conference on Formal Structures for Computation and Deduction (FSCD), 2022 [DOI]

    The ZX-calculus is a powerful framework for reasoning in quantum computing. It provides in particular a compact representation of matrices of interests. A peculiar property of the ZX-calculus is the absence of a formal sum allowing the linear combinations of arbitrary ZX-diagrams. The universality of the formalism guarantees however that for any two ZX-diagrams, the sum of their interpretations can be represented by a ZX-diagram. We introduce a general, inductive definition of the addition of ZX-diagrams, relying on the construction of controlled diagrams. Based on this addition technique, we provide an inductive differentiation of ZX-diagrams. Indeed, given a ZX-diagram with variables in the description of its angles, one can differentiate the diagram according to one of these variables. Differentiation is ubiquitous in quantum mechanics and quantum computing (e.g. for solving optimization problems). Technically, differentiation of ZX-diagrams is strongly related to summation as witnessed by the product rules. We also introduce an alternative, non inductive, differentiation technique rather based on the isolation of the variables. Finally, we apply our results to deduce a diagram for an Ising Hamiltonian.

  3. Emmanuel Hainry, Emmanuel Jeandel, Romain Péchoux, and Olivier Zeyen. ComplexityParser: an automatic tool for certifying poly-time complexity of Java programs. In International Colloquium on Theoretical Aspects of Computing (ICTAC), volume 12819, 2021 [DOI][DL]

    ComplexityParser is a static complexity analyzer for Java programs providing the first implementation of a tier-based typing discipline. The input is a file containing Java classes. If the main method can be typed and, provided the program terminates, then the program is guaranteed to do so in polynomial time and hence also to have heap and stack sizes polynomially bounded. The application uses antlr to generate a parse tree on which it performs an efficient type inference: linear in the input size, provided that the method arity is bounded by some constant.

  4. Titouan Carette and Emmanuel Jeandel. A recipe for Quantum Graphical Languages. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP), volume 168, pages 118:1–118:17, 2020 [DOI]

    Different graphical calculi have been proposed to represent quantum computation. First the ZX-calculus [Coecke and Duncan, 2011], followed by the ZW-calculus [Hadzihasanovic, 2015] and then the ZH-calculus [Backens and Kissinger, 2018]. We can wonder if new ZX-like calculi will continue to be proposed forever. This article answers negatively. All those language share a common core structure we call \(Z^*\)-algebras. We classify \(Z^*\)-algebras up to isomorphism in two dimensional Hilbert spaces and show that they are all variations of the aforementioned calculi. We do the same for linear relations and show that the calculus of [Bonchi et al., 2017] is essentially the unique one.

  5. Titouan Carette, Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. Completeness of Graphical Languages for Mixed States Quantum Mechanics. In International Colloquium on Automata, Languages and Programming (ICALP), 2019 [DL]

    There exist several graphical languages for quantum information processing, like quantum circuits, ZX-Calculus, ZW-Calculus, etc. Each of these languages forms a †-symmetric monoidal category (†-SMC) and comes with an interpretation functor to the †-SMC of (finite dimension) Hilbert spaces. In the recent years, one of the main achievements of the categorical approach to quantum mechanics has been to provide several equational theories for most of these graphical languages, making them complete for various fragments of pure quantum mechanics. We address the question of the extension of these languages beyond pure quantum mechanics, in order to reason on mixed states and general quantum operations, i.e. completely positive maps. Intuitively, such an extension relies on the axiomatisation of a discard map which allows one to get rid of a quantum system, operation which is not allowed in pure quantum mechanics. We introduce a new construction, the discard construction, which transforms any †-symmetric monoidal category into a symmetric monoidal category equipped with a discard map. Roughly speaking this construction consists in making any isometry causal. Using this construction we provide an extension for several graphical languages that we prove to be complete for general quantum operations. However this construction fails for some fringe cases like the Clifford+T quantum mechanics, as the category does not have enough isometries.

  6. Pierre Guillon, Emmanuel Jeandel, Jarkko Kari, and Pascal Vanier. Undecidable word problem in subshift automorphism groups. In International Computer Science Symposium in Russia (CSR), volume 11532 of Lecture Notes in Computer Science. Springer, 2019 [DOI][DL]

    This article studies the complexity of the word problem in groups of automorphisms (or reversible cellular automata) of subshifts. We show in particular that for any computably enumerable Turing degree, there exists a (two-dimensional) subshift of finite type whose automorphism group contains a subgroup whose word problem has exactly this degree. In particular, there are such subshifts of finite type where this problem is uncomputable. This remains true in a large setting of subshifts over groups.

  7. Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. A Generic Normal Form for ZX-Diagrams and Application to the Rational Angle Completeness. In ACM/IEEE Symposium on Logic in Computer Science (LICS), 2019 [DOI][DL]

    Recent completeness results on the ZX-Calculus used a third-party language, namely the ZW-Calculus. As a consequence, these proofs are elegant, but sadly non-constructive. We address this issue in the following. To do so, we first describe a generic normal form for ZX-diagrams in any fragment that contains Clifford+T quantum mechanics. We give sufficient conditions for an axiomatisation to be complete, and an algorithm to reach the normal form. Finally, we apply these results to the Clifford+T fragment and the general ZX-Calculus – for which we already know the completeness–, but also for any fragment of rational angles: we show that the axiomatisation for Clifford+T is also complete for any fragment of dyadic angles, and that a simple new rule (called cancellation) is necessary and sufficient otherwise.

  8. Emmanuel Jeandel and Pascal Vanier. A characterization of subshifts with a computable language. In Symposium on Theoretical Aspects of Computer Science (STACS), volume 126, pages 40:1–40:16, 2019 [DOI]

    Subshifts are sets of colorings of \(\mathbb{Z}^d\) by a finite alphabet that avoid some family of forbidden patterns. We investigate here some analogies with group theory that were first noticed by the first author. In particular we prove several theorems on subshifts inspired by Higman’s embedding theorems of group theory, among which, the fact that subshifts with a computable language can be obtained as restrictions of minimal subshifts of finite type.

  9. Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. A Complete Axiomatisation of the ZX-Calculus for Clifford+T Quantum Mechanics. In ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 559–568, 2018 [DOI][DL]

    We introduce the first complete and approximatively universal diagrammatic language for quantum mechanics. We make the ZX-Calculus, a diagrammatic language introduced by Coecke and Duncan, complete for the so-called Clifford+T quantum mechanics by adding four new axioms to the language. The completeness of the ZX-Calculus for Clifford+T quantum mechanics was one of the main open questions in categorical quantum mechanics. We prove the completeness of the Clifford+T fragment of the ZX-Calculus using the recently studied ZW-Calculus, a calculus dealing with integer matrices. We also prove that the Clifford+T fragment of the ZX-Calculus represents exactly all the matrices over some finite dimensional extension of the ring of dyadic rationals.

  10. Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. Diagrammatic Reasoning beyond Clifford+T Quantum Mechanics. In ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 569–578, 2018 [DOI][DL]

    The ZX-Calculus is a graphical language for quantum mechanics. An axiomatisation has recently been proven to be complete for an approximatively universal fragment of quantum mechanics, the so-called Clifford+T fragment. We focus here on the expressive power of this axiomatisation beyond Clifford+T Quantum mechanics. We consider the full pure qubit quantum mechanics, and mainly prove two results: (i) First, the axiomatisation for Clifford+T quantum mechanics is also complete for all equations involving some kind of linear diagrams. The linearity of the diagrams reflects the phase group structure, an essential feature of the ZX-calculus. In particular all the axioms of the ZX-calculus are involving linear diagrams. (ii) We also show that the axiomatisation for Clifford+T is not complete in general but can be completed by adding a single (non linear) axiom, providing a simpler axiomatisation of the ZX-calculus for pure quantum mechanics than the one recently introduced by Ng&Wang.

  11. Emmanuel Jeandel. Enumeration Reducibility in Closure Spaces with Applications to Logic and Algebra. In ACM/IEEE Symposium on Logic in Computer Science (LICS), 2017 [DOI][DL]

    In many instances in first order logic or computable algebra, classical theorems show that many problems are undecidable for general structures, but become decidable if some rigidity is imposed on the structure. For example, the set of theorems in many finitely axiomatisable theories is nonrecursive, but the set of theorems for any finitely axiomatisable complete theory is recursive. Finitely presented groups might have an nonrecursive word problem, but finitely presented simple groups have a recursive word problem. In this article we introduce a topological framework based on closure spaces to show that many of these proofs can be obtained in a similar setting. We will show in particular that these statements can be generalized to cover arbitrary structures, with no finite or recursive presentation/axiomatization. This generalizes in particular work by Kuznetsov and others. Examples from first order logic and symbolic dynamics will be discussed at length.

  12. Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. Y-Calculus: A language for real Matrices derived from the ZX-Calculus. In International Conference on Quantum Physics and Logic (QPL), number 266 in Electronic Proceedings in Theoretical Computer Science, pages 23–57, 2017 [DOI]

    We introduce a ZX-like diagrammatic language devoted to manipulating real matrices (and rebits), with its own set of axioms. We prove the necessity of some non trivial axioms of these. We show that some restriction of the language is complete. We exhibit two interpretations to and from the ZX-Calculus, thus showing the consistency between the two languages. Finally, we derive from our work a way to extract the real or imaginary part of a ZX-diagram, and prove that a restriction of our language is complete if the equivalent restriction of the ZX-calculus is complete.

  13. Emmanuel Jeandel, Simon Perdrix, Renaud Vilmart, and Quanlong Wang. ZX-Calculus: Cyclotomic Supplementarity and Incompleteness for Clifford+T quantum mechanics. In Mathematical Foundations of Computer Science (MFCS), number 83 in LIPIcs, pages 11:1 – 11:13, 2017 [DOI][DL]

    The ZX-Calculus is a powerful graphical language for quantum mechanics and quantum information processing. The completeness of the language – i.e. the ability to derive any true equation – is a crucial question. In the quest of a complete ZX-calculus, supplementarity has been recently proved to be necessary for quantum diagram reasoning (MFCS 2016). Roughly speaking, supplementarity consists in merging two subdiagrams when they are parameterized by antipodal angles. We introduce a generalised supplementarity – called cyclotomic supplementarity – which consists in merging n subdiagrams at once, when the n angles divide the circle into equal parts. We show that when n is an odd prime number, the cyclotomic supplementarity cannot be derived, leading to a countable family of new axioms for diagrammatic quantum reasoning. We exhibit another new simple axiom that cannot be derived from the existing rules of the ZX-Calculus, implying in particular the incompleteness of the language for the so-called Clifford+T quantum mechanics. We end up with a new axiomatisation of an extended ZX-Calculus, including an axiom schema for the cyclotomic supplementarity.

  14. Emmanuel Jeandel. Computability in Symbolic Dynamics. In Computability in Europe (CiE), volume 9709 of Lecture Notes in Computer Science, pages 124–131, 2016 . Invited talk[DOI][DL]

    We give an overview of the interplay between computability and symbolic dynamics.

  15. Emmanuel Jeandel. Computability of the entropy of one-tape Turing machines. In Symposium on Theoretical Aspects of Computer Science (STACS), volume 25, pages 421–432, 2014 [DOI]

    We prove that the maximum speed and the entropy of a one-tape Turing machine are computable, in the sense that we can approximate them to any given precision . This is counterintuitive, as all dynamical properties are usually undecidable for Turing machines. The result is quite specific to one-tape Turing machines, as it is not true anymore for two-tape Turing machines by the results of Blondel et al., and uses the approach of crossing sequences introduced by Hennie.

  16. Emmanuel Jeandel and Pascal Vanier. Hardness of conjugacy and factorization of multidimensional subshifts of finite type. In Symposium on Theoretical Aspects of Computer Science (STACS), volume 20, pages 490–501, 2013 [DOI][DL]

    We investigate here the hardness of conjugacy and factorization of subshifts of finite type (SFTs) in dimension \(d>1\). In particular, we prove that the factorization problem is \(\Sigma^0_3\)-complete and the conjugacy problem \(\Sigma^0_1\)-complete in the arithmetical hierarchy.

  17. Emmanuel Jeandel. On Immortal configurations in Turing machines. In Computability in Europe (CiE), volume 7318 of Lecture Notes in Computer Science, pages 334–343, 2012 [DOI][DL]

    We investigate the immortality problem for Turing machines and prove that there exists a Turing Machine that is immortal but halts on every recursive configuration. The result is obtained by combining a new proof of Hooper’s theorem [11] with recent results on effective symbolic dynamics.

  18. Emmanuel Jeandel and Nicolas Rolin. Fixed Parameter Undecidability for Wang Tilesets. In Symposium on Cellular Automata (JAC), pages 69–85, 2012 [DOI]

    Deciding if a given set of Wang tiles admits a tiling of the plane is decidable if the number of Wang tiles (or the number of colors) is bounded, for a trivial reason, as there are only finitely many such tilesets. We prove however that the tiling problem remains undecidable if the difference between the number of tiles and the number of colors is bounded by 43. One of the main new tool is the concept of Wang bars, which are equivalently inflated Wang tiles or thin polyominoes.

  19. Emmanuel Jeandel and Pascal Vanier. \(\Pi_1^0\) sets and tilings. In Theory and Applications of Models of Computation (TAMC), volume 6648 of Lecture Notes in Computer Science, pages 230–239, 2011 [DOI][DL]

    In this paper, we prove that given any \(\Pi_1^0\) subset \(P\) of \(\{0,1\}^\mathbb{N}\) there is a tileset \(\tau\) with a set of configurations \(C\) such that \(P \times \mathbb{Z}^2\) is recursively homeomorphic to \(C\setminus U\) where \(U\) is a computable set of configurations. As a consequence, if \(P\) is countable, this tileset has the exact same set of Turing degrees.

  20. Alexis Ballier, Bruno Durand, and Emmanuel Jeandel. Tilings robust to errors. In Latin American Theoretical Informatics Symposium (LATIN), volume 6034 of Lecture Notes in Computer Science, pages 480–491. Springer, 2010 [DOI][DL]

    We study the error robustness of tilings of the plane. The fundamental question is the following: given a tileset, what happens if we allow a small probability of errors? Are the objects we obtain close to an error-free tiling of the plane? We prove that tilesets that produce only periodic tilings are robust to errors; for this proof, we use a hierarchical construction of islands of errors. We also show that another class of tilesets, those that admit countably many tilings is not robust and that there is no computable way to distinguish between these two classes.

  21. Alexis Ballier and Emmanuel Jeandel. Computing (or not) quasi-periodicity functions of tilings. In Symposium on Cellular Automata (JAC), pages 54–64, 2010 [DL]

    We know that tilesets that can tile the plane always admit a quasi-periodic tiling, yet they hold many uncomputable properties. The quasi-periodicity function is one way to measure the regularity of a quasi-periodic tiling. We prove that the tilings by a tileset that admits only quasi-periodic tilings have a recursively (and uniformly) bounded quasi-periodicity function. This corrects an error from [CervelleDurand2004] which stated the contrary. Instead we construct a tileset for which any quasi-periodic tiling has a quasi-periodicity function that cannot be recursively bounded. We provide such a construction for \(1-\)dimensional effective subshifts and obtain as a corollary the result for tilings of the plane via recent links between these objects.

  22. Emmanuel Jeandel and Pascal Vanier. Periodicity in Tilings. In Developments in Language Theory (DLT), volume 6224 of Lecture Notes in Computer Science, pages 243–254. Springer, 2010 [DOI][DL]

    Tilings and tiling systems are an abstract concept that arise both as a computational model and as a dynamical system. In this paper, we prove an analog of the theorems of Fagin [9] and Selman and Jones [14] by characterizing sets of periods of tiling systems by complexity classes.

  23. Emmanuel Jeandel and Pascal Vanier. Slopes of tilings. In Symposium on Cellular Automata (JAC), pages 145–155, 2010 [DL]

    We study here slopes of periodicity of tilings. A tiling is of slope \(\theta\) if it is periodic along direction \(\theta\) but has no other direction of periodicity.
    We characterize in this paper the set of slopes we can achieve with tilings, and prove they coincide with recursively enumerable sets of rationals.

  24. Emmanuel Jeandel and Guillaume Theyssier. Subshifts, Languages and Logic. In Developments in Language Theory (DLT), volume 5583 of Lecture Notes in Computer Science, pages 288–299. Springer, 2009 [DOI][DL]

    We study the Monadic Second Order (MSO) Hierarchy over infinite pictures, that is tilings. We give a characterization of existential MSO in terms of tilings and projections of tilings. Conversely, we characterise logic fragments corresponding to various classes of infinite pictures (subshifts of finite type, sofic subshifts).

  25. Alexis Ballier, Bruno Durand, and Emmanuel Jeandel. Structural Aspects of Tilings. In Symposium on Theoretical Aspects of Computer Science (STACS), pages 61–72. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2008 [DOI][DL]

    In this paper, we study the structure of the set of tilings produced by any given tile-set. For better understanding this structure, we address the set of finite patterns that each tiling contains. This set of patterns can be analyzed in two different contexts: the first one is combinatorial and the other topological. These two approaches have independent merits and, once combined, provide somehow surprising results. The particular case where the set of produced tilings is countable is deeply investigated while we prove that the uncountable case may have a completely different structure. We introduce a pattern preorder and also make use of Cantor-Bendixson rank. Our first main result is that a tile-set that produces only periodic tilings produces only a finite number of them. Our second main result exhibits a tiling with exactly one vector of periodicity in the countable case.

  26. Alexis Ballier and Emmanuel Jeandel. Tilings and Model Theory. In Symposium on Cellular Automata Journées Automates Cellulaires (JAC), pages 29–39, Moscow, 2008 . MCCME Publishing House[DL]

    In this paper we emphasize the links between model theory and tilings. More precisely, after giving the definitions of what tilings are, we give a natural way to have an interpretation of the tiling rules in first order logics. This opens the way to map some model theoretical properties onto some properties of sets of tilings, or tilings themselves.

  27. Emmanuel Jeandel. Topological Automata. In Symposium on Theoretical Aspects of Computer Science (STACS), volume 3404 of Lecture Notes in Computer Science, pages 389–398. Springer, 2005 [DOI][DL]

    We give here a new, topological, definition of automata that extends previous definitions of probabilistic and quantum automata. We then prove in an unified framework that deterministic or non-deterministic probabilistic and quantum automata recognise only regular languages with an isolated threshold.

  28. Emmanuel Jeandel. Universality in Quantum Computation. In International Colloquium on Automata, Languages and Programming (ICALP), volume 3142 of Lecture Notes in Computer Science, pages 793–804. Springer, 2004 [DOI][DL]

    " We introduce several new definitions of universality for sets of quantum gates, and prove separation results for these definitions. In particular, we prove that realisability with ancillas is different from the classical notion of completeness. We give a polynomial time algorithm of independent interest which decides if a subgroup of a classical group (\(SO_n\), \(SU_n\), \(SL_n\)) is Zariski dense, thus solving the decision problem for the completeness. We also present partial methods for the realisability with ancillas."

(Published) Posters

  1. Frederic Grosshans, Ruben Y. Cohen, Emmanuel Jeandel, and Simon Perdrix. Entanglement Distribution Across a Quantum Peer-to-Peer Network. In Quantum Information and Measurement (QIM), Optical Society of America Technical Digest, page QT6A.21, 2017 [DOI]

Research Reports

  1. Emmanuel Jeandel. Computability of the entropy of one-tape Turing Machines. Technical Report hal-00785232, Universite de Lorraine, 2013 [DL]

  2. Pierre Charbit, Emmanuel Jeandel, Pascal Koiran, Sylvain Perifel, and Stéphan Thomassé. Finding a Vector Orthogonal to Roughly Half a Collection of Vectors. Technical Report RR2006-05, LIP, ENS Lyon, January 2006[DL]

    Dimitri Grigoriev has shown that for any family of \(N\) vectors in the \(d\)-dimensional linear space \(E=(F_2^d)\), there exists a vector in \(E\) which is orthogonal to at least \(N/3\) and at most \(2N/3\) vectors of the family. We show that the range \([N/3,2N/3]\) can be replaced by the much smaller range \([N/2-\sqrt{N}/2,N/2+\sqrt{N}/2]\) and we give an efficient, deterministic parallel algorithm which finds a vector achieving this bound. The optimality of the bound is also investigated.

  3. Emmanuel Jeandel and Nicolas Ollinger. Playing with Conway’s Problem. Technical Report ccsd-00013788, Laboratoire d’informatique Fondamentale de Marseille, 2005 [DL]

    The centralizer of a language is the maximal language commuting with it. The question, raised by Conway in 1971, whether the centralizer of a rational language is always rational, recently received a lot of attention. In Kunc 2005, a strong negative answer to this problem was given by showing that even complete co-recursively enumerable centralizers exist for finite languages. Using a combinatorial game approach, we give here an incremental construction of rational languages embedding any recursive computation in their centralizers.

  4. Harm Derksen, Emmanuel Jeandel, and Pascal Koiran. Quantum automata and algebraic groups. Technical Report RR2003-39, LIP, ENS Lyon, July 2003[DL]

    We show that several problems which are known to be undecidable for probabilistic automata become decidable for quantum finite automata. Our main tool is an algebraic result of independent interest: we give an algorithm which, given a finite number of invertible matrices, computes the Zariski closure of the group generated by these matrices.

  5. Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, and Natacha Portier. Decidable and undecidable problems about quantum automata. Technical Report RR2003-24, LIP, ENS Lyon, April 2003[DL]

    We study the following decision problem: is the language recognized by a quantum finite automaton empty or non-empty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or non-strict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata for which it is known that strict and non-strict thresholds both lead to undecidable problems.

  6. Emmanuel Jeandel. Evaluation rapide de fonctions hypergeometriques. Technical Report RT-0242, INRIA - ENS Lyon, 2000 [DL]

    Nous presentons ici l’implantation des fonctions hypergeometriques dans la bibliotheque MPFR. Ceci a ete effectue a l’aide de la methode Binary Splitting. Un algorithme generique a donc ete cree, qui a permis l’amelioration de l’exponentielle, de certaines constantes, et l’implantation du sinus et du cosinus. Nous exposons l’algorithme pour le cas rationnel, puis nous montrons comment ce cas particulier permet d’obtenir l’exponentielle. Nous utilisons ensuite une methode similaire pour les autres fonctions. Les experiences montrent que la methode est plus efficace que celles employees precedemment dans MPFR.

Diploma Thesis

  1. Emmanuel Jeandel. Propriétés structurelles et calculatoires des pavages. Habilitation thesis, Université Montpellier 2, 2011 [DL]

  2. Emmanuel Jeandel. Techniques algébriques en calcul quantique. PhD thesis, ENS Lyon, 2005 [DL]

    Le principal problème étudié est le calcul de l’adhérence de Zariski de groupes algébriques, et leurs applications en calcul quantique. On donne ici un algorithme en temps polynomial qui décide si un sous-groupe finiment engendré d’un groupe reductif est dense dans ce groupe. On donne également un algorithme qui calcule précisément l’adhérence d’un groupe. Ces résultats sont utilisés afin de résoudre plusieurs problèmes en calcul quantique, en particulier liés aux circuits quantiques. Ainsi divers algorithmes qui décident si des jeux de portes sont universels, ou qui permettent de séparer les différentes notions d’universalité, sont donnés. Nous nous intéressons aussi ici aux automates finis. Nous introduisons ici un nouvel modèle, les automates topologiques, qui permet de généraliser les modèles existants. Nous montrons ainsi, dans un contexte unifié, que tous les modèles d’automates finis classiques, quantiques ou probabilistes ne reconnaissent que des langages rationnels par seuil isolé.

  3. Emmanuel Jeandel. Indecidabilite sur les automates quantiques. Master’s thesis, ENS Lyon, 2002 [DL]

    Apres avoir introduit les automates quantiques MO et MM, nous discuterons ici des principaux problemes de decision qui se posent. Alors que tous les problemes naturels que l’on peut se poser sont indecidables pour le modele stochastique, l’existence d’un mot accepte avec seuil strict par un automate quantique MO est montre decidable, par une methode mathematique basee sur quelques proprietes remarquables des groupes de Lie. Tous les autres problemes sont montres indecidables par reduction a la correspondance de Post, en utilisant un encodage des mots par des matrices unitaires. Nous decrirons enfin comment les differents modeles rencontres se simulent entre eux.