A compositional approach to quantum functions. (English) Zbl 1395.05112
Summary: We introduce a notion of quantum function and develop a compositional framework for finite quantum set theory based on a 2-category of quantum sets and quantum functions. We use this framework to formulate a 2-categorical theory of quantum graphs, which captures the quantum graphs and quantum graph homomorphisms recently discovered in the study of nonlocal games and zero-error communication and relates them to quantum automorphism groups of graphs considered in the setting of compact quantum groups. We show that the 2-categories of quantum sets and quantum graphs are semisimple. We analyze dualisable and invertible 1-morphisms in these 2-categories and show that they correspond precisely to the existing notions of quantum isomorphism and classical isomorphism between sets and graphs.
MSC:
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 05C57 | Games on graphs (graph-theoretic aspects) |
| 05C15 | Coloring of graphs and hypergraphs |
| 91A43 | Games involving graphs |
| 17B37 | Quantum groups (quantized enveloping algebras) and related deformations |
| 81P99 | Foundations, quantum information and its processing, quantum axioms, and philosophy |
References:
| [1] | Brassard, G.; Broadbent, A.; Tapp, A., Quantum pseudo-telepathy, Found. Phys., 35, 1877-1907, (2005) · Zbl 1102.81302 · doi:10.1007/s10701-005-7353-4 |
| [2] | Mančinska, L.; Roberson, D. E., Quantum homomorphisms, J. Comb. Theory, Ser. B, 118, 228-267, (2016) · Zbl 1332.05098 · doi:10.1016/j.jctb.2015.12.009 |
| [3] | Wang, S., Quantum symmetry groups of finite spaces, Commun. Math. Phys., 195, 195-211, (1998) · Zbl 1013.17008 · doi:10.1007/s002200050385 |
| [4] | Woronowicz, S. L., Compact quantum groups, Symétries Quantiques, 845-884, (1998), Les Houches: North-Holland, Les Houches: Les Houches: North-Holland, Les Houches, Amsterdam · Zbl 0997.46045 |
| [5] | Banica, T., Quantum automorphism groups of homogeneous graphs, J. Funct. Anal., 224, 243-280, (2005) · Zbl 1088.46040 · doi:10.1016/j.jfa.2004.11.002 |
| [6] | Atserias, A.; Mančinska, L.; Roberson, D. E.; Šámal, R.; Severini, S.; Varvitsiotis, A., Quantum and non-signalling graph isomorphisms, (2016) |
| [7] | Duan, R.; Severini, S.; Winter, A., Zero-error communication via quantum channels, noncommutative graphs, and a quantum Lovász number, IEEE Trans. Inf. Theory, 59, 1164-1174, (2013) · Zbl 1364.81059 · doi:10.1109/tit.2012.2221677 |
| [8] | Weaver, N., Quantum graphs as quantum relations, (2015) |
| [9] | Musto, B.; Reutter, D.; Verdon, D., The Morita theory of quantum graph isomorphisms, Commun. Math. Phys. · Zbl 1405.05119 |
| [10] | Eckmann, B.; Hilton, P. J., Group-like structures in general categories. I. Multiplications and comultiplications, Math. Ann., 145, 227-255, (1962) · Zbl 0099.02101 · doi:10.1007/bf01451367 |
| [11] | Stahlke, D., Quantum zero-error source-channel coding and non-commutative graph theory, IEEE Trans. Inf. Theory, 62, 554-577, (2016) · Zbl 1359.94454 · doi:10.1109/tit.2015.2496377 |
| [12] | Kuperberg, G.; Weaver, N., A von Neumann Algebra Approach to Quantum Metrics/Quantum Relations, (2012), American Mathematical Society |
| [13] | Bichon, J., Quantum automorphism groups of finite graphs, Proc. Am. Math. Soc., 131, 665-673, (2003) · Zbl 1013.16032 · doi:10.1090/s0002-9939-02-06798-9 |
| [14] | Weaver, N., Quantum relations, (2010) |
| [15] | Banica, T.; Bichon, J.; Collins, B., Quantum permutation groups: A survey, Noncommutative Harmonic Analysis with Applications to Probability, (2007), Institute of Mathematics Polish Academy of Sciences |
| [16] | Banica, T.; Bichon, J., Quantum automorphism groups of vertex-transitive graphs of order ≤11, J. Algebraic Combinatorics, 26, 83-105, (2007) · Zbl 1125.05049 · doi:10.1007/s10801-006-0049-9 |
| [17] | Banica, T.; Bichon, J., Quantum groups acting on 4 points, J. Reine Angew. Math. (Crelles J.), 2009, 75-114 · Zbl 1187.46058 · doi:10.1515/crelle.2009.003 |
| [18] | Banica, T.; Bichon, J.; Chenevier, G., Graphs having no quantum symmetry, Ann. Inst. Fourier, 57, 955-971, (2007) · Zbl 1178.05047 · doi:10.5802/aif.2282 |
| [19] | Sołtan, P. M., Quantum families of maps and quantum semigroups on finite quantum spaces, J. Geom. Phys., 59, 354-368, (2009) · Zbl 1160.58007 · doi:10.1016/j.geomphys.2008.11.007 |
| [20] | Neshveyev, S.; Tuset, L., Compact Quantum Groups and Their Representation Categories, Collection SMF: Cours Spécialisés, (2013), American Mathematical Society · Zbl 1316.46003 |
| [21] | Kornell, A., Quantum functions, (2011) |
| [22] | Kornell, A., Quantum sets, (2018) |
| [23] | Cameron, P. J.; Montanaro, A.; Newman, M. W.; Severini, S.; Winter, A., On the quantum chromatic number of a graph, Electron. J. Combinatorics, 14, R81, (2007) · Zbl 1182.05054 |
| [24] | Scarpa, G.; Severini, S., Kochen-Specker sets and the rank-1 quantum chromatic number, IEEE Trans. Inf. Theory, 58, 2524-2529, (2012) · Zbl 1365.05100 · doi:10.1109/tit.2011.2178018 |
| [25] | Avis, D.; Hasegawa, J.; Kikuchi, Y.; Sasaki, Y., A quantum protocol to win the graph colouring game on all Hadamard graphs, IEICE Trans. Fundam. Electron., Commun. Comput. Sci., 89, 1378-1381, (2006) · doi:10.1093/ietfec/e89-a.5.1378 |
| [26] | Paulsen, V. I.; Todorov, I. G., Quantum chromatic numbers via operator systems, Q. J. Math., 66, 677-692, (2015) · Zbl 1314.05078 · doi:10.1093/qmath/hav004 |
| [27] | Paulsen, V. I.; Severini, S.; Stahlke, D.; Todorov, I. G.; Winter, A., Estimating quantum chromatic numbers, J. Funct. Anal., 270, 2188-2222, (2016) · Zbl 1353.46043 · doi:10.1016/j.jfa.2016.01.010 |
| [28] | Roberson, D. E., Conic formulations of graph homomorphisms, J. Algebraic Combinatorics, 43, 877-913, (2016) · Zbl 1339.05401 · doi:10.1007/s10801-016-0665-y |
| [29] | Ortiz, C. M.; Paulsen, V. I., Quantum graph homomorphisms via operator systems, Linear Algebra Appl., 497, 23-43, (2016) · Zbl 1353.46041 · doi:10.1016/j.laa.2016.02.019 |
| [30] | Abramsky, S.; Coecke, B., Categorical quantum mechanics, Handbook of Quantum Logic and Quantum Structures: Quantum Logic, 261-324, (2008), Elsevier |
| [31] | Coecke, B.; Duncan, R., Interacting quantum observables, Automata, Languages and Programming, 298-310, (2008), Springer Science + Business Media · Zbl 1155.81316 |
| [32] | Coecke, B.; Pavlović, D.; Chen, G.; Kauffman, L.; Lomonaco, S. J., Quantum measurements without sums, Mathematics of Quantum Computation and Quantum Technology, 559-596, (2007), Chapman and Hall/CRC |
| [33] | Coecke, B.; Pavlović, D.; Vicary, J., A new description of orthogonal bases, 555-567, (2009), Cambridge University Press · Zbl 1276.46016 |
| [34] | Vicary, J., Categorical formulation of finite-dimensional quantum algebras, Commun. Math. Phys., 304, 765-796, (2010) · Zbl 1221.81146 · doi:10.1007/s00220-010-1138-0 |
| [35] | Coecke, B.; Heunen, C.; Kissinger, A., Categories of quantum and classical channels, Quantum Inf. Process., 15, 5179, (2014) · Zbl 1357.81039 · doi:10.1007/s11128-014-0837-4 |
| [36] | Vicary, J., Higher quantum theory, (2012) |
| [37] | Vicary, J., Higher semantics of quantum protocols, (2012), Institute of Electrical & Electronics Engineers (IEEE) · Zbl 1364.81084 |
| [38] | Reutter, D.; Vicary, J., Biunitary constructions in quantum information, (2016) |
| [39] | Street, R., The formal theory of monads, J. Pure Appl. Algebra, 2, 149-168, (1972) · Zbl 0241.18003 · doi:10.1016/0022-4049(72)90019-9 |
| [40] | Marsden, D., Category theory using string diagrams, (2014) |
| [41] | Hinze, R.; Marsden, D., Equational reasoning with lollipops, forks, cups, caps, snakes, and speedometers, J. Logical Algebraic Methods Program., 85, 931-951, (2016) · Zbl 1375.18027 · doi:10.1016/j.jlamp.2015.12.004 |
| [42] | Abramsky, S.; Barbosa, R. S.; de Silva, N.; Zapata, O., The quantum monad on relational structures |
| [43] | Selinger, P., A survey of graphical languages for monoidal categories, New Structures for Physics, 289-355, (2010), Springer: Springer, Berlin, Heidelberg · Zbl 1217.18002 |
| [44] | Borceux, F., Handbook of Categorical Algebra, Encyclopedia of Mathematics and its Applications, (1994), Cambridge University Press · Zbl 0803.18001 |
| [45] | Heunen, C.; Karvonen, M., Monads on dagger categories, Theory Appl. Categories, 31, 1016-1043, (2016) · Zbl 1378.18003 |
| [46] | Joyal, A.; Street, R., The geometry of tensor calculus. I, Adv. Math., 88, 55-112, (1991) · Zbl 0738.18005 · doi:10.1016/0001-8708(91)90003-p |
| [47] | Joyal, A.; Street, R., The geometry of tensor calculus. II, (1991) · Zbl 0738.18005 |
| [48] | Coecke, B., Quantum picturalism, Contemp. Phys., 51, 59-83, (2010) · doi:10.1080/00107510903257624 |
| [49] | Kelly, G., Many-variable functorial calculus. I, Coherence in Categories, 66-105, (1972), Springer · Zbl 0243.18015 |
| [50] | Kelly, G.; Laplaza, M., Coherence for compact closed categories, J. Pure Appl. Algebra, 19, 193-213, (1980) · Zbl 0447.18005 · doi:10.1016/0022-4049(80)90101-2 |
| [51] | Abramsky, S.; Coecke, B., A categorical semantics of quantum protocols, 415-425, (2004), IEEE |
| [52] | Selinger, P., Dagger compact closed categories and completely positive maps, Electron. Notes Theor. Comput. Sci., 170, 139-163, (2007) · Zbl 1277.18008 · doi:10.1016/j.entcs.2006.12.018 |
| [53] | Adámek, J.; Herrlich, H.; Strecker, G. E., Abstract and Concrete Categories: The Joy of Cats, (1990), John Wiley and Sons · Zbl 0695.18001 |
| [54] | Freyd, P., Homotopy is not concrete, The Steenrod Algebra and its Applications: A Conference to Celebrate NE Steenrod’s Sixtieth Birthday, 25-34, (1970), Springer · Zbl 0212.55801 |
| [55] | Joyal, A.; Street, R., An introduction to Tannaka duality and quantum groups, Lecture Notes in Mathematics, 413-492, (1991), Springer Berlin Heidelberg · Zbl 0745.57001 |
| [56] | Maes, A.; Van Daele, A., Notes on compact quantum groups, Nieuw Archief voor Wiskunde, 4, 73-112, (1998) · Zbl 0962.46054 |
| [57] | Musto, B.; Vicary, J., Quantum Latin squares and unitary error bases, Quantum Inf. Comput., 16, 1318-1332, (2015) |
| [58] | Musto, B., Constructing mutually unbiased bases from quantum Latin squares, Electron. Proc. Theor. Comput. Sci., 236, 108-126, (2017) · Zbl 1486.81055 · doi:10.4204/eptcs.236.8 |
| [59] | Werner, R. F., All teleportation and dense coding schemes, J. Phys. A: Math. Gen., 34, 7081, (2001) · Zbl 1024.81006 · doi:10.1088/0305-4470/34/35/332 |
| [60] | Müger, M., Abstract duality theory for symmetric tensor *-categories, Philosophy of Physics, 865-922, (2007), Elsevier |
| [61] | Etingof, P.; Gelaki, S.; Nikshych, D.; Ostrik, V., Tensor Categories, (2015), American Mathematical Society · Zbl 1365.18001 |
| [62] | Müger, M., From subfactors to categories and topology. I. Frobenius algebras in and Morita equivalence of tensor categories, J. Pure Appl. Algebra, 180, 81-157, (2003) · Zbl 1033.18002 · doi:10.1016/s0022-4049(02)00247-5 |
| [63] | Müger, M.; Roberts, J. E.; Tuset, L., Representations of algebraic quantum groups and reconstruction theorems for tensor categories, Algebras Representation Theory, 7, 517-573, (2004) · Zbl 1098.17012 · doi:10.1023/b:alge.0000048337.34810.6f |
| [64] | Vicary, J., Completeness of †-categories and the complex numbers, J. Math. Phys., 52, 082104, (2011) · Zbl 1272.81013 · doi:10.1063/1.3549117 |
| [65] | Selinger, P., Idempotents in dagger categories, Electron. Notes Theor. Comput. Sci., 210, 107-122, (2008) · Zbl 1279.18006 · doi:10.1016/j.entcs.2008.04.021 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
