論文の概要: Comparison of Hyperplane Rounding for Max-Cut and Quantum Approximate Optimization Algorithm over Certain Regular Graph Families
- arxiv url: http://arxiv.org/abs/2509.24108v1
- Date: Sun, 28 Sep 2025 23:00:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-30 22:32:19.637631
- Title: Comparison of Hyperplane Rounding for Max-Cut and Quantum Approximate Optimization Algorithm over Certain Regular Graph Families
- Title（参考訳）: 正則グラフファミリ上での最大カットと量子近似最適化のための超平面ラウンドリングの比較
- Authors: Reuben Tate, Swati Gupta,
- Abstract要約: Goemans-Williamson アルゴリズムによる Max-Cut の近似は 0.912-approximation で達成される。
エッジウェイトを摂動することで計算的に難解なインスタンスの構築について検討する。
- 参考スコア（独自算出の注目度）: 0.9699101045941679
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: There is a strong interest in finding challenging instances of NP-hard problems, from the perspective of showing quantum advantage. Due to the limits of near-term NISQ devices, it is moreover useful if these instances are small. In this work, we identify two graph families ($|V|<1000$) on which the Goemans-Williamson algorithm for approximating the Max-Cut achieves at most a 0.912-approximation. We further show that, in comparison, a recent quantum algorithm, Quantum Approximate Optimization Algorithm (depth $p=1$), is a 0.592-approximation on Karloff instances in the limit ($n \to \infty$), and is at best a $0.894$-approximation on a family of strongly-regular graphs. We further explore construction of challenging instances computationally by perturbing edge weights, which may be of independent interest, and include these in the CI-QuBe github repository.
- Abstract（参考訳）: 量子的優位性を示す観点から、NPハード問題の挑戦的な事例を見つけることに強い関心がある。
NISQデバイスの短期的限界のため、これらのインスタンスが小さくても有用である。
この研究では、マックス・カットを近似するゲーマン・ウィリアムソンアルゴリズムが少なくとも0.912近似を達成できる2つのグラフ族(|V|<1000$)を同定する。
さらに、最近の量子アルゴリズムであるQuantum Approximate Optimization Algorithm (depth $p=1$)は、カルロフのインスタンスの極限(n \to \infty$)での0.592近似であり、少なくとも強い正則グラフの族における0.894$-近似であることを示す。
さらに、独立した関心を持つかもしれないエッジウェイトを摂動することで計算的に困難なインスタンスの構築を検討し、それらをCI-QuBe githubリポジトリに含める。
関連論文リスト
- On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms [0.0]
NPにおける制約満足度問題の特徴は近似硬度であり、最悪の場合、十分な品質の近似解を見つけることは指数関数的に困難である。
ハミルトニアン時間進化に基づくアルゴリズムでは、原型的にハードなMAX-3-XORSAT問題クラスを通してこの問題を探索する。
近似系におけるランダムなハイパーグラフに対して、エネルギーを$E = N_mathrmunsat-N_mathrmsat$と定義すれば、スペクトルフィルタリングされた量子最適化は$E leq q_mで状態を返す。
論文 参考訳（メタデータ） (2023-12-11T04:15:55Z) - Low-depth Clifford circuits approximately solve MaxCut [44.99833362998488]
低深さクリフォード回路に基づくMaxCutの量子インスピレーション近似アルゴリズムを提案する。
我々のアルゴリズムは、深さ$O(N)$ Clifford回路を構築することにより、$N$頂点グラフ上のMaxCutの近似解を求める。
論文 参考訳（メタデータ） (2023-10-23T15:20:03Z) - Computing Star Discrepancies with Numerical Black-Box Optimization
Algorithms [56.08144272945755]
我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。
使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。
我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
論文 参考訳（メタデータ） (2023-06-29T14:57:56Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Sampling Frequency Thresholds for Quantum Advantage of Quantum
Approximate Optimization Algorithm [0.7046417074932257]
量子近似最適化アルゴリズム(QAOA)の性能を最先端の古典解法と比較する。
古典的解法は線形時間複雑性において高品質な近似解を生成することができる。
異なるグラフ、重み付けされたMaxCut、最大独立集合、および3-SATといった他の問題は、短期量子デバイスにおける量子優位性を達成するのに適しているかもしれない。
論文 参考訳（メタデータ） (2022-06-07T20:59:19Z) - 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) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Classical algorithms and quantum limitations for maximum cut on
high-girth graphs [6.262125516926276]
すべての(量子または古典的な)一局所アルゴリズムが$D$正規グラフに対して$5$の最大カットが1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$であることを示す。
1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$,
論文 参考訳（メタデータ） (2021-06-10T16:28:23Z) - Generating Target Graph Couplings for QAOA from Native Quantum Hardware
Couplings [3.2622301272834524]
本稿では,Ising型量子スピン系における限定大域制御を用いた任意の対象結合グラフの構築手法を提案する。
本手法は、量子近似最適化アルゴリズム(QAOA)をトラップされたイオン量子ハードウェア上に実装することによるものである。
Max-Cut QAOAのノイズシミュレーションにより、我々の実装は標準ゲートベースのコンパイルよりもノイズの影響を受けにくいことが示された。
論文 参考訳（メタデータ） (2020-11-16T18:43:09Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。