Fugu-MT 論文翻訳(概要): A sharp interaction-degree threshold for simulating QAOA

論文の概要: A sharp interaction-degree threshold for simulating QAOA

arxiv url: http://arxiv.org/abs/2605.22758v1
Date: Thu, 21 May 2026 17:24:00 GMT
ステータス: 翻訳完了
システム内更新日: 2026-05-22 16:35:42.372611
Title: A sharp interaction-degree threshold for simulating QAOA
Title（参考訳）: QAOAシミュレーションのための鋭い相互作用度閾値
Authors: Ralfs Āboliņš, Andris Ambainis,
Abstract要約: 深さ-$p$ QAOA on $nO(1)$ every $p = O。ハード次数-3$インスタンスは自明に最適化可能なコスト関数を持つので、サンプリング硬さはそれ自体が量子最適化の利点を意味するものではない。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We identify a sharp interaction-degree threshold for the classical simulation of QAOA with $2$-local cost functions. At degree $3$, classical sampling from depth-$1$ QAOA with small multiplicative error would collapse the polynomial hierarchy to its third level. At degree $2$, exact classical sampling from depth-$p$ QAOA on $n$ qubits runs in time $n^{O(1)}$ whenever $p = O(\log n)$. The hard degree-$3$ instances have trivially optimizable cost functions, so sampling hardness does not by itself imply a quantum optimization advantage.
Abstract（参考訳）: 局所コスト関数が2ドルであるQAOAの古典シミュレーションにおいて、鋭い相互作用度閾値を同定する。次数$$3の古典的なサンプリングは、小さな乗法誤差を持つ深さ$1$QAOAから行われ、多項式階層を3番目のレベルに崩壊させる。 $n$ qubits における深さ-$p$ QAOA からの正確な古典的なサンプリングは、いつでも$p = O(\log n)$ で実行される。ハード次数-3$インスタンスは自明に最適化可能なコスト関数を持つので、サンプリング硬さはそれ自体が量子最適化の利点を意味するものではない。

関連論文リスト

Quantum Causal Discovery via Amplitude Estimation of Kullback-Leibler Divergence [0.0]
本稿では,クリッピングされた対数密度比を振幅推定として符号化した量子アルゴリズムQKLA(Quantum Kullback-Leibler Amplitude Estimation)を提案する。 QKLAは2次精度の改善を実現し、$mathcalO((L/)log (1/)$クエリのみを必要とする。階層ごとの条件付きオーラルアクセスとCI決定のマージン仮定の下で、PCアルゴリズムの化合物にこの推定器を埋め込み、$widetilde (1/(L)にする。
論文参考訳（メタデータ） (2026-04-25T21:46:28Z)
Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
乗算前の2つの行列のエントリーワイズスカラー量子化について検討した。我々は、閉形式の最適点密度 [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X を求め、相関駆動相転移を証明した。
論文参考訳（メタデータ） (2026-03-20T01:53:44Z)
Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
本稿では、リプシッツ連続目的の$(,epsilon)$-Goldstein定常点を求める問題を考える。代理オラクル関数に対するゼロ階量子推定器を構築する。
論文参考訳（メタデータ） (2024-10-21T16:52:26Z)
Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文参考訳（メタデータ） (2024-01-17T18:59:38Z)
More Optimal Simulation of Universal Quantum Computers [0.0]
最悪のサンプリングコストは$le(2+sqrt2)xi_t delta-1$であり、$t rightarrow infty$である。我々は、この68倍のプレファクタを、相関サンプリングにより$t$の先行値の低減により削減する。
論文参考訳（メタデータ） (2022-02-02T19:00:03Z)
Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation [92.99933928528797]
エピソードマルコフ決定過程(MDP)に対する線形関数近似を用いたモデルに基づく無報酬強化学習について検討する。計画段階では、特定の報酬関数が与えられ、探索フェーズから収集したサンプルを使用して良い政策を学ぶ。任意の報酬関数に対して$epsilon$-optimal Policyを得るには,最大$tilde O(H4d(H + d)epsilon-2)$ episodesをサンプリングする必要がある。
論文参考訳（メタデータ） (2021-10-12T23:03:58Z)
Improved Weak Simulation of Universal Quantum Circuits by Correlated $L_1$ Sampling [0.0]
弱シミュレーションはしばしば弱いシミュレーションと呼ばれ、量子的優位性をいつ求めるかを決定する方法である。最低の$L_$ノルムサンプリングコストの上限を$mathcal O(xit delta-2)$から$t$の次の順序に構築的に締め付ける。これは、我々の知識の最悪の場合において、この境界の有限t$への依存を下げた最初の弱いシミュレーションアルゴリズムである。
論文参考訳（メタデータ） (2021-04-15T05:50:11Z)
Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning [59.71676469100807]
この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
論文参考訳（メタデータ） (2021-02-12T14:22:05Z)
Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文参考訳（メタデータ） (2020-06-04T17:51:00Z)
Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits [0.755972004983746]
変分量子アルゴリズム (VQA) はパラメタライズド量子回路のパラメータ $vectheta$ を最適化する。我々は、$V(vectheta)$が局所的な2-デザインを形成するブロックからなる交互層状アンサッツであると仮定して、2つの結果を証明した。量子オートエンコーダの実装において、これらのアイデアを最大100キュービットの大規模シミュレーションで説明する。
論文参考訳（メタデータ） (2020-01-02T18:18:25Z)

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