Search Results

Documents authored by Jeandel, Emmanuel

Document
DOI: 10.4230/LIPIcs.FSCD.2022.13
Addition and Differentiation of ZX-Diagrams

Authors: Emmanuel Jeandel, Simon Perdrix, and Margarita Veshchezerova

Published in: LIPIcs, Volume 228, 7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022)

Abstract
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.
Cite as

Emmanuel Jeandel, Simon Perdrix, and Margarita Veshchezerova. Addition and Differentiation of ZX-Diagrams. In 7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 228, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{jeandel_et_al:LIPIcs.FSCD.2022.13,
  author =	{Jeandel, Emmanuel and Perdrix, Simon and Veshchezerova, Margarita},
  title =	{{Addition and Differentiation of ZX-Diagrams}},
  booktitle =	{7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-233-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{228},
  editor =	{Felty, Amy P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2022.13},
  URN =		{urn:nbn:de:0030-drops-162946},
  doi =		{10.4230/LIPIcs.FSCD.2022.13},
  annote =	{Keywords: ZX calculus, Addition of ZX diagrams, Diagrammatic differentiation}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2020.118
A Recipe for Quantum Graphical Languages

Authors: Titouan Carette and Emmanuel Jeandel

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
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.
Cite as

Titouan Carette and Emmanuel Jeandel. A Recipe for Quantum Graphical Languages. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 118:1-118:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{carette_et_al:LIPIcs.ICALP.2020.118,
  author =	{Carette, Titouan and Jeandel, Emmanuel},
  title =	{{A Recipe for Quantum Graphical Languages}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{118:1--118:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.118},
  URN =		{urn:nbn:de:0030-drops-125250},
  doi =		{10.4230/LIPIcs.ICALP.2020.118},
  annote =	{Keywords: Categorical Quantum Mechanics, Quantum Computing, Category Theory}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2019.108
Completeness of Graphical Languages for Mixed States Quantum Mechanics (Track B: Automata, Logic, Semantics, and Theory of Programming)

Authors: Titouan Carette, Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
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 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 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 the Clifford+T quantum mechanics, as the category does not have enough isometries.
Cite as

Titouan Carette, Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. Completeness of Graphical Languages for Mixed States Quantum Mechanics (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 108:1-108:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{carette_et_al:LIPIcs.ICALP.2019.108,
  author =	{Carette, Titouan and Jeandel, Emmanuel and Perdrix, Simon and Vilmart, Renaud},
  title =	{{Completeness of Graphical Languages for Mixed States Quantum Mechanics}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{108:1--108:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.108},
  URN =		{urn:nbn:de:0030-drops-106844},
  doi =		{10.4230/LIPIcs.ICALP.2019.108},
  annote =	{Keywords: Quantum Computing, Quantum Categorical Mechanics, Category Theory, Mixed States, Completely Positive Maps}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.40
A Characterization of Subshifts with Computable Language

Authors: Emmanuel Jeandel and Pascal Vanier

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
Subshifts are sets of colorings of 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.
Cite as

Emmanuel Jeandel and Pascal Vanier. A Characterization of Subshifts with Computable Language. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jeandel_et_al:LIPIcs.STACS.2019.40,
  author =	{Jeandel, Emmanuel and Vanier, Pascal},
  title =	{{A Characterization of Subshifts with Computable Language}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{40:1--40:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.40},
  URN =		{urn:nbn:de:0030-drops-102798},
  doi =		{10.4230/LIPIcs.STACS.2019.40},
  annote =	{Keywords: subshifts, computability, Enumeration degree, Turing degree, minimal subshifts}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.11
ZX-Calculus: Cyclotomic Supplementarity and Incompleteness for Clifford+T Quantum Mechanics

Authors: Emmanuel Jeandel, Simon Perdrix, Renaud Vilmart, and Quanlong Wang

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
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.
Cite as

Emmanuel Jeandel, Simon Perdrix, Renaud Vilmart, and Quanlong Wang. ZX-Calculus: Cyclotomic Supplementarity and Incompleteness for Clifford+T Quantum Mechanics. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jeandel_et_al:LIPIcs.MFCS.2017.11,
  author =	{Jeandel, Emmanuel and Perdrix, Simon and Vilmart, Renaud and Wang, Quanlong},
  title =	{{ZX-Calculus: Cyclotomic Supplementarity and Incompleteness for Clifford+T Quantum Mechanics}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.11},
  URN =		{urn:nbn:de:0030-drops-81173},
  doi =		{10.4230/LIPIcs.MFCS.2017.11},
  annote =	{Keywords: Categorical Quantum Mechanincs, ZX-Calculus, Completeness, Cyclotomic Supplmentarity, Clifford+T}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.421
Computability of the entropy of one-tape Turing machines

Authors: Emmanuel Jeandel

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
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.
Cite as

Emmanuel Jeandel. Computability of the entropy of one-tape Turing machines. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 421-432, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{jeandel:LIPIcs.STACS.2014.421,
  author =	{Jeandel, Emmanuel},
  title =	{{Computability of the entropy of one-tape Turing machines}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{421--432},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.421},
  URN =		{urn:nbn:de:0030-drops-44767},
  doi =		{10.4230/LIPIcs.STACS.2014.421},
  annote =	{Keywords: Turing Machines, Dynamical Systems, Entropy, Crossing Sequences, Automata}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.490
Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type

Authors: Emmanuel Jeandel and Pascal Vanier

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
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 of finite type (SFTs) in dimension d > 1. In particular, we prove that the factorization problem is Sigma^0_3-complete and that the conjugacy and embedding problems are Sigma^0_1-complete in the arithmetical hierarchy.
Cite as

Emmanuel Jeandel and Pascal Vanier. Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 490-501, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{jeandel_et_al:LIPIcs.STACS.2013.490,
  author =	{Jeandel, Emmanuel and Vanier, Pascal},
  title =	{{Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{490--501},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.490},
  URN =		{urn:nbn:de:0030-drops-39592},
  doi =		{10.4230/LIPIcs.STACS.2013.490},
  annote =	{Keywords: Subshifts, Computability, Factorization, Embedding, Conjugacy}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact