論文の概要: Unconditional Quantum PAC Learning Advantage in the Large Error Regime

• arxiv url: http://arxiv.org/abs/2610.23268v1
• Date: Fri, 16 Oct 2026 10:41:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-20 00:56:07.878169
• Title: Unconditional Quantum PAC Learning Advantage in the Large Error Regime
• Title（参考訳）: 大規模エラーレジームにおける非条件量子PAC学習の有用性
• Abstract要約: 関数の量子的学習と古典的学習を非条件で分離する。 堅牢なPAC学習の利点は、大きなエラー状態において無条件に保持する。 堅牢な量子PAC学習の利点は、大きなエラー状態において無条件に保たれるが、小さなエラー状態における量子学習と古典学習の類似的な分離は、$mathsfNP nsubseteq mathsfB$を暗示する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We establish an unconditional super-polynomial separation between quantum and classical PAC learning of Boolean functions under the uniform distribution in the large error regime. For every advantage $λ(n) = n^{-ω(1)}$, we construct a concept class that a polynomial-time quantum learner learns to agreement $1/2+λ(n)$ with success probability at least $1-1/n^k$. The learner uses only quantum random examples and outputs a polynomial-size deterministic classical circuit. In contrast, no polynomial-time classical learner achieves agreement $1/2 + λ(n)/n^k$ with success probability greater than $1/n^k$, even with membership queries. To achieve this, we develop a nearly-optimal quantum learner that uses quantum random examples to produce a hypothesis achieving a prescribed correlation with an arbitrary Boolean function. The learner generalizes Fourier sampling from parity hypotheses to quadratic hypotheses. While standard Fourier sampling is insensitive to the sign of the correlation, we use interference to bias sampling toward positively correlated hypotheses. This is combined with a careful analysis of the resulting distribution to boost both the learner's success probability and its agreement with the target function. We believe that the resulting quantum learning algorithm might be of independent interest. Finally, although a robust quantum PAC learning advantage holds unconditionally in the large error regime, we note that an analogous separation between quantum and classical learning in the small error regime would imply that $\mathsf{NP} \nsubseteq \mathsf{BPP}$.
• Abstract（参考訳）: 我々は,大誤差状態の均一分布下でのブール関数の量子と古典的PAC学習の非条件的超多項式分離を確立する。 すべての有利な$λ(n) = n^{-ω(1)}$に対して、多項式時間量子学習者が少なくとも1-1/n^k$の確率で1/2+λ(n)$と一致することを学習する概念クラスを構築する。 学習者は量子ランダムな例のみを使用し、多項式サイズの決定論的古典回路を出力する。 対照的に、多項式時間古典学習者は1/2 + λ(n)/n^k$ の一致を得られず、その成功確率は1/n^k$ より大きい。 これを実現するために、量子ランダムな例を用いて任意のブール関数と所定の相関を達成できる仮説を生成する、ほぼ最適量子学習器を開発した。 学習者はパリティ仮説から二次仮説へのフーリエサンプリングを一般化する。 標準フーリエサンプリングは相関の兆候に敏感であるが,正の相関仮説に対するバイアスサンプリングには干渉を用いる。 これは、学習者の成功確率と目標関数との一致の両方を高めるために、結果の分布を慎重に分析することと組み合わせられる。 得られた量子学習アルゴリズムは、独立した関心事であると信じている。 最後に、ロバストな量子PAC学習の利点は、大きなエラー状態において無条件に保たれるが、小さなエラー状態における量子学習と古典学習の類似的な分離は、$\mathsf{NP} \nsubseteq \mathsf{BPP}$を意味する。

関連論文リスト

• Verifiable quantum advantage based on polynomials with planted structures [13.376362080307027]
  検証可能なシミュレーションシークレットのアイデアを,検証可能な優位性のために開発する。 検証者はシミュレーション秘密を使って、クロスエントロピーテストを評価することができる。
  論文  参考訳（メタデータ） (2026-09-30T15:08:28Z)
• On the Cryptographic Structure Required for Verifying Qubits [4.440305753099884]
  我々は、(ある種の)古典的なアンチ・コンミューテーションテストから強力な暗号を構築する。 量子後KAとOTの硬度増幅に関する最初の既知の結果を提供するが、通信は古典的だが、敵は量子的かもしれない。
  論文  参考訳（メタデータ） (2026-06-04T00:16:07Z)
• Provable Advantage in Quantum PAC Learning [3.291862617649511]
  PAC学習者は量子学習において汎用的な優位性を得ることができることを示す。 多相性因子は古典的な学習サンプルの複雑さよりも正方形の改善である。
  論文  参考訳（メタデータ） (2023-09-19T19:26:20Z)
• Optimal lower bounds for Quantum Learning via Information Theory [3.093890460224435]
  我々は、PACとモデルの両方において、情報理論的アプローチにより、量子サンプルの複雑さに対して最適な下界を導出する。 次に、確率論から古典的な問題であるクーポンコレクタ問題(英語版)の量子アナログに目を向ける。 量子クーポンコレクター問題のすべての側面は、関連するグラム行列のスペクトルの性質について研究する。
  論文  参考訳（メタデータ） (2023-01-05T18:55:04Z)
• Validation tests of GBS quantum computers give evidence for quantum advantage with a decoherent target [62.997667081978825]
  複数モードデータの検証に指紋としてグループカウント確率の正P位相空間シミュレーションを用いる。 偽データを解き放つ方法を示し、これを古典的なカウントアルゴリズムに適用する。
  論文  参考訳（メタデータ） (2022-11-07T12:00:45Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。 ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
  論文  参考訳（メタデータ） (2022-07-07T08:04:15Z)
• Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
  証明者と検証者の間の「相互作用」は、検証可能性と実装のギャップを埋めることができる。 イオントラップ量子コンピュータを用いた対話型量子アドバンストプロトコルの最初の実装を実演する。
  論文  参考訳（メタデータ） (2021-12-09T19:00:00Z)
• Learnability of the output distributions of local quantum circuits [53.17490581210575]
  2つの異なるオラクルモデルにおいて、量子回路Bornマシンの学習可能性について検討する。 我々はまず,超対数深度クリフォード回路の出力分布がサンプル効率良く学習できないという負の結果を示した。 より強力なオラクルモデル、すなわちサンプルに直接アクセスすると、局所的なクリフォード回路の出力分布は計算効率よくPACを学習可能であることを示す。
  論文  参考訳（メタデータ） (2021-10-11T18:00:20Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)

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

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