論文の概要: Proper vs Improper Quantum PAC learning
- arxiv url: http://arxiv.org/abs/2403.03295v1
- Date: Tue, 5 Mar 2024 19:49:44 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-07 16:53:33.962450
- Title: Proper vs Improper Quantum PAC learning
- Title（参考訳）: 不適切な量子PAC学習
- Authors: Ashwin Nayak, Pulkit Sinha
- Abstract要約: 本稿では,サンプリング複雑性を伴う量子クーポンコレクタ問題に対するアルゴリズムを提案する。
両学習モードにおける古典的クーポンコレクタ問題と,そのサンプルの複雑性が一致することを証明した。
パディングがより一般的に、古典的な学習行動から量子環境へと持ち上げられることを願っています。
- 参考スコア（独自算出の注目度）: 3.292420364429101
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A basic question in the PAC model of learning is whether proper learning is
harder than improper learning. In the classical case, there are examples of
concept classes with VC dimension $d$ that have sample complexity
$\Omega\left(\frac d\epsilon\log\frac1\epsilon\right)$ for proper learning with
error $\epsilon$, while the complexity for improper learning is O$\!\left(\frac
d\epsilon\right)$. One such example arises from the Coupon Collector problem.
Motivated by the efficiency of proper versus improper learning with quantum
samples, Arunachalam, Belovs, Childs, Kothari, Rosmanis, and de Wolf (TQC 2020)
studied an analogue, the Quantum Coupon Collector problem. Curiously, they
discovered that for learning size $k$ subsets of $[n]$ the problem has sample
complexity $\Theta(k\log\min\{k,n-k+1\})$, in contrast with the complexity of
$\Theta(k\log k)$ for Coupon Collector. This effectively negates the
possibility of a separation between the two modes of learning via the quantum
problem, and Arunachalam et al.\ posed the possibility of such a separation as
an open question.
In this work, we first present an algorithm for the Quantum Coupon Collector
problem with sample complexity that matches the sharper lower bound of
$(1-o_k(1))k\ln\min\{k,n-k+1\}$ shown recently by Bab Hadiashar, Nayak, and
Sinha (IEEE TIT 2024), for the entire range of the parameter $k$. Next, we
devise a variant of the problem, the Quantum Padded Coupon Collector. We prove
that its sample complexity matches that of the classical Coupon Collector
problem for both modes of learning, thereby exhibiting the same asymptotic
separation between proper and improper quantum learning as mentioned above. The
techniques we develop in the process can be directly applied to any form of
padded quantum data. We hope that padding can more generally lift other forms
of classical learning behaviour to the quantum setting.
- Abstract（参考訳）: PAC学習モデルにおける基本的な疑問は、適切な学習が不適切な学習よりも難しいかどうかである。
古典的なケースでは、VC次元が$d$のコンセプトクラスにはサンプル複雑性を持つ例がある: $\Omega\left(\frac d\epsilon\log\frac1\epsilon\right)$ for proper learning with error $\epsilon$, and the complexity for improper learning is O$!
\left(\frac d\epsilon\right)$
そのような例の1つはクーポンコレクター問題から生じる。
arunachalam, belovs, childs, kothari, rosmanis, de wolf (tqc 2020)は、量子サンプルを用いた適切な学習と不適切な学習の効率に動機づけられ、類似の量子クーポンコレクター問題の研究を行った。
奇妙なことに、学習サイズ$k$$$[n]$の場合、問題はサンプル複雑性$\Theta(k\log\min\{k,n-k+1\})$であり、Coupon Collectorの$\Theta(k\log k)$の複雑さとは対照的である。
これにより、量子問題による2つの学習モードとArunachalamらとの分離の可能性を効果的に否定する。
\は、そのような分離がオープンな問題である可能性を示唆した。
そこで本研究では,bab hadiashar,nayak,sinha (ieee tit 2024) によって最近提示された$(1-o_k(1))k\ln\min\{k,n-k+1\}$のシャープな下限に一致するサンプル複雑性を持つ量子クーポンコレクタ問題のアルゴリズムを提案する。
次に、この問題の変種であるQuantum Padded Coupon Collectorを考案する。
本研究は,古典的クーポンコレクタ問題と学習モードの両問題とが一致し,量子学習の完全性と不適切なことの漸近的分離が示されることを示した。
このプロセスで私たちが開発する技術は、パッド化された任意の量子データに直接適用することができる。
我々は、パディングがより一般的に、古典的学習行動の他の形態を量子環境へ持ち上げることを望んでいる。
関連論文リスト
- New Bounds on Quantum Sample Complexity of Measurement Classes [18.531114735719274]
本稿では量子状態からの古典的推論のための量子教師あり学習について研究する。
学習の難しさは、よく知られたほぼ正しい(PAC)量子対して、サンプルの複雑さによって測定される
論文 参考訳（メタデータ） (2024-08-22T18:43:13Z) - Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Provable Advantage in Quantum PAC Learning [3.291862617649511]
PAC学習者は量子学習において汎用的な優位性を得ることができることを示す。
多相性因子は古典的な学習サンプルの複雑さよりも正方形の改善である。
論文 参考訳（メタデータ） (2023-09-19T19:26:20Z) - Testing and Learning Quantum Juntas Nearly Optimally [3.030969076856776]
量子量$k$-juntasの検証と学習の問題を考察する。
a)$widetildeO(sqrtk)$-query量子アルゴリズムを与え、量子$k$-juntaと量子$k$-juntaの「遠い」ユニタリ行列を区別することができる。
我々は、量子$k$-juntasのテストと量子$k$-juntasの学習のための上限を、ほぼ一致する$Omega(sqrtk)$と$Omega(frac)$で補完する。
論文 参考訳（メタデータ） (2022-07-13T00:11:14Z) - 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) - Exponential separations between learning with and without quantum memory [17.763817187554096]
量子システムと力学の学習特性を学習するための量子メモリのパワーについて検討する。
多くの最先端の学習アルゴリズムは、追加の外部量子メモリへのアクセスを必要とする。
このトレードオフは、幅広い学習問題に固有のものであることを示す。
論文 参考訳（メタデータ） (2021-11-10T19:03:49Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。