論文の概要: Striving for simplicity and effectiveness: quantum algorithm for
distribution property testing
- arxiv url: http://arxiv.org/abs/2304.12916v1
- Date: Tue, 25 Apr 2023 15:32:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-26 20:06:18.431311
- Title: Striving for simplicity and effectiveness: quantum algorithm for
distribution property testing
- Title(参考訳): 簡易性と有効性を追求する: 分布特性テストのための量子アルゴリズム
- Authors: Jingquan Luo and Lvzhou Li
- Abstract要約: 分布特性の試験法の基本問題に対する潜在的な量子スピードアップについて検討する。
最初の問題として、現在最高の量子アルゴリズムを$l1$-distanceと$l2$-distanceのメトリクスで提案する。
後者の問題に対しては、最先端の古典的アルゴリズムを2次高速化する最初の量子アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 0.2741266294612775
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We explore potential quantum speedups for the fundamental problem of testing
properties of distributions. In particular, we focus on two different problems:
the first one is to test whether two unknown classical distributions are close
or far enough, and the second one is to test whether a given distribution over
$\{0, 1\}^n$ is $k$-wise uniform or far from any $k$-wise uniform distribution.
For the first problem, we propose the currently best quantum algorithm under
the metrics of $l^1$-distance and $l^2$-distance. Compared with the latest
result given in \cite{gilyen2019distributional} which relied on the technique
of quantum singular value transformation (QSVT), our algorithm is not only more
concise, but also more efficient. For the latter problem, we propose the first
quantum algorithm achieving a quadratic speedup over the state-of-the-art
classical algorithm. It is worthy noting that the analysis of our quantum
algorithm is much more intuitive and concise than that of the classical one.
- Abstract(参考訳): 分布特性の試験法の基本問題に対する潜在的な量子スピードアップについて検討する。
特に、2つの異なる問題に焦点を当てている: 1つは、2つの未知の古典分布が十分に近いか遠くにあるかをテストし、もう1つは$\{0, 1\}^n$ 上の与えられた分布が$k$-wise 一様か、あるいは任意の$k$-wise 一様分布から遠く離れているかをテストすることである。
最初の問題として、現在最高の量子アルゴリズムを$l^1$-distanceと$l^2$-distanceのメトリクスで提案する。
量子特異値変換 (qsvt) の手法に依存する \cite{gilyen2019distributional} の最新の結果と比較すると, アルゴリズムはより簡潔なだけでなく, より効率的である。
後者の問題に対しては、最先端の古典的アルゴリズムを2次高速化する最初の量子アルゴリズムを提案する。
量子アルゴリズムの分析は、従来のものよりもはるかに直感的で簡潔であることは注目に値する。
関連論文リスト
- 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) - On the exact quantum query complexity of $\text{MOD}_m^n$ and
$\text{EXACT}_{k,l}^n$ [0.0]
我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。
我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
論文 参考訳(メタデータ) (2023-03-20T08:17:32Z) - A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation [13.810917492304565]
離散確率分布の特性を推定するための統一量子アルゴリズムフレームワークを提案する。
我々のフレームワークは、$alpha$-R'enyi entropy $H_alpha(p)$を、少なくとも2/3$の確率で加算エラー$epsilon$内で推定する。
論文 参考訳(メタデータ) (2022-12-03T08:01:55Z) - 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) - 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) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳(メタデータ) (2020-02-21T18:30:48Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。