論文の概要: A Multilevel Approach For Solving Large-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization
- arxiv url: http://arxiv.org/abs/2408.07793v1
- Date: Wed, 14 Aug 2024 20:06:32 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-16 15:38:42.377733
- Title: A Multilevel Approach For Solving Large-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization
- Title（参考訳）: 雑音ハイブリッド量子近似最適化を用いた大規模QUBO問題の多レベル解法
- Authors: Filip B. Maciejewski, Bao Gia Bach, Maxime Dupont, P. Aaron Lott, Bhuvanesh Sundar, David E. Bernal Neira, Ilya Safro, Davide Venturelli,
- Abstract要約: 既存の量子処理ユニット(QPU)がマルチレベル戦略においてサブソルバとしてどのように機能するかを実験的に検証する。
完全連結な 82$-qubit Sherrington-Kirkpatrick グラフに対して 10$ の近似解を求める。
量子最適化の結果は古典学と比較して解の質に関して競争力がある。
- 参考スコア（独自算出の注目度）: 3.3493770627144004
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum approximate optimization is one of the promising candidates for useful quantum computation, particularly in the context of finding approximate solutions to Quadratic Unconstrained Binary Optimization (QUBO) problems. However, the existing quantum processing units (QPUs) are relatively small, and canonical mappings of QUBO via the Ising model require one qubit per variable, rendering direct large-scale optimization infeasible. In classical optimization, a general strategy for addressing many large-scale problems is via multilevel/multigrid methods, where the large target problem is iteratively coarsened, and the global solution is constructed from multiple small-scale optimization runs. In this work, we experimentally test how existing QPUs perform as a sub-solver within such a multilevel strategy. We combine and extend (via additional classical processing) the recent Noise-Directed Adaptive Remapping (NDAR) and Quantum Relax $\&$ Round (QRR) algorithms. We first demonstrate the effectiveness of our heuristic extensions on Rigetti's transmon device Ankaa-2. We find approximate solutions to $10$ instances of fully connected $82$-qubit Sherrington-Kirkpatrick graphs with random integer-valued coefficients obtaining normalized approximation ratios (ARs) in the range $\sim 0.98-1.0$, and the same class with real-valued coefficients (ARs $\sim 0.94-1.0$). Then, we implement the extended NDAR and QRR algorithms as subsolvers in the multilevel algorithm for $6$ large-scale graphs with at most $\sim 27,000$ variables. The QPU (with classical post-processing steps) is used to find approximate solutions to dozens of problems, at most $82$-qubit, which are iteratively used to construct the global solution. We observe that quantum optimization results are competitive regarding the quality of solutions compared to classical heuristics used as subsolvers within the multilevel approach.
- Abstract（参考訳）: 量子近似最適化は有用な量子計算の候補の1つであり、特に擬似非制約二項最適化(QUBO)問題に対する近似解を見つける文脈において有望である。
しかし、既存の量子処理ユニット(QPU)は比較的小さく、IsingモデルによるQUBOの標準マッピングでは1変数あたり1キュービットが必要であり、直接の大規模最適化は不可能である。
古典的最適化において、多くの大規模問題に対処するための一般的な戦略はマルチレベル/マルチグリッド法であり、そこでは、大きな目標問題が反復的に粗くなり、大域的な解は、複数の小規模最適化実行から構築される。
本研究では,このようなマルチレベル戦略において,既存のQPUがサブソルバとしてどのように機能するかを実験的に検証する。
我々は、最近のNoss-Directed Adaptive Remapping (NDAR)アルゴリズムとQuantum Relax $\&$ Round (QRR)アルゴリズムを組み合わせて拡張する。
我々はまず,リゲッティのトランスモンデバイスAnkaa-2におけるヒューリスティック拡張の有効性を実証した。
正規化近似比 (ARs) が$\sim 0.98-1.0$、実数値係数 (ARs $\sim 0.94-1.0$) のクラスが同じである。
次に,拡張NDARアルゴリズムとQRRアルゴリズムを,最大$\sim 27,000$変数を持つ6ドルの大規模グラフに対して,マルチレベルアルゴリズムのサブソルバとして実装する。
QPU(古典的な後処理ステップを持つ)は、数十の問題の近似解を見つけるために使用され、少なくとも82$-qubitは、グローバルなソリューションを構築するために反復的に使用される。
量子最適化の結果は,マルチレベルアプローチにおける解法として用いられる古典的ヒューリスティックスと比較して,解の質に関して競争力がある。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Variational Quantum Multi-Objective Optimization [5.381539115778766]
本稿では,量子コンピュータ上での離散多目的最適化問題を解くための変分量子最適化アルゴリズムを提案する。
最大5つの目的を持つベンチマーク問題に対して提案アルゴリズムの有効性を示す。
論文 参考訳（メタデータ） (2023-12-21T18:59:21Z) - QAOA with fewer qubits: a coupling framework to solve larger-scale
Max-Cut problem [6.783232060611114]
より大規模なMax-Cut問題を解決するためにQAOA回路を設計するためのフレームワークを提案する。
古典アルゴリズムとQAOAの近似比を仮定して理論的に近似を保証する。
われわれのフレームワークは平均で18ドルと0.950ドルしか消費しない。
論文 参考訳（メタデータ） (2023-07-28T02:06:42Z) - 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) - Analysis of The Vehicle Routing Problem Solved via Hybrid Quantum
Algorithms in Presence of Noisy Channels [0.0]
目的は、最適な効率で一定数の顧客に商品を届けるための車両のルートを計画することである。
固定アンサッツ上の変分量子固有解法を用いて,3都市と4都市を対象とした基本的VRP解法を構築した。
量子アルゴリズムの性能は、どのノイズモデルが使われているかに大きく依存している。
論文 参考訳（メタデータ） (2022-05-13T11:29:12Z) - An evolving objective function for improved variational quantum
optimisation [0.0]
本稿では, Ascending-CVaR と呼ばれる目的関数を導入し,任意の最適化問題に有効であることを示す。
いずれの場合も, CVaR は標準目的関数や Barkoutsos et al (Quantum 2020) の "constant" CVaR よりも優れていた。
提案手法は, 難易度, 難易度, 難易度を問わず, 全ての問題において理想的な状態と高い重複性を実現する。
論文 参考訳（メタデータ） (2021-05-25T09:03:56Z) - Improving the Quantum Approximate Optimization Algorithm with
postselection [0.0]
組合せ最適化は、短期的およびフォールトトレラントな量子コンピュータに想定される主な応用の1つである。
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は3つの正則グラフ上のMaxCut問題に適用される。
理論上界と下界を導いており、満たされた辺の分数の一定(小さい)増加が実際に達成可能であることを示す。
論文 参考訳（メタデータ） (2020-11-10T22:17:50Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。