Ma 148a: Geometric and Categorical Information Theory
Fall 2021, Caltech Math Department, Monday-Wednesday-Friday 11:00 - 11:55 am, Room (to be assigned), Instructor:
Matilde Marcolli
(Regina Valluzzi, "Structure Evolution", ca 2010)
Brief Course Description
This class will present various ways in which geometry and physics
play a role in information theory. Topics will include information geometry;
algebraic and categorical structures of entropy; geometric aspects
of quantum information; methods of statistical physics in coding theory;
quantum field theory methods in the theory of computation.
Slides
Slides of classes will be added here: (more slides will be added)
Summary of Lectures
A brief summary of the material covered in each lecture will be posted here
- September 27: convex sets, convex bodies and their basic properties; categories, functors, and natural transformations; simplicial sets, nerves of categories
- September 29: simplicial and cubical sets, simplicies and probabilities, partial ordering, stochastic matrices, Perron-Frobenius, categories of finite probabilities
- October 1: probabilistic categories, zero objects and coproducts, statistical independence as product or coproduct, Shannon entropy and Khinchin axioms, Renyi entropy, Kullback-Leibler divergence, escort probabilities and statistical mechanics of Renyi entropy
- October 4: Renyi entropy and theremodynamics, Renyi dimensions, Tsallis entropy and q-analogs, combinatorial interpretation of the Shannon entropy, multinomial coefficients and q-analogs, geometric interpretation with flag varieties over finite fields, q-Bernoulli processes
- October 6: geometric processes in Grassmannian with underlying Bernoulli processes, q-analogs and the field with one element; extensivity fo entropy and functional equations, finite logarithm and entropy, cohomological interpretation, finite polylogarithms; categorical formulation of information loss
- October 8: KL divergence and Fisher-Rao metric, connections, Amari-Chentsov tensor, thermodynamical formulation, divergence functions and Bregman generators, Pythagorean relation of information geometry and optimization
- October 11 (Happy Indigenous Peoples Day!): Frobenius manifolds, F-manifolds and flat strctures, Frobenius manifolds in algebraic geometry, convex cones and F-manifolds from characteristic functions; Hochschild cohomology, Shannon higher mutual information and Hochschild cohomology, information structures, probability functors, modules category and Hochschild complex, cohomological information and Tsallis entropy, KL divergence.
- October 13: Kolmogorov complexity, conditional complexity, non-computability, complexity and Shannon entropy, Kraft inequality, Levin measure, Gell-Mann effective complexity, logical depth, depth and complexity, integrated information
- October 15: Classical and quantum information compared, complex projective geometry and pure states, structure of the convex space of density matrices
- October 18: entropy in quantum information, von Neumann entropy and relative entropy, Fisher metric and the Baker-Campbell-Hausdorff formula, quantum channels, categories of quantum information
- October 20: min-plus tropical semiring, convexity and Legendre transform, thermodynamic semirings, Khinchin axioms and algebraic properties, Maslov dequantization, Renyi and Tsallis semirings, KL divergence and multifractal decomposition of Cantor sets with Bernoulli measures
- October 22: hyperfields, successor function, cumulant generating function; operads, algebras over operads, operad of rooted trees, Ainfty operad of planar rooted trees, DG-operad, entropy operads, guessing trees and entropy functionals, entropy functionals and Ainfty operad, Witt rings and entropy in positive characteristic
- October 25: operads in quantum information, density matrices and compositions, projective quantum measurements, quantum entropy functionals and operad, Ainfty operad of quantum channels, non-unital operads, action on densities
- October 27: classical error-correcting codes, mutual information and channel capacity, code parameters, bounds in the space of code parameters, Shannon randon code ensemble and Gilbert-Vashramiv bound, asymptotic bound, spoiling operations on codes and asymptotic bound, relation to other bounds
- October 29: asymptotic bound and Kolmogorov complexity, oracle mediated construction, asymptotic bound as phase transition
- November 1: spherical codes and sphere packings, spherical codes and binary codes, code parameters, the asymptotic bound for spherical codes
- November 3: CRSS algorithm, quantum codes from classical, symplectic vector spaces over finite fields, symplectic quantization and the CRSS algorithm
- November 5: case of characteristic two; perfect tensors and tensor networks, role in AdS/CFT physics, entanglement entropy
- November 8: CRSS codes and rational noncommutative tori; Moufang loops and classical and quantum codes, almost symplectic spaces over finite fields
- November 10: Latin squares and Moufang loops, Latin squares and chamber systems and buildings, tensor networks and buildings
- November 12: probabilistic categories and information loss, Gamma spaces and spectra, cubical sets, information loss and probabilistic Gamma spaces
- November 15: quantum information and Gamma spaces, categories of Gapped quantum systems and Gamma spaces; mathematical theory of resources
- November 17: Gamma spaces on networks, summing functors and dynamics on networks, conservation laws, neural codes and information, categories for concurrent/distributed computing, categorical Hopfield dynamics
- November 19: renormalization and computation, overview of algebraic renormalization in QFT, computable and semi-computable functions and Hopf algebra of flow charts
- November 22: Dyson-Schwinger equations in Hopf algebras, operads, and properads, Birkhoff factorization of the halting problem
- November 24: no class today to allow everybody
safe Thanksgiving travel
- November 26: Thanksgiving hooliday, no class
- November 29: Rota-Baxter min-plus algebras and thermodynamic deformations and Birkhoff factorization
- December 1: graph hypersurfaces, polynomial countability, and families of mixed-Tate graphs
- December 3: anyon systems, fusion rings and modular tensor categories, categories of modules on noncommutative tori and anyons
Suggested readings: Books
The class has no official textbook, but there are some useful reference books
- M.Mezard, A.Montanari, "Information, physics and computation", Oxford
University Press, 2009.
- I.Bengtsson, K.Zyczkowski, "Geometry of quantum states", Cambridge
University Press, 2006.
- K.R. Parthasarathy, "Quantum Computation, quantum error
correcting codes and information theory", Narosa, 2006.
- Gilles Pisier, K. R. Parthasarathy, Vern Paulsen and Andreas Winter,
"The Functional Analysis of Quantum Information Theory", Springer 2015.
- S.Amari, H.Nagaoka, "Methods of Information Geometry" AMS and Oxford, 2000
Additional suggested readings: articles on material
covered in class
Additional reading material will be added as the class
progresses. Papers listed here refer to some of the
material that will be covered in class:
- Paolo Perrone, "Notes on Category Theory with examples from basic mathematics", arXiv:1912.10642
- Brendan Fong, David I Spivak, "Seven Sketches in Compositionality: An Invitation to Applied Category Theory", arXiv:1803.05316
- D.C.Brody, L.P.Hughston, "Geometric Quantum Mechanics", quant-ph/9906086
- Paolo Facchi, Ravi Kulkarni, V. I. Man'ko, Giuseppe Marmo, E. C. G. Sudarshan, Franco Ventriglia, "Classical
and Quantum Fisher Information in the Geometrical Formulation of Quantum Mechanics", arXiv:1009.5219
- Philippe Elbaz-Vincent, Herbert Gangl, Maxim Knotsevich, "On Poly(ana)logs I", arXiv:math/0008089
- Juan Pablo Vigneaux, "Information theory with finite vector spaces", arXiv:1807.05152
- Juan Pablo Vigneaux, "Generalized information structures and their cohomology", arXiv:1709.07807
- Pierre Badot, Daniel Bennequin, "The Homological Nature of Entropy", Entropy 2015, 17(5), 3253-3318
- John C. Baez, Tobias Fritz, Tom Leinster, "A Characterization of Entropy in Terms of Information Loss", arXiv:1106.1791
- Frank Nielsen, "An elementary introduction to information geometry",
arXiv:1808.08271
- Noemie C.Combe, Yuri I.Manin, "F-manifolds and geometry
of information", arXiv:2004.08808
- Claus Hertling, Yuri Manin, "Weak Frobenius manifolds", arXiv:math/9810132
- Noemie Combe, Yuri I. Manin, Matilde Marcolli, "Geometry of Information: classical and quantum aspects", arXiv:2107.08006
- Matilde Marcolli, "Gamma Spaces and Information", arXiv:1807.05314
- Yuri Manin, Matilde Marcolli, "Homotopy Theoretic and Categorical Models of Neural Information Networks", arXiv:2006.15136
- Greg Friedman,"An elementary illustrated introduction to simplicial sets", arXiv:0809.4221
- Matilde Marcolli, Ryan Thorngren, "Thermodynamic semirings",
arXiv:1108.2874
- Matilde Marcolli, Nicolas Tedeschi, "Entropy algebras and
Birkhoff factorization", arXiv:1412.0247
- Nihat Ay, Markus Mueller, Arleta Szkola, "Effective Complexity and its Relation to Logical Depth", arXiv:0810.5663
- Masafumi Oizumi, Naotsugu Tsuchiya, Shun-ichi Amari, "A unified framework for information integration based on information geometry", arXiv:1510.04455
- Yuri Manin, Matilde Marcolli, "Error-correcting codes
and phase transitions", arXiv:0910.5135
- Yuri Manin, Matilde Marcolli, "Kolmogorov complexity
and the asymptotic bound for error-correcting codes", arXiv:1203.0653
- Yuri Manin, "A computability challenge: asymptotic
bounds and isolated error-correcting codes",
arXiv:1107.4246
- Yuri Manin, "Complexity vs Energy: Theory of Computation and
Theoretical Physics", arXiv:1302.6695
- Yuri Manin, "Zipf's law and L. Levin's probability distributions",
arXiv:1301.0427
- Yuri I. Manin, Matilde Marcolli, "Asymptotic bounds for spherical codes", arXiv:1801.01552
- Noemie Combe, Yuri I. Manin, Matilde Marcolli, "Moufang Patterns and Geometry of Information", arXiv:2107.07486
- Matilde Marcolli, Christopher Perez, "Codes as fractals
and noncommutative spaces", arXiv:1107.5782
- Matilde Marcolli, John Napp, "Quantum computation and
real multiplication", arXiv:1312.3590
- Yuri Manin, "Renormalization and computation I:
motivation and background", arXiv:0904.4921,
- Yuri Manin, "Renormalization and Computation II:
Time Cut-off and the Halting Problem", arXiv:0908.3430.
- Colleen Delaney, Matilde Marcolli, "Dyson-Schwinger
equations in the theory of computation", arXiv:1302.5040
Suggested papers for student presentations:
(more material will be added here)
- John C. Baez, Mike Stay, "Physics, Topology, Logic and
Computation: A Rosetta Stone", arXiv:0903.0340
- Juan Pablo Vigneaux, "A homological characterization of generalized multinomial coefficients related to the entropic chain rule", arXiv:2003.02021
- Gy.Maksa, The general solution of a functional equation
related to the mixed theory of information, Aequationes
Mathematicae, Vol. 22 (1981), 90-96
pdf
- Philippe Elbaz-Vincent, Herbert Gangl, "Finite polylogarithms, their multiple analogues and the
Shannon entropy" pdf
- S. Amari, A. Chichoki, Information Geometry derived of
divergence functions, Bull. Polish Acad. Sci. Tech. Ser.,
Vol.58 (2010), No. 1, 183-195
pdf
- Yuri I. Manin, "F-manifolds with flat structure and Dubrovin's duality", arXiv:math/0402451
- Pierre Baudot, Monica Tapia, Daniel Bennequin, Jean-Marc Goaillard, "Topological Information Data Analysis", arXiv:1907.04242
- G. L. Litvinov, "The Maslov dequantization, idempotent and tropical mathematics: A brief introduction", arXiv:math/0507014
- Oleg Viro, "Dequantization of real algebraic geometry on logarithmic paper", arXiv:math/0005163
- A.Voronov, "The Ainfty operad and Ainfty algebras", pdf
- Frederic Chapoton, Muriel Livernet, "Pre-Lie algebras and the rooted trees operad", arXiv:math/0002069v2
- Martin Markl, "Operads and PROPs", arXiv:math/0601129
- Alain Connes, Caterina Consani, "Characteristic one, entropy and the absolute point", arXiv:0911.3537
- Oliver Lorscheid, "F1 for everyone", arXiv:1801.05337
- Young-Tak Oh, "q-deformation of Witt-Burnside rings", arXiv:math/0411353
- Henry Cohn, Yang Jiao, Abhinav Kumar, Salvatore Torquato, "Rigidity of spherical codes", arXiv:1102.5060
- A.R. Calderbank, E.M. Rains, P.W. Shor, N.J.A. Sloane, "Quantum Error Correction via Codes over GF(4)", arXiv:quant-ph/9608006
- A.R. Calderbank, E.M. Rains, P.W. Shor, N.J.A. Sloane, "Quantum Error Correction and orthogonal geometry", arXiv:quant-ph/9605005
- F. Pastawski, B. Yoshida, D. Harlow, and J. Preskill, "Holographic quantum error-correcting
codes: Toy models for the bulk/boundary correspondence", arXiv:1503.06237
- Matthew Heydeman, Matilde Marcolli, Sarthak Parikh, Ingmar Saberi, "Nonarchimedean Holographic Entropy from Networks of Perfect Tensors", arXiv:1812.04057
- Shamgar Gurevich, Ronny Hadani, "Quantization of symplectic vector spaces over finite fields", arXiv:0705.4556
- Shamgar Gurevich, Ronny Hadani, "The Weil Representation in Characteristic Two", arXiv:0808.1664
- Gunnar Carlsson, "Deloopings in algebraic K-theory" pdf
- Graeme Segal, "Categories and cohomology theories" pdf
- Bob Coecke, Tobias Fritz, Robert W. Spekkens, "A mathematical theory of resources", arXiv:1409.5531
- Tom Mainiero, "Homological Tools for the Quantum Mechanic", arXiv:1901.02011
- Yuri Manin, "Classical computing, quantum computing,
and Shor's factoring algorithm", arXiv:quant-ph/9903008
- S.Trebst, M.Troyer, Z.Wang, A.Ludwig, "A short introduction
to Fibonacci anyon models", arXiv:0902.3275
- Michael H. Freedman, Alexei Kitaev, Michael J. Larsen, Zhenghan Wang,
"Topological quantum computation", arXiv:quant-ph/0101025
- C.Nayak, S.Simon, A.Stern, M.Freedman, S.Sarma,
"Non-Abelian Anyons and Topological Quantum Computation", arXiv:0707.1889
- Eric Rowell, Richard Stong, Zhenghan Wang, "On classification of modular tensor categories", arXiv:0712.1377
- Colleen Delaney, Zhenghan Wang, "Symmetry defects and their application to topological quantum computing", arXiv:1811.02143
- Colleen Delaney, Eric C. Rowell, Zhenghan Wang, "Local unitary representations of the braid group and their applications to quantum computing", arXiv:1604.06429
- M.Redei, S.J.Summers, "Quantum Probability Theory", arXiv:quant-ph/0601158
- P.Jizba, "Information theory and generalized statistics"
pdf
- Bernard Field and Tapio Simula, "Introduction to topological quantum computation with non-Abelian anyons", Quantum Sci. Technol. 3 (2018) 045004
pdf
Syllabus
Requirements for the class: one oral
presentation on reading materials chosen from the list
provided above (first come first serve) and attendance
of (most) lectures.
Assigned student presentations:
The schedule of assigned persentations will be added here
- December 3: "A Mathematical Theory of Resources"
- December 3: "Classical computing, quantum computing, and Shor’s factoring algorithm"
- December 6: "Quantum Error and Orthogonal Geometry" and "Quantum Error Correction via Codes over GF(4)"
- December 6: "Sphere Packing and Quantum Gravity"
- December 6: "The Maslov dequantization, idempotent and tropical mathematics" and "Dequantization of real algebraic geometry on logarithmic paper" and "Quantum Information Theory and Free Semialgebraic Geometry"