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

• arxiv url: http://arxiv.org/abs/2510.05028v2
• Date: Mon, 10 Nov 2025 07:22:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-11 14:56:00.264851
• Title: On Cryptography and Distribution Verification, with Applications to Quantum Advantage
• Title（参考訳）: 暗号と分布検証 : 量子アドバンテージへの応用
• Authors: Bruno Cavalar, Eli Goldin, Matthew Gray, Taiga Hiroka, Tomoyuki Morimae,
• Abstract要約: 仮説テストの分野における最も基本的な問題の1つはアイデンティティテストの問題である。 古典/量子分布の効率的な検証と古典/量子暗号の関係について検討する。
• 参考スコア（独自算出の注目度）: 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 samplable, and therefore it is enough to consider only identity testers that are not fooled by efficiently-sampled distributions. In this setting we can hope to construct efficient identity testers. We investigate relations between efficient verification of classical/quantum distributions with classical/quantum cryptography, showing the following results: (1). Classically efficiently samplable distributions are verifiable if and only if one-way functions do not exist. (2). Quantumly efficiently samplable distributions are verifiable by $\mathbf{P}^\mathbf{PP}$ with a polynomial number of samples. (3). Sampling-based quantum advantage can be verified quantumly (with a polynomial number of samples) if one-way puzzles do not exist. (4). If QEFID pairs exist, then some quantumly efficiently samplable distributions are not verifiable.
• Abstract（参考訳）: ある未知分布$\mathcal{G}$のサンプルが実際にある明示分布$\mathcal{D}$のサンプルであるかどうか。 分布 $\mathcal{D}$ が $[N]$ をサポートするとき、アイデンティティテスト問題の最適なサンプル複雑性はおよそ $O(\sqrt{N})$ であることが知られている。 しかし、効率的なサンプル化が可能なものを含む多くの興味の分布は指数的な支持サイズを持ち、したがって最適なアイデンティティテスタは指数的なサンプルも必要である。 本稿では、制限された設定を考慮し、この下限をバイパスする。 上記の$O(\sqrt{N})$ sample complexity identity tester は、(非効率にサンプリングされた)分布に騙されないように構成される。 しかし、ほとんどのアプリケーションでは、検討中の分布は効率的にサンプリング可能であるため、効率的にサンプリングされた分布に騙されないアイデンティティテスターのみを考えるのに十分である。 この設定では、効率的なアイデンティティテスタを構築したいと思っています。 本研究では,古典/量子分布の効率検証と古典/量子暗号の関係を考察し,以下の結果を示した。 古典的に効率的にサンプリング可能な分布は、一方通行関数が存在しない場合にのみ検証可能である。 (2)。 量子的に効率的にサンプリング可能な分布は、多項式数のサンプルを持つ$\mathbf{P}^\mathbf{PP}$で検証できる。 (3)。 サンプリングに基づく量子優位性は、一方のパズルが存在しない場合、(サンプルの多項式数で)量子的に検証することができる。 (4)。 QEFID対が存在する場合、量子的に効率的にサンプリング可能な分布は検証できない。

関連論文リスト

• 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)

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

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