論文の概要: Tight Bound for Estimating Expectation Values from a System of Linear Equations

• arxiv url: http://arxiv.org/abs/2111.10485v3
• Date: Sat, 3 Sep 2022 23:08:59 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-07 08:10:02.392089
• Title: Tight Bound for Estimating Expectation Values from a System of Linear Equations
• Title（参考訳）: 線形方程式系からの期待値推定のためのタイト境界
• Authors: Abhijeet Alase, Robert R. Nerem, Mohsen Bagherimehrab, Peter H{\o}yer, and Barry C. Sanders
• Abstract要約: 線形方程式系 (SLEP) は複素可逆行列$A$によって定義される。 ここで、$x$ は方程式 $Ax = b$ の解ベクトルである。 この設定におけるSLEPの量子クエリの複雑さは$Theta(alpha/epsilon)$であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The System of Linear Equations Problem (SLEP) is specified by a complex invertible matrix $A$, the condition number $\kappa$ of $A$, a vector $b$, a Hermitian matrix $M$ and an accuracy $\epsilon$, and the task is to estimate $x^\dagger Mx$, where $x$ is the solution vector to the equation $Ax = b$. We aim to establish a lower bound on the complexity of the end-to-end quantum algorithms for SLEP with respect to $\epsilon$, and devise a quantum algorithm that saturates this bound. To make lower bounds attainable, we consider query complexity in the setting in which a block encoding of $M$ is given, i.e., a unitary black box $U_M$ that contains $M/\alpha$ as a block for some $\alpha \in \mathbb R^+$. We show that the quantum query complexity for SLEP in this setting is $\Theta(\alpha/\epsilon)$. Our lower bound is established by reducing the problem of estimating the mean of a black box function to SLEP. Our $\Theta(\alpha/\epsilon)$ result tightens and proves the common assertion of polynomial accuracy dependence (poly$(1/\epsilon)$) for SLEP, and shows that improvement beyond linear dependence on accuracy is not possible if $M$ is provided via block encoding.
• Abstract（参考訳）: 線形方程式問題(slep)は、複素可逆行列 $a$、条件数 $\kappa$ of $a$、ベクトル $b$、エルミート行列 $m$、精度 $\epsilon$ によって指定され、そのタスクは $x^\dagger mx$ を推定することであり、ここで $x$ は方程式 $ax = b$ の解ベクトルである。 我々は,SLEP の$\epsilon$ に対する終端量子アルゴリズムの複雑性の低い境界を確立することを目的としており,この境界を飽和させる量子アルゴリズムを考案する。 より低いバウンダリを実現するために、$m$のブロックエンコーディングが与えられる設定、すなわち、いくつかの$\alpha \in \mathbb r^+$のブロックとして$m/\alpha$を含むユニタリブラックボックス $u_m$ を考える。 この設定におけるSLEPの量子クエリ複雑性は$\Theta(\alpha/\epsilon)$であることを示す。 我々の下界は、ブラックボックス関数の平均をSLEPに推定する問題を小さくすることで確立される。 我々の$\Theta(\alpha/\epsilon)$ result は SLEP に対して多項式精度依存(poly$(1/\epsilon)$)の共通主張を強くし、証明し、M$ がブロック符号化によって提供される場合、精度への線形依存を超えた改善は不可能であることを示す。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• 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)
• Misspecified $Q$-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error [25.777423855881878]
  我々は、$Oleft(Hepsilonright)$-optimal Policyを得ることができることを示す新しい除去アルゴリズムを示す。 我々は上界を$widetildeOmegaleft(Hepsilonright)$-optimality lower boundで補い、この問題の完全な図面を与える。
  論文  参考訳（メタデータ） (2024-07-18T15:58:04Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
  本稿では,オフライン強化学習におけるポリシー評価のサンプル複雑さについて検討する。 低分布シフトの仮定の下では、最大$oleft(maxleft fracleftvert thetapirightvert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$サンプルを必要とするアルゴリズムがあることを示す。
  論文  参考訳（メタデータ） (2021-03-17T18:18:57Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• 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)
• Fast digital methods for adiabatic state preparation [0.0]
  ゲート型量子コンピュータにおいて,逆誤差の複雑多元対数を伴う断熱状態生成のための量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-08T18:00:01Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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