論文の概要: 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) は、この問題の量子サンプルの複雑さを一定要素まで特徴づけた。 まず,上述した情報理論のアプローチが最適下界を導出しないことを示す。 副産物として、任意の高次元の純粋な状態の自然なアンサンブルが得られ、それは(同時に)容易に区別できない。 第二に、情報理論的なアプローチは問題の近似変種に対する漸近的最適境界をもたらすことを発見した。 最後に,量子クーポンコレクタ問題に対するよりシャープな下界を,アンサンブルの識別性に基づく一般化されたホレボ・カルランダー境界を通じて導出する。 量子クーポンコレクター問題のすべての側面は、関連するグラマー行列のスペクトルの性質に残っており、これは独立な関心を持つかもしれない。

関連論文リスト

• Few measurement shots challenge generalization in learning to classify entanglement [0.0]
  本稿では,古典的機械学習手法を量子アルゴリズムと組み合わせたハイブリッド量子学習技術に焦点を当てる。 いくつかの設定では、いくつかの測定ショットから生じる不確実性がエラーの主な原因であることを示す。 従来の影をベースとした推定器を導入し,その性能を向上する。
  論文  参考訳（メタデータ） (2024-11-10T21:20:21Z)
• Bosonic Quantum Computational Complexity [0.0]
  私たちはそのような研究計画の基礎をつくった。 本稿では,BQPのボゾン一般化に基づく自然複雑性クラスと問題を紹介する。 ボソニックハミルトニアンのスペクトルの有界性を決定する問題はコ-NPハードであることを示す。
  論文  参考訳（メタデータ） (2024-10-05T19:43:41Z)
• Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem [70.42372213666553]
  No-Free-Lunch(NFL)定理は、最適化プロセスに関係なく問題とデータ非依存の一般化誤差を定量化する。 我々は、様々な量子学習アルゴリズムを、特定の観測可能条件下で量子力学を学習するために設計された3つの学習プロトコルに分類する。 得られたNFL定理は, CLC-LP, ReQu-LP, Qu-LPにまたがるサンプルの複雑性を2次的に低減することを示した。 この性能差は、非直交量子状態のグローバル位相に関する情報を間接的に活用するために、量子関連学習プロトコルのユニークな能力に起因している。
  論文  参考訳（メタデータ） (2024-05-12T09:05:13Z)
• 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)

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

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