Compositionality of Planar Perfect Matchings: A Universal and Complete Fragment of ZW-Calculus

Autor:	Carette, Titouan, Moutot, Etienne, Perez, Thomas, Vilmart, Renaud
Jazyk:	angličtina
Rok vydání:	2023
Předmět:	Completeness Theory of computation → Quantum computation theory Mathematics of computing → Matchings and factors Theory of computation → Equational logic and rewriting Quantum Computing String Diagrams ZW-Calculus Perfect Matchings Counting Matchgates
DOI:	10.4230/lipics.icalp.2023.120
Popis:	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. LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 120:1-120:17
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::67b49775203b3780c680d5b1860cab55 Zobrazit plný text záznamu