Quantum Algorithms for Representation-Theoretic Multiplicities
- URL: http://arxiv.org/abs/2407.17649v1
- Date: Wed, 24 Jul 2024 21:34:05 GMT
- Title: Quantum Algorithms for Representation-Theoretic Multiplicities
- Authors: Martin Larocca, Vojtech Havlicek,
- Abstract summary: We give quantum algorithms that efficiently compute Kostka, Littlewood-Richardson, Plethysm and Kronecker coefficients.
We argue why the same classical algorithm does not straightforwardly work for the Plethysm and Kronecker coefficients, and conjecture that the problem could lead to superpolynomial quantum speedups on some inputs.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Kostka, Littlewood-Richardson, Plethysm and Kronecker coefficients are multiplicities of irreducible representations (irreps) of the symmetric group in restrictions and products of irreps. They play an important role in representation theory and are notoriously hard to compute. We give quantum algorithms that efficiently compute these coefficients whenever the ratio of dimensions of the representations is polynomial. Using that the Kostka numbers admit combinatorial interpretation, we show that there is an efficient classical algorithm for polynomially-bounded Kostka numbers and conjecture existence of a similar algorithm for the Littlewood-Richardson coefficients. We argue why the same classical algorithm does not straightforwardly work for the Plethysm and Kronecker coefficients, give evidence on how our quantum algorithm may avoid some hardness obstructions in their computation, and conjecture that the problem could lead to superpolynomial quantum speedups on some inputs. We finally use Frobenius reciprocity to derive another quantum algorithm that estimates these coefficients using induction and has a different cost-to-input dependence.
Related papers
- An Incremental Span-Program-Based Algorithm and the Fine Print of
Quantum Topological Data Analysis [1.2246649738388387]
We introduce a new quantum algorithm for computing the Betti numbers of a simplicial complex.
Our algorithm works best when the complex has close to the maximal number of simplices.
arXiv Detail & Related papers (2023-07-13T21:46:45Z) - A remark on the quantum complexity of the Kronecker coefficients [1.6498361958317633]
We prove that the computation of the Kronecker coefficients of the symmetric group is contained in the complexity class #BQP.
This improves a recent result of Bravyi, Chowdhury, Gosset, Havlicek, and Zhu.
arXiv Detail & Related papers (2023-07-05T15:57:53Z) - Quantum complexity of the Kronecker coefficients [2.2983894078587963]
We show that a given Kronecker coefficient counts the dimension of the vector space spanned by the accepting witnesses of a QMA verifier.
This implies that approximating the Kronecker coefficients to within a given relative error is not harder than a certain natural class of quantum approximate counting problems.
arXiv Detail & Related papers (2023-02-22T15:43:26Z) - An in-principle super-polynomial quantum advantage for approximating
combinatorial optimization problems via computational learning theory [5.907281242647458]
We prove that quantum computers feature an in-principle super-polynomial advantage over classical computers in approximating solutions to optimization problems.
The core of the quantum advantage is ultimately borrowed from Shor's quantum algorithm for factoring.
arXiv Detail & Related papers (2022-12-16T19:01:04Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms.
We exploit quantum phenomena to speed up the computation of distances.
We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z) - 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) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach.
We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers.
We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
arXiv Detail & Related papers (2022-09-28T17:53:25Z) - 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) - Using Shor's algorithm on near term Quantum computers: a reduced version [0.0]
We introduce a reduced version of Shor's algorithm that proposes a step forward in increasing the range of numbers that can be factorized on noisy Quantum devices.
In particular, we have found noteworthy results in most cases, often being able to factor the given number with only one of the proposed algorithm.
arXiv Detail & Related papers (2021-12-23T15:36:59Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard.
We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware.
The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
arXiv Detail & Related papers (2021-07-08T17:59:55Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression.
We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
arXiv Detail & Related papers (2020-11-09T01:13:07Z)
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.