論文の概要: Quantum Algorithms for the Pathwise Lasso
- arxiv url: http://arxiv.org/abs/2312.14141v1
- Date: Thu, 21 Dec 2023 18:57:54 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-22 13:30:14.872289
- Title: Quantum Algorithms for the Pathwise Lasso
- Title（参考訳）: パスワイズラッソのための量子アルゴリズム
- Authors: Jo\~ao F. Doriguello, Debbie Lim, Chi Seng Pun, Patrick Rebentrost,
Tushar Vaidya
- Abstract要約: 古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。
我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。
- 参考スコア（独自算出の注目度）: 1.9374282535132377
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: We present a novel quantum high-dimensional linear regression algorithm with
an $\ell_1$-penalty based on the classical LARS (Least Angle Regression)
pathwise algorithm. Similarly to available classical numerical algorithms for
Lasso, our quantum algorithm provides the full regularisation path as the
penalty term varies, but quadratically faster per iteration under specific
conditions. A quadratic speedup on the number of features/predictors $d$ is
possible by using the simple quantum minimum-finding subroutine from D\"urr and
Hoyer (arXiv'96) in order to obtain the joining time at each iteration. We then
improve upon this simple quantum algorithm and obtain a quadratic speedup both
in the number of features $d$ and the number of observations $n$ by using the
recent approximate quantum minimum-finding subroutine from Chen and de Wolf
(ICALP'23). As one of our main contributions, we construct a quantum unitary
based on quantum amplitude estimation to approximately compute the joining
times to be searched over by the approximate quantum minimum finding. Since the
joining times are no longer exactly computed, it is no longer clear that the
resulting approximate quantum algorithm obtains a good solution. As our second
main contribution, we prove, via an approximate version of the KKT conditions
and a duality gap, that the LARS algorithm (and therefore our quantum
algorithm) is robust to errors. This means that it still outputs a path that
minimises the Lasso cost function up to a small error if the joining times are
only approximately computed. Finally, in the model where the observations are
generated by an underlying linear model with an unknown coefficient vector, we
prove bounds on the difference between the unknown coefficient vector and the
approximate Lasso solution, which generalises known results about convergence
rates in classical statistical learning theory analysis.
- Abstract（参考訳）: 古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づいて,$\ell_1$-penaltyの量子高次元線形回帰アルゴリズムを提案する。
ラッソの古典的数値アルゴリズムと同様に、我々の量子アルゴリズムは、ペナルティ項が変化するにつれて完全な正規化パスを提供するが、特定の条件下では反復ごとに2次的に高速である。
D\"urr と Hoyer (arXiv'96) の単純な量子最小フィン化サブルーチンを用いて、各イテレーションにおける結合時間を取得することで、特徴/予測子数$d$の2次高速化が可能となる。
次に、この単純な量子アルゴリズムを改善し、Chen と de Wolf (ICALP'23) の近似量子最小有限サブルーチンを用いて、特徴数 $d$ と観測数 $n$ の両方で二次的なスピードアップを得る。
我々の主な貢献の1つとして、量子振幅推定に基づく量子ユニタリを構築し、近似量子最小探索によって探索される結合時間を近似的に計算する。
結合時間はもはや正確に計算されないため、得られた近似量子アルゴリズムが良い解を得るかどうかはもはや明らかではない。
2つ目の主な貢献として、KKT条件の近似バージョンと双対性ギャップを通じて、LARSアルゴリズム(したがって我々の量子アルゴリズム)がエラーに対して堅牢であることを示す。
これは、結合時間がほぼ計算されている場合に、ラッソのコスト関数を小さな誤差まで最小化する経路を出力することを意味する。
最後に、未知の係数ベクトルを持つ基底線形モデルにより観測結果が生成されるモデルにおいて、未知の係数ベクトルと近似ラッソ解との差を証明し、古典的統計学習理論解析における収束率に関する既知の結果を一般化する。
関連論文リスト
- A quantum-classical hybrid algorithm with Ising model for the learning with errors problem [13.06030390635216]
本稿では,Ising Model (HAWI) を用いた量子古典ハイブリッドアルゴリズムを提案し,LWE問題に対処する。
我々は、ハミルトンの低エネルギーレベルを同定して解を抽出し、現在のノイズの多い中間スケール量子(NISQ)デバイスの実装に適したものにする。
我々のアルゴリズムは反復であり、その時間複雑性はハミルトンの低エネルギーレベルを見つけるために使われる特定の量子アルゴリズムに依存する。
論文 参考訳（メタデータ） (2024-08-15T05:11:35Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Solving k-SAT problems with generalized quantum measurement [0.7373617024876725]
我々は、ベンジャミン、ザオ、フィッツシモンズのプロジェクションに基づく量子測定駆動の$k$-SATアルゴリズムを任意の強度量子測定に一般化する。
このアルゴリズムは連続極限において時間と測定資源が有限であれば最も効率的であると主張する。
解ける$k$-SAT問題に対して、アルゴリズムによって生成されるダイナミクスは、長期(ゼノ)限界におけるターゲットダイナミクスに決定論的に収束する。
論文 参考訳（メタデータ） (2024-06-19T15:05:18Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。
我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
論文 参考訳（メタデータ） (2023-05-19T00:07:32Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳（メタデータ） (2022-10-12T19:10:43Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Adaptive Algorithm for Quantum Amplitude Estimation [13.82667502131475]
振幅の間隔推定のための適応アルゴリズムを提案する。
提案アルゴリズムは、同じレベルの精度を達成するために、同じ数の量子クエリを使用する。
我々は,古典モンテカルロサンプリングに対する2次高速化として,オラクルクエリの数が$O(1/epsilon)$に達することを厳密に証明する。
論文 参考訳（メタデータ） (2022-06-16T21:11:15Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。
プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
論文 参考訳（メタデータ） (2021-11-30T12:21:41Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。