論文の概要: Mean estimation when you have the source code; or, quantum Monte Carlo methods

• arxiv url: http://arxiv.org/abs/2208.07544v1
• Date: Tue, 16 Aug 2022 05:34:26 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-30 23:03:40.428396
• Title: Mean estimation when you have the source code; or, quantum Monte Carlo methods
• Title（参考訳）: ソースコードを持っている場合の平均推定、または量子モンテカルロ法
• Authors: Robin Kothari, Ryan O'Donnell
• Abstract要約: 我々は、$O(n)$倍のコードを実行し、$muに対して$widehatboldsymbolmu$を見積もる量子手順を与える。 この$n$への依存は量子アルゴリズムに最適である。
• 参考スコア（独自算出の注目度）: 2.9697051524971743
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Suppose $\boldsymbol{y}$ is a real random variable, and one is given access to ``the code'' that generates it (for example, a randomized or quantum circuit whose output is $\boldsymbol{y}$). We give a quantum procedure that runs the code $O(n)$ times and returns an estimate $\widehat{\boldsymbol{\mu}}$ for $\mu = \mathrm{E}[\boldsymbol{y}]$ that with high probability satisfies $|\widehat{\boldsymbol{\mu}} - \mu| \leq \sigma/n$, where $\sigma = \mathrm{stddev}[\boldsymbol{y}]$. This dependence on $n$ is optimal for quantum algorithms. One may compare with classical algorithms, which can only achieve the quadratically worse $|\widehat{\boldsymbol{\mu}} - \mu| \leq \sigma/\sqrt{n}$. Our method improves upon previous works, which either made additional assumptions about $\boldsymbol{y}$, and/or assumed the algorithm knew an a priori bound on $\sigma$, and/or used additional logarithmic factors beyond $O(n)$. The central subroutine for our result is essentially Grover's algorithm but with complex phases.ally Grover's algorithm but with complex phases.
• Abstract（参考訳）: 例えば、$\boldsymbol{y}$ は実確率変数であり、それを生成する ``the code'' へのアクセスが与えられる(例えば、出力が $\boldsymbol{y}$ であるランダム化または量子回路)。 我々は、$O(n)$ timesを実行し、$\mu = \mathrm{E}[\boldsymbol{y}]$に対して$\widehat{\boldsymbol{\mu}}$ for $\mu = \mathrm{E}[\boldsymbol{y}]$に対して、高い確率で $|\widehat{\boldsymbol{\mu}} - \mu| \leq \sigma/n$, ここで$\sigma = \mathrm{stddev}[\boldsymbol{y}]$を返します。 この$n$への依存は量子アルゴリズムに最適である。 古典アルゴリズムと比較すると、二次的に悪い$|\widehat{\boldsymbol{\mu}} - \mu| \leq \sigma/\sqrt{n}$ しか達成できない。 我々の手法は、$\boldsymbol{y}$に関する仮定を追加し、/またはアルゴリズムが$\sigma$の先行値を知っていると仮定し、/または$O(n)$を超える追加の対数因子を使用した。 我々の結果の中心的なサブルーチンは、本質的にはグロバーのアルゴリズムであるが、複雑な位相を持つ。

関連論文リスト

• Solving Quadratic Systems with Full-Rank Matrices Using Sparse or Generative Priors [33.0212223058894]
  二次系$y_i=boldsymbol xtopboldsymbol A_iboldsymbol x, i=1,ldots,m$とフルランク行列$boldsymbol A_i$からの信号を回復する問題は、未割り当て距離幾何学やサブ波長イメージングなどの応用で頻繁に発生する。 本稿では、$mll n$ が $boldsymbol x$ の事前知識を取り入れた高次元の場合について述べる。
  論文  参考訳（メタデータ） (2023-09-16T16:00:07Z)
• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
  論文  参考訳（メタデータ） (2023-02-20T19:11:44Z)
• 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)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• The Quantum Supremacy Tsirelson Inequality [0.22843885788439797]
  量子回路 $C$ on $n$ qubits とサンプル $z in 0,1n$ のとき、ベンチマークは$|langle z|C|0n rangle|2$ の計算を伴う。 任意の $varepsilon ge frac1mathrmpoly(n)$ に対して、サンプル $z$ を出力することは、平均で $|langle z|C|0nrangle|2$ に対して最適な 1-クエリであることを示す。
  論文  参考訳（メタデータ） (2020-08-20T01:04:32Z)
• Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time [14.990725929840892]
  ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。 我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
  論文  参考訳（メタデータ） (2020-06-23T20:21:27Z)
• 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)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)

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

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