論文の概要: More-efficient Quantum Multivariate Mean Value Estimator from Generalized Grover Gate

• arxiv url: http://arxiv.org/abs/2504.06940v1
• Date: Wed, 09 Apr 2025 14:48:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-10 16:14:52.575834
• Title: More-efficient Quantum Multivariate Mean Value Estimator from Generalized Grover Gate
• Title（参考訳）: 一般化グローバーゲートを用いた高効率量子多変量平均値推定器
• Authors: Letian Tang,
• Abstract要約: 精度$fracsqrttexttr Sigman$ in $lVert rVert_infty$ norm を達成するために$Oleft(n log fracddeltaright)$を使用するアルゴリズムを見つける。 また、より小さなメモリを使用する別のアルゴリズムも提示しますが、さらにdfrac14$の複雑さがあります。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: In this work, we present an efficient algorithm for multivariate mean value estimation. Our algorithm outperforms previous work by polylog factors and nearly saturates the known lower bound. We find an algorithm that uses $O\left(n \log \frac{d}{\delta}\right)$ to achieve precision $\frac{\sqrt{\text{tr } \Sigma}}{n}$ in $\lVert \rVert_\infty$ norm and hence $\frac{\sqrt{d \text{ tr } \Sigma}}{n}$ in $\lVert \rVert_2$ norm, where $d$ is the dimension and $\Sigma$ is the covariance matrix. We also presented another algorithm that uses smaller memory but costs an extra $d^\frac{1}{4}$ in complexity. The idea originates from the previous observations that the Grover gate, when generalized to allow for arbitrary phases instead of $\pm 1$, becomes a good mean value estimator in some mathematical notion. The only remaining $\log \frac{d}{\delta}$ as opposed to $\log \frac{1}{\delta}$ is due to the phase estimation primitive we employed, which so far is the only major known method to tackle the problem. Our results demonstrates that our methodology with generalized Grover gate can be used locate the optimal algorithm, without polylog overhead, for different taks relating to mean value estimation.
• Abstract（参考訳）: 本研究では,多変量平均値推定のための効率的なアルゴリズムを提案する。 我々のアルゴリズムは、ポリログ因子による以前の研究よりも優れており、既知の下界をほぼ飽和させる。 精度を高めるために$O\left(n \log \frac{d}{\delta}\right)$を使用するアルゴリズムを見つける。$\frac{\sqrt{\text{tr } \Sigma}}{n}$ in $\lVert \rVert_\infty$ norm そして$\frac{\sqrt{d \text{ tr } \Sigma}}{n}$ in $\lVert \rVert_2$ norm, $d$は次元であり、$\Sigma$は共分散行列である。 また、より小さなメモリを使用する別のアルゴリズムも提示しましたが、複雑さが増すとさらに$d^\frac{1}{4}がかかります。 この考え方は、グロバーゲートが$\pm 1$ではなく任意の位相を許容するように一般化されたとき、ある数学的概念において良い平均値推定器となるという以前の観測に由来する。 残る$\log \frac{d}{\delta}$は、$\log \frac{1}{\delta}$とは対照的に、私たちが採用した位相推定プリミティブのためである。 以上の結果から,一般化したGroverゲートを用いた手法は,平均値推定に関する異なるタクに対して,ポリログのオーバーヘッドを伴わずに最適なアルゴリズムを見つけることができることを示す。

関連論文リスト

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• 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)
• Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
  我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。 特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。 主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
  論文  参考訳（メタデータ） (2023-12-14T12:53:34Z)
• Online Robust Mean Estimation [37.746091744197656]
  オンライン環境における高次元ロバスト平均推定問題について検討する。 このモデルでは、オンラインロバスト平均推定の主な2つの結果が証明されている。
  論文  参考訳（メタデータ） (2023-10-24T15:28:43Z)
• Weak Schur sampling with logarithmic quantum memory [0.0]
  弱いシュアサンプリングのための新しいアルゴリズムを提案する。 我々のアルゴリズムは、既約表現をインデックスするヤングラベルと対称群の多重度ラベルの両方を効率的に決定する。
  論文  参考訳（メタデータ） (2023-09-21T10:02:46Z)
• Do you know what q-means? [45.810803542748495]
  Kerenidis, Landman, Luongo, Prakash (NeurIPS')によって提案された量子アルゴリズムの改良版を提案する。 我々のアルゴリズムは、先行研究の量子線型代数プリミティブに頼るのではなく、QRAMを用いて単純な状態を作成する。 また、$varepsilon$-$k$-meansに対して、$Obigで実行される"dequantized"アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Mean estimation when you have the source code; or, quantum Monte Carlo methods [2.9697051524971743]
  我々は、$O(n)$倍のコードを実行し、$muに対して$widehatboldsymbolmu$を見積もる量子手順を与える。 この$n$への依存は量子アルゴリズムに最適である。
  論文  参考訳（メタデータ） (2022-08-16T05:34:26Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
  データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。 本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。 我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
  論文  参考訳（メタデータ） (2020-08-15T11:06:45Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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