論文の概要: 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次高速化する最初の量子アルゴリズムを提案する。 量子アルゴリズムの分析は、従来のものよりもはるかに直感的で簡潔であることは注目に値する。

関連論文リスト

• 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)

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

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