More Web Proxy on the site http://driver.im/

research-article

Interacting Frobenius Algebras are Hopf

Authors:

Kevin DunneAuthors Info & Claims

LICS '16: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science

Pages 535 - 544

https://doi.org/10.1145/2933575.2934550

Published: 05 July 2016 Publication History

Abstract

Theories featuring the interaction between a Frobenius algebra and a Hopf algebra have recently appeared in several areas in computer science: concurrent programming, control theory, and quantum computing, among others. Bonchi, Sobocinski, and Zanasi [9] have shown that, given a suitable distribution law, a pair of Hopf algebras forms two Frobenius algebras. Here we take the opposite approach, and show that interacting Frobenius algebras form Hopf algebras. We generalise [9] by including non-trivial dynamics of the underlying object---the so-called phase group---and investigate the effects of finite dimensionality of the underlying model, and recover the system of Bonchi et al as a subtheory in the prime power dimensional case. However the more general theory does not arise from a distributive law.

References

[1]

Samson Abramsky and Bob Coecke. Categorical quantum mechanics. In Handbook of Quantum Logic and Quantum Structures, volume II. Elsevier, 2008, arXiv:0808.1023.

[2]

Nicolás Andruskiewitsch and Walter Ferrer Santos. The beginnings of the theory of Hopf algebras. Acta Applicandae Mathematicae, 108(1):3--17, 2009, arXiv:0901.2460.

[3]

Miriam Backens. The zx-calculus is complete for stabilizer quantum mechanics. New Journal of Physics, 16(9):093021, 2014, arXiv:1307.7025.

[4]

Miriam Backens. Making the stabilizer zx-calculus complete for scalars. In QPL 2015, 2015, arXiv:1507.03854.

[5]

Miriam Backens and Ali Nabi Duman. A complete graphical calculus for Spekkens' toy bit theory. Foundations of Physics, pages 1--34, 2015, arXiv:1411.1618.

[6]

John C. Baez and Jason Erbele. Categories in control. arXiv.org, (1405.6881), 2014, arXiv:1405.6881.

[7]

David B. Benson. The shuffle bialgebra. In Mathematical Foundations of Programming Language Semantics, volume 298 of LNCS, pages 616--637. Springer Berlin Heidelberg, 1988.

Digital Library

[8]

F. Bonchi, P. Sobociński, and F. Zanasi. Interacting bialgebras are Frobenius. In FoSSaCS '14, 2014.

[9]

F. Bonchi, P. Sobociński, and F. Zanasi. Interacting Hopf algebras. Technical report, arXiv:1403.7048, 2014.

[10]

Filippo Bonchi, Paweł Sobociński, and Fabio Zanasi. A categorical semantics of signal flow graphs. In CONCUR'14, 2014.

[11]

Roberto Bruni, Hernán Melgratti, and Ugo Montanari. A connector algebra for P/T nets interactions. In Proc. CONCUR 2011, volume 6901 of LNCS, pages 312--326. Springer Berlin Heidelberg, 2011.

Digital Library

[12]

Eugenia Cheng. Iterated distributive laws. Mathematical Proceedings of the Cambridge Philosophical Society, 150:459--487, 5 2011.

[13]

B. Coecke and R. Duncan. Interacting quantum observables. In Proc. ICALP 2008, volume 5126 of LNCS, pages 298--310. Springer, 2008.

Digital Library

[14]

B. Coecke and E. O. Paquette. POVMs and Naimark's theorem without sums. In Proceedings of the 4th International Workshop on Quantum Programming Languages, volume 210 of Electronic Notes in Theoretical Computer Science, pages 131--152, 2006, arXiv:quant-ph/0608072.

Digital Library

[15]

B. Coecke, D. Pavlovic, and J. Vicary. A new description of orthogonal bases. Math. Structures in Comp. Sci., 23(3):555--567, 2013, arxiv:0810.0812.

[16]

Bob Coecke and Ross Duncan. Interacting quantum observables: Categorical algebra and diagrammatics. New J. Phys, 13(043016), 2011, arXiv:0906.4725.

[17]

Bob Coecke, Ross Duncan, Aleks Kissinger, and Quanlong Wang. Strong complementarity and non-locality in categorical quantum mechanics. In Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science. (LiCS2012), pages 245--254. IEEE Computer Society Press, 2012, arXiv:1203.4988.

Digital Library

[18]

Ross Duncan and Maxime Lucas. Verifying the Steane code with Quantomatic. In Proc.QPL 2013, volume 171 of Electronic Proceedings in Theoretical Computer Science, pages 33--49, 2014, arXiv:1306.4532.

[19]

Ross Duncan and Simon Perdrix. Pivoting makes the zx-calculus complete for real stabilizers. In Proc. QPL 2013, volume 171 of Electronic Proceedings in Theoretical Computer Science, pages 50--62. Open Publishing Association, 2014, arXiv:1307.7048.

[20]

William Edwards. Non-locality in Categorical Quantum Mechanics. PhD thesis, Oxford University, 2009.

[21]

Bertfried Fauser. Some graphical aspects of Frobenius algebras. In Quantum Physics and Linguistics: A Compositional, Diagrammatic Discourse. Oxford, 2013, arXiv:1202.6380.

[22]

Stefano Gogioso and William Zeng. Fourier transforms from strongly complementary observables. Sumbitted to Applied Categorical Structures, 2015, arXiv:1501.04995.

[23]

G.M. Kelly and M.L. Laplaza. Coherence for compact closed categories. Journal of Pure and Applied Algebra, 19:193--213, 1980.

[24]

J. Kock. Frobenius Algebras and 2-D Topological Quantum Field Theories. Cambridge University Press, 2003.

[25]

Stephen Lack. Composing PROPs. Theory and Applications of Categories, 13(9):147--163, 2004, http://www.tac.mta.ca/tac/volumes/13/9/13-09abs.html.

[26]

S. Mimram. The structure of first-order causality. In Logic In Computer Science, 2009. LICS '09. 24th Annual IEEE Symposium on, pages 212-- 221, Aug 2009.

Digital Library

[27]

Simon Perdrix and Quanlong Wang. The ZX calculus is incomplete for Clifford+T quantum mechanics. arXiv.org, 2015, arXiv:1506.03055.

[28]

R. Rosebrugh, N. Sabadini, and R.F.C. Walters. Generic commutative separable algebras and cospans of graphs. Theory and Applications of Categories (Special Issue for CT2004), 15(6):164--177, 2005.

[29]

Mehrnoosh Sadrzadeh, Stephen Clark, and Bob Coecke. The Frobenius anatomy of word meanings i: subject and object relative pronouns. Journal of Logic and Computation, 23(6):1293--1317, 2013.

[30]

Mehrnoosh Sadrzadeh, Stephen Clark, and Bob Coecke. The Frobenius anatomy of word meanings ii: possessive relative pronouns. Journal of Logic and Computation, 2014.

[31]

P. Selinger. Autonomous categories in which A &cong; A*. In Proceedings of 7th Workshop on Quantum Physics and Logic (QPL 2010), 2010.

[32]

Peter Selinger. A survey of graphical languages for monoidal categories. In New structures for physics, volume 813 of Lecture Notes in Physics, pages 289--355. Springer, 2011, arXiv:0908.3347.

[33]

Paweł Sobociński. Nets, relations and linking diagrams. In Algebra and Coalgebra in Computer Science, volume 8089 of LNCS, pages 282--298. Springer Berlin Heidelberg, 2013.

[34]

R. Street. Quantum Groups: A Path to Current Algebra. Australian Mathematical Society Lecture Series. Cambridge University Press, 2007.

[35]

Moss E. Sweedler. Hopf Algebras. W. A. Benjamin Inc., 1969.

[36]

James Worthington. A bialgebraic approach to automata and formal language theory. In Logical Foundations of Computer Science, volume 5407 of LNCS, pages 451--467. Springer Berlin Heidelberg, 2009, arXiv:0807.4553.

Digital Library

Cited By

Roy Pvan de Wetering JYeh L(2023)The Qudit ZH-Calculus: Generalised Toffoli+Hadamard and UniversalityElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.384.9384(142-170)Online publication date: 30-Aug-2023
https://doi.org/10.4204/EPTCS.384.9
Comfort C(2021)The ZX&-calculus: A complete graphical calculus for classical circuits using spidersElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.340.4340(60-90)Online publication date: 6-Sep-2021
https://doi.org/10.4204/EPTCS.340.4
Carette TJeandel EPerdrix SVilmart R(2021)Completeness of Graphical Languages for Mixed State Quantum MechanicsACM Transactions on Quantum Computing10.1145/34646932:4(1-28)Online publication date: 21-Dec-2021
https://dl.acm.org/doi/10.1145/3464693
Show More Cited By

Index Terms

Interacting Frobenius Algebras are Hopf
1. Software and its engineering
  1. Software notations and tools
    1. Formal language definitions
2. Theory of computation

Recommendations

Coloured peak algebras and Hopf algebras

For G a finite abelian group, we study the properties of general equivalence relations on G _n = G ⁿ $${\mathfrak S}$$ _n, the wreath product of G with the symmetric group $${\mathfrak S}$$ _n, also known as the G -coloured symmetric group. We show that under ...
Infinitesimal Hopf Algebras and the cd-Index of Polytopes

Infinitesimal bialgebras were introduced by Joni and Rota [JR]. The basic theory of these objects was developed in [Aff1] and [Aff2]. In this paper we present a simple proof of the existence of the cd-index of polytopes, based on the theory of ...
Lattice congruences, fans and Hopf algebras

We give a unified explanation of the geometric and algebraic properties of two well-known maps, one from permutations to triangulations, and another from permutations to subsets. Furthermore we give a broad generalization of the maps. Specifically for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

LICS '16: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science

July 2016

901 pages

ISBN:9781450343916

DOI:10.1145/2933575

Conference Chair:
Eric Koskinen,
General Chair:
Martin Grohe,
Program Chair:
Natarajan Shankar

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGLOG: ACM Special Interest Group on Logic and Computation
EACSL: European Association for Computer Science Logic
IEEE-CS\DATC: IEEE Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Conference

LICS '16

Sponsor:

SIGLOG
EACSL
IEEE-CS\DATC

LICS '16: 31st Annual ACM/IEEE Symposium on Logic in Computer Science

July 5 - 8, 2016

NY, New York, USA

Acceptance Rates

Overall Acceptance Rate 215 of 622 submissions, 35%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
85
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)5

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Roy Pvan de Wetering JYeh L(2023)The Qudit ZH-Calculus: Generalised Toffoli+Hadamard and UniversalityElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.384.9384(142-170)Online publication date: 30-Aug-2023
https://doi.org/10.4204/EPTCS.384.9
Comfort C(2021)The ZX&-calculus: A complete graphical calculus for classical circuits using spidersElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.340.4340(60-90)Online publication date: 6-Sep-2021
https://doi.org/10.4204/EPTCS.340.4
Carette TJeandel EPerdrix SVilmart R(2021)Completeness of Graphical Languages for Mixed State Quantum MechanicsACM Transactions on Quantum Computing10.1145/34646932:4(1-28)Online publication date: 21-Dec-2021
https://dl.acm.org/doi/10.1145/3464693
Hadzihasanovic AGorla D(2021)The smash product of monoidal theoriesProceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science10.1109/LICS52264.2021.9470575(1-13)Online publication date: 29-Jun-2021
https://dl.acm.org/doi/10.1109/LICS52264.2021.9470575
Coecke BHorsman DKissinger AWang Q(2021)Kindergarden quantum mechanics graduates ...or how I learned to stop gluing LEGO together and love the ZX-calculusTheoretical Computer Science10.1016/j.tcs.2021.07.024Online publication date: Aug-2021
https://doi.org/10.1016/j.tcs.2021.07.024
Collins JDuncan R(2020)Hopf-Frobenius Algebras and a Simpler Drinfeld DoubleElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.318.10318(150-180)Online publication date: 1-May-2020
https://doi.org/10.4204/EPTCS.318.10
Vilmart RBouyer P(2019)A near-minimal axiomatisation of ZX-calculus for pure qubit quantum mechanicsProceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3470152.3470198(1-10)Online publication date: 24-Jun-2019
https://dl.acm.org/doi/10.5555/3470152.3470198
Jeandel EPerdrix SVilmart RBouyer P(2019)A generic normal form for ZX-diagrams and application to the rational angle completenessProceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3470152.3470196(1-10)Online publication date: 24-Jun-2019
https://dl.acm.org/doi/10.5555/3470152.3470196
Fagan ADuncan R(2019)Optimising Clifford Circuits with QuantomaticElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.287.5287(85-105)Online publication date: 31-Jan-2019
https://doi.org/10.4204/EPTCS.287.5
Vilmart R(2019)A Near-Minimal Axiomatisation of ZX-Calculus for Pure Qubit Quantum Mechanics2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)10.1109/LICS.2019.8785765(1-10)Online publication date: Jun-2019
https://doi.org/10.1109/LICS.2019.8785765
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten