Uniformity testing when you have the source code

• URL: http://arxiv.org/abs/2411.04972v1
• Date: Thu, 07 Nov 2024 18:48:29 GMT
• Title: Uniformity testing when you have the source code
• Abstract summary: We study quantum algorithms for verifying properties of the output probability distribution of a classical or quantum circuit. We consider the basic task of uniformity testing, which is to decide if the output distribution is uniform on $[d]$ or $epsilon$-far from uniform in total variation distance.
• Score: 16.232881331802687
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study quantum algorithms for verifying properties of the output probability distribution of a classical or quantum circuit, given access to the source code that generates the distribution. We consider the basic task of uniformity testing, which is to decide if the output distribution is uniform on $[d]$ or $\epsilon$-far from uniform in total variation distance. More generally, we consider identity testing, which is the task of deciding if the output distribution equals a known hypothesis distribution, or is $\epsilon$-far from it. For both problems, the previous best known upper bound was $O(\min\{d^{1/3}/\epsilon^{2},d^{1/2}/\epsilon\})$. Here we improve the upper bound to $O(\min\{d^{1/3}/\epsilon^{4/3}, d^{1/2}/\epsilon\})$, which we conjecture is optimal.

Related papers

• Quantum Speedups for Testing Similar Means [4.1765120028423]
  This work focuses on quantum algorithms for testing whether $m$ distributions have similar means or are $$-far from mean similarity under two models.<n>In the query model, the algorithm can choose which distribution to sample from, whereas in the sampling model, the distributions are selected uniformly.
  arXiv  Detail & Related papers  (2026-08-01T16:23:28Z)
• Rényi divergence-based uniformity guarantees for $k$-universal hash functions [59.90381090395222]
  Universal hash functions map the output of a source to random strings over a finite alphabet. We show that it is possible to distill random bits that are nearly uniform, as measured by min-entropy.
  arXiv  Detail & Related papers  (2024-10-21T19:37:35Z)
• Replicable Uniformity Testing [1.5883812630616523]
  This work revisits uniformity testing under the framework of algorithmic replicability. We obtain a replicable tester using only $tildeO(sqrtn varepsilon-2 rho-1)$ samples.
  arXiv  Detail & Related papers  (2024-10-12T02:55:17Z)
• Out-of-Distribution Detection using Maximum Entropy Coding [4.7768369720936255]
  For discrete distributions, the definitive answer is in principle given by Kolmogorov-Martin-L"of randomness. We transform data into a standard distribution in the latent space using a bidirectional generate network and use maximum entropy coding there.
  arXiv  Detail & Related papers  (2024-04-25T20:28:43Z)
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
  We explore potential quantum speedups for the fundamental problem of testing the properties of closeness and $k$-wise uniformity of probability distributions. We show that the quantum query complexities for $ell1$- and $ell2$-closeness testing are $O(sqrtn/varepsilon)$ and $O(sqrtnk/varepsilon)$. We propose the first quantum algorithm for this problem with query complexity $O(sqrtnk/varepsilon)
  arXiv  Detail & Related papers  (2023-04-25T15:32:37Z)
• Robust Mean Estimation Without Moments for Symmetric Distributions [7.105512316884493]
  We show that for a large class of symmetric distributions, the same error as in the Gaussian setting can be achieved efficiently. We propose a sequence of efficient algorithms that approaches this optimal error. Our algorithms are based on a generalization of the well-known filtering technique.
  arXiv  Detail & Related papers  (2023-02-21T17:52:23Z)
• Sharp Constants in Uniformity Testing via the Huber Statistic [16.384142529375435]
  Uniformity testing is one of the most well-studied problems in property testing. It is known that the optimal sample complexity to distinguish the uniform distribution on $m$ elements from any $epsilon$-far distribution with $1-delta probability is $n. We show that the collisions tester achieves a sharp maximal constant in the number of standard deviations of separation between uniform and non-uniform inputs.
  arXiv  Detail & Related papers  (2022-06-21T20:43:53Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• 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)
• 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)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

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.