論文の概要: Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions
- arxiv url: http://arxiv.org/abs/2304.12916v4
- Date: Tue, 25 Jun 2024 19:43:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-27 20:03:37.808746
- Title: Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions
- Title（参考訳）: 確率分布の近接性と$k$-wise一様性に対する付帯量子テスター
- Authors: Jingquan Luo, Qisheng Wang, Lvzhou Li,
- Abstract要約: 確率分布の近さ特性と$k$-wise均一性をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。
我々は、$ell1$-および$ell2$-closenessテストの量子クエリ複雑性が$O(sqrtn/varepsilon)$と$O(sqrtnk/varepsilon)$であることを示す。
クエリ複雑性を$O(sqrtnk/varepsilon)で表した最初の量子アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 2.3466828785520373
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We explore potential quantum speedups for the fundamental problem of testing the properties of closeness and $k$-wise uniformity of probability distributions. Closeness testing is the problem of distinguishing whether two $n$-dimensional distributions are identical or at least $\varepsilon$-far in $\ell^1$- or $\ell^2$-distance. We show that the quantum query complexities for $\ell^1$- and $\ell^2$-closeness testing are $O(\sqrt{n}/\varepsilon)$ and $O(1/\varepsilon)$, respectively, both of which achieve optimal dependence on $\varepsilon$, improving the prior best results of Gily\'en and Li (2020). $k$-wise uniformity testing is the problem of distinguishing whether a distribution over $\{0, 1\}^n$ is uniform when restricted to any $k$ coordinates or $\varepsilon$-far from any such distributions. We propose the first quantum algorithm for this problem with query complexity $O(\sqrt{n^k}/\varepsilon)$, achieving a quadratic speedup over the state-of-the-art classical algorithm with sample complexity $O(n^k/\varepsilon^2)$ by O'Donnell and Zhao (2018). Moreover, when $k = 2$ our quantum algorithm outperforms any classical one because of the classical lower bound $\Omega(n/\varepsilon^2)$. All our quantum algorithms are fairly simple and time-efficient, using only basic quantum subroutines such as amplitude estimation.
- Abstract（参考訳）: 確率分布の近さ特性と$k$-wise均一性をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。
クローズネステストは、2つの$n$次元分布が同一であるか、少なくとも$\varepsilon$-far in $\ell^1$-または$\ell^2$-distanceのどちらかを区別する問題である。
我々は、$\ell^1$-と$\ell^2$-クロースネステストの量子クエリ複雑性が、それぞれ$O(\sqrt{n}/\varepsilon)$と$O(1/\varepsilon)$であり、どちらも$\varepsilon$への最適依存を達成し、 Gily\en と Li (2020) の以前の最良の結果を改善することを示す。
$k$-wise uniformity testing は、${0, 1\}^n$ 上の分布が任意の$k$座標に制限された場合、またはそのような分布から$\varepsilon$-far を区別する問題である。
質問複雑性$O(\sqrt{n^k}/\varepsilon)$, サンプル複雑性$O(n^k/\varepsilon^2)$, O'Donnell and Zhao (2018) による最先端の古典的アルゴリズムの2次高速化を実現する。
さらに、$k = 2$のとき、量子アルゴリズムは古典的下界の$\Omega(n/\varepsilon^2)$のために古典的よりも優れる。
我々の量子アルゴリズムは、振幅推定のような基本的な量子サブルーチンのみを用いて、かなり単純で時間効率が高い。
関連論文リスト
- Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。
また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-04T11:03:48Z) - A Quantum Approximation Scheme for k-Means [0.16317061277457]
QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。
我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。
教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
論文 参考訳（メタデータ） (2023-08-16T06:46:37Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Robustness of Quantum Algorithms for Nonconvex Optimization [7.191453718557392]
量子アルゴリズムは多対数あるいは指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができることを示す。
また、量子アルゴリズムが多対数または指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができる領域を特徴付ける。
論文 参考訳（メタデータ） (2022-12-05T19:10:32Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - 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) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z) - Towards Optimal Separations between Quantum and Randomized Query
Complexities [0.30458514384586394]
入力に対して2O(k)$クエリを行うことで量子アルゴリズムを解くことができることを示す。
任意の定数 $varepsilon>0$ に対して、$O(1)$ 対 $N2/3-varepsilon$ 分離を与える。
論文 参考訳（メタデータ） (2019-12-29T01:42:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。