Ma 148 a: The Geometry and Physics of Information Theory

Brief Course Description

Possible topics include

• Algebraic structures based on entropy functions and their relation to Maslov dequantization, toric varieties and mirror symmetry
• Noncommutative geometry methods in coding theory
• Renormalization and computation
• Dynamical entropy for operator algebras

Textbooks (suggested reading)

• I.Bengtsson, K.Zyczkowski, "Geometry of quantum states", Cambridge University Press, 2006.
• M.Mezard, A.Montanari, "Information, physics and computation", Oxford University Press, 2009.
• S.Neshveyev, E.Stormer, "Dynamical entropy in operator algebras", Springer, 2006.
• K.R. Parthasarathy, "Quantum Computation, quantum error correcting codes and information theory", Narosa, 2006.
• E.Rieffel, W.Polak, "Quantum computing: a gentle introduction", MIT Press, 2011.

Additional suggested readings

• John C. Baez, Mike Stay, "Physics, Topology, Logic and Computation: A Rosetta Stone", arXiv:0903.0340
• John C. Baez, Tobias Fritz, Tom Leinster, "A characterization of entropy in terms of information loss", arXiv:1106.1791.
• Michael H. Freedman, Alexei Kitaev, Michael J. Larsen, Zhenghan Wang, "Topological quantum computation", arXiv:quant-ph/0101025
• Tobias Fritz, "Convex Spaces I: Definition and Examples", arXiv:0903.5522, and "A presentation of the category of stochastic matrices", arXiv:0902.2554.
• Mikhail Kapranov, "Thermodynamics and the moment map", arXiv:1108.3472.
• Yuri Manin, "A computability challenge: asymptotic bounds and isolated error-correcting codes", arXiv:1107.4246.
• Hiroki Suyari "Generalization of Shannon-Khinchin axioms to nonextensive systems and the uniqueness theorem", arXiv:math-ph/0205004.
• I. Itenberg and G. Mikhalkin, "Geometry in tropical limit", ArXiv: 1108.3111v2.
• Gilles de Castro, Artur Lopes, "KMS states, entropy and a variational principle for pressure", arXiv:0812.4222.
• Mario Berta, Fabian Furrer, Volkher Scholz, "The smooth entropy formalism on von Neumann algebras", arXiv+1107.5460.
• Joseph Ben Geloun, Cecilia Flori, "Topos Analogues of the KMS State", arXiv:1207.0227.

• Yuri Manin, "Classical computing, quantum computing, and Shor's factoring algorithm", arXiv:quant-ph/9903008.
• Yuri Manin, Matilde Marcolli, "Kolmogorov complexity and the asymptotic bound for error-correcting codes", arXiv:1203.0653
• Yuri Manin, Matilde Marcolli, "Error-correcting codes and phase transitions", arXiv:0910.5135
• Matilde Marcolli, Christopher Perez, "Codes as fractals and noncommutative spaces", arXiv:1107.5782
• Matilde Marcolli, Ryan Thorngren, "Thermodynamic semirings", arXiv:1108.2874
• Yuri Manin, "Renormalization and computation I: motivation and background", arXiv:0904.4921, and "Renormalization and Computation II: Time Cut-off and the Halting Problem", arXiv:0908.3430.
• Noson Yanofsky, "Galois theory of algorithms", arXiv:1011.0014.

Notes of classes

• October 1: Introduction: Physics, Geometry and Information Theory; Convexity: geometry of convex bodies, the space of colors, metrics, convex sets and statistics.
• October 3: Probability distributions and simplexes, stochastic matrices, Perron-Frobenius theory, Shannon entropy.
• October 5: Kullback-Leibler divergence; Fisher-Rao metric; generalizations of Shannon entropy: Renyi and Tsallis entropies.
• October 8: Khinchin axioms for Shannon entropy; Fisher-Rao metric and spherical geometry; mixture and exponential geodesics.
• October 10: Classical error-correcting codes; code parameters and optimization; spoiling operations on codes; the asymptotic bound for error-correcting codes: existence and properties.
• October 12: finite and infinite multiplicities of code parameters; the singleton bound; q-ary entropy; the Hamming bound; the Gilbert-Varshamov bound.
• October 15: The Shannon Random Code Ensemble, average distance enumerator function, exponential scarcity/concentration of code words and the GV curve; the statistical mechanics of transmission errors.
• October 17: Kolmogorov complexity versus Shannon entropy; partial recursive functions, enumerable families, constructive worlds, Kolmogorov complexity; Kolmogorov ordering; an oracle mediated construction of finite and infinite multiplicity codes.
• October 19: Partition functions, Kolmogorov complexity, and the asymptotic bound as a phase transition; quantum statistical mechanical systems of single codes and code space, Toeplitz algebras, quantum and classical partition functions.
• October 22: Operator algebra based quantum statistical mechanics, evolution, partition function and equilibrium states; tensor product of Toeplitz algebras and a QSM system for codes space; the asymptotic bound as a separation between quantum mechanical systems (isolated codes region) and bosonic second quantization (limit points region).
• October 24: classical versus quantum probability: sample/state space; events; observables; probability distributions and states; expectation values; variance; extremal states (pure states); product space (independent systems); dynamics: Heisenberg and Schroedinger picture.
• October 26: finite dimensional quantum mechanics as complex projective geometry; complex projective spaces, linear subspaces, curves (quadrics in P2, twisted cubics in P3), tensor product of state spaces and Segre embeddings of projective spaces, case of P1xP1 (quadric surface, ruling), Pn as symmetric products of P1, spinor coordinates and multispinors, Fubini-Study metric, isometries, Killing flow and Schroedinger equation.
• October 29: density matrices, pure states and complex projective spaces, time evolution, expectation values, Bloch sphere and hermitian matrices, Bloch vectors and Bloch ball, Bhattacharyya distance and Fubini-Study metric, space of density matrices, Hilbert-Schmidt distance.
• October 31: Weyl chamber and stratification of the space of density matrices by flag manifolds and simplexes; von Neumann entropy; operator-monotone and operator-convex functions; means of operators (arithmetic, geometric, harmonic); convex trace functions; Klein inequality and Peierl inequality; von Neumann entropy and Shannon entropy; decompositions into pure states; extensivity, concavity and subadditivity of the von Neumann entropy.
• November 2: Relative entropy in quantum probability; relative entropy in terms of Bloch vectors; positive and completely positive maps; measurement postulate; positive operator valued measurements; projective measurements; trace preserving completely postive maps and Kraus representation; quantum channel; entropy of a quantum channel.
• November 5: quantum gates, one q-bit gates (Pauli, Hadamard, phase, pi/8 gates), rotation gates; two q-bits gates (controlled NOT, swap); examples of 3-qbits gates and decompositions; quantum teleportation and quantum communication; generalization to finite abelian groups and Weyl operators.
• November 7: Decomposition of quantum gates in terms of single q-bit gates and CNOT; quantum Fourier transform; quantum error correcting codes
• November 9: recovery operators and equivalent formulations of quantum error-correcting codes; examples from finite groups; error operators of given strength and basis in terms of Weyl operators
• November 12: The CSS algorithm relating classical self-orthogonal q-ary codes and q-ary quantum stabilizer codes
• November 14: The CSS algorithm and the geometry of rational noncommutative tori
• November 16: Models of classical and quantum computation: Boolean polynomials and logical gates, least period and search problems, from classical to quantum algorithms, Shor's factorization algorithm
• November 19: Thermodynamic Semirings: axioms for entropy functions and algebraic properties of semirings, entropy operads (guest lecture by Ryan Thorngren)
• November 21: no class today
• November 26: decorated graphs, graphs and algorithms, recursive functions: basic generators and elementary operations; marked trees as programs computing recursive functions; cuts; graded Hopf algebra of flowcharts.
• November 28: The algebraic formulation of renormalization in quantum field theory: unrenormalized Feynman amplitudes and Feynman graphs; regularization of Feynman amplitudes; Rota-Baxter algebras of weight -1
• November 30: Commutative Hopf algebras and affine group schemes, Birkhoff factorization of algebra homomorphisms from commutative Hopf algebras to Rota-Baxter algebras of weight -1, BPHZ renormalization in quantum field theory.
• December 3: Regularization and renormalization of partial recursive functions: permutations and associated meromorphic functions, permutations with bounded shift and Kolmogorov ordering, renormalization by Birkhoff decomposition.
• December 5: Galois theory of algorithms: programs, algorithms and recursive functions; relations among programs; automorphisms, subgroups and "Galois correspondence".
• December 7: The insertion Lie algebra of Feynman graphs; graph languages and graph grammars; node replacement and edge replacement; context-free graph languages; graph grammars, gluing and connecting rules; graph grammars and Lie algebras.

Policy

Seminars

• October 3: Colleen Delaney, "Dyson-Schwinger equations in the theory of computation"
• October 17: Victor Kasatkin, "Does quantum entanglement aid information transfer?"
• October 17: Tanvir Bhuyain, "Entropy as information loss"
• October 24: Branimir Cacic, "Information geometry and equilibrium states"
• October 31: Du Pei, "Topological quantum computing"
• November 7: Christopher Estrada, "Tropical geometry, dequantization and the zero-temperature limit in thermodynamics"
• November 14: Gjergji Zaimi, "Thermodynamics and moment map"
• November 28: Mark Greenfield, "Stochastics matrices: a categorical view"
• November 28: Tristan McKinney, "Quantum simulation"
• December 5: Ingmar Saberi, "TQFTs, quantum simulation, and the Jones polynomial"

Back to my home page