論文の概要: Efficient Use of Quantum Linear System Algorithms in Interior Point
Methods for Linear Optimization
- arxiv url: http://arxiv.org/abs/2205.01220v2
- Date: Fri, 10 Feb 2023 19:25:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-14 20:23:27.626915
- Title: Efficient Use of Quantum Linear System Algorithms in Interior Point
Methods for Linear Optimization
- Title(参考訳): 線形最適化のための内部点法における量子線形系アルゴリズムの有効利用
- Authors: Mohammadhossein Mohammadisiahroudi, Ramin Fakhimi, Tam\'as Terlaky
- Abstract要約: 線形最適化問題を解くために、非現実的な量子内点法を開発した。
また、量子ソルバの過度な時間なしで、反復リファインメントによって正確な解を得る方法についても論じる。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum computing has attracted significant interest in the optimization
community because it potentially can solve classes of optimization problems
faster than conventional supercomputers. Several researchers proposed quantum
computing methods, especially Quantum Interior Point Methods (QIPMs), to solve
convex optimization problems, such as Linear Optimization, Semidefinite
Optimization, and Second-order Cone Optimization problems. Most of them have
applied a Quantum Linear System Algorithm at each iteration to compute a Newton
step. However, using quantum linear solvers in QIPMs comes with many
challenges, such as having ill-conditioned systems and the considerable error
of quantum solvers. This paper investigates how one can efficiently use quantum
linear solvers in QIPMs. Accordingly, an Inexact Infeasible Quantum Interior
Point Method is developed to solve linear optimization problems. We also
discuss how can we get an exact solution by Iterative Refinement without
excessive time of quantum solvers. Finally, computational results with QISKIT
implementation of our QIPM using quantum simulators are analyzed.
- Abstract(参考訳): 量子コンピューティングは、従来のスーパーコンピュータよりも早く最適化問題のクラスを解くことができるため、最適化コミュニティにおいて大きな関心を集めている。
量子コンピューティング手法、特に量子内点法(QIPM)を提案し、線形最適化、半有限最適化、二階錐最適化といった凸最適化問題を解く。
彼らのほとんどは、ニュートンステップを計算するために各イテレーションで量子線形システムアルゴリズムを適用した。
しかし、QIPMにおける量子線形解法の使用には、不条件のシステムや量子解法のかなりの誤差など、多くの課題が伴う。
本稿では,量子線形解法をQIPMで効率的に利用する方法を検討する。
そこで, 線形最適化問題を解くために, 不正確な量子内点法を開発した。
また、量子ソルバの過度な時間なしで、反復リファインメントによって正確な解を得る方法についても論じる。
最後に,量子シミュレータを用いたQIPMのQISKIT実装による計算結果を解析した。
関連論文リスト
- Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳(メタデータ) (2023-04-18T11:57:15Z) - An Inexact Feasible Quantum Interior Point Method for Linearly
Constrained Quadratic Optimization [0.0]
量子線形システムアルゴリズム(QLSA)は、線形システムの解法に依存するアルゴリズムを高速化する可能性がある。
本研究では, 線形制約付き2次最適化問題の解法において, 実効性のないQIPM(Inexact-Feasible QIPM)を提案する。
論文 参考訳(メタデータ) (2023-01-13T01:36:13Z) - NP-hard but no longer hard to solve? Using quantum computing to tackle
optimization problems [1.1470070927586016]
量子コンピュータを用いて最適化問題を解く量子最適化の分野について論じる。
適切なユースケースを通じてこれを実証し、量子コンピュータの現在の品質について論じる。
本稿では、最近の量子最適化のブレークスルーと現状と今後の方向性について論じる。
論文 参考訳(メタデータ) (2022-12-21T12:56:37Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - 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) - Efficient Classical Computation of Quantum Mean Values for Shallow QAOA
Circuits [15.279642278652654]
浅いQAOA回路の量子ビット数と線形にスケールするグラフ分解に基づく古典的アルゴリズムを提案する。
我々の結果は、QAOAによる量子アドバンテージの探索だけでなく、NISQプロセッサのベンチマークにも有用である。
論文 参考訳(メタデータ) (2021-12-21T12:41:31Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。
その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文 参考訳(メタデータ) (2021-06-24T20:16:02Z) - Filtering variational quantum algorithms for combinatorial optimization [0.0]
本稿では、フィルタ演算子を用いて最適解への高速で信頼性の高い収束を実現する変分量子固有解法(F-VQE)を提案する。
また、量子コンピュータに必要な量子ビット数を減らすために因果錐を用いる方法についても検討する。
論文 参考訳(メタデータ) (2021-06-18T11:07:33Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳(メタデータ) (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。