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
- 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) - Quantum Parallelized Variational Quantum Eigensolvers for Excited States [0.0]
Calculating excited-state properties of molecules and solids is one of the main computational challenges of modern electronic structure theory.
By combining and advancing recent ideas from the field of quantum computing we propose a more effective variational quantum eigensolver.
arXiv Detail & Related papers (2023-06-20T18:53:09Z) - 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) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - 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) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions.
Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
arXiv Detail & Related papers (2021-06-24T20:16:02Z) - Quantum information theory and Fourier multipliers on quantum groups [0.0]
We compute the exact values of the minimum output entropy and the completely bounded minimal entropy of quantum channels acting on matrix algebras.
Our results use a new and precise description of bounded Fourier multipliers from $mathrmL1(mathbbG)$ into $mathrmLp(mathbbG)$ for $1 p leq infty$ where $mathbbG$ is a co-amenable locally compact quantum group.
arXiv Detail & Related papers (2020-08-27T09:47:10Z)
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.