Computing moment polytopes - with a focus on tensors, entanglement and matrix multiplication

• URL: http://arxiv.org/abs/2510.08336v1
• Date: Thu, 09 Oct 2025 15:23:49 GMT
• Title: Computing moment polytopes - with a focus on tensors, entanglement and matrix multiplication
• Authors: Maxim van den Berg, Matthias Christandl, Vladimir Lysikov, Harold Nieuwboer, Michael Walter, Jeroen Zuiddam,
• Abstract summary: In quantum information, moment polytopes provide a framework for the single-particle quantum marginal problem and offer a geometric characterization of entanglement.<n>We give a new algorithm for computing moment polytopes of tensors based on a mathematical description by Franz.
• Score: 3.1021364569486214
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Tensors are fundamental in mathematics, computer science, and physics. Their study through algebraic geometry and representation theory has proved very fruitful in the context of algebraic complexity theory and quantum information. In particular, moment polytopes have been understood to play a key role. In quantum information, moment polytopes (also known as entanglement polytopes) provide a framework for the single-particle quantum marginal problem and offer a geometric characterization of entanglement. In algebraic complexity, they underpin quantum functionals that capture asymptotic tensor relations. More recently, moment polytopes have also become foundational to the emerging field of scaling algorithms in computer science and optimization. Despite their fundamental role and interest from many angles, much is still unknown about these polytopes, and in particular for tensors beyond $\mathbb{C}^2\otimes\mathbb{C}^2\otimes\mathbb{C}^2$ and $\mathbb{C}^2\otimes\mathbb{C}^2\otimes\mathbb{C}^2\otimes\mathbb{C}^2$ only sporadically have they been computed. We give a new algorithm for computing moment polytopes of tensors (and in fact moment polytopes for the general class of reductive algebraic groups) based on a mathematical description by Franz (J. Lie Theory 2002). This algorithm enables us to compute moment polytopes of tensors of dimension an order of magnitude larger than previous methods, allowing us to compute with certainty, for the first time, all moment polytopes of tensors in $\mathbb{C}^3\otimes\mathbb{C}^3\otimes\mathbb{C}^3$, and with high probability those in $\mathbb{C}^4\otimes\mathbb{C}^4\otimes\mathbb{C}^4$ (which includes the $2\times 2$ matrix multiplication tensor). We discuss how these explicit moment polytopes have led to several new theoretical directions and results.

Related papers

• Explicit non-free tensors [3.1593341358400737]
  We prove that non-free tensors exist in $mathbbCn otimes mathbbCn otimes mathbbCn$, where they are not generic.<n>We show that if a tensor $T$ is free, then there is a tensor $S$ in the GL-orbit closure of $T$, whose support is free and whose moment map image is the minimum-norm point of the moment polytope of $T$.
  arXiv  Detail & Related papers  (2025-03-28T17:38:44Z)
• The moment polytope of matrix multiplication is not maximal [3.1593341358400737]
  We prove separations between the moment polytopes of matrix multiplication tensors and unit tensors.<n>As a consequence, we find that matrix multiplication moment polytopes are not maximal.<n>We extend these techniques to obtain a new proof of the optimal border subrank bound for matrix multiplication.
  arXiv  Detail & Related papers  (2025-03-28T17:25:06Z)
• Skein Construction of Balanced Tensor Products [0.0]
  We introduce a topological construction based on skein theory that offers a better mix of algebra and topology.<n>We prove that the Turaev-Viro state sum model naturally arises from the 3-functor in the classification of fully extended field theories.
  arXiv  Detail & Related papers  (2025-01-10T06:27:15Z)
• Unitary Closed Timelike Curves can Solve all of NP [5.475280561991127]
  We show that $mathbfBQP_ell CTC$ contains tasks that are outside $mathbfBQP$. Our work shows that non-linearity is what enables CTCs to solve $mathbfNP$, is false, and raises the importance of understanding whether purifiable process matrices are physical or not.
  arXiv  Detail & Related papers  (2024-10-06T21:28:56Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  We show that PCA becomes computationally hard at a critical value of the signal's magnitude. We define a new set of objects, which provide an explicit, near-orthogonal basis for invariants of a given degree. It also lets us analyze a new problem of distinguishing between different ensembles.
  arXiv  Detail & Related papers  (2024-04-29T14:33:24Z)
• Machine learning detects terminal singularities [49.1574468325115]
  Q-Fano varieties are positively curved shapes which have Q-factorial terminal singularities. Despite their importance, the classification of Q-Fano varieties remains unknown. In this paper we demonstrate that machine learning can be used to understand this classification.
  arXiv  Detail & Related papers  (2023-10-31T13:51:24Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  We show a new way to relate functions on the hypergrid to their harmonic extensions over the polytorus. We show the supremum of a function $f$ over products of the cyclic group $exp(2pi i k/K)_k=1K$. We extend to new spaces a recent line of work citeEI22, CHP, VZ22 that gave similarly efficient methods for learning low-degrees on hypercubes and observables on qubits.
  arXiv  Detail & Related papers  (2023-01-04T04:15:40Z)
• Construction of multipartite unextendible product bases and geometric measure of entanglement of positive-partial-transpose entangled states [0.0]
  We show that there exist two families UPBs in Hilbert space $mathbbC2otimesmathbbC2otimesmathbbC2otimesmathbbC2otimesmathbbC4$ by merging two different systems of an existing $7$-qubit UPB of size $11$. A new family of $7$-qubit positive-partial-transpose entangled states of rank $27-11$ is constructed.
  arXiv  Detail & Related papers  (2022-12-05T17:42:47Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  "Statistical-computational gaps" occur in many statistical inference tasks. We consider a model for random order-3 decomposition where one component is slightly larger in norm than the rest. We show that tensor entries can accurately estimate the largest component when $ll n3/2$ but fail to do so when $rgg n3/2$.
  arXiv  Detail & Related papers  (2022-11-10T00:40:37Z)
• Near-term quantum algorithm for computing molecular and materials properties based on recursive variational series methods [44.99833362998488]
  We propose a quantum algorithm to estimate the properties of molecules using near-term quantum devices. We test our method by computing the one-particle Green's function in the energy domain and the autocorrelation function in the time domain.
  arXiv  Detail & Related papers  (2022-06-20T16:33:23Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Stochastic behavior of outcome of Schur-Weyl duality measurement [45.41082277680607]
  We focus on the measurement defined by the decomposition based on Schur-Weyl duality on $n$ qubits. We derive various types of distribution including a kind of central limit when $n$ goes to infinity.
  arXiv  Detail & Related papers  (2021-04-26T15:03:08Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.