Compositionality of planar perfect matchings
| Autor: | Carette, Titouan, Moutot, Etienne, Perez, Thomas, Vilmart, Renaud |
|---|---|
| Přispěvatelé: | University of Latvia (LU), Centre National de la Recherche Scientifique (CNRS), Institut de Mathématiques de Marseille (I2M), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon), Université de Lyon, Quantum Computation Structures (QuaCS), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Méthodes Formelles (LMF), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay), Laboratoire Méthodes Formelles (LMF), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay), ERDF project 1.1.1.5/18/A/020 'Quantum algorithms: from complexity theory to experiment', ANR-22-PETQ-0007,EPiQ,Etude de la pile quantique : Algorithmes, modèles de calcul et simulation pour l'informatique quantique(2022), ANR-22-CE47-0012,TaQC,Dompter la causalité quantique(2022) |
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| Předmět: |
Completeness
Quantum Physics [PHYS.QPHY]Physics [physics]/Quantum Physics [quant-ph] FOS: Physical sciences [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] Quantum Computing String Diagrams ZW-Calculus [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] Quantum Physics (quant-ph) Perfect Matchings Counting Matchgates |
| Zdroj: | 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), Jul 2023, Paderborn, Germany. pp.120:1--120:17, ⟨10.4230/LIPIcs.ICALP.2023.120⟩ |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|