論文の概要: Quantum Algorithms for Representation-Theoretic Multiplicities
- arxiv url: http://arxiv.org/abs/2407.17649v5
- Date: Tue, 25 Mar 2025 18:51:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-27 20:08:12.850296
- Title: Quantum Algorithms for Representation-Theoretic Multiplicities
- Title（参考訳）: 表現論的多重性のための量子アルゴリズム
- Authors: Martin Larocca, Vojtech Havlicek,
- Abstract要約: 我々は、Kostka、Littlewood-Richardson、Plethysm、Kronecker係数を計算するための量子アルゴリズムを提供する。
この制限の下では、Kostka数に対して効率的な古典的アルゴリズムがあることを示し、Littlewood-Richardson係数に対する類似アルゴリズムの存在を予想する。
このような古典的アルゴリズムがPlethysm と Kronecker の係数に対して直接作用しない理由を論じ、量子アルゴリズムがこれらの問題に対してスーパーポリノミカルなスピードアップをもたらすと推測する。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: Kostka, Littlewood-Richardson, Plethysm and Kronecker coefficients are the multiplicities of irreducible representations in the decomposition of representations of the symmetric group that play an important role in representation theory, geometric complexity and algebraic combinatorics. We give quantum algorithms for computing these coefficients whenever the ratio of dimensions of the representations is polynomial and study the computational complexity of this problem. We show that there is an efficient classical algorithm for computing the Kostka numbers under this restriction and conjecture the existence of an analogous algorithm for the Littlewood-Richardson coefficients. We argue why such classical algorithm does not straightforwardly work for the Plethysm and Kronecker coefficients and conjecture that our quantum algorithms lead to superpolynomial speedups for these problems. The conjecture about Kronecker coefficients was disproved by Greta Panova in [arXiv:2502.20253] with a classical solution which, if optimal, points to a $\OC(n^{4+2k})$ vs $\tilde{\Omega}(n^{4k^2+1})$ polynomial gap in quantum vs classical computational complexity for an integer parameter $k$.
- Abstract（参考訳）: Kostka, Littlewood-Richardson, Plethysm および Kronecker 係数は、表現論、複雑性、代数的組合せ論において重要な役割を果たす対称群の表現の分解における既約表現の多重性である。
表現の次元の比が多項式であるときに、これらの係数を計算するための量子アルゴリズムを与え、この問題の計算複雑性を研究する。
この制限の下では、Kostka数を計算するための効率的な古典的アルゴリズムがあることを示し、Littlewood-Richardson係数の類似アルゴリズムの存在を予想する。
このような古典的アルゴリズムがPlethysm と Kronecker の係数に対して直接作用しない理由を論じ、量子アルゴリズムがこれらの問題に対してスーパーポリノミカルなスピードアップをもたらすと推測する。
クロネッカー係数に関する予想は、[arXiv:2502.20253] のグレタ・パノヴァによって古典解で証明され、最適ならば、$\OC(n^{4+2k})$ vs $\tilde{\Omega}(n^{4k^2+1})$ の多項式ギャップを整数パラメータ$k$に対して指す。
関連論文リスト
- Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
古典的マルチロー反復法に着想を得た量子アルゴリズムを提案する。
本アルゴリズムは,不整合系の解法に適した係数行列の要求を小さくする。
論文 参考訳（メタデータ） (2024-09-06T03:32:02Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - A remark on the quantum complexity of the Kronecker coefficients [1.6498361958317633]
我々は、対称群のクロネッカー係数の計算が複雑性クラス#BQPに含まれることを証明した。
これによりBravyi, Chowdhury, Gosset, Havlicek, Zhuの最近の結果が改善されている。
論文 参考訳（メタデータ） (2023-07-05T15:57:53Z) - A hybrid quantum-classical algorithm for multichannel quantum scattering
of atoms and molecules [62.997667081978825]
原子と分子の衝突に対するシュリンガー方程式を解くためのハイブリッド量子古典アルゴリズムを提案する。
このアルゴリズムはコーン変分原理の$S$-matrixバージョンに基づいており、基本散乱$S$-matrixを計算する。
大規模多原子分子の衝突をシミュレートするために,アルゴリズムをどのようにスケールアップするかを示す。
論文 参考訳（メタデータ） (2023-04-12T18:10:47Z) - An in-principle super-polynomial quantum advantage for approximating
combinatorial optimization problems via computational learning theory [5.907281242647458]
量子コンピュータは、最適化問題に対する近似解法において、古典的コンピュータよりも高次超多項式的優位性を有することを証明している。
量子アドバンテージのコアは、究極的にはShorの量子アルゴリズムからファクタリングのために借用されている。
論文 参考訳（メタデータ） (2022-12-16T19:01:04Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - An efficient quantum algorithm for lattice problems achieving
subexponential approximation factor [2.3351527694849574]
整数格子のクラスに対する指数近似係数を用いて,境界距離復号法(BDD)問題を解く量子アルゴリズムを提案する。
量子アルゴリズムの実行時間は、近似因子の1つの範囲と、第2の範囲の近似因子のサブ指数時間である。
この見解は、有限アーベル群の観点からクリーンな量子アルゴリズムを定め、格子理論から相対的にほとんど使用せず、次元以外のパラメータの格子問題に対する近似アルゴリズムを探求することを提案している。
論文 参考訳（メタデータ） (2022-01-31T18:58:33Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。
プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
論文 参考訳（メタデータ） (2021-11-30T12:21:41Z) - Quantum algorithms for group convolution, cross-correlation, and
equivariant transformations [9.134244356393665]
群畳み込みと相互相関は、与えられた問題設定に固有の対称性を解析または活用するために一般的に数学で使用される。
ここでは,量子状態として格納されたデータの線形群畳み込みと相互相関を行うための効率的な量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-23T12:21:31Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。
これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文 参考訳（メタデータ） (2020-11-09T01:13:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。