論文の概要: Hardness of Quantum Distribution Learning and Quantum Cryptography

• arxiv url: http://arxiv.org/abs/2507.01292v1
• Date: Wed, 02 Jul 2025 02:12:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-03 14:22:59.983942
• Title: Hardness of Quantum Distribution Learning and Quantum Cryptography
• Title（参考訳）: 量子分布学習と量子暗号の硬さ
• Authors: Taiga Hiroka, Min-Hsiu Hsieh, Tomoyuki Morimae,
• Abstract要約: ワンウェイパズル(OWPuzzs)はワンウェイ関数(OWFs)の自然量子アナログを提供する。 本稿では、よく研究された学習モデルの硬さに基づくOWPuzzの完全な特徴付けとして、分布学習を初めて確立する。
• 参考スコア（独自算出の注目度）: 11.85957541950196
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The existence of one-way functions (OWFs) forms the minimal assumption in classical cryptography. However, this is not necessarily the case in quantum cryptography. One-way puzzles (OWPuzzs), introduced by Khurana and Tomer, provide a natural quantum analogue of OWFs. The existence of OWPuzzs implies $PP\neq BQP$, while the converse remains open. In classical cryptography, the analogous problem-whether OWFs can be constructed from $P \neq NP$-has long been studied from the viewpoint of hardness of learning. Hardness of learning in various frameworks (including PAC learning) has been connected to OWFs or to $P \neq NP$. In contrast, no such characterization previously existed for OWPuzzs. In this paper, we establish the first complete characterization of OWPuzzs based on the hardness of a well-studied learning model: distribution learning. Specifically, we prove that OWPuzzs exist if and only if proper quantum distribution learning is hard on average. A natural question that follows is whether the worst-case hardness of proper quantum distribution learning can be derived from $PP \neq BQP$. If so, and a worst-case to average-case hardness reduction is achieved, it would imply OWPuzzs solely from $PP \neq BQP$. However, we show that this would be extremely difficult: if worst-case hardness is PP-hard (in a black-box reduction), then $SampBQP \neq SampBPP$ follows from the infiniteness of the polynomial hierarchy. Despite that, we show that $PP \neq BQP$ is equivalent to another standard notion of hardness of learning: agnostic. We prove that $PP \neq BQP$ if and only if agnostic quantum distribution learning with respect to KL divergence is hard. As a byproduct, we show that hardness of agnostic quantum distribution learning with respect to statistical distance against $PPT^{\Sigma_3^P}$ learners implies $SampBQP \neq SampBPP$.
• Abstract（参考訳）: ワンウェイ関数(OWF)の存在は、古典暗号における最小の仮定を形成する。 しかし、量子暗号では必ずしもそうではない。 KhuranaとTomerによって導入されたワンウェイパズル(OWPuzzs)は、OWFの自然な量子アナログを提供する。 OWPuzzsの存在は$PP\neq BQP$を意味するが、逆は開である。 古典暗号において、OWFが$P \neq NP$-hasから構築できるかどうかという類似の問題は、学習の難しさの観点から長い間研究されてきた。 様々なフレームワーク(PAC学習を含む)での学習の困難さは、OWFや$P \neq NP$に関連付けられている。 対照的に、OWPuzzs にはそのような特徴は存在しなかった。 本稿では、よく研究された学習モデルの硬さに基づくOWPuzzの完全な特徴付けとして、分布学習を初めて確立する。 具体的には、適切な量子分布学習が平均的に困難である場合にのみOWPuzzが存在することを示す。 従う自然な疑問は、適切な量子分布学習の最悪のハードネスが$PP \neq BQP$から導かれるかどうかである。 もしそうなら、平均ケースの硬度を下げる最悪のケースは、$PP \neq BQP$のみからOWPuzzsを暗示する。 しかし、最悪ケース硬度がPPハードであれば(ブラックボックス還元の場合)、$SampBQP \neq SampBPP$は多項式階層の無限性から従う。 それにもかかわらず、$PP \neq BQP$は学習の難しさという別の標準概念と等価である。 PP \neq BQP$は、KLの発散に関して学習する非依存的な量子分布が困難である場合に限る。 副産物として、PPT^{\Sigma_3^P}$学習者に対する統計的距離に対する非依存的な量子分布学習の難しさは、$SampBQP \neq SampBPP$を意味することを示す。

関連論文リスト

• Complexity Theory for Quantum Promise Problems [5.049812996253858]
  p/mBQP, p/mQ(C)MA, $textp/mQSZK_texthv$, p/mQIP, p/mBQP/qpoly, p/mBQP/poly, p/mPSPACEの構造結果を示す。 驚いたことに、我々の発見は、彼らの古典的な類推から分岐する関係を明らかにした。 応用においては、量子暗号、量子特性試験、およびユニタリ合成における興味深い問題に対処する。
  論文  参考訳（メタデータ） (2024-11-06T07:29:52Z)
• Quantum Cryptography and Meta-Complexity [2.6089354079273512]
  古典暗号では、ワンウェイ関数(OWF)は最小の仮定であるが、量子暗号ではそうではない。 片方向パズル(OWPuzzs)がGapKが弱量子平均ハードである場合にのみ存在することを示す。 また、量子PRGが存在する場合、GapKは量子平均ハードであることを示す。
  論文  参考訳（メタデータ） (2024-10-02T09:30:06Z)
• New Bounds on Quantum Sample Complexity of Measurement Classes [18.531114735719274]
  本稿では量子状態からの古典的推論のための量子教師あり学習について研究する。 学習の難しさは、よく知られたほぼ正しい(PAC)量子対して、サンプルの複雑さによって測定される
  論文  参考訳（メタデータ） (2024-08-22T18:43:13Z)
• Proper vs Improper Quantum PAC learning [3.292420364429101]
  本稿では,サンプリング複雑性を伴う量子クーポンコレクタ問題に対するアルゴリズムを提案する。 両学習モードにおける古典的クーポンコレクタ問題と,そのサンプルの複雑性が一致することを証明した。 パディングがより一般的に、古典的な学習行動から量子環境へと持ち上げられることを願っています。
  論文  参考訳（メタデータ） (2024-03-05T19:49:44Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Provable Advantage in Quantum PAC Learning [3.291862617649511]
  PAC学習者は量子学習において汎用的な優位性を得ることができることを示す。 多相性因子は古典的な学習サンプルの複雑さよりも正方形の改善である。
  論文  参考訳（メタデータ） (2023-09-19T19:26:20Z)
• On sampling determinantal and Pfaffian point processes on a quantum computer [49.1574468325115]
  DPPは1970年代の量子光学のモデルとしてマッキによって導入された。 ほとんどのアプリケーションはDPPからのサンプリングを必要としており、その量子起源を考えると、古典的なコンピュータでDPPをサンプリングするのは古典的なものよりも簡単かどうか疑問に思うのが自然である。 バニラサンプリングは、各コスト$mathcalO(N3)$と$mathcalO(Nr2)$の2つのステップから構成される。
  論文  参考訳（メタデータ） (2023-05-25T08:43:11Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Quantum double aspects of surface code models [77.34726150561087]
  基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。 有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:03:38Z)
• Quantum Coupon Collector [62.58209964224025]
  我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。 我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-02-18T16:14:55Z)

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

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