論文の概要: Polynomial time classical versus quantum algorithms for representation theoretic multiplicities
- arxiv url: http://arxiv.org/abs/2502.20253v1
- Date: Thu, 27 Feb 2025 16:39:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-28 14:55:43.667381
- Title: Polynomial time classical versus quantum algorithms for representation theoretic multiplicities
- Title（参考訳）: 表現論的乗法に対する多項式時間古典対量子アルゴリズム
- Authors: Greta Panova,
- Abstract要約: 多くの場合、Kronecker係数とplethysm係数も古典的アルゴリズムで計算可能であることを示す。
これは、望まれる超多項式量子スピードアップが達成できるケースを著しく制限する。
- 参考スコア（独自算出の注目度）: 0.18130068086063336
- License:
- 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.
- Abstract（参考訳）: Littlewood-Richardson, Kronecker and plethysm coefficients は表現論と代数的組合せ論の基本的な多元性である。
Kronecker係数とplethysm係数の組合せ解釈を決定することは、主要な開問題であり、計算複雑性の考慮を促す。
最近、それらは量子計算に関して比較的よく振る舞うことが示され、いくつかの大家族には多項式時間量子アルゴリズム(Larocca,Havlicek, arXiv:2407.17649)がある([BCGHZ,arXiv:2302.11454])。
この論文では、クローネッカー係数とプレシズム係数は古典的アルゴリズムによって多項式時間で計算可能であることを示し、したがって [LH24] の予想の一部を否定する。
これは、望まれる超多項式量子スピードアップが達成できるケースを著しく制限する。
関連論文リスト
- 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) - Quantum Algorithms for Representation-Theoretic Multiplicities [0.0]
我々は、Kostka、Littlewood-Richardson、Plethysm、Kronecker係数を計算するための量子アルゴリズムを提供する。
リトルウッド・リチャードソン係数の計算に有効な古典的アルゴリズムが存在することを示す。
量子アルゴリズムがスーパーポリノミカルなスピードアップにつながると推測する。
論文 参考訳（メタデータ） (2024-07-24T21:34:05Z) - Quantum Query Complexity of Boolean Functions under Indefinite Causal
Order [0.9208007322096533]
一般高次量子計算におけるブール関数の問合せ複雑性について検討する。
最近導入された因果順序の量子制御を持つ量子回路のクラスは、クエリの複雑さを減らすことは不可能である。
因果不確定なスーパーマップを利用する場合、2つのクエリで計算できる最小誤差が厳密に低い関数がいくつか見つかる。
論文 参考訳（メタデータ） (2023-07-18T13:12:55Z) - A hybrid quantum-classical algorithm for multichannel quantum scattering
of atoms and molecules [62.997667081978825]
原子と分子の衝突に対するシュリンガー方程式を解くためのハイブリッド量子古典アルゴリズムを提案する。
このアルゴリズムはコーン変分原理の$S$-matrixバージョンに基づいており、基本散乱$S$-matrixを計算する。
大規模多原子分子の衝突をシミュレートするために,アルゴリズムをどのようにスケールアップするかを示す。
論文 参考訳（メタデータ） (2023-04-12T18:10:47Z) - Quantum complexity of the Kronecker coefficients [2.2983894078587963]
与えられたクロネッカー係数は、QMA検証器の受理証人によって区切られたベクトル空間の次元をカウントすることを示す。
これは、クロネッカー係数を与えられた相対誤差の範囲内で近似することは、ある量子近似数え上げ問題の自然クラスよりも難しくないことを意味する。
論文 参考訳（メタデータ） (2023-02-22T15:43:26Z) - An Exponential Separation Between Quantum Query Complexity and the
Polynomial Degree [79.43134049617873]
本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。
アルファベットのサイズについては、定値対分離の複雑さがある。
論文 参考訳（メタデータ） (2023-01-22T22:08:28Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
量子計算の2つのモデル: CQ_dとQC_d。
CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。
CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
論文 参考訳（メタデータ） (2022-01-06T03:10:53Z) - Quantum computational advantage implies contextuality [0.0]
量子コンピュータ上で効率的に解ける全ての問題のクラスと古典的アルゴリズムを用いたクラスとの分離は、量子アルゴリズムの時間一般化された文脈性を意味することを示す。
この結果は、特別の場合としてゴッテマン・クニルの定理のバージョンを仮定する。
論文 参考訳（メタデータ） (2021-11-30T19:00:02Z) - The Hidden Subgroup Problem for Universal Algebras [0.7832189413179361]
隠れ部分群問題(英: Hidden Subgroup Problem、HSP)は、特殊の場合の整数分解、離散離散問題、グラフ同型、最短ベクトル問題を含む計算問題である。
論文 参考訳（メタデータ） (2020-01-30T13:09:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。