Polynomial time classical versus quantum algorithms for representation theoretic multiplicities

• URL: http://arxiv.org/abs/2502.20253v1
• Date: Thu, 27 Feb 2025 16:39:17 GMT
• Title: Polynomial time classical versus quantum algorithms for representation theoretic multiplicities
• Authors: Greta Panova,
• Abstract summary: We show that for many cases the Kronecker and plethysm coefficients can also be computed in time via classical algorithms.<n>This vastly limits the cases in which the desired super-polynomial quantum speedup could be achieved.
• Score: 0.18130068086063336
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Littlewood-Richardson, Kronecker and plethysm coefficients are fundamental multiplicities of interest in Representation Theory and Algebraic Combinatorics. Determining a combinatorial interpretation for the Kronecker and plethysm coefficients is a major open problem, and prompts the consideration of their computational complexity. Recently it was shown that they behave relatively well with respect to quantum computation, and for some large families there are polynomial time quantum algorithms [Larocca,Havlicek, arXiv:2407.17649] (also [BCGHZ,arXiv:2302.11454]). In this paper we show that for many of those cases the Kronecker and plethysm coefficients can also be computed in polynomial time via classical algorithms, thereby refuting some of the conjectures in [LH24]. This vastly limits the cases in which the desired super-polynomial quantum speedup could be achieved.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Quantum Algorithms for Representation-Theoretic Multiplicities [0.0]
  We give quantum algorithms for computing Kostka, Littlewood-Richardson, Plethysm and Kronecker coefficients. We show that there is an efficient classical algorithm for computing the Littlewood-Richardson coefficients. We conjecture that our quantum algorithms lead to superpolynomial speedups.
  arXiv  Detail & Related papers  (2024-07-24T21:34:05Z)
• Quantum Query Complexity of Boolean Functions under Indefinite Causal Order [0.9208007322096533]
  We study the query complexity of Boolean functions under general higher order quantum computations. We show that the recently introduced class of quantum circuits with quantum control of causal order cannot lead to any reduction in query complexity. We find some functions for which the minimum error with which they can be computed using two queries is strictly lower when exploiting causally indefinite supermaps.
  arXiv  Detail & Related papers  (2023-07-18T13:12:55Z)
• 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 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 Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  In this paper, we demonstrate an exponential separation between exact degree and approximate quantum query for a partial function. For an alphabet size, we have a constant versus separation complexity.
  arXiv  Detail & Related papers  (2023-01-22T22:08:28Z)
• 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)
• 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)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  Two models of quantum computation: CQ_d and QC_d. CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation. We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
  arXiv  Detail & Related papers  (2022-01-06T03:10:53Z)
• Quantum computational advantage implies contextuality [0.0]
  We show that a separation between the class of all problems that can efficiently be solved on a quantum computer and those using classical algorithms implies the time generalized contextuality of quantum algorithms. Our result subsumes versions of Gottesman-Knill theorem as special cases.
  arXiv  Detail & Related papers  (2021-11-30T19:00:02Z)
• The Hidden Subgroup Problem for Universal Algebras [0.7832189413179361]
  The Hidden Subgroup Problem (HSP) is a computational problem which includes as special cases integer factorization, the discrete discrete problem, graph isomorphism, and the shortest vector problem.
  arXiv  Detail & Related papers  (2020-01-30T13:09:35Z)

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.