論文の概要: Quantum algorithm for matrix functions by Cauchy's integral formula
- arxiv url: http://arxiv.org/abs/2106.08075v1
- Date: Tue, 15 Jun 2021 12:10:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-26 15:31:06.181067
- Title: Quantum algorithm for matrix functions by Cauchy's integral formula
- Title（参考訳）: コーシー積分公式による行列関数の量子アルゴリズム
- Authors: Souichi Takahira, Asuka Ohashi, Tomohiro Sogabe, and Tsuyoshi Sasaki
Usuda
- Abstract要約: 量子状態 $lvert f rangle$ をベクトル $f(A)boldsymbolb$ に対応する問題を考える。
固有値推定を回避する手法として,コーシーの積分公式と台形規則を用いる量子アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 1.399948157377307
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: For matrix $A$, vector $\boldsymbol{b}$ and function $f$, the computation of
vector $f(A)\boldsymbol{b}$ arises in many scientific computing applications.
We consider the problem of obtaining quantum state $\lvert f \rangle$
corresponding to vector $f(A)\boldsymbol{b}$. There is a quantum algorithm to
compute state $\lvert f \rangle$ using eigenvalue estimation that uses phase
estimation and Hamiltonian simulation $\mathrm{e}^{\mathrm{{\bf i}} A t}$.
However, the algorithm based on eigenvalue estimation needs
$\textrm{poly}(1/\epsilon)$ runtime, where $\epsilon$ is the desired accuracy
of the output state. Moreover, if matrix $A$ is not Hermitian,
$\mathrm{e}^{\mathrm{{\bf i}} A t}$ is not unitary and we cannot run eigenvalue
estimation. In this paper, we propose a quantum algorithm that uses Cauchy's
integral formula and the trapezoidal rule as an approach that avoids eigenvalue
estimation. We show that the runtime of the algorithm is
$\mathrm{poly}(\log(1/\epsilon))$ and the algorithm outputs state $\lvert f
\rangle$ even if $A$ is not Hermitian.
- Abstract（参考訳）: matrix $a$, vector $\boldsymbol{b}$ および function $f$ に対して、vector $f(a)\boldsymbol{b}$ の計算は多くの科学計算アプリケーションで発生する。
我々はベクトル $f(a)\boldsymbol{b}$ に対応する量子状態 $\lvert f \rangle$ を得る問題を考える。
位相推定とハミルトンシミュレーションを用いた固有値推定を用いて、状態$\lvert f \rangle$を計算する量子アルゴリズム $\mathrm{e}^{\mathrm{{\bf i}} a t}$ がある。
しかし、固有値推定に基づくアルゴリズムは$\textrm{poly}(1/\epsilon)$ランタイムを必要とし、$\epsilon$は出力状態の所望の精度である。
さらに、行列 $A$ がエルミート的でないなら、$\mathrm{e}^{\mathrm{{\bf i}} A t}$ はユニタリではなく、固有値推定を実行することはできない。
本稿では,コーシーの積分公式と台形規則を固有値推定を回避する手法として用いた量子アルゴリズムを提案する。
アルゴリズムのランタイムは$\mathrm{poly}(\log(1/\epsilon))$であり、$A$がHermitianでない場合でも、そのアルゴリズムは状態$\lvert f \rangle$を出力する。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Oja's Algorithm for Streaming Sparse PCA [7.059472280274011]
Oja's Algorithm for Streaming principal Component Analysis (PCA) for $n$ data-points in a $d$ dimensional space achieves the same sin-squared error $O(r_mathsfeff/n)$ as the offline algorithm in $O(d)$ space and $O(nd)$ time。
Ojaのアルゴリズムの出力をしきい値にする単純なシングルパス手順は、$O(d)$ space と $O(nd)$ time の正則性条件下での最小誤差を達成できることを示す。
論文 参考訳（メタデータ） (2024-02-11T16:36:48Z) - A Quantum Approximation Scheme for k-Means [0.16317061277457]
QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。
我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。
教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
論文 参考訳（メタデータ） (2023-08-16T06:46:37Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Unique Games hardness of Quantum Max-Cut, and a conjectured
vector-valued Borell's inequality [6.621324975749854]
関数 $f:mathbbRn の -1, 1$ への雑音安定性は $f(boldsymbolx) cdot f(boldsymboly)$ の期待値であることを示す。
我々は $langle f(boldsymbolx), f(boldsymboly)rangle$ の期待値は、関数 $f(x) = x_leq k / Vert x_leq k / によって最小化されると予想する。
論文 参考訳（メタデータ） (2021-11-01T20:45:42Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。
規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
論文 参考訳（メタデータ） (2021-05-31T16:10:49Z) - An improved quantum-inspired algorithm for linear regression [15.090593955414137]
量子行列反転アルゴリズムに類似した線形回帰の古典的アルゴリズムを提案する。
量子コンピュータは、このQRAMデータ構造設定において、線形回帰の最大12倍の高速化を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-15T17:58:25Z) - The Average-Case Time Complexity of Certifying the Restricted Isometry
Property [66.65353643599899]
圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。
Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
論文 参考訳（メタデータ） (2020-05-22T16:55:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。