論文の概要: On constant-time quantum annealing and guaranteed approximations for
graph optimization problems
- arxiv url: http://arxiv.org/abs/2202.01636v1
- Date: Thu, 3 Feb 2022 15:23:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-26 22:56:18.080075
- Title: On constant-time quantum annealing and guaranteed approximations for
graph optimization problems
- Title（参考訳）: グラフ最適化問題に対する定数時間量子アニールと保証近似について
- Authors: Arthur Braida, Simon Martiel, Ioan Todinca
- Abstract要約: 量子アニーリング(Quantum Annealing, QA)は、量子系の連続的な進化が目的関数の最小値を見つけるために用いられる計算フレームワークである。
本稿では、理論物理学、リーブ・ロビンソン境界(LR)から借用した手法を用いて、短時間の量子アニールにより定数係数の近似比が保証されることを示す新しいツールを開発する。
我々の結果は、異なるが関連するQAOA(量子最適化アルゴリズム)フレームワークで得られたよく知られたものと類似している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum Annealing (QA) is a computational framework where a quantum system's
continuous evolution is used to find the global minimum of an objective
function over an unstructured search space. It can be seen as a general
metaheuristic for optimization problems, including NP-hard ones if we allow an
exponentially large running time. While QA is widely studied from a heuristic
point of view, little is known about theoretical guarantees on the quality of
the solutions obtained in polynomial time.
In this paper we use a technique borrowed from theoretical physics, the
Lieb-Robinson (LR) bound, and develop new tools proving that short, constant
time quantum annealing guarantees constant factor approximations ratios for
some optimization problems when restricted to bounded degree graphs.
Informally, on bounded degree graphs the LR bound allows us to retrieve a
(relaxed) locality argument, through which the approximation ratio can be
deduced by studying subgraphs of bounded radius.
We illustrate our tools on problems MaxCut and Maximum Independent Set for
cubic graphs, providing explicit approximation ratios and the runtimes needed
to obtain them. Our results are of similar flavor to the well-known ones
obtained in the different but related QAOA (quantum optimization algorithms)
framework.
Eventually, we discuss theoretical and experimental arguments for further
improvements.
- Abstract（参考訳）: 量子アニーリング(quantum annealing, qa)は、非構造化探索空間上の目的関数の極大最小値を求めるために量子システムの連続進化を用いる計算フレームワークである。
指数関数的に大きな実行時間を許すと、NPハードを含む最適化問題に対する一般的なメタヒューリスティックと見なすことができる。
QAはヒューリスティックの観点から広く研究されているが、多項式時間で得られる解の品質に関する理論的保証についてはほとんど知られていない。
本稿では,理論物理学,リーブ・ロビンソン境界(LR)から借用した手法を用いて,有界次数グラフに制限された場合の最適化問題に対する定数係数近似比が一定であることを示す新しいツールを開発する。
非公式に、有界次数グラフ上の lr 境界は、有界半径の部分グラフを研究することによって近似比を導出できる(相対的な)局所性引数を取得することができる。
我々は、立方体グラフに対するMaxCutとMaximum Independent Setの問題に関するツールを説明し、それらを得るために必要な明示的な近似比とランタイムを提供する。
我々の結果は、異なるが関連するQAOA(量子最適化アルゴリズム)フレームワークで得られたよく知られたものと類似している。
最終的に、さらなる改善の理論的および実験的議論を議論する。
関連論文リスト
- Solving QUBOs with a quantum-amenable branch and bound method [0.3749861135832072]
本研究では,2次非制約二項最適化問題に対して,古典分枝および有界解法について記述し,実験的に検証する。
本稿では,Isingモデルに対して提案した文献から,低コストで実装可能なバウンダリを利用する。
本稿では,ソルバ性能向上に使用される高性能コンピューティングとオペレーション研究の様々な技術について詳述する。
論文 参考訳（メタデータ） (2024-07-29T17:13:01Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - Tight Lieb-Robinson Bound for approximation ratio in Quantum Annealing [0.0]
本稿では,QAのパラメータ化バージョンを新たに導入し,アルゴリズムの正確な1局所解析を実現する。
1局所解析を持つ線形スケジュールQAは0.7020以上の近似比を達成し、既知の1局所アルゴリズムよりも優れていることを示す。
論文 参考訳（メタデータ） (2023-11-21T17:15:21Z) - Local to Global: A Distributed Quantum Approximate Optimization
Algorithm for Pseudo-Boolean Optimization Problems [7.723735038335632]
量子近似最適化アルゴリズム(QAOA)は、量子超越性を実証するための有望な候補と考えられている。
量子ビットの可用性が制限され、コヒーレンス時間制限がQAOAに挑戦し、大規模な擬ブール問題を解く。
本稿では,これを単純化したIsingモデルに変換することで,一般の擬似ブール問題を解く分散QAOAを提案する。
論文 参考訳（メタデータ） (2023-10-08T08:07:11Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。
我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
論文 参考訳（メタデータ） (2022-02-10T18:59:52Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳（メタデータ） (2022-01-06T21:02:30Z) - Predicting parameters for the Quantum Approximate Optimization Algorithm
for MAX-CUT from the infinite-size limit [0.05076419064097732]
推定次数$d$のランダムエルドス・レーニグラフに適用したMAX-CUT上でのQAOAの性能を評価するための明示的なアルゴリズムを提案する。
この解析により、エルドス・レーニグラフ上のMAX-CUTのQAOAパラメータとシェリントン・カークパトリックモデルとの明示的なマッピングが得られる。
論文 参考訳（メタデータ） (2021-10-20T17:58:53Z) - Empirical performance bounds for quantum approximate optimization [0.27998963147546135]
パフォーマンスバウンダリの定量化は、QAOAが現実のアプリケーションの解決に有効である可能性についての洞察を提供する。
QAOA は、ほとんどのグラフに対して有界な Goemans-Williamson 近似比を超える。
得られたデータセットは、QAOAパフォーマンスに関する経験的バウンダリを確立するためのベンチマークとして提示される。
論文 参考訳（メタデータ） (2021-02-12T23:12:09Z) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
論文 参考訳（メタデータ） (2020-06-12T00:32:21Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳（メタデータ） (2020-04-25T05:45:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。