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

• arxiv url: http://arxiv.org/abs/2504.06940v2
• Date: Thu, 10 Apr 2025 19:50:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-14 10:55:27.489805
• Title: More-efficient Quantum Multivariate Mean Value Estimator from Generalized Grover Gate
• Title（参考訳）: 一般化グローバーゲートを用いた高効率量子多変量平均値推定器
• Authors: Letian Tang,
• Abstract要約: 我々は、$Oleft(n log fracddeltaright)$サンプルを使用して、$vectildemu$の平均推定値を求めるアルゴリズムを見つける。 我々の結果は、複雑さの$log fracddelta$項が原因で、まだ正確には最適ではない。
• 参考スコア（独自算出の注目度）: 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. More formally, given a random vector $\vec{X}$ of dimension $d$, we find an algorithm that uses $O\left(n \log \frac{d}{\delta}\right)$ samples to find a mean estimate that $\vec{\tilde{\mu}}$ that differs from the true mean $\vec{\mu}$ by $\frac{\sqrt{\text{tr } \Sigma}}{n}$ in $\ell^\infty$ norm and hence $\frac{\sqrt{d \text{ tr } \Sigma}}{n}$ in $\ell^2$ norm, where $\Sigma$ is the covariance matrix of the components of the random vector. We also presented another algorithm that uses smaller memory but costs an extra $d^\frac{1}{4}$ in complexity. Consider the Grover gate, the unitary operator used in Grover's algorithm. It contains an oracle that uses a $\pm 1$ phase for each candidate for the search space. Previous work has demonstrated that when we substitute the oracle in Grover gate with generic phases, it ended up being a good mean value estimator in some mathematical notion. We used this idea to build our algorithm. Our result remains not exactly optimal due to a $\log \frac{d}{\delta}$ term in our complexity, as opposed to something nicer such as $\log \frac{1}{\delta}$; This comes from the phase estimation primitive in our algorithm. So far, this primitive is the only major known method to tackle the problem, and moving beyond this idea seems hard. Our results demonstrates that the methodology with generalized Grover gate can be used develop the optimal algorithm without polylog overhead for different tasks relating to mean value estimation.
• Abstract（参考訳）: 本研究では,多変量平均値推定のための効率的なアルゴリズムを提案する。 我々のアルゴリズムは、ポリログ因子による以前の研究よりも優れており、既知の下界をほぼ飽和させる。 より正式には、次元$d$のランダムベクトル$\vec{X}$が与えられたとき、$O\left(n \log \frac{d}{\delta}\right)$サンプルを用いて、真平均$\vec{\mu}$ by $\frac{\sqrt{\text{tr } \Sigma}}{n}$が$\ell^\infty$ノルムであり、従って$\frac{\sqrt{d \text{ tr } \Sigma}}{n}$が$\ell^2$ノルムであるような平均推定値を求めるアルゴリズムを見つける。 また、より小さなメモリを使用する別のアルゴリズムも提示しましたが、複雑さが増すとさらに$d^\frac{1}{4}がかかります。 グロバーのアルゴリズムで使用されるユニタリ作用素であるグロバーゲートを考える。 そこには、検索スペースの候補毎に$\pm 1$のフェーズを使用するオラクルが含まれている。 以前の研究は、グローバーゲートのオラクルを一般的な位相で置き換えると、ある数学的概念において良い平均値推定器となることを示した。 私たちはこのアイデアを使ってアルゴリズムを構築しました。 私たちの結果は、$\log \frac{d}{\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)

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

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