論文の概要: The Quantum Overlap Gap Property and Algorithmic Hardness for the Quantum Hypergraph Max-Cut Problem

• arxiv url: http://arxiv.org/abs/2609.10838v1
• Date: Wed, 09 Sep 2026 21:18:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-11 23:53:35.141448
• Title: The Quantum Overlap Gap Property and Algorithmic Hardness for the Quantum Hypergraph Max-Cut Problem
• Title（参考訳）: 量子ハイパーグラフマックスカット問題に対する量子オーバーラップギャップ特性とアルゴリズム的硬さ
• Abstract要約: 我々は,量子ハイパーグラフのMax-Cut問題に対する近似の平均ケース硬さを解析する。 弱硬度の結果を示し、任意のリプシッツ定数$L$に対して、$L$stableアルゴリズムが最適解を近似できないような$k$が存在することを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we analyze the average-case hardness of approximation for the Quantum Hypergraph Max-Cut problem using the theoretical framework of the Quantum Overlap Gap Property (QOGP). We establish two main results. Our first result applies to a wide class of stable quantum algorithms, satisfying a Lipschitz property with respect to the quantum Wasserstein distance of order $2$. We show a weak hardness result, demonstrating that for any Lipschitz constant $L$, there is some $k$ such that $L$-stable algorithms cannot approximate the optimal solution to Quantum Hypergraph Max-Cut on $k$-uniform hypergraphs in the average case. Additionally, we establish a strong hardness result where $k$ is independent of $L$, but only for a more restricted class of local quantum algorithms defined using the quantum Wasserstein distance of order $\infty$. We apply these results to establish concrete depth lower bounds for popular quantum algorithms for preparing near-optimal states for this problem.
• Abstract（参考訳）: 本研究では,量子オーバーラップギャップ特性(QOGP)の理論的枠組みを用いて,量子ハイパーグラフの最大カウト問題に対する近似の平均ケース硬さを解析する。 主な成果は2つある。 最初の結果は、リプシッツの性質を満たす安定な量子アルゴリズムの幅広いクラスに適用され、量子ワッサーシュタイン距離は2ドルである。 弱硬度の結果を示し、任意のリプシッツ定数$L$に対して、$L$stableアルゴリズムが平均の場合の$k$uniformハイパーグラフ上の量子ハイパーグラフMax-Cutの最適解を近似できないような$k$が存在することを示した。 さらに、$k$ が$L$ から独立であるような強い硬さの結果を確立するが、これは順序$\infty$ の量子ワッサーシュタイン距離を用いて定義されるより制限された局所量子アルゴリズムのクラスに対してのみ成立する。 これらの結果を用いて、この問題に対する準最適状態を作成するために、一般的な量子アルゴリズムに対して、具体的な深さの低い境界を確立する。

関連論文リスト

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  浅量子回路では解けない問題を格子ベースの仮定で解くのが困難である。 浅量子回路は、解を効率よく検証できる古典的な難題を解くのに十分な構造を持っていることを証明している。
  論文  参考訳（メタデータ） (2026-09-01T15:54:34Z)
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  重み付き確率変数に対する新しい量子平均推定器を開発した。 尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。 凸目的関数に対して,量子射影勾配降下法を提案する。
  論文  参考訳（メタデータ） (2026-07-28T09:29:37Z)
• Quantum Approximate $k$-Minimum Finding [2.810947654192424]
  我々は、全ての$k geq 1$に対して近似値を扱う最適量子$k$-minimum探索アルゴリズムを提案する。 我々は、複数の観測可能量のうち、$k$最小の期待値を同定し、ハミルトンの最低基底状態エネルギーを$k$最小に決定するための効率的な量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-12-21T11:21:15Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Approximation Algorithms for Quantum Max-$d$-Cut [42.248442410060946]
  量子Max-$d$-Cut問題(Quantum Max-$d$-Cut problem)は、プロジェクターに付随する期待エネルギーを、全ての局所相互作用上の2つの$d$-dimensional quditsの非対称部分空間に最大化する量子状態を見つけることである。 我々は,非自明な性能保証を実現するために,有界な純度を持つ混合状態の積状態解を求めるアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-09-19T22:53:17Z)
• Alleviating the quantum Big-$M$ problem [0.22615818641180715]
  古典的には "Big-$M$" 問題として知られており、物理的エネルギースケールに影響を与える。 我々は、量子ビッグ-M$問題を体系的に包含し、最適の$M$を見つけるのにNPハードネスを明らかにする。 本稿では,SDP緩和に基づく実用的な翻訳アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-07-19T18:00:05Z)
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm [0.7046417074932257]
  量子近似最適化アルゴリズム(QAOA)の性能を最先端の古典解法と比較する。 古典的解法は線形時間複雑性において高品質な近似解を生成することができる。 異なるグラフ、重み付けされたMaxCut、最大独立集合、および3-SATといった他の問題は、短期量子デバイスにおける量子優位性を達成するのに適しているかもしれない。
  論文  参考訳（メタデータ） (2022-06-07T20:59:19Z)
• The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut [0.07614628596146598]
  グラフストリーミング問題であるMax-Cutとその量子アナログQuantum Max-Cutの空間複雑性について検討する。 我々の研究は、$textrmo(n)$ space を用いて量子および古典マックスキュートの量子的および古典的近似性を解決する。
  論文  参考訳（メタデータ） (2022-06-01T03:40:56Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。 本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
  論文  参考訳（メタデータ） (2021-06-11T09:43:09Z)

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

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