論文の概要: On Cryptography and Distribution Verification, with Applications to Quantum Advantage

• arxiv url: http://arxiv.org/abs/2510.05028v1
• Date: Mon, 06 Oct 2025 17:05:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-07 16:53:00.005659
• Title: On Cryptography and Distribution Verification, with Applications to Quantum Advantage
• Title（参考訳）: 暗号と分布検証 : 量子アドバンテージへの応用
• Authors: Bruno Cavalar, Eli Goldin, Matthew Gray, Taiga Hiroka, Tomoyuki Morimae,
• Abstract要約: 古典/量子分布の効率検証と古典/量子暗号の関係について検討する。 量子サンプリング可能な分布はすべて$mathbfPPP$アルゴリズムで検証可能であることを示す。
• 参考スコア（独自算出の注目度）: 6.483138672954648
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: One of the most fundamental problems in the field of hypothesis testing is the identity testing problem: whether samples from some unknown distribution $\mathcal{G}$ are actually from some explicit distribution $\mathcal{D}$. It is known that when the distribution $\mathcal{D}$ has support $[N]$, the optimal sample complexity for the identity testing problem is roughly $O(\sqrt{N})$. However, many distributions of interest, including those which can be sampled efficiently, have exponential support size, and therefore the optimal identity tester also requires exponential samples. In this paper, we bypass this lower bound by considering restricted settings. The above $O(\sqrt{N})$ sample complexity identity tester is constructed so that it is not fooled by any (even inefficiently-sampled) distributions. However, in most applications, the distributions under consideration are efficiently sampleable, and therefore it is enough to consider only identity testers that are not fooled by efficiently-sampled distributions. In that case, we can focus on efficient verification with efficient identity testers. We investigate relations between efficient verifications of classical/quantum distributions and classical/quantum cryptography, and show the following results: (i) Every quantumly samplable distribution is verifiable with a $\mathbf{P^{PP}}$ algorithm. (ii) If one-way functions exist, then no sufficiently random classically samplable distribution is efficiently verifiable. (iii) If one-way functions do not exist, then every classically samplable distribution is efficiently verifiable. (iv) If QEFID pairs exist, then there exists a quantumly samplable distribution which is not efficiently verifiable. (v) If one-way puzzles do not exist, then it is possible to verify sampling-based quantum advantage with a efficient quantum computer.
• Abstract（参考訳）: ある未知分布$\mathcal{G}$のサンプルが実際にある明示分布$\mathcal{D}$のサンプルであるかどうか。 分布 $\mathcal{D}$ が $[N]$ をサポートするとき、アイデンティティテスト問題の最適なサンプル複雑性はおよそ $O(\sqrt{N})$ であることが知られている。 しかし、効率的なサンプル化が可能なものを含む多くの興味の分布は指数的な支持サイズを持ち、したがって最適なアイデンティティテスタは指数的なサンプルも必要である。 本稿では、制限された設定を考慮し、この下限をバイパスする。 上記の$O(\sqrt{N})$ sample complexity identity tester は、(非効率にサンプリングされた)分布に騙されないように構成される。 しかし、ほとんどのアプリケーションでは、検討中の分布は効率的にサンプリング可能であるため、効率的にサンプリングされた分布に騙されないアイデンティティテスターのみを考えるのに十分である。 この場合、効率的なアイデンティティテスタによる効率的な検証に重点を置くことができます。 古典/量子分布の効率検証と古典/量子暗号の関係を考察し、以下の結果を示す。 (i)任意の量子サンプリング可能な分布は$\mathbf{P^{PP}}$アルゴリズムで検証可能である。 (ii)片方向関数が存在する場合、十分にランダムな古典的サンプリング可能な分布は効率よく検証されない。 三 片方向関数が存在しないとき、古典的にサンプリング可能な分布はすべて効率よく検証できる。 4) QEFID 対が存在する場合、量子的にサンプリング可能な分布が存在し、効率よく検証できない。 (v)一方向パズルが存在しない場合、効率的な量子コンピュータを用いてサンプリングベースの量子優位性を検証することができる。

関連論文リスト

• Complement Sampling: Provable, Verifiable and NISQable Quantum Advantage in Sample Complexity [0.0]
  1つの量子サンプル(サブセットの要素上の一様重ね合わせの1つのコピー)のみを使用する単純な量子アルゴリズムを提供する。 サンプル対サンプルの設定では、量子計算は古典的な計算よりも最も大きな分離を達成できる。
  論文  参考訳（メタデータ） (2025-02-12T19:00:10Z)
• How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions [0.0]
  本研究では,確率的検証器が解析結果がほぼ正しいことを確認するための証明システムについて検討する。 未知の分布が要求される特性を持っていることを検証する。 我々の主な貢献は、検証者と信頼できない証明者との間の対話的プロトコルであり、任意のプロパティを検証するのに使用できる。
  論文  参考訳（メタデータ） (2024-09-10T15:37:23Z)
• Validation tests of GBS quantum computers give evidence for quantum advantage with a decoherent target [62.997667081978825]
  複数モードデータの検証に指紋としてグループカウント確率の正P位相空間シミュレーションを用いる。 偽データを解き放つ方法を示し、これを古典的なカウントアルゴリズムに適用する。
  論文  参考訳（メタデータ） (2022-11-07T12:00:45Z)
• Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling [5.3098033683382155]
  本研究では,高次元分布におけるアイデンティティテスト問題について検討する。 私たちは、$mathsfCoordinate Oracle$という、非常に弱い条件付きサンプリングオラクルを考えています。 エントロピーの近似テンソル化(英語版)として知られる解析的性質が$n$-次元可視分布$mu$に対して成り立つならば、$tildeO(n/varepsilon)$クエリを使用して、隠れ分布$pi$に対して効率的なアイデンティティテストアルゴリズムが存在することを証明している。
  論文  参考訳（メタデータ） (2022-07-19T06:49:24Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  高確率状態に着目して離散分布を試験する問題について検討する。 一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-09-14T16:09:17Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)

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

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