論文の概要: A Copositive Framework for Analysis of Hybrid Ising-Classical Algorithms
- arxiv url: http://arxiv.org/abs/2207.13630v3
- Date: Tue, 23 Jan 2024 01:22:12 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-24 20:19:42.740927
- Title: A Copositive Framework for Analysis of Hybrid Ising-Classical Algorithms
- Title（参考訳）: ハイブリッドイジング古典アルゴリズムの解析のための共陽性フレームワーク
- Authors: Robin Brown, David E. Bernal Neira, Davide Venturelli, Marco Pavone
- Abstract要約: 本稿では,Isingソルバを用いた混合二項二次プログラムの解法におけるハイブリッドアルゴリズムの形式解析について述べる。
本稿では,ハイブリッド量子古典的切削平面アルゴリズムを用いてこの問題を解決することを提案する。
- 参考スコア（独自算出の注目度）: 18.075115172621096
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent years have seen significant advances in quantum/quantum-inspired
technologies capable of approximately searching for the ground state of Ising
spin Hamiltonians. The promise of leveraging such technologies to accelerate
the solution of difficult optimization problems has spurred an increased
interest in exploring methods to integrate Ising problems as part of their
solution process, with existing approaches ranging from direct transcription to
hybrid quantum-classical approaches rooted in existing optimization algorithms.
While it is widely acknowledged that quantum computers should augment classical
computers, rather than replace them entirely, comparatively little attention
has been directed toward deriving analytical characterizations of their
interactions. In this paper, we present a formal analysis of hybrid algorithms
in the context of solving mixed-binary quadratic programs (MBQP) via Ising
solvers. By leveraging an existing completely positive reformulation of MBQPs,
as well as a new strong-duality result, we show the exactness of the dual
problem over the cone of copositive matrices, thus allowing the resulting
reformulation to inherit the straightforward analysis of convex optimization.
We propose to solve this reformulation with a hybrid quantum-classical
cutting-plane algorithm. Using existing complexity results for convex
cutting-plane algorithms, we deduce that the classical portion of this hybrid
framework is guaranteed to be polynomial time. This suggests that when applied
to NP-hard problems, the complexity of the solution is shifted onto the
subroutine handled by the Ising solver.
- Abstract（参考訳）: 近年、量子/量子にインスパイアされた技術は、イジングスピンハミルトニアンの基底状態のおよその探索が可能になった。
このような技術を活用して難しい最適化問題の解決を加速するという約束は、直接転写から既存の最適化アルゴリズムに根ざしたハイブリッド量子古典的アプローチまで、ソリューションプロセスの一部としてIsing問題を統合する方法の探求への関心を高めている。
量子コンピュータは、それらを完全に置き換えるのではなく、古典的コンピュータを強化するべきであると広く認識されているが、その相互作用の分析的特徴付けの導出に比較的注意が向けられている。
本稿では、Isingソルバを用いた混合二項二次プログラム(MBQP)の解法におけるハイブリッドアルゴリズムの形式解析について述べる。
既存のmbqpsの完全正の再構成と新しい強双対性結果を利用することで、共陽性行列の円錐上の双対問題の厳密性を示し、結果として得られる再構成は凸最適化の直接的な解析を継承することができる。
本稿では,ハイブリッド量子古典的切削平面アルゴリズムを用いてこの問題を解決することを提案する。
凸切断平面アルゴリズムの既存の複雑性結果を用いて、このハイブリッドフレームワークの古典的な部分は多項式時間であることが保証されていると推定する。
これはnpハード問題に適用すると、解の複雑さはイジングソルバによって処理されるサブルーチンに移されることを示唆している。
関連論文リスト
- Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search [61.08720171136229]
本稿では,3つの革新的手法のハイブリッド化に基づく問題に対する新しいアルゴリズムSMARTを提案する。
これらの2つの手法は動的プログラミングに基づいており、評価のために選択された連立関係とアルゴリズムの性能の強力な関係を示す。
我々の手法は、問題にアプローチする新しい方法と、その分野に新しいレベルの精度をもたらす。
論文 参考訳（メタデータ） (2024-07-22T23:24:03Z) - Integrating Quantum Algorithms Into Classical Frameworks: A Predictor-corrector Approach Using HHL [0.562479170374811]
我々は、Harrow, Hassidim and Lloyd (HHL) によって提案された方程式の線形系に対するよく知られたアルゴリズムを、直接解法ではなく予測子-相関子に適応させることにより適用する。
この戦略は、多くの古典的アルゴリズムでよく見られる計算コストの高いステップのインテリジェントな省略を可能にし、同時に量子状態の抽出に関連する悪名高い読み出し問題を緩和する。
このアプローチの汎用性は、滑らかな粒子流体力学、プラズマシミュレーション、反応性流れ構成など、様々な分野の応用を通して説明される。
論文 参考訳（メタデータ） (2024-06-28T15:31:10Z) - A hybrid Quantum-Classical Algorithm for Mixed-Integer Optimization in Power Systems [0.0]
量子コンピュータ(QC)を用いた電力系統最適化問題の解法フレームワークを提案する。
我々の指導的応用は、DC Optimal Power Flowを解くために訓練されたニューラルネットワークの最適送信切替と検証である。
論文 参考訳（メタデータ） (2024-04-16T16:11:56Z) - Improving the convergence of an iterative algorithm for solving arbitrary linear equation systems using classical or quantum binary optimization [39.58317527488534]
本稿では,線形システムの解法を提案する。
線形系を二進最適化問題に変換し、元の問題の幾何学からインスピレーションを得る。
問題固有の幾何学の部分的知識を活用することで、元の問題をより小さく独立したサブプロブレムに分解できることを実証する。
論文 参考訳（メタデータ） (2023-09-18T16:51:03Z) - An Optimization-based Deep Equilibrium Model for Hyperspectral Image
Deconvolution with Convergence Guarantees [71.57324258813675]
本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。
新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。
導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
論文 参考訳（メタデータ） (2023-06-10T08:25:16Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳（メタデータ） (2023-04-18T11:57:15Z) - A quantum-inspired tensor network method for constrained combinatorial
optimization problems [5.904219009974901]
本稿では,一般に局所的に制約された最適化問題に対する量子インスパイアされたテンソルネットワークに基づくアルゴリズムを提案する。
我々のアルゴリズムは、興味のある問題に対してハミルトニアンを構築し、量子問題に効果的にマッピングする。
本研究は,本手法の有効性と応用の可能性を示すものである。
論文 参考訳（メタデータ） (2022-03-29T05:44:07Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。
我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
論文 参考訳（メタデータ） (2021-08-18T09:26:17Z) - Polynomial unconstrained binary optimisation inspired by optical
simulation [52.11703556419582]
制約のないバイナリ最適化の問題を解決するために,光コヒーレントIsingマシンにヒントを得たアルゴリズムを提案する。
提案アルゴリズムを既存のPUBOアルゴリズムに対してベンチマークし,その優れた性能を観察する。
タンパク質の折り畳み問題や量子化学問題へのアルゴリズムの適用は、PUBO問題による電子構造問題の近似の欠点に光を当てる。
論文 参考訳（メタデータ） (2021-06-24T16:39:31Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。