論文の概要: An improved quantum algorithm for low-rank rigid linear regressions with
vector solution outputs
- arxiv url: http://arxiv.org/abs/2301.06107v1
- Date: Sun, 15 Jan 2023 14:40:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-18 17:22:22.872995
- Title: An improved quantum algorithm for low-rank rigid linear regressions with
vector solution outputs
- Title（参考訳）: ベクトル解出力を用いた低ランク剛性線形回帰の量子アルゴリズムの改良
- Authors: Changpeng Shao
- Abstract要約: 本稿では,ブロック符号化の枠組みにおいて,ベクトル解を$tildex_rm opt$で返す量子アルゴリズムを提案する。
レバレッジスコアサンプリングの高速化は、ある場合では二次的あるいは指数的である。
我々は、量子コンピュータ上でレバレッジスコアサンプリングと線形回帰の解法を行う際のいくつかの低い限界を示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Let $A\in \mathbb{R}^{n\times d}, \b \in \mathbb{R}^{n}$ and $\lambda>0$, for
rigid linear regression \[ \argmin_{\x} \quad Z(\x) = \|A\x-\b\|^2 + \lambda^2
\|\x\|^2, \] we propose a quantum algorithm, in the framework of
block-encoding, that returns a vector solution $\tilde{\x}_{\rm opt}$ such that
$Z(\tilde{\x}_{\rm opt}) \leq (1+\varepsilon) Z(\x_{\rm opt})$, where $\x_{\rm
opt}$ is an optimal solution. If a block-encoding of $A$ is constructed in time
$O(T)$, then the cost of the quantum algorithm is roughly $\widetilde{O}(\K
\sqrt{d}/\varepsilon^{1.5} + d/\varepsilon)$ when $A$ is low-rank and
$n=\widetilde{O}(d)$. Here $\K=T\alpha/\lambda$ and $\alpha$ is a normalization
parameter such that $A/\alpha$ is encoded in a unitary through the
block-encoding. This can be more efficient than naive quantum algorithms using
quantum linear solvers and quantum tomography or amplitude estimation, which
usually cost $\widetilde{O}(\K d/\varepsilon)$. The main technique we use is a
quantum accelerated version of leverage score sampling, which may have other
applications. The speedup of leverage score sampling can be quadratic or even
exponential in certain cases. As a byproduct, we propose an improved randomized
classical algorithm for rigid linear regressions. Finally, we show some lower
bounds on performing leverage score sampling and solving linear regressions on
a quantum computer.
- Abstract（参考訳）: A\in \mathbb{R}^{n\times d}, \b \in \mathbb{R}^{n}$ and $\lambda>0$, for rigid linear regression \[ \argmin_{\x} \quad Z(\x) = \|A\x-\b\|^2 + \lambda^2 \|\x\|^2, \] 我々は、ブロックエンコーディングの枠組みにおいて、ベクトル解 $\tilde{\x}_{\rm opt}$Z(\tilde{\x}_{\rm opt}) \leq (1+\varepsilon) Z(\x_{\rm opt})$, ここで、$\x_{\rm}$が最適解であるような量子アルゴリズムを提案する。
もし$a$のブロックエンコーディングが時間$o(t)$で構築されているなら、量子アルゴリズムのコストは、$a$が低ランクで$n=\widetilde{o}(d)$の場合、およそ$\widetilde{o}(\k \sqrt{d}/\varepsilon^{1.5} + d/\varepsilon)$である。
ここで$\K=T\alpha/\lambda$と$\alpha$は正規化パラメータであり、ブロックエンコーディングを通して$A/\alpha$がユニタリにエンコードされる。
これは、量子線形解法や量子トモグラフィや振幅推定を用いたナイーブ量子アルゴリズムよりも効率的であり、通常は$\widetilde{o}(\k d/\varepsilon)$である。
私たちが使う主なテクニックは、他の応用があるかもしれないレバレッジスコアサンプリングの量子加速バージョンです。
レバレッジスコアサンプリングの高速化は、ある場合には二次的あるいは指数的である。
副産物として,剛性線形回帰のためのランダム化古典アルゴリズムを提案する。
最後に,量子コンピュータ上でのスコアサンプリングと線形回帰の解法について,下限を示す。
関連論文リスト
- Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
古典的マルチロー反復法に着想を得た量子アルゴリズムを提案する。
本アルゴリズムは,不整合系の解法に適した係数行列の要求を小さくする。
論文 参考訳（メタデータ） (2024-09-06T03:32:02Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - Solving the semidefinite relaxation of QUBOs in matrix multiplication
time, and faster with a quantum computer [0.20999222360659603]
いくつかの量子SDOソルバは、低精度な状態において高速化を提供する。
この事実を利用してアルゴリズムの精度への依存を指数関数的に改善する。
我々のアルゴリズムの量子実装は、$mathcalO left(ns + n1.5 cdot textpolylog left(n, | C |_F, frac1epsilon right)$の最悪の実行時間を示す。
論文 参考訳（メタデータ） (2023-01-10T23:12:05Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Quantum Algorithm For Estimating Eigenvalue [0.0]
与えられたエルミート行列の大きさで最大の固有値を推定するための量子アルゴリズムを提供する。
我々の量子プロシージャは、同じ問題を解決する古典的なアルゴリズムと比較して指数的なスピードアップを得ることができる。
論文 参考訳（メタデータ） (2022-11-11T13:02:07Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Quantum Levenberg--Marquardt Algorithm for optimization in Bundle
Adjustment [0.0]
本稿では,正規方程式の線形系を解くための量子アルゴリズムを実装し,レバンス-マルカールトの最適化ステップを計算する。
提案した量子アルゴリズムは、点数に関して、この演算の複雑さを劇的に低減する。
論文 参考訳（メタデータ） (2022-03-04T13:38:21Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。
プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
論文 参考訳（メタデータ） (2021-11-30T12:21:41Z) - An optimal quantum sampling regression algorithm for variational
eigensolving in the low qubit number regime [0.0]
量子サンプリング回帰(QSR)は、代替の量子古典的アルゴリズムである。
低量子ビット数構造における時間的複雑さに基づいて,その利用事例を分析した。
ベンチマーク問題に対するアルゴリズムの有効性を示す。
論文 参考訳（メタデータ） (2020-12-04T00:01:15Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。
これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文 参考訳（メタデータ） (2020-11-09T01:13:07Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。