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

• arxiv url: http://arxiv.org/abs/2504.06940v3
• Date: Thu, 29 May 2025 17:01:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-30 15:42:33.688568
• Title: More-efficient Quantum Multivariate Mean Value Estimator from Generalized Grover Operator
• Title（参考訳）: 一般化グローバー演算子を用いた高効率量子多変量平均値推定器
• Authors: Letian Tang,
• Abstract要約: 我々は、$Oleft(n log fracddeltaright)$サンプルを使用して、$vectildemu$の平均推定値を求めるアルゴリズムを見つける。 我々の結果は、複雑さの$log fracddelta$項が原因で、まだ正確には最適ではない。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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 operator, 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 operator 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 operator 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)
• A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation [6.853165736531941]
  逆数外乱の存在下でのスパース平均推定のアルゴリズム的問題について検討する。 我々の主な貢献は、$mathrmpoly(k,log d,1/epsilon)$サンプルを用いて、エフェサブクアクラティック時間で実行される頑健なスパース平均推定アルゴリズムである。
  論文  参考訳（メタデータ） (2024-03-07T18:23:51Z)
• 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 Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。 クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。 我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
  論文  参考訳（メタデータ） (2024-02-09T19:01:48Z)
• 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)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• 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)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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