論文の概要: Quantum Coupon Collector

• arxiv url: http://arxiv.org/abs/2002.07688v1
• Date: Tue, 18 Feb 2020 16:14:55 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-03 07:11:28.391195
• Title: Quantum Coupon Collector
• Title（参考訳）: 量子クーポンコレクタ
• Authors: Srinivasan Arunachalam and Aleksandrs Belovs and Andrew M. Childs and Robin Kothari and Ansis Rosmanis and Ronald de Wolf
• Abstract要約: 我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。 我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
• 参考スコア（独自算出の注目度）: 62.58209964224025
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study how efficiently a $k$-element set $S\subseteq[n]$ can be learned from a uniform superposition $|S\rangle$ of its elements. One can think of $|S\rangle=\sum_{i\in S}|i\rangle/\sqrt{|S|}$ as the quantum version of a uniformly random sample over $S$, as in the classical analysis of the ``coupon collector problem.'' We show that if $k$ is close to $n$, then we can learn $S$ using asymptotically fewer quantum samples than random samples. In particular, if there are $n-k=O(1)$ missing elements then $O(k)$ copies of $|S\rangle$ suffice, in contrast to the $\Theta(k\log k)$ random samples needed by a classical coupon collector. On the other hand, if $n-k=\Omega(k)$, then $\Omega(k\log k)$ quantum samples are~necessary. More generally, we give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms. We also give tight bounds in the model where we can additionally reflect through $|S\rangle$. Finally, we relate coupon collection to a known example separating proper and improper PAC learning that turns out to show no separation in the quantum case.
• Abstract（参考訳）: 我々は、$k$-要素集合$S\subseteq[n]$が、その要素の均一な重ね合わせ$|S\rangle$からいかに効率的に学習できるかを研究する。 |s\rangle=\sum_{i\in s}|i\rangle/\sqrt{|s|}$ を ``coupon collector problem の古典的な解析のように、$s$ 上の一様ランダムなサンプルの量子バージョンと考えることができる。 もし$k$が$n$に近いなら、ランダムなサンプルよりも漸近的に少ない量子サンプルを使って$s$を学ぶことができる。 特に、$n-k=O(1)$ 欠落元がある場合、$O(k)$ suffice の $|S\rangle$ suffice は、古典的なクーポンコレクタが必要とする $\Theta(k\log k)$ ランダムサンプルとは対照的である。 一方、$n-k=\Omega(k)$ならば、$\Omega(k\log k)$量子サンプルは必要である。 より一般的には、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。 また、$|S\rangle$を反射できるようなモデルに厳密な境界を与える。 最後に、クーポン収集と、量子の場合の分離を示さない適切なPAC学習と不適切なPAC学習を分離した既知の例を関連付ける。

関連論文リスト

• New Bounds on Quantum Sample Complexity of Measurement Classes [18.531114735719274]
  本稿では量子状態からの古典的推論のための量子教師あり学習について研究する。 学習の難しさは、よく知られたほぼ正しい(PAC)量子対して、サンプルの複雑さによって測定される
  論文  参考訳（メタデータ） (2024-08-22T18:43:13Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。 本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
  論文  参考訳（メタデータ） (2024-08-10T04:26:19Z)
• Proper vs Improper Quantum PAC learning [3.292420364429101]
  本稿では,サンプリング複雑性を伴う量子クーポンコレクタ問題に対するアルゴリズムを提案する。 両学習モードにおける古典的クーポンコレクタ問題と,そのサンプルの複雑性が一致することを証明した。 パディングがより一般的に、古典的な学習行動から量子環境へと持ち上げられることを願っています。
  論文  参考訳（メタデータ） (2024-03-05T19:49:44Z)
• Time-Efficient Quantum Entropy Estimator via Samplizer [7.319050391449301]
  量子状態のエントロピーを推定することは、量子情報の基本的な問題である。 我々は、フォン・ノイマンエントロピー $S(rho)$ と R'enyi entropy $S_alpha(rho)$ を$N$次元量子状態 $rho として推定するための時間効率のよい量子アプローチを導入する。
  論文  参考訳（メタデータ） (2024-01-18T12:50:20Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• Improved quantum data analysis [1.8416014644193066]
  我々は、$O(log2 m)/epsilon2)$$$d$次元状態のサンプルのみを必要とする量子"Threshold Search"アルゴリズムを提供する。 また, $tildeO((log3 m)/epsilon2)$サンプルを用いた仮説選択法も提案する。
  論文  参考訳（メタデータ） (2020-11-22T01:22:37Z)
• 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)

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

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