論文の概要: Quantum Algorithms for Representation-Theoretic Multiplicities
- arxiv url: http://arxiv.org/abs/2407.17649v2
- Date: Fri, 2 Aug 2024 00:11:56 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-05 15:50:45.692894
- Title: Quantum Algorithms for Representation-Theoretic Multiplicities
- Title(参考訳): 表現論的多重性のための量子アルゴリズム
- Authors: Martin Larocca, Vojtech Havlicek,
- Abstract要約: 我々は、Kostka、Littlewood-Richardson、Plethysm、Kronecker係数を効率的に計算する量子アルゴリズムを提供する。
同じ古典的アルゴリズムがプレトヒズム係数やクロネッカー係数に対して直接作用しない理由を論じ、この問題がいくつかの入力における超多項式量子スピードアップに繋がる可能性があると推測する。
- 参考スコア(独自算出の注目度): 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.
- Abstract(参考訳): Kostka, Littlewood-Richardson, Plethysm および Kronecker 係数は、既約の制限と積における対称群の既約表現(不規則)の多重性である。
それらは表現論において重要な役割を担い、計算が難しいことで知られている。
表現の次元の比が多項式であれば、これらの係数を効率的に計算する量子アルゴリズムを与える。
コストカ数は組合せ解釈を許容するので、多項式有界コストカ数に対する効率的な古典的アルゴリズムと、リトルウッド・リチャードソン係数に対する同様のアルゴリズムの存在が示される。
同じ古典的アルゴリズムがプレトヒズム係数やクロネッカー係数に対して直接作用しない理由を論じ、我々の量子アルゴリズムが計算の困難さをいかに回避するかを証明し、この問題がいくつかの入力における超多項式量子スピードアップに繋がるかを推測する。
最終的にフロベニウスの相互性を用いて別の量子アルゴリズムを導出し、誘導法を用いてこれらの係数を推定し、異なるコスト対インプット依存を持つ。
関連論文リスト
- An Incremental Span-Program-Based Algorithm and the Fine Print of
Quantum Topological Data Analysis [1.2246649738388387]
単純複素数のベッチ数を計算するための新しい量子アルゴリズムを提案する。
我々のアルゴリズムは、複素数が最大数の単純数に近い場合に最もよく機能する。
論文 参考訳(メタデータ) (2023-07-13T21:46:45Z) - A remark on the quantum complexity of the Kronecker coefficients [1.6498361958317633]
我々は、対称群のクロネッカー係数の計算が複雑性クラス#BQPに含まれることを証明した。
これによりBravyi, Chowdhury, Gosset, Havlicek, Zhuの最近の結果が改善されている。
論文 参考訳(メタデータ) (2023-07-05T15:57:53Z) - Quantum complexity of the Kronecker coefficients [2.2983894078587963]
与えられたクロネッカー係数は、QMA検証器の受理証人によって区切られたベクトル空間の次元をカウントすることを示す。
これは、クロネッカー係数を与えられた相対誤差の範囲内で近似することは、ある量子近似数え上げ問題の自然クラスよりも難しくないことを意味する。
論文 参考訳(メタデータ) (2023-02-22T15:43:26Z) - 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) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳(メタデータ) (2022-09-28T17:53:25Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳(メタデータ) (2022-05-26T20:32:36Z) - Using Shor's algorithm on near term Quantum computers: a reduced version [0.0]
我々は、ノイズの多い量子デバイス上で分解可能な数値の範囲を拡大するステップを推し進めるShorのアルゴリズムの縮小版を導入する。
特に、ほとんどのケースで注目すべき結果が得られており、しばしば提案されたアルゴリズムの1つで与えられた数を分解できる。
論文 参考訳(メタデータ) (2021-12-23T15:36:59Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。
これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文 参考訳(メタデータ) (2020-11-09T01:13:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。