On Cryptography and Distribution Verification, with Applications to Quantum Advantage

• URL: http://arxiv.org/abs/2510.05028v2
• Date: Mon, 10 Nov 2025 07:22:18 GMT
• Title: On Cryptography and Distribution Verification, with Applications to Quantum Advantage
• Authors: Bruno Cavalar, Eli Goldin, Matthew Gray, Taiga Hiroka, Tomoyuki Morimae,
• Abstract summary: One of the most fundamental problems in the field of hypothesis testing is the identity testing problem.<n>We investigate relations between efficient verification of classical/quantum distributions with classical/quantum cryptography.
• Score: 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.

Related papers

• Large Language Models Are Bad Dice Players: LLMs Struggle to Generate Random Numbers from Statistical Distributions [50.1404916337174]
  We present the first large-scale, statistically powered audit of native probabilistic sampling in large language models (LLMs)<n>We show that batch generation achieves only modest statistical validity, with a 13% median pass rate, while independent requests collapse almost entirely.<n>We conclude that current LLMs lack a functional internal sampler, necessitating the use of external tools for applications requiring statistical guarantees.
  arXiv  Detail & Related papers  (2026-01-08T22:33:12Z)
• Complement Sampling: Provable, Verifiable and NISQable Quantum Advantage in Sample Complexity [0.0]
  We give a simple quantum algorithm that uses only a single quantum sample -- a single copy of the uniform superposition over elements of the subset.<n>In a sample-to-sample setting, quantum computation can achieve the largest possible separation over classical computation.
  arXiv  Detail & Related papers  (2025-02-12T19:00:10Z)
• How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions [0.0]
  We study proof-systems that allow a probabilistic verifier to ascertain that the results of an analysis are approximately correct. We focus on distribution testing problems: verifying that an unknown distribution has a claimed property. Our main contribution is a interactive protocol between a verifier and an untrusted prover which can be used to verify any property.
  arXiv  Detail & Related papers  (2024-09-10T15:37:23Z)
• Validation tests of GBS quantum computers give evidence for quantum advantage with a decoherent target [62.997667081978825]
  We use positive-P phase-space simulations of grouped count probabilities as a fingerprint for verifying multi-mode data. We show how one can disprove faked data, and apply this to a classical count algorithm.
  arXiv  Detail & Related papers  (2022-11-07T12:00:45Z)
• Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling [5.3098033683382155]
  We study the identity testing problem for high-dimensional distributions. We consider a significantly weaker conditional sampling oracle, which we call the $mathsfCoordinate Oracle$. We prove that if an analytic property known as approximate tensorization of entropy holds for an $n$-dimensional visible distribution $mu$, then there is an efficient identity testing algorithm for any hidden distribution $pi$ using $tildeO(n/varepsilon)$ queries.
  arXiv  Detail & Related papers  (2022-07-19T06:49:24Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  We are given i.i.d. samples from a distribution of the form $Z = (1-epsilon) X + epsilon B$, where $X$ is a zero-mean and unknown covariance Gaussian $mathcalN(0, Sigma)$. In the absence of contamination, prior work gave a simple tester for this hypothesis testing task that uses $O(d)$ samples. We prove a sample complexity lower bound of $Omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma
  arXiv  Detail & Related papers  (2020-12-31T18:24:41Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  We study the problem of testing discrete distributions with a focus on the high probability regime. We provide the first algorithms for closeness and independence testing that are sample-optimal, within constant factors.
  arXiv  Detail & Related papers  (2020-09-14T16:09:17Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  Two players each receive $t$ samples from one distribution over $[n]$. The goal is to decide whether their two distributions are equal, or are $epsilon$-far apart. We show that the quantum communication complexity of this problem is $tildeO$(tepsilon2))$ qubits when distributions have low $l$-norm.
  arXiv  Detail & Related papers  (2020-06-26T09:05:58Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.