論文の概要: Quantum Algorithms for the Pathwise Lasso

• arxiv url: http://arxiv.org/abs/2312.14141v2
• Date: Mon, 17 Jun 2024 08:55:21 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-19 07:14:24.120995
• Title: Quantum Algorithms for the Pathwise Lasso
• Title（参考訳）: パスワイズラッソのための量子アルゴリズム
• Authors: Joao F. Doriguello, Debbie Lim, Chi Seng Pun, Patrick Rebentrost, Tushar Vaidya,
• Abstract要約: 古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。 我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。 我々は、KKT条件の近似バージョンと双対性ギャップにより、LARSアルゴリズムがエラーに対して堅牢であることを証明した。
• 参考スコア（独自算出の注目度）: 1.8058773918890538
• License: http://creativecommons.org/licenses/by/4.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 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 $d$ is possible by using the quantum minimum-finding routine 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 approximate quantum minimum-finding routine from Chen and de Wolf (ICALP'23). As one of our main contributions, we construct a quantum unitary 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 thus 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 approximately computed. Moreover, we show that, when the observations are sampled from a Gaussian distribution, our quantum algorithm's complexity only depends polylogarithmically on $n$, exponentially better than the classical LARS algorithm, while keeping the quadratic improvement on $d$. Finally, we propose a dequantised algorithm that also retains the polylogarithmic dependence on $n$, albeit with the linear scaling on $d$ from the standard LARS algorithm.
• Abstract（参考訳）: 古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づいて,$\ell_1$-penaltyの量子高次元線形回帰アルゴリズムを提案する。 ラッソの古典的アルゴリズムと同様に、我々の量子アルゴリズムは、ペナルティ項が変化するにつれて完全な正規化パスを提供するが、特定の条件下では反復ごとに2次的に高速である。 D\"urr と Hoyer (arXiv'96) の量子最小フィンディングルーチンを使うことで、各イテレーションにおける結合時間を取得することで、機能数$d$の二次的なスピードアップが可能になる。 次に、この単純な量子アルゴリズムを改善し、Chen と de Wolf (ICALP'23) の近似量子最小有限ルーチンを用いて、特徴数 $d$ と観測数 $n$ の両方で二次的なスピードアップを得る。 我々の主な貢献の一つとして、近似量子最小探索によって探索される結合時間を近似的に計算する量子ユニタリを構築している。 結合時間はもはや正確に計算されないため、得られた近似量子アルゴリズムが良い解を得るかどうかはもはや明らかではない。 2つ目の主な貢献として、KKT条件の近似バージョンと双対性ギャップを通じて、LARSアルゴリズム(つまり我々の量子アルゴリズム)がエラーに対して堅牢であることを証明する。 これは、結合時間がほぼ計算された場合、ラッソのコスト関数を小さな誤差まで最小化する経路を出力することを意味する。 さらに、ガウス分布から観測結果がサンプリングされると、量子アルゴリズムの複雑さは、古典的なLARSアルゴリズムよりも指数関数的に良い$n$にのみ依存し、$d$に二次的な改善を保っていることを示す。 最後に、標準的なLARSアルゴリズムから$d$の線形スケーリングとともに、$n$の多元対数依存を保ち続ける非等化アルゴリズムを提案する。

関連論文リスト

• Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
  本稿では,多数決のランダムウォーク解釈に類似したライン上の重み付けウォークとして理解可能な,新たに単純化された浄化器の構成を提案する。 我々の浄化器は、前者よりも指数関数的に空間の複雑さが良く、精製されるアルゴリズムの音質-完全性ギャップに四分法的に依存している。
  論文  参考訳（メタデータ） (2025-02-13T12:04:39Z)
• 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)
• 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)

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

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