論文の概要: Mixed Integer Linear Programming Solver Using Benders Decomposition
Assisted by Neutral Atom Quantum Processor
- arxiv url: http://arxiv.org/abs/2402.05748v1
- Date: Thu, 8 Feb 2024 15:33:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-09 14:28:33.149183
- Title: Mixed Integer Linear Programming Solver Using Benders Decomposition
Assisted by Neutral Atom Quantum Processor
- Title(参考訳): 中性原子量子プロセッサを用いたブレンダー分解を用いた混合整数線形計画法
- Authors: M.Yassine Naghmouchi and Wesley da Silva Coelho
- Abstract要約: 本稿では、MILP(Mixed Linear Programming)を解くためのハイブリッド古典量子法を提案する。
我々は、MILPをマスター問題(MP)とサブプロブレム(SP)に分割するためにベンダー分解(BD)を適用する。
我々の知る限り、この研究は、BDを通してMILPを解くための、自動化された問題に依存しないフレームワークを開発する際に、中性原子量子プロセッサを利用する最初のものである。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper presents a new hybrid classical-quantum approach to solve Mixed
Integer Linear Programming (MILP) using neutral atom quantum computations. We
apply Benders decomposition (BD) to segment MILPs into a master problem (MP)
and a subproblem (SP), where the MP is addressed using a neutral-atom device,
after being transformed into a Quadratic Unconstrained Binary Optimization
(QUBO) model. To solve the QUBO, we develop a heuristic for atom register
embedding and apply Quantum Approximate Optimization Algorithm (QAOA) for pulse
shaping. In addition, we implement a Proof of Concept (PoC) that outperforms
existing solutions. We also conduct preliminary numerical results: in a series
of small MILP instances our algorithm identifies over 95\% of feasible
solutions of high quality, outperforming classical BD approaches where the MP
is solved using simulated annealing. To the best of our knowledge, this work is
the first to utilize a neutral atom quantum processor in developing an
automated, problem-agnostic framework for solving MILPs through BD.
- Abstract(参考訳): 本稿では,中性原子量子計算を用いたMILP(Mixed Integer Linear Programming)の解法を提案する。
そこで,我々はBenders decomposition (BD) を用いてMILPをマスター問題 (MP) とサブプロブレム (SP) に分割し,MPを準非拘束バイナリ最適化 (QUBO) モデルに変換した後,中性原子デバイスを用いて対処する。
QUBOを解くために、原子レジスタ埋め込みのためのヒューリスティックを開発し、パルス整形のための量子近似最適化アルゴリズム(QAOA)を適用した。
さらに、既存のソリューションよりも優れたPoC(Proof of Concept)を実装します。
シミュレーションアニーリングを用いてMPを解いた古典的BD手法よりも優れた,高品質な実現可能な解の95%以上を,我々のアルゴリズムが同定する。
我々の知る限り、この研究は、BDを通してMILPを解くための、自動化された問題に依存しないフレームワークを開発する際に、中性原子量子プロセッサを利用する最初のものである。
関連論文リスト
- A Universal Quantum Algorithm for Weighted Maximum Cut and Ising
Problems [0.0]
本稿では,二項問題の近似解を計算するためのハイブリッド量子古典アルゴリズムを提案する。
我々は、重み付き最大カットまたはイジング・ハミルトン演算子をブロック符号化するユニタリおよびエルミート演算子を実装するために浅深さ量子回路を用いる。
この作用素の変動量子状態への期待を測定すると、量子系の変動エネルギーが得られる。
論文 参考訳(メタデータ) (2023-06-10T23:28:13Z) - An Optimization-based Deep Equilibrium Model for Hyperspectral Image
Deconvolution with Convergence Guarantees [71.57324258813675]
本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。
新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。
導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
論文 参考訳(メタデータ) (2023-06-10T08:25:16Z) - Efficient MILP Decomposition in Quantum Computing for ReLU Network
Robustness [2.854196251981274]
本研究では,MILP(Mixed-Integer Linear Programming)の2つの分解法について検討した。
我々は、元の問題をより小さなサブプロブレムに分割することに集中し、量子古典的ハードウェアのアプローチを組み合わせて反復的に解決する。
実験の結果,従来の量子アニール法やゲートベース量子コンピュータと比較して最大90%の量子ビットを削減できることがわかった。
論文 参考訳(メタデータ) (2023-04-30T13:10:56Z) - A hybrid quantum-classical algorithm for multichannel quantum scattering
of atoms and molecules [62.997667081978825]
原子と分子の衝突に対するシュリンガー方程式を解くためのハイブリッド量子古典アルゴリズムを提案する。
このアルゴリズムはコーン変分原理の$S$-matrixバージョンに基づいており、基本散乱$S$-matrixを計算する。
大規模多原子分子の衝突をシミュレートするために,アルゴリズムをどのようにスケールアップするかを示す。
論文 参考訳(メタデータ) (2023-04-12T18:10:47Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
波長割当問題を解くための量子インスピレーションアルゴリズムを提案し,開発する。
本研究は,電気通信における現実的な問題に対する量子インスパイアされたアルゴリズムの活用の道筋をたどるものである。
論文 参考訳(メタデータ) (2022-11-01T07:52:47Z) - Optimization of Robot Trajectory Planning with Nature-Inspired and
Hybrid Quantum Algorithms [0.0]
産業規模でロボット軌道計画問題を解く。
我々のエンドツーエンドソリューションは、高度に多目的なランダムキーアルゴリズムとモデル積み重ねとアンサンブル技術を統合している。
我々は、後者が我々のより大きなパイプラインにどのように統合され、問題に対する量子対応ハイブリッドソリューションを提供するかを示す。
論文 参考訳(メタデータ) (2022-06-08T02:38:32Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳(メタデータ) (2022-02-17T18:59:20Z) - Hybrid Quantum-Classical Multi-cut Benders Approach with a Power System
Application [0.0]
単位コミット(UC)問題に対する量子古典解(HQC)が提示される。
D-Wave Advantage 4.1 Quantum annealerを用いて提案手法の有効性と計算可能性を示す。
論文 参考訳(メタデータ) (2021-12-10T16:16:09Z) - Polynomial unconstrained binary optimisation inspired by optical
simulation [52.11703556419582]
制約のないバイナリ最適化の問題を解決するために,光コヒーレントIsingマシンにヒントを得たアルゴリズムを提案する。
提案アルゴリズムを既存のPUBOアルゴリズムに対してベンチマークし,その優れた性能を観察する。
タンパク質の折り畳み問題や量子化学問題へのアルゴリズムの適用は、PUBO問題による電子構造問題の近似の欠点に光を当てる。
論文 参考訳(メタデータ) (2021-06-24T16:39:31Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。