Quantum complexity of the Kronecker coefficients

• URL: http://arxiv.org/abs/2302.11454v3
• Date: Tue, 7 May 2024 16:12:24 GMT
• Title: Quantum complexity of the Kronecker coefficients
• Authors: Sergey Bravyi, Anirban Chowdhury, David Gosset, Vojtech Havlicek, Guanyu Zhu,
• Abstract summary: 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.
• Score: 2.2983894078587963
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Whether or not the Kronecker coefficients of the symmetric group count some set of combinatorial objects is a longstanding open question. In this work we show that a given Kronecker coefficient is proportional to the rank of a projector that can be measured efficiently using a quantum computer. In other words a Kronecker coefficient counts the dimension of the vector space spanned by the accepting witnesses of a QMA verifier, where QMA is the quantum analogue of NP. 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 that captures the complexity of estimating thermal properties of quantum many-body systems. A second consequence is that deciding positivity of Kronecker coefficients is contained in QMA, complementing a recent NP-hardness result of Ikenmeyer, Mulmuley and Walter. We obtain similar results for the related problem of approximating row sums of the character table of the symmetric group. Finally, we discuss an efficient quantum algorithm that approximates normalized Kronecker coefficients to inverse-polynomial additive error.

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)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model. We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• 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)
• Universality of critical dynamics with finite entanglement [68.8204255655161]
  We study how low-energy dynamics of quantum systems near criticality are modified by finite entanglement. Our result establishes the precise role played by entanglement in time-dependent critical phenomena.
  arXiv  Detail & Related papers  (2023-01-23T19:23:54Z)
• Field theory approach to eigenstate thermalization in random quantum circuits [0.0]
  We use field-theoretic methods to explore the statistics of eigenfunctions of the Floquet operator for a large family of quantum circuits. The correlation function of the quasienergy eigenstates is calculated and shown to exhibit random matrix circular unitary ensemble statistics.
  arXiv  Detail & Related papers  (2022-10-12T18:00:00Z)
• Three-fold way of entanglement dynamics in monitored quantum circuits [68.8204255655161]
  We investigate the measurement-induced entanglement transition in quantum circuits built upon Dyson's three circular ensembles. We obtain insights into the interplay between the local entanglement generation by the gates and the entanglement reduction by the measurements.
  arXiv  Detail & Related papers  (2022-01-28T17:21:15Z)
• Random quantum circuits anti-concentrate in log depth [118.18170052022323]
  We study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated. Our definition of anti-concentration is that the expected collision probability is only a constant factor larger than if the distribution were uniform. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n log(n)) gates are also sufficient.
  arXiv  Detail & Related papers  (2020-11-24T18:44:57Z)
• 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)
• Quantum Chaos and the Spectrum of Factoring [0.9023847175654603]
  We show that a function $E$, that may take only discrete values, should be the analogous of the energy from a confined system of charges in a magnetic trap. This is the quantum factoring simulator hypothesis connecting quantum mechanics with number theory.
  arXiv  Detail & Related papers  (2020-08-24T19:40:28Z)
• 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.