論文の概要: An Inexact Feasible Quantum Interior Point Method for Linearly
Constrained Quadratic Optimization
- arxiv url: http://arxiv.org/abs/2301.05357v1
- Date: Fri, 13 Jan 2023 01:36:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-16 15:18:46.363801
- Title: An Inexact Feasible Quantum Interior Point Method for Linearly
Constrained Quadratic Optimization
- Title(参考訳): 線形制約付き二次最適化のための不可分な量子内部点法
- Authors: Zeguan Wu, Mohammadhossein Mohammadisiahroudi, Brandon Augustino, Xiu
Yang and Tam\'as Terlaky
- Abstract要約: 量子線形システムアルゴリズム(QLSA)は、線形システムの解法に依存するアルゴリズムを高速化する可能性がある。
本研究では, 線形制約付き2次最適化問題の解法において, 実効性のないQIPM(Inexact-Feasible QIPM)を提案する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum linear system algorithms (QLSAs) have the potential to speed up
algorithms that rely on solving linear systems. Interior Point Methods (IPMs)
yield a fundamental family of polynomial-time algorithms for solving
optimization problems. IPMs solve a Newton linear system at each iteration to
find the search direction, and thus QLSAs can potentially speed up IPMs. Due to
the noise in contemporary quantum computers, such quantum-assisted IPM (QIPM)
only allows an inexact solution for the Newton linear system. Typically, an
inexact search direction leads to an infeasible solution. In our work, we
propose an Inexact-Feasible QIPM (IF-QIPM) and show its advantage in solving
linearly constrained quadratic optimization problems. We also apply the
algorithm to $\ell_1$-norm soft margin support vector machine (SVM) problems
and obtain the best complexity regarding dependence on dimension. This
complexity bound is better than any existing classical or quantum algorithm
that produces a classical solution.
- Abstract(参考訳): 量子線形システムアルゴリズム(QLSA)は、線形システムの解法に依存するアルゴリズムを高速化する可能性がある。
内部点法 (IPMs) は最適化問題を解くための多項式時間アルゴリズムの基本的なファミリーである。
IPMは各イテレーションでニュートン線形システムを解いて探索方向を見つけるため、QLSAはIPMを高速化する可能性がある。
現代の量子コンピュータのノイズのため、量子アシスト型IPM (QIPM) はニュートン線形系の不正確な解しか得られない。
通常、不正確な探索方向は実現不可能な解決策につながる。
本研究では, 線形制約付き2次最適化問題の解法において, 実効性のないQIPM (IF-QIPM) を提案する。
また、このアルゴリズムを$\ell_1$-norm soft margin support vector machine (svm)問題に適用し、次元依存性に関する最良の複雑さを得る。
この複雑性境界は、古典解を生成する既存の古典アルゴリズムや量子アルゴリズムよりも優れている。
関連論文リスト
- Limitations for Quantum Algorithms to Solve Turbulent and Chaotic
Systems [0.5735035463793008]
非線形力学系を解くための量子コンピュータの限界について検討する。
正規化解ベクトルを近似した量子状態を出力することを目的とした量子アルゴリズムに対して、重要な制限を提供する。
論文 参考訳(メタデータ) (2023-07-13T11:06:02Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Time-marching based quantum solvers for time-dependent linear
differential equations [3.1952399274829775]
タイムマーチング戦略は、古典コンピュータ上の時間依存微分方程式を解く自然な戦略である。
時間マーチングに基づく量子解法は、時間ステップ数に関して指数関数的に成功確率を逸脱させる可能性があることを示す。
これは、量子線型系アルゴリズムに基づくものに代わる量子微分方程式の解法を設計する道を提供する。
論文 参考訳(メタデータ) (2022-08-14T23:49:19Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳(メタデータ) (2022-05-24T03:49:10Z) - Efficient Use of Quantum Linear System Algorithms in Interior Point
Methods for Linear Optimization [0.0]
線形最適化問題を解くために、非現実的な量子内点法を開発した。
また、量子ソルバの過度な時間なしで、反復リファインメントによって正確な解を得る方法についても論じる。
論文 参考訳(メタデータ) (2022-05-02T21:30:56Z) - A near-term quantum algorithm for solving linear systems of equations
based on the Woodbury identity [0.0]
本稿では,不規則高原や局所最適解などの問題を回避し,方程式の線形系を解くための量子アルゴリズムについて述べる。
このアルゴリズムは、他の(容易に可逆な)行列の低ランクな修正である行列の逆を解析的に記述するウッドベリー恒等式に基づいている。
我々は、IBMのオークランド量子コンピュータを用いて、2%の誤差で1600万以上の方程式を解いたシステムの内部積を推定する。
論文 参考訳(メタデータ) (2022-05-02T04:32:01Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳(メタデータ) (2022-02-17T18:59:20Z) - Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations [0.22940141855172036]
アルゴリズムの複雑さは$O(rm polylog(n/epsilon))$であり、これは次元$n$の最適古典アルゴリズムよりも指数関数的に改善される。
我々のアルゴリズムは指数関数的にQNSEの解を加速し、あらゆる非線形問題に適用できる。
論文 参考訳(メタデータ) (2021-12-03T00:27:16Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。
プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
論文 参考訳(メタデータ) (2021-11-30T12:21:41Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳(メタデータ) (2021-05-06T17:59:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。