論文の概要: Optimal lower bounds for Quantum Learning via Information Theory
- arxiv url: http://arxiv.org/abs/2301.02227v3
- Date: Tue, 27 Feb 2024 23:20:19 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-29 19:20:53.059738
- Title: Optimal lower bounds for Quantum Learning via Information Theory
- Title(参考訳): 情報理論による量子学習のための最適下界
- Authors: Shima Bab Hadiashar, Ashwin Nayak, Pulkit Sinha
- Abstract要約: 我々は、PACとモデルの両方において、情報理論的アプローチにより、量子サンプルの複雑さに対して最適な下界を導出する。
次に、確率論から古典的な問題であるクーポンコレクタ問題(英語版)の量子アナログに目を向ける。
量子クーポンコレクター問題のすべての側面は、関連するグラム行列のスペクトルの性質について研究する。
- 参考スコア(独自算出の注目度): 3.093890460224435
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Although a concept class may be learnt more efficiently using quantum samples
as compared with classical samples in certain scenarios, Arunachalam and de
Wolf (JMLR, 2018) proved that quantum learners are asymptotically no more
efficient than classical ones in the quantum PAC and Agnostic learning models.
They established lower bounds on sample complexity via quantum state
identification and Fourier analysis. In this paper, we derive optimal lower
bounds for quantum sample complexity in both the PAC and agnostic models via an
information-theoretic approach. The proofs are arguably simpler, and the same
ideas can potentially be used to derive optimal bounds for other problems in
quantum learning theory.
We then turn to a quantum analogue of the Coupon Collector problem, a classic
problem from probability theory also of importance in the study of PAC
learning. Arunachalam, Belovs, Childs, Kothari, Rosmanis, and de Wolf (TQC,
2020) characterized the quantum sample complexity of this problem up to
constant factors. First, we show that the information-theoretic approach
mentioned above provably does not yield the optimal lower bound. As a
by-product, we get a natural ensemble of pure states in arbitrarily high
dimensions which are not easily (simultaneously) distinguishable, while the
ensemble has close to maximal Holevo information. Second, we discover that the
information-theoretic approach yields an asymptotically optimal bound for an
approximation variant of the problem. Finally, we derive a sharper lower bound
for the Quantum Coupon Collector problem, via the generalized Holevo-Curlander
bounds on the distinguishability of an ensemble. All the aspects of the Quantum
Coupon Collector problem we study rest on properties of the spectrum of the
associated Gram matrix, which may be of independent interest.
- Abstract(参考訳): Arunachalam and de Wolf (JMLR, 2018) は、量子学習者は量子PACとAgnostic学習モデルにおける古典的なものよりも漸近的に効率が良くないことを証明した。
彼らは量子状態の同定とフーリエ解析によってサンプルの複雑さの低い境界を確立した。
本稿では,PACモデルと非依存モデルの両方において,情報理論的手法を用いて量子サンプル複雑性の最適下界を導出する。
証明は間違いなく単純であり、同じアイデアは量子学習理論における他の問題の最適境界を導出するためにも使用できる。
次に、確率論の古典的な問題であるクーポンコレクタ問題(英語版)の量子アナログ(英語版)に目を向け、pac学習の研究においても重要である。
Arunachalam, Belovs, Childs, Kothari, Rosmanis, de Wolf (TQC, 2020) は、この問題の量子サンプルの複雑さを一定要素まで特徴づけた。
まず,上述した情報理論のアプローチが最適下界を導出しないことを示す。
副産物として、任意の高次元の純粋な状態の自然なアンサンブルが得られ、それは(同時に)容易に区別できない。
第二に、情報理論的なアプローチは問題の近似変種に対する漸近的最適境界をもたらすことを発見した。
最後に,量子クーポンコレクタ問題に対するよりシャープな下界を,アンサンブルの識別性に基づく一般化されたホレボ・カルランダー境界を通じて導出する。
量子クーポンコレクター問題のすべての側面は、関連するグラマー行列のスペクトルの性質に残っており、これは独立な関心を持つかもしれない。
関連論文リスト
- Learning unitaries with quantum statistical queries [0.0]
量子統計クエリ(QSQ)からユニタリ演算子を学習するためのいくつかのアルゴリズムを提案する。
本手法は, 1つの量子統計的クエリを用いて, パウリ弦の部分集合上のユニタリのフーリエ質量を推定する新しい手法に基づく。
量子統計的クエリは,Choi-Jamiolkowski状態に対する分離可能な測定値と比較して,特定のタスクに対して指数関数的に大きなサンプル複雑性をもたらすことを示す。
論文 参考訳(メタデータ) (2023-10-03T17:56:07Z) - Ansatz-Agnostic Exponential Resource Saving in Variational Quantum
Algorithms Using Shallow Shadows [5.618657159109373]
変分量子アルゴリズム(VQA)は、短期的な量子優位性の実証の有望な候補として特定されている。
本報告では,本論文で研究されている浅層アンザッツに対して,同様のレベルの貯蓄を実現するための浅層影に基づくプロトコルを提案する。
VQAが強力な選択肢となる量子情報、すなわち変分量子状態準備と変分量子回路合成の2つの重要な応用が示されている。
論文 参考訳(メタデータ) (2023-09-09T11:00:39Z) - A simple formulation of no-cloning and no-hiding that admits efficient
and robust verification [0.0]
不和合性は古典理論とは別の量子論の特徴である。
ノーハイディング定理(英: no-hiding theorem)は、ブラックホール情報パラドックス(英語版)の文脈で生じる別の例である。
量子論の基本的特徴のどちらも、効率的な検証が可能な単一形式で定式化する。
論文 参考訳(メタデータ) (2023-03-05T12:48:11Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。
我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。
すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
論文 参考訳(メタデータ) (2023-03-02T14:18:17Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳(メタデータ) (2022-09-28T17:53:25Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳(メタデータ) (2022-05-26T20:32:36Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳(メタデータ) (2022-03-30T02:02:16Z) - Probably approximately correct quantum source coding [0.0]
Holevo と Nayak の境界は、量子状態に格納できる古典的な情報の量を推定する。
量子学習理論における2つの新しい応用と、純粋に古典的なクライアントを用いた代入量子計算について述べる。
論文 参考訳(メタデータ) (2021-12-13T17:57:30Z) - A Theoretical Framework for Learning from Quantum Data [15.828697880068704]
量子データから古典パターンを学習するための理論的基盤を提案する。
我々はよく知られたPACフレームワークの量子対について述べる。
量子サンプル複雑性量子概念クラスの上界を確立する。
論文 参考訳(メタデータ) (2021-07-13T21:39:47Z) - From a quantum theory to a classical one [117.44028458220427]
量子対古典的交叉を記述するための形式的アプローチを提示し議論する。
この手法は、1982年にL. Yaffeによって、大きな$N$の量子場理論に取り組むために導入された。
論文 参考訳(メタデータ) (2020-04-01T09:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。