論文の概要: 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)$は制約行列にある非ゼロ要素の総数である。

関連論文リスト

• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problems with Optimal Iteration Complexity [2.815239177328595]
  凸凹極小最適化問題の解法として,Lipschitz-free Cubal regularization (LF-CR)アルゴリズムを提案する。 また,この問題のパラメータを必要としない完全パラメータフリー立方正則化(FF-CR)アルゴリズムを提案する。 我々の知る限り、FF-CRアルゴリズムは凸凹極小最適化問題の解法として初めて完全にパラメータフリーな2次アルゴリズムである。
  論文  参考訳（メタデータ） (2024-07-04T01:46:07Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Efficient quantum linear solver algorithm with detailed running costs [0.0]
  量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。 我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
  論文  参考訳（メタデータ） (2023-05-19T00:07:32Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• 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-classical algorithms for skewed linear systems with optimized Hadamard test [10.386115383285288]
  我々は、過度に決定された場合と過度に決定された場合のスキュード線形系に対するハイブリッド量子古典アルゴリズムについて論じる。 我々の入力モデルは、線形系を定義する行列の列または行が多対数深さの量子回路によって与えられるようなものである。 本稿では,各次元における実時間多対数性を持つ分解線形系の特殊ケースに対するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-28T12:59:27Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• 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)

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

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