論文の概要: A quantum central path algorithm for linear optimization
- arxiv url: http://arxiv.org/abs/2311.03977v2
- Date: Wed, 16 Oct 2024 12:11:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-17 13:38:22.437438
- Title: A quantum central path algorithm for linear optimization
- Title(参考訳): 線形最適化のための量子中心経路アルゴリズム
- Authors: Brandon Augustino, Jiaqi Leng, Giacomo Nannicini, Tamás Terlaky, Xiaodi Wu,
- Abstract要約: 中心経路の量子力学的シミュレーションにより線形最適化問題を解くための新しい量子アルゴリズムを提案する。
このアプローチは、$m$制約と$n$変数を含む線形最適化問題を$varepsilon$-optimalityに解くアルゴリズムをもたらす。
標準ゲートモデル(すなわち、量子RAMにアクセスせずに)では、我々のアルゴリズムは少なくとも$$mathcalO left( sqrtm + n textsfnnz (A) fracR_1 を用いてLO問題の高精度な解を得ることができる。
- 参考スコア(独自算出の注目度): 5.450016817940232
- License:
- Abstract: We propose a novel quantum algorithm for solving linear optimization problems by quantum-mechanical simulation of the central path. While interior point methods follow the central path with an iterative algorithm that works with successive linearizations of the perturbed KKT conditions, we perform a single simulation working directly with the nonlinear complementarity equations. This approach yields an algorithm for solving linear optimization problems involving $m$ constraints and $n$ variables to $\varepsilon$-optimality using $\mathcal{O} \left( \sqrt{m + n} \frac{R_{1}}{\varepsilon}\right)$ queries to an oracle that evaluates a potential function, where $R_{1}$ is an $\ell_{1}$-norm upper bound on the size of the optimal solution. In the standard gate model (i.e., without access to quantum RAM) our algorithm can obtain highly-precise solutions to LO problems using at most $$\mathcal{O} \left( \sqrt{m + n} \textsf{nnz} (A) \frac{R_1}{\varepsilon}\right)$$ elementary gates, where $\textsf{nnz} (A)$ is the total number of non-zero elements found in the constraint matrix.
- Abstract(参考訳): 中心経路の量子力学的シミュレーションにより線形最適化問題を解くための新しい量子アルゴリズムを提案する。
内部点法は、摂動KKT条件の逐次線形化を扱う反復アルゴリズムで中心経路を辿るが、非線形相補性方程式を直接扱う単一のシミュレーションを行う。
このアプローチは、$m$制約と$n$変数を含む線形最適化問題を$\varepsilon$-optimalityに$\mathcal{O} \left( \sqrt{m + n} \frac{R_{1}}{\varepsilon}\right)$クエリで解くアルゴリズムを提供する。
標準ゲートモデル(すなわち、量子RAMにアクセスせずに)では、我々のアルゴリズムは、最大$$\mathcal{O} \left( \sqrt{m + n} \textsf{nnz} (A) \frac{R_1}{\varepsilon}\right)$$$小ゲート($\textsf{nnz} (A)$は制約行列にある非ゼロ要素の総数である。
関連論文リスト
- Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
我々は、スペクトルテール条件数である$kappa_ell$を、システムを表す行列の最小特異値と$ell$2の比として定義する。
結果のいくつかの意味と$kappa_ell$の使用は、Conjugateメソッドのきめ細かい解析を直接改善することを含んでいる。
論文 参考訳(メタデータ) (2024-05-09T14:56:49Z) - Structured Semidefinite Programming for Recovering Structured
Preconditioners [41.28701750733703]
正定値$mathbfK を mathbbRd times d$ と $mathrmnnz(mathbfK)$ の 0 でないエントリで与えられるアルゴリズムは、時間内に$epsilon$-optimal diagonal preconditioner を計算する。
我々は、行列辞書近似SDPと呼ばれる半定値プログラムのクラスに対して、新しいアルゴリズムを用いて結果を得る。
論文 参考訳(メタデータ) (2023-10-27T16:54:29Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳(メタデータ) (2023-06-30T08:34:29Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - Efficient quantum algorithms for solving quantum linear system problems [0.0]
拡張行列 $C$ の特異値 0 の右特異ベクトルを求める問題を解くための2つの量子アルゴリズムを提案する。
どちらのアルゴリズムも$kappa $の最適なクエリ複雑性を満たす。
論文 参考訳(メタデータ) (2022-08-14T02:49:26Z) - Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient
Oracle Complexity [15.18055488087588]
上記の凸定式化を$widetildeO(sum_i=1n d_i log (1 /epsilon))$グラデーション計算で$epsilon$-accuracyに最小化するアルゴリズムを与える。
我々の主な技術的貢献は、カットプレーン法とインテリアポイント法を組み合わせた新しい組み合わせにより、各イテレーションで$f_i$項を選択する適応的な手順である。
論文 参考訳(メタデータ) (2022-08-07T20:53:42Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳(メタデータ) (2022-04-13T22:18:47Z) - Learning Stochastic Shortest Path with Linear Function Approximation [74.08819218747341]
線形関数近似を用いた強化学習における最短経路 (SSP) 問題について検討し, 遷移カーネルを未知モデルの線形混合として表現する。
本稿では,線形混合SSPを学習するための新しいアルゴリズムを提案し,このアルゴリズムにより,$tilde O(d B_star1.5sqrtK/c_min)$ regretを実現する。
論文 参考訳(メタデータ) (2021-10-25T08:34:00Z) - Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix
Factorization [49.090785356633695]
非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
論文 参考訳(メタデータ) (2021-06-27T17:25:24Z) - Solving the Robust Matrix Completion Problem via a System of Nonlinear
Equations [28.83358353043287]
低階行列 $L_*$ とスパース行列 $S_*$ をそれらの和 $M=L_*+S_*inmathbbRmtimes n$ の不完全観測から回復することを目的としたロバスト行列完備化の問題を考える。
このアルゴリズムは並列性が高く、大規模な問題に適している。
数値シミュレーションにより、単純な手法は期待通りに動作し、最先端の手法に匹敵することを示した。
論文 参考訳(メタデータ) (2020-03-24T17:28:15Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳(メタデータ) (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。