Weighted slice rank and a minimax correspondence to Strassen's spectra
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
Weighted slice rank and a minimax correspondence to Strassen's spectra. / Christandl, Matthias; Lysikov, Vladimir; Zuiddam, Jeroen.
I: Journal des Mathematiques Pures et Appliquees, Bind 172, 2023, s. 299-329.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Weighted slice rank and a minimax correspondence to Strassen's spectra
AU - Christandl, Matthias
AU - Lysikov, Vladimir
AU - Zuiddam, Jeroen
N1 - Publisher Copyright: © 2023 The Author(s)
PY - 2023
Y1 - 2023
N2 - Structural and computational understanding of tensors is the driving force behind faster matrix multiplication algorithms, the unraveling of quantum entanglement, and the breakthrough on the cap set problem. Strassen's asymptotic spectra program (FOCS 1986) characterizes optimal matrix multiplication algorithms through monotone functionals. Our work advances and makes novel connections among two recent developments in the study of tensors, namely • the slice rank of tensors, a notion of rank for tensors that emerged from the resolution of the cap set problem (Ann. Math. 2017), • and the quantum functionals of tensors (STOC 2018), monotone functionals defined as optimizations over moment polytopes. More precisely, we introduce an extension of slice rank that we call weighted slice rank and we develop a minimax correspondence between the asymptotic weighted slice rank and the quantum functionals. Weighted slice rank encapsulates different notions of bipartiteness of quantum entanglement. The correspondence allows us to give a rank-type characterization of the quantum functionals. Moreover, whereas the original definition of the quantum functionals only works over the complex numbers, this new characterization can be extended to all fields. Thereby, in addition to gaining deeper understanding of Strassen's theory for the complex numbers, we obtain a proposal for quantum functionals over other fields. The finite field case is crucial for combinatorial and algorithmic problems where the field can be optimized over.
AB - Structural and computational understanding of tensors is the driving force behind faster matrix multiplication algorithms, the unraveling of quantum entanglement, and the breakthrough on the cap set problem. Strassen's asymptotic spectra program (FOCS 1986) characterizes optimal matrix multiplication algorithms through monotone functionals. Our work advances and makes novel connections among two recent developments in the study of tensors, namely • the slice rank of tensors, a notion of rank for tensors that emerged from the resolution of the cap set problem (Ann. Math. 2017), • and the quantum functionals of tensors (STOC 2018), monotone functionals defined as optimizations over moment polytopes. More precisely, we introduce an extension of slice rank that we call weighted slice rank and we develop a minimax correspondence between the asymptotic weighted slice rank and the quantum functionals. Weighted slice rank encapsulates different notions of bipartiteness of quantum entanglement. The correspondence allows us to give a rank-type characterization of the quantum functionals. Moreover, whereas the original definition of the quantum functionals only works over the complex numbers, this new characterization can be extended to all fields. Thereby, in addition to gaining deeper understanding of Strassen's theory for the complex numbers, we obtain a proposal for quantum functionals over other fields. The finite field case is crucial for combinatorial and algorithmic problems where the field can be optimized over.
KW - Asymptotic spectrum
KW - Moment polytopes
KW - Slice rank
KW - Tensors
UR - http://www.scopus.com/inward/record.url?scp=85149769520&partnerID=8YFLogxK
U2 - 10.1016/j.matpur.2023.02.006
DO - 10.1016/j.matpur.2023.02.006
M3 - Journal article
AN - SCOPUS:85149769520
VL - 172
SP - 299
EP - 329
JO - Journal des Mathematiques Pures et Appliquees
JF - Journal des Mathematiques Pures et Appliquees
SN - 0021-7824
ER -
ID: 343168073