論文の概要: Quantum speedups for linear programming via interior point methods
- arxiv url: http://arxiv.org/abs/2311.03215v1
- Date: Mon, 6 Nov 2023 16:00:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-07 13:46:45.492629
- Title: Quantum speedups for linear programming via interior point methods
- Title（参考訳）: インテリアポイント法による線形プログラミングのための量子スピードアップ
- Authors: Simon Apers and Sander Gribling
- Abstract要約: 本稿では,$d$変数上の不等式制約で線形プログラムを解く量子アルゴリズムについて述べる。
我々のアルゴリズムは、リーとシドフォードの最先端インテリアポイント法におけるニュートンステップを高速化する。
- 参考スコア（独自算出の注目度）: 2.07180164747172
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We describe a quantum algorithm based on an interior point method for solving
a linear program with $n$ inequality constraints on $d$ variables. The
algorithm explicitly returns a feasible solution that is $\epsilon$-close to
optimal, and runs in time $\sqrt{n}\,
\mathrm{poly}(d,\log(n),\log(1/\varepsilon))$ which is sublinear for tall
linear programs (i.e., $n \gg d$). Our algorithm speeds up the Newton step in
the state-of-the-art interior point method of Lee and Sidford [FOCS '14]. This
requires us to efficiently approximate the Hessian and gradient of the barrier
function, and these are our main contributions.
To approximate the Hessian, we describe a quantum algorithm for the spectral
approximation of $A^T A$ for a tall matrix $A \in \mathbb R^{n \times d}$. The
algorithm uses leverage score sampling in combination with Grover search, and
returns a $\delta$-approximation by making $O(\sqrt{nd}/\delta)$ row queries to
$A$. This generalizes an earlier quantum speedup for graph sparsification by
Apers and de Wolf [FOCS '20]. To approximate the gradient, we use a recent
quantum algorithm for multivariate mean estimation by Cornelissen, Hamoudi and
Jerbi [STOC '22]. While a naive implementation introduces a dependence on the
condition number of the Hessian, we avoid this by pre-conditioning our random
variable using our quantum algorithm for spectral approximation.
- Abstract（参考訳）: 本稿では,$d$変数上の不等式制約で線形プログラムを解くための内部点法に基づく量子アルゴリズムについて述べる。
このアルゴリズムは、最適に$\epsilon$-closeである実現可能な解を明示的に返し、時間$\sqrt{n}\, \mathrm{poly}(d,\log(n),\log(1/\varepsilon)$で実行し、これは背の高い線形プログラム(例えば$n \gg d$)のサブ線形である。
我々のアルゴリズムは,lee と sidford [focs '14] の最先端インテリアポイント法においてニュートンステップを高速化する。
これにより、障壁関数のヘシアンと勾配を効率的に近似する必要があり、これらが主な貢献である。
ヘッシアンを近似するために、高行列 $a \in \mathbb r^{n \times d}$ に対するスペクトル近似 $a^t a$ の量子アルゴリズムを記述する。
このアルゴリズムはGrover検索と組み合わせてスコアサンプリングを利用し、$O(\sqrt{nd}/\delta)$行クエリを$A$にすることで$\delta$-approximationを返す。
これは apers と de wolf [focs '20] によるグラフスパーシフィケーションの初期の量子速度アップを一般化する。
この勾配を近似するために、Cornelissen, Hamoudi, Jerbi [STOC '22] による多変量平均推定に最近の量子アルゴリズムを用いる。
直観的な実装はヘッセンの条件数に依存するが、スペクトル近似の量子アルゴリズムを用いて確率変数を事前条件付けすることでこれを回避している。
関連論文リスト
- Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。
また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-04T11:03:48Z) - Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning [10.690769339903941]
我々は、$Ax = b$という形式の線形系を解くための、新しい条件付き反復法のクラスを示す。
提案手法は,低ランクなNystr"om近似をスパースランダムスケッチを用いて$A$に構築することに基づいている。
我々は、我々の手法の収束が自然平均条件数$A$に依存することを証明し、Nystr"om近似のランクとして改善する。
論文 参考訳（メタデータ） (2024-05-09T15:53:43Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - A Quantum Approximation Scheme for k-Means [0.16317061277457]
QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。
我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。
教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
論文 参考訳（メタデータ） (2023-08-16T06:46:37Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - 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 speedups for convex dynamic programming [6.643082745560234]
本稿では,凸値関数を用いた動的プログラミング問題を解く量子アルゴリズムを提案する。
提案アルゴリズムは、値関数の量子力学的表現を時間$O(T gammadTmathrmpolylog(N,(T/varepsilon)d))$で出力する。
論文 参考訳（メタデータ） (2020-11-23T19:00:11Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - An improved quantum-inspired algorithm for linear regression [15.090593955414137]
量子行列反転アルゴリズムに類似した線形回帰の古典的アルゴリズムを提案する。
量子コンピュータは、このQRAMデータ構造設定において、線形回帰の最大12倍の高速化を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-15T17:58:25Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。