Fugu-MT 論文翻訳(概要): No Quantum Advantage in Decoded Quantum Interferometry for MaxCut

論文の概要: No Quantum Advantage in Decoded Quantum Interferometry for MaxCut

arxiv url: http://arxiv.org/abs/2509.19966v1
Date: Wed, 24 Sep 2025 10:21:31 GMT
ステータス: 翻訳完了
システム内更新日: 2025-09-25 20:53:19.774678
Title: No Quantum Advantage in Decoded Quantum Interferometry for MaxCut
Title（参考訳）: 量子干渉法によるMaxCutの量子アドバンテージ
Authors: Ojas Parekh,
Abstract要約: Decoded Quantum Interferometry (DQI)は、特別な種類の離散最適化問題を近似するためのフレームワークである。 DQI が非自明な保証を得た MaxCut のインスタンスは、古典的な時間で正確に解決可能であることを示す。
参考スコア（独自算出の注目度）: 0.08122270502556375
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Decoded Quantum Interferometry (DQI) is a framework for approximating special kinds of discrete optimization problems that relies on problem structure in a way that sets it apart from other classical or quantum approaches. We show that the instances of MaxCut on which DQI attains a nontrivial asymptotic approximation guarantee are solvable exactly in classical polynomial time. We include a streamlined exposition of DQI tailored for MaxCut that relies on elementary graph theory instead of coding theory to motivate and explain the algorithm.
Abstract（参考訳）: 復号量子干渉法(Decoded Quantum Interferometry, DQI)は、他の古典的あるいは量子的アプローチとは異なる方法で問題構造に依存する特別な種類の離散最適化問題を近似するためのフレームワークである。 DQI が非自明な漸近近似を保証する MaxCut のインスタンスは、古典多項式時間で正確に解けることを示す。アルゴリズムのモチベーションと説明のために、符号化理論の代わりに基本グラフ理論に依存するMaxCut用に調整されたDQIの合理化された表現を含む。

関連論文リスト

A Depth-Independent Linear Chain Ansatz for Large-Scale Quantum Approximate Optimization [19.43182259360486]
本稿では, 線形連鎖 QAOA の変種を提案するとともに, 従来の QAOA のパラダイムである MaxCut 問題に対して, その優位性を実証する。アンザッツでは、元のMaxCutグラフから線形鎖を見つけ、この鎖に沿ってエンタングゲートを順次配置する。この線形鎖アンサッツは、浅い量子回路と、問題の大きさとは独立にスケールする低い実行時間によって特徴付けられる。
論文参考訳（メタデータ） (2025-09-22T00:33:54Z)
A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
提案手法では,Groverをベースとした進化的枠組みと分割・分散原理を用いた量子遺伝的アルゴリズム(QGA)を提案する。完全グラフ上では、提案手法は真に最適なMaxCut値を一貫して達成し、セミデフィニティプログラミング(SDP)アプローチより優れている。 ErdHos-R'enyiランダムグラフでは、QGAは競合性能を示し、SDP結果の92-96%で中央値の解が得られる。
論文参考訳（メタデータ） (2025-01-02T05:06:16Z)
Optimization by Decoded Quantum Interferometry [42.169154389732036]
Decoded Quantum Interferometry (DQI) という量子アルゴリズムを導入する。有限体上のデータに近似するために、DQIは我々の知るどの時間よりも良い近似比を達成する。
論文参考訳（メタデータ） (2024-08-15T17:47:42Z)
An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-06-11T04:40:05Z)
Recursive Quantum Relaxation for Combinatorial Optimization Problems [3.3053321430025258]
本稿では,既存の量子最適化手法を解法に統一して二項解を求める方法を示す。 MAX-CUT問題における数百ノードの標準ベンチマークグラフの実験は、完全に古典的な方法で行われた。
論文参考訳（メタデータ） (2024-03-04T13:48:21Z)
QNEAT: Natural Evolution of Variational Quantum Circuit Architecture [95.29334926638462]
我々は、ニューラルネットワークの量子対する最も有望な候補として登場した変分量子回路(VQC)に注目した。有望な結果を示す一方で、バレン高原、重みの周期性、アーキテクチャの選択など、さまざまな問題のために、VQCのトレーニングは困難である。本稿では,VQCの重みとアーキテクチャの両方を最適化するために,自然進化にインスパイアされた勾配のないアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-04-14T08:03:20Z)
Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
論文参考訳（メタデータ） (2022-09-27T17:56:15Z)
Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文参考訳（メタデータ） (2021-07-08T17:59:55Z)
Using Quantum Metrological Bounds in Quantum Error Correction: A Simple Proof of the Approximate Eastin-Knill Theorem [77.34726150561087]
本稿では、量子誤り訂正符号の品質と、論理ゲートの普遍的な集合を達成する能力とを結びつける、近似したイージン・クニル定理の証明を示す。我々の導出は、一般的な量子気象プロトコルにおける量子フィッシャー情報に強力な境界を用いる。
論文参考訳（メタデータ） (2020-04-24T17:58:10Z)

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