論文の概要: Quantum Optimization: Lagrangian Dual versus QUBO in Solving Constrained
Problems
- arxiv url: http://arxiv.org/abs/2310.04542v1
- Date: Fri, 6 Oct 2023 19:09:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-12 17:50:43.140649
- Title: Quantum Optimization: Lagrangian Dual versus QUBO in Solving Constrained
Problems
- Title(参考訳): 量子最適化:制約問題の解法におけるラグランジアン双対QUBO
- Authors: Einar Gabbassov, Gili Rosenberg, Artur Scherer
- Abstract要約: 本稿では,ラグランジアン双対性の概念を離散化された断熱量子計算の枠組みに組み込むことにより,制約付き最適化問題の解法を提案する。
回路モデル-フォールトトレラント量子計算の設定において,本手法が回路深さの2次改善を実現し,制約に依存しない回路幅を維持できることを示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose an approach to solving constrained combinatorial optimization
problems based on embedding the concept of Lagrangian duality into the
framework of discretized adiabatic quantum computation (DAQC). Within the
setting of circuit-model fault-tolerant quantum computation, we present
numerical evidence that our approach achieves a quadratic improvement in
circuit depth and maintains a constraint-independent circuit width, in contrast
to the prevalent approach of solving constrained problems via reformulations
based on the quadratic unconstrained binary optimization (QUBO) formalism. Our
study includes a detailed analysis of the limitations and challenges
encountered when using QUBO for constrained optimization in both classical and
quantum contexts. While the focus of the present study is deep quantum circuits
allowing pre-tuned adiabatic schedules, our proposed methodology is also
directly applicable to variational algorithms suitable for implementations on
noisy intermediate-scale quantum (NISQ) devices, such as the quantum
approximate optimization algorithm (QAOA). Our findings are illustrated by
benchmarking the Lagrangian dual approach against the QUBO approach using the
NP-complete 0-1 knapsack problem.
- Abstract(参考訳): 本稿では, 離散化断熱量子計算(DAQC)の枠組みにラグランジアン双対性の概念を組み込んだ制約付き組合せ最適化問題の解法を提案する。
回路モデル-フォールトトレラント量子計算の設定において,2次非拘束二元最適化(QUBO)の形式に基づくリフォームによる制約問題の解法とは対照的に,回路深さの2次改善を実現し,制約非依存の回路幅を維持するという数値的証拠を示す。
本研究は、quboを用いた古典的および量子的文脈における制約付き最適化の限界と課題の詳細な分析を含む。
本研究の焦点は、事前調整された断熱スケジュールを実現するディープ量子回路であるが、提案手法は、量子近似アルゴリズム(QAOA)のようなノイズの多い中間規模量子(NISQ)デバイスの実装に適した変分アルゴリズムにも直接適用可能である。
NP完全0-1knapsack問題を用いて,QUBO法に対するラグランジアン双対アプローチのベンチマークを行った。
関連論文リスト
- Hybrid Quantum Algorithms integrating QAOA, Penalty Dephasing and Zeno
Effect for Solving Binary Optimization Problems with Multiple Constraints [5.259170150405252]
本稿では,制約のサブセットを解決するために標準イジング・ハミルトニアン(Ising Hamiltonian)を併用したハイブリッドフレームワークを提案する。
これらの非Ising制約の解決は、ペナルティの軽視または量子ゼノ効果によって達成される。
論文 参考訳(メタデータ) (2023-05-14T03:49:10Z) - Quantum annealing with inequality constraints: the set cover problem [0.0]
本稿では,複数の不等式制約を持つ集合被覆問題を量子アニール上で解くための2つの新しい手法を提案する。
第1の方法は拡張ラグランジアン法を用いて制約を表現し、第2の方法は高階バイナリ最適化(HUBO)を用いる。
どちらのアプローチも、D-Wave量子アニールの不等式制約の問題を解くために、スラック変数で標準的なアプローチより優れている。
論文 参考訳(メタデータ) (2023-02-22T07:39:51Z) - Constrained Optimization via Quantum Zeno Dynamics [23.391640416533455]
量子ゼノダイナミクスを用いて、不等式を含む複数の任意の制約で最適化問題を解く手法を提案する。
量子最適化のダイナミクスは、フォールトトレラントな量子コンピュータ上の制約内部分空間に効率的に制限できることを示す。
論文 参考訳(メタデータ) (2022-09-29T18:00:40Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳(メタデータ) (2022-02-17T18:59:20Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。
我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
論文 参考訳(メタデータ) (2021-08-18T09:26:17Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。
その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文 参考訳(メタデータ) (2021-06-24T20:16:02Z) - Polynomial unconstrained binary optimisation inspired by optical
simulation [52.11703556419582]
制約のないバイナリ最適化の問題を解決するために,光コヒーレントIsingマシンにヒントを得たアルゴリズムを提案する。
提案アルゴリズムを既存のPUBOアルゴリズムに対してベンチマークし,その優れた性能を観察する。
タンパク質の折り畳み問題や量子化学問題へのアルゴリズムの適用は、PUBO問題による電子構造問題の近似の欠点に光を当てる。
論文 参考訳(メタデータ) (2021-06-24T16:39:31Z) - Quantum constraint learning for quantum approximate optimization
algorithm [0.0]
本稿では,探索部分空間を厳しく制約するミキサーハミルトンを学習するための量子機械学習手法を提案する。
学習したユニタリを直接適応可能なアンサッツを使用してQAOAフレームワークにプラグインすることができる。
また,Wasserstein距離を用いた近似最適化アルゴリズムの性能を,制約なしで評価する直感的計量法を開発した。
論文 参考訳(メタデータ) (2021-05-14T11:31:14Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。
我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。
すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
論文 参考訳(メタデータ) (2020-10-01T18:14:11Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳(メタデータ) (2020-03-11T13:52:41Z) - Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical
and Quantum Computers [3.04585143845864]
本稿では,2次最適化問題に対する現行手法の適用性を高めるために,分解に基づくアプローチを提案する。
我々は、乗算器の交互方向法(ADMM)が、MBOを二項制約のない問題(量子アルゴリズムで解ける)に分割できることを示した。
提案手法の有効性は,Qiskit で実装された量子回路上での VQE と QAOA を用いたシミュレーションにより,いくつかの最適化問題に対して得られた数値結果によって示される。
論文 参考訳(メタデータ) (2020-01-07T14:43:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。