Weighted slice rank and a minimax correspondence to Strassen's spectra

• URL: http://arxiv.org/abs/2012.14412v3
• Date: Wed, 19 Apr 2023 15:11:04 GMT
• Title: Weighted slice rank and a minimax correspondence to Strassen's spectra
• Authors: Matthias Christandl, Vladimir Lysikov, Jeroen Zuiddam
• Abstract summary: Strassen's spectra program characterizes optimal matrix algorithms through monotone functionals. Weighted slice rank encapsulates different notions of bipartiteness of quantum entanglement. New characterization can be extended to all fields.
• Score: 5.348876409230947
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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. of 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.

Related papers

• Quantum Algorithm For Testing Convexity of Function [0.0]
  An important property of a real-valued function is its convexity, which plays a very crucial role in many areas, such as thermodynamics and geometry. Motivated by recent advances in quantum computation as well as the quest for quantum advantage, we give a quantum algorithm for testing convexity of functions. We show that quantum computers can reveal the convexity property superpolynomially faster than classical computers with respect to number of variables.
  arXiv  Detail & Related papers  (2024-09-05T07:38:38Z)
• Quantum channels, complex Stiefel manifolds, and optimization [45.9982965995401]
  We establish a continuity relation between the topological space of quantum channels and the quotient of the complex Stiefel manifold. The established relation can be applied to various quantum optimization problems.
  arXiv  Detail & Related papers  (2024-08-19T09:15:54Z)
• Exploiting Structure in Quantum Relative Entropy Programs [6.281229317487581]
  We show how common structures arising from applications in quantum information theory can be exploited to improve the efficiency of solving quantum relative entropy programs. Our numerical results show that these techniques improve computation times by up to several orders of magnitude, and allow previously intractable problems to be solved.
  arXiv  Detail & Related papers  (2024-06-28T21:37:45Z)
• 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)
• Quantum Computing and Tensor Networks for Laminate Design: A Novel Approach to Stacking Sequence Retrieval [1.6421520075844793]
  A prime example is the weight optimization of laminated composite materials, which to this day remains a formidable problem. The rapidly developing field of quantum computation may offer novel approaches for addressing these intricate problems.
  arXiv  Detail & Related papers  (2024-02-09T15:01:56Z)
• Quantum Kernel Machine Learning With Continuous Variables [0.0]
  The popular qubit framework has dominated recent work on quantum kernel machine learning. There is no comparative framework to understand these concepts for continuous variable (CV) quantum computing platforms.
  arXiv  Detail & Related papers  (2024-01-11T03:49:40Z)
• Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators [0.3177496877224142]
  The Quantum Max Cut (QMC) problem has emerged as a test-problem for designing approximation algorithms for local Hamiltonian problems. In this paper we attack this problem using the algebraic structure of QMC, in particular the relationship between the quantum max cut Hamiltonian and the representation theory of the symmetric group.
  arXiv  Detail & Related papers  (2023-07-28T16:45:16Z)
• A hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
  We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions. The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix. We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
  arXiv  Detail & Related papers  (2023-04-12T18:10:47Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• 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)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)

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.