A remark on the quantum complexity of the Kronecker coefficients

• URL: http://arxiv.org/abs/2307.02389v1
• Date: Wed, 5 Jul 2023 15:57:53 GMT
• Title: A remark on the quantum complexity of the Kronecker coefficients
• Authors: Christian Ikenmeyer, Sathyawageeswar Subramanian
• Abstract summary: 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.
• Score: 1.6498361958317633
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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. We use only the quantum computing tools that are used in their paper and additional classical representation theoretic insights. We also prove the analogous result for the plethysm coefficients.

Related papers

• 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)
• 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)
• Quantization of Large Language Models with an Overdetermined Basis [73.79368761182998]
  We introduce an algorithm for data quantization based on the principles of Kashin representation. Our findings demonstrate that Kashin Quantization achieves competitive or superior quality in model performance.
  arXiv  Detail & Related papers  (2024-04-15T12:38:46Z)
• Machine-Learning Kronecker Coefficients [0.0]
  We show that standard machine-learning algorithms may be trained to predict whether a given Kronecker coefficient is zero or not. Our results show that a trained machine can efficiently perform this binary classification with high accuracy.
  arXiv  Detail & Related papers  (2023-06-07T19:10:44Z)
• 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)
• General quantum algorithms for Hamiltonian simulation with applications to a non-Abelian lattice gauge theory [44.99833362998488]
  We introduce quantum algorithms that can efficiently simulate certain classes of interactions consisting of correlated changes in multiple quantum numbers. The lattice gauge theory studied is the SU(2) gauge theory in 1+1 dimensions coupled to one flavor of staggered fermions. The algorithms are shown to be applicable to higher-dimensional theories as well as to other Abelian and non-Abelian gauge theories.
  arXiv  Detail & Related papers  (2022-12-28T18:56:25Z)
• Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions [9.428671399402553]
  We extend three related results from the analysis of influences of Boolean functions to the quantum inequality setting. Our results are derived by a joint use of recently studied hypercontractivity and gradient estimates. We comment on the implications of our results as regards to noncommutative extensions of isoperimetric type inequalities, quantum circuit complexity lower bounds and the learnability of quantum observables.
  arXiv  Detail & Related papers  (2022-09-15T13:12:32Z)
• Quantum mechanics of bipartite ribbon graphs: Integrality, Lattices and Kronecker coefficients [0.0]
  We define solvable quantum mechanical systems on a Hilbert space spanned by bipartite ribbon graphs with a fixed number of edges. The square of the Kronecker coefficient for a triple of Young diagrams is shown to be equal to the dimension of a sub-lattice in the lattice of ribbon graphs. As an avenue to explore quantum supremacy and its implications for computational complexity theory, we outline experiments to detect non-vanishing Kronecker coefficients for hypothetical quantum realizations/simulations of these quantum systems.
  arXiv  Detail & Related papers  (2020-10-08T15:18:46Z)
• Relevant OTOC operators: footprints of the classical dynamics [68.8204255655161]
  The OTOC-RE theorem relates the OTOCs summed over a complete base of operators to the second Renyi entropy. We show that the sum over a small set of relevant operators, is enough in order to obtain a very good approximation for the entropy. In turn, this provides with an alternative natural indicator of complexity, i.e. the scaling of the number of relevant operators with time.
  arXiv  Detail & Related papers  (2020-07-31T19:23:26Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
  arXiv  Detail & Related papers  (2019-09-04T11:46:26Z)
• Joint measurability meets Birkhoff-von Neumann's theorem [77.34726150561087]
  We prove that joint measurability arises as a mathematical feature of DNTs in this context, needed to establish a characterisation similar to Birkhoff-von Neumann's. We also show that DNTs emerge naturally from a particular instance of a joint measurability problem, remarking its relevance in general operator theory.
  arXiv  Detail & Related papers  (2018-09-19T18:57:45Z)

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.