論文の概要: Quantum complexity of the Kronecker coefficients

• arxiv url: http://arxiv.org/abs/2302.11454v3
• Date: Tue, 7 May 2024 16:12:24 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-08 20:42:53.462961
• Title: Quantum complexity of the Kronecker coefficients
• Title（参考訳）: クロネッカー係数の量子複雑性
• Authors: Sergey Bravyi, Anirban Chowdhury, David Gosset, Vojtech Havlicek, Guanyu Zhu,
• Abstract要約: 与えられたクロネッカー係数は、QMA検証器の受理証人によって区切られたベクトル空間の次元をカウントすることを示す。 これは、クロネッカー係数を与えられた相対誤差の範囲内で近似することは、ある量子近似数え上げ問題の自然クラスよりも難しくないことを意味する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 対称群のクロネッカー係数が組合せ対象の集合を数えるかどうかは、長年の開問題である。 本研究では、与えられたクロネッカー係数が、量子コンピュータを用いて効率的に測定できるプロジェクターのランクに比例することを示す。 言い換えれば、クロネッカー係数は、QMA検証器の受理証人によって広がるベクトル空間の次元を数え、QMAはNPの量子アナログである。 このことは、クロネッカー係数を与えられた相対誤差の範囲内で近似することは、量子多体系の熱的性質を推定する複雑さをとらえる特定の自然クラスである量子近似数問題よりも難しくないことを意味する。 第2の結果は、クロネッカー係数の正の判定がQMAに含まれており、最近のIkenmeyer、Mulmuley、WalterのNP硬度の結果を補完するということである。 対称群の文字テーブルの行和を近似する問題の類似した結果を得る。 最後に、正規化Kronecker係数を逆多項式加法誤差に近似する効率的な量子アルゴリズムについて議論する。

関連論文リスト

• Quantum channels, complex Stiefel manifolds, and optimization [45.9982965995401]
  我々は、量子チャネルの位相空間と複素スティーフェル多様体の商の間の連続性関係を確立する。 確立された関係は、様々な量子最適化問題に適用できる。
  論文  参考訳（メタデータ） (2024-08-19T09:15:54Z)
• Quantum Algorithms for Representation-Theoretic Multiplicities [0.0]
  我々は、Kostka、Littlewood-Richardson、Plethysm、Kronecker係数を計算するための量子アルゴリズムを提供する。 リトルウッド・リチャードソン係数の計算に有効な古典的アルゴリズムが存在することを示す。 量子アルゴリズムがスーパーポリノミカルなスピードアップにつながると推測する。
  論文  参考訳（メタデータ） (2024-07-24T21:34:05Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• A remark on the quantum complexity of the Kronecker coefficients [1.6498361958317633]
  我々は、対称群のクロネッカー係数の計算が複雑性クラス#BQPに含まれることを証明した。 これによりBravyi, Chowdhury, Gosset, Havlicek, Zhuの最近の結果が改善されている。
  論文  参考訳（メタデータ） (2023-07-05T15:57:53Z)
• Universality of critical dynamics with finite entanglement [68.8204255655161]
  臨界近傍の量子系の低エネルギー力学が有限絡みによってどのように変化するかを研究する。 その結果、時間依存的臨界現象における絡み合いによる正確な役割が確立された。
  論文  参考訳（メタデータ） (2023-01-23T19:23:54Z)
• Field theory approach to eigenstate thermalization in random quantum circuits [0.0]
  我々は、Floquet演算子の固有関数の統計を量子回路の大規模なファミリに対して探索するために、場の理論的手法を用いる。 準エネルギー固有状態の相関関数を計算し、ランダムな行列一様アンサンブル統計を示す。
  論文  参考訳（メタデータ） (2022-10-12T18:00:00Z)
• Three-fold way of entanglement dynamics in monitored quantum circuits [68.8204255655161]
  ダイソンの3つの円形アンサンブル上に構築された量子回路における測定誘起エンタングルメント遷移について検討する。 ゲートによる局所的絡み合い発生と測定による絡み合い低減との相互作用について考察した。
  論文  参考訳（メタデータ） (2022-01-28T17:21:15Z)
• Random quantum circuits anti-concentrate in log depth [118.18170052022323]
  本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。 我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。 ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
  論文  参考訳（メタデータ） (2020-11-24T18:44:57Z)
• Quantum mechanics of bipartite ribbon graphs: Integrality, Lattices and Kronecker coefficients [0.0]
  ヒルベルト空間上の可解量子力学系を、固定数のエッジを持つ二部格子リボングラフで定義する。 ヤング図形の3重のクロネッカー係数の平方は、リボングラフの格子内の部分格子の次元と等しいことが示されている。 量子超越性とその計算複雑性理論への応用を探求する手段として、これらの量子系の仮想量子実現・シミュレーションのための非消滅的クロネッカー係数を検出する実験を概説する。
  論文  参考訳（メタデータ） (2020-10-08T15:18:46Z)
• Quantum Chaos and the Spectrum of Factoring [0.9023847175654603]
  離散値のみを取る関数である$E$は、磁気トラップにおける電荷の制限系からのエネルギーの類似であることを示す。 これは、量子力学と数論を結びつける量子ファクタリングシミュレータ仮説である。
  論文  参考訳（メタデータ） (2020-08-24T19:40:28Z)
• Joint measurability meets Birkhoff-von Neumann's theorem [77.34726150561087]
  我々は、この文脈でDNTの数学的特徴として関節測度が生じることを証明し、バーホフ=ヴォン・ノイマン(Birkhoff-von Neumann)と同様の性格化を確立する必要がある。 また、DNTは、一般作用素理論におけるその関連性に言及しながら、結合可測性問題の特定の事例から自然に現れることを示す。
  論文  参考訳（メタデータ） (2018-09-19T18:57:45Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。