Overview

[ Français ]

Tensors: Quantum Information, Complexity and Combinatorics
November 7-25,2022

The structural and computational study of tensors is a driving force behind progress in a wide variety of areas: from faster matrix multiplication algorithms in algebraic complexity theory, to unraveling quantum entanglement and computation in quantum information theory, to the breakthrough result on the cap set problem in combinatorics, to name a few. Combining the intuitions from quantum information and algebraic complexity and the mathematical tools from representation theory, tensor research, Positivstellensätze and real geometry, a fruitful common line of research has emerged. This thematic month will bring together experts in the areas of quantum information (tensor networks, stabilizer rank), complexity (matrix multiplication, direct-sum problems) and combinatorics to deepen and expand these connections.

Tensors in Algebraic Complexity and Combinatorics. Strassen published in 1969 his celebrated algorithm to multiply n x n matrices using only O(n2.81) arithmetic operations, improving on the standard cubic algorithm. Over the years, increasingly ingenious tensor methods have led to better and better upper bounds on the optimal exponent ω, which culminated in the current upper bound ω ≤ 2.37286 by Alman and Vassilevska Williams in 2020. However, the question whether ω = 2 or ω > 2 remains wide open.
With the solution of the cap set problem in 2016 by Ellenberg and Gijswijt (and the slice rank proof of Tao) a new connection between tensors and extremal combinatorics was firmly established. This breakthrough led to a concentrated interest in studying new tensor parameters such as analytic rank, subrank, geometric rank and G-stable rank. These tools moreover opened a rich line of work on barrier theorems for matrix multiplication algorithms in recent years.

Direct-sum Theorems and Dualities. In many computational and economic settings problems come in batches (e.g. computing one function many times, simultaneously communicating many messages through parallel channels, buying or selling many identical items, etc.). In others, multiple copies are generated artificially to achieve some “amplification”, making hard problems harder (e.g. for cryptographic purposes or in optimization settings. In many areas of mathematics and physics, “direct sum” and “tensor product” apply to different types of objects, and it is natural to study how various parameters of these objects are affected by sum and product.
Strassen developed a sophisticated duality theory for studying such properties, called the theory of asymptotic spectra. Originally, he developed this theory for studying matrix multiplication and other tensor problems (which was recently connected to moment polytopes in representation theory), but his general duality theory (a Positivstellensatz, closely related to the Positivstellensatz of Krivine, Kadison and Dubois) has recently been shown to apply to many other settings (in combinatorics, quantum information, etc.).

Tensors in Quantum Information: Entanglement and Tensor Networks. The efficient representation of tensors of large size and dimension is an important problem in different areas of mathematics and the sciences. Glueing together smaller tensors in clever ways provides an important approach to this problem. Known as tensor networks, these objects inherit structure from their smaller constituencies, yet give rise to entirely new asymptotic behaviour. In quantum information, tensor networks (which are generalizations of matrix product states and entangled projected pair states) describe quantum matter. In quantum computing, tensor networks can be used for efficient classical simulations.

We expect that continued deepening of the connections between the physical, mathematical and computational viewpoints on tensors will generate valuable directions in these research areas.