License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.120
URN: urn:nbn:de:0030-drops-181726
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18172/
Carette, Titouan ;
Moutot, Etienne ;
Perez, Thomas ;
Vilmart, Renaud
Compositionality of Planar Perfect Matchings: A Universal and Complete Fragment of ZW-Calculus
Abstract
We exhibit a strong connection between the matchgate formalism introduced by Valiant and the ZW-calculus of Coecke and Kissinger. This connection provides a natural compositional framework for matchgate theory as well as a direct combinatorial interpretation of the diagrams of ZW-calculus through the perfect matchings of their underlying graphs.
We identify a precise fragment of ZW-calculus, the planar W-calculus, that we prove to be complete and universal for matchgates, that are linear maps satisfying the matchgate identities. Computing scalars of the planar W-calculus corresponds to counting perfect matchings of planar graphs, and so can be carried in polynomial time using the FKT algorithm, making the planar W-calculus an efficiently simulable fragment of the ZW-calculus, in a similar way that the Clifford fragment is for ZX-calculus. This work opens new directions for the investigation of the combinatorial properties of ZW-calculus as well as the study of perfect matching counting through compositional diagrammatical technics.
BibTeX - Entry
@InProceedings{carette_et_al:LIPIcs.ICALP.2023.120,
author = {Carette, Titouan and Moutot, Etienne and Perez, Thomas and Vilmart, Renaud},
title = {{Compositionality of Planar Perfect Matchings: A Universal and Complete Fragment of ZW-Calculus}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {120:1--120:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-278-5},
ISSN = {1868-8969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18172},
URN = {urn:nbn:de:0030-drops-181726},
doi = {10.4230/LIPIcs.ICALP.2023.120},
annote = {Keywords: Perfect Matchings Counting, Quantum Computing, Matchgates, ZW-Calculus, String Diagrams, Completeness}
}
|
Keywords: |
|
Perfect Matchings Counting, Quantum Computing, Matchgates, ZW-Calculus, String Diagrams, Completeness |
|
Collection: |
|
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
05.07.2023 |
