論文の概要: 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)問題に適用し、次元依存性に関する最良の複雑さを得る。 この複雑性境界は、古典解を生成する既存の古典アルゴリズムや量子アルゴリズムよりも優れている。

関連論文リスト

• Optimization by Decoded Quantum Interferometry [43.55132675053983]
  本稿では,古典的復号化問題に対する古典的最適化問題を減じるための量子アルゴリズムを提案する。 DQIは、既知の量子時間古典アルゴリズムよりも近似比が良いことを示す。
  論文  参考訳（メタデータ） (2024-08-15T17:47:42Z)
• A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm [9.804179673817574]
  古典的近位点法(PPA)に着想を得た量子線形系問題(QLSP)に対する新しい量子アルゴリズムを提案する。 提案手法は,既存のtexttimattQLSP_solverを経由した修正行列の逆変換が可能なメタアルゴリズムとみなすことができる。 ステップサイズ$eta$を慎重に選択することにより、提案アルゴリズムは線形システムに対して、以前のアプローチの適用性を阻害する条件数への依存を軽減するために、効果的に事前条件を定めることができる。
  論文  参考訳（メタデータ） (2024-06-19T23:15:35Z)
• An Efficient Quantum Algorithm for Linear System Problem in Tensor Format [4.264200809234798]
  本稿では,最近のアディバティック・インスパイアされたQLSAの進歩に基づく量子アルゴリズムを提案する。 実装の全体的な複雑さは、その次元において多対数的であることを厳密に示します。
  論文  参考訳（メタデータ） (2024-03-28T20:37:32Z)
• Polynomial-time Solver of Tridiagonal QUBO and QUDO problems with Tensor Networks [41.94295877935867]
  本稿では,3次元非拘束二項最適化(QUBO)問題と準拘束非拘束離散最適化(QUDO)問題を一方の相互作用で解くアルゴリズムを提案する。 提案手法は, 仮想時間進化を適用し, 最大振幅を得るために一連の部分的トレースを行う量子状態のシミュレーションに基づく。
  論文  参考訳（メタデータ） (2023-09-19T10:45:15Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• 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.602276990341246]
  本稿では,不規則高原や局所最適解などの問題を回避し,方程式の線形系を解くための量子アルゴリズムについて述べる。 このアルゴリズムは、他の(容易に可逆な)行列の低ランクな修正である行列の逆を解析的に記述するウッドベリー恒等式に基づいている。 我々は、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)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。