論文の概要: Copositive programming for mixed-binary quadratic optimization via Ising
solvers
- arxiv url: http://arxiv.org/abs/2207.13630v1
- Date: Wed, 27 Jul 2022 16:47:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-03 07:39:04.738112
- Title: Copositive programming for mixed-binary quadratic optimization via Ising
solvers
- Title(参考訳): isingソルバを用いた混合双対最適化のための共負計画法
- Authors: Robin Brown, David E. Bernal Neira, Davide Venturelli, Marco Pavone
- Abstract要約: ブラックボックスとイジングソルバを用いた混合二項二次プログラムを大域的最適に解くためのフレームワークを提案する。
このハイブリッドフレームワークの古典的な部分は時間であることが保証されており、NPハード問題に適用すると、解の複雑さはイジングソルバが処理するサブルーチンに移る。
- 参考スコア(独自算出の注目度): 24.649182423382353
- 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.
Due to the heuristic and black-box nature of the underlying Ising solvers, many
such approaches have limited optimality guarantees. While some hybrid
algorithms may converge to global optima, their underlying classical algorithms
typically rely on exhaustive search, making it unclear if such algorithmic
scaffolds are primed to take advantage of speed-ups that the Ising solver may
offer. In this paper, we propose a framework for solving mixed-binary quadratic
programs (MBQP) to global optimality using black-box and heuristic Ising
solvers. We show the exactness of a convex copositive reformulation of MBQPs,
which we propose to solve via a hybrid quantum-classical cutting-plane
algorithm. The classical portion of this hybrid framework is guaranteed to be
polynomial time, suggesting that when applied to NP-hard problems, the
complexity of the solution is shifted onto the subroutine handled by the Ising
solver.
- Abstract(参考訳): 近年、量子/量子にインスパイアされた技術は、イジングスピンハミルトニアンの基底状態のおよその探索が可能になった。
このような技術を活用して難しい最適化問題の解決を加速するという約束は、直接転写から既存の最適化アルゴリズムに根ざしたハイブリッド量子古典的アプローチまで、ソリューションプロセスの一部としてIsing問題を統合する方法の探求への関心を高めている。
基礎となるイジングソルバのヒューリスティックでブラックボックスな性質のため、そのようなアプローチの多くは最適化の保証が限られている。
一部のハイブリッドアルゴリズムはグローバル・オプティマに収束するかもしれないが、彼らの基礎となる古典的アルゴリズムは概して徹底的な探索に依存しているため、そのようなアルゴリズム的足場がイジング・ソルバが提供するスピードアップを活用できるかどうかは不明である。
本稿では,ブラックボックスとヒューリスティックイジングの解法を用いて,混合二項二次プログラム(MBQP)を大域的最適に解くための枠組みを提案する。
MBQPの凸共正再構成の正確性を示すとともに,ハイブリッド量子古典的切削平面アルゴリズムを用いて解くことを提案する。
このハイブリッドフレームワークの古典的な部分は多項式時間であることが保証されており、NPハード問題に適用すると、解の複雑さはイジング解法によって処理されるサブルーチンに移る。
関連論文リスト
- Solving non-native combinatorial optimization problems using hybrid
quantum-classical algorithms [0.0]
組合せ最適化は、物流から金融まで幅広い分野に適用可能な、困難な問題である。
量子コンピューティングは、様々なアルゴリズムを用いてこれらの問題を解決するために使われてきた。
この研究は、量子と古典のリソースをハイブリッドなアプローチで統合することで、これらの課題を克服する枠組みを提示している。
論文 参考訳(メタデータ) (2024-03-05T17:46:04Z) - Quantum Optimization: Lagrangian Dual versus QUBO in Solving Constrained
Problems [0.0]
本稿では,ラグランジアン双対性の概念を離散化された断熱量子計算の枠組みに組み込むことにより,制約付き最適化問題の解法を提案する。
回路モデル-フォールトトレラント量子計算の設定において,本手法が回路深さの2次改善を実現し,制約に依存しない回路幅を維持できることを示す。
論文 参考訳(メタデータ) (2023-10-06T19:09:55Z) - 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) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳(メタデータ) (2023-02-24T18:41:48Z) - 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) - An adaptive quantum approximate optimization algorithm for solving
combinatorial problems on a quantum computer [0.0]
量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くハイブリッド変分量子古典アルゴリズムである。
我々は,QAOAの反復バージョンを開発し,特定のハードウェア制約に適応することができる。
アルゴリズムをMax-Cutグラフのクラス上でシミュレートし、標準QAOAよりもはるかに高速に収束することを示す。
論文 参考訳(メタデータ) (2020-05-20T18:00:01Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。