Uniformity Testing When You Have the Source Code

We study the quantum query complexity of finding a collision for a function f whose outputs are chosen according to a non-uniform distribution D. We derive some upper bounds and lower bounds depending on the min-entropy and the collision-entropy of D. In particular, we improve the previous lower bound by Ebrahimi Targhi et al. from \Omega(2^{k/9}) to \Omega(2^{k/5}) where k is the min-entropy of D.

Quantum Information and ComputationDec 1, 20182 citations

Tight bounds on the convergence of noisy random circuits to uniform.

Abhinav Deshpande, Bill Fefferman, Alexey Vyacheslavovich Gorshkov +3 more

Dec 1, 20213 citations

Uniformity Testing When You Have the Source Code

Clément L. Canonne, Robin Kothari, O'Donnell, Ryan

Published Jan 1, 2025• 0 citations

Publisher

Abstract

DOI: 10.4230/lipics.tqc.2025.7

Related papers

Uniformity Testing When You Have the Source Code

Clément L. Canonne, Robin Kothari, Ryan O’Donnell

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 $ε$ -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 $ε$ -far from it. For both problems, the previous best known upper bound was $O(\min\{d^{1/3}/ε^{2},d^{1/2}/ε\})$ . Here we improve the upper bound to $O(\min\{d^{1/3}/ε^{4/3}, d^{1/2}/ε\})$ , which we conjecture is optimal.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 $ε$-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 $ε$-far from it. For both problems, the previous best known upper bound was $O(\min\{d^{1/3}/ε^{2},d^{1/2}/ε\})$. Here we improve the upper bound to $O(\min\{d^{1/3}/ε^{4/3}, d^{1/2}/ε\})$, which we conjecture is optimal.

arXiv:2411.04972Leibniz international proceedings in informaticsNov 7, 20240 citations

Succinct Quantum Testers for Closeness and k-Wise Uniformity of Probability Distributions

Jingquan Luo, Qisheng Wang, Lvzhou Li

We explore potential quantum speedups for the fundamental problem of testing the properties of closeness andk-wise uniformity of probability distributions. •Closeness testingis the problem of distinguishing whether twon-dimensional distributions are identical or at least ε-far in ℓ1- or ℓ2-distance. We show that the quantum query complexities for ℓ1- and ℓ2-closeness testing areO(√n/ε) andO(1/ε), respectively, both of which achieve optimal dependence on ε, improving the prior best results of Gilyén and Li (2019). •k-wise uniformity testingis the problem of distinguishing whether a distribution over {0, 1}nis uniform when restricted to anykcoordinates or ε-far from any such distribution. We propose the first quantum algorithm for this problem with query complexityO(√nk/ε), achieving a quadratic speedup over the state-of-the-art classical algorithm with sample complexityO(nk/ε2) by O’Donnell and Zhao (2018). Moreover, whenk= 2 our quantum algorithm outperforms any classical one because of the classical lower bound Ω(n/ε2). All our quantum algorithms are fairly simple and time-efficient, using only basic quantum subroutines such as amplitude estimation.We explore potential quantum speedups for the fundamental problem of testing the properties of closeness andk-wise uniformity of probability distributions. •Closeness testingis the problem of distinguishing whether twon-dimensional distributions are identical or at least ε-far in ℓ1- or ℓ2-distance. We show that the quantum query complexities for ℓ1- and ℓ2-closeness testing areO(√n/ε) andO(1/ε), respectively, both of which achieve optimal dependence on ε, improving the prior best results of Gilyén and Li (2019). •k-wise uniformity testingis the problem of distinguishing whether a distribution over {0, 1}nis uniform when restricted to anykcoordinates or ε-far from any such distribution. We propose the first quantum algorithm for this problem with query complexityO(√nk/ε), achieving a quadratic speedup over the state-of-the-art classical algorithm with sample complexityO(nk/ε2) by O’Donnell and Zhao (2018). Moreover, whenk= 2 our quantum algorithm outperforms any classical one because of the classical lower bound Ω(n/ε2). All our quantum algorithms are fairly simple and time-efficient, using only basic quantum subroutines such as amplitude estimation.

arXiv:2304.12916IEEE Transactions on Information TheoryApr 25, 20244 citations

Entanglement is Necessary for Optimal Quantum Property Testing

Sébastien Bubeck, Sitan Chen, Jerry Zheng Li

There has been a surge of progress in recent years in developing algorithms for testing and learning quantum states that achieve optimal copy complexity [1]–[6]. Unfortunately, they require the use of entangled measurements across many copies of the underlying state and thus remain outside the realm of what is currently experimentally feasible. A natural question is whether one can match the copy complexity of such algorithms using only independent-but possibly adaptively chosen-measurements on individual copies. We answer this in the negative for arguably the most basic quantum testing problem: deciding whether a given $d$ -dimensional quantum state is equal to or $\epsilon$ -far in trace distance from the maximally mixed state. While it is known how to achieve optimal $O(d/\epsilon^{2})$ copy complexity using entangled measurements, we show that with independent measurements, $\Omega(d^{4/3}/\epsilon^{2})$ is necessary, even if the measurements are chosen adaptively. This resolves a question posed in [7]. To obtain this lower bound, we develop several new techniques, including a chain-rule style proof of Paninski's lower bound for classical uniformity testing, which may be of independent interest.There has been a surge of progress in recent years in developing algorithms for testing and learning quantum states that achieve optimal copy complexity [1]–[6]. Unfortunately, they require the use of entangled measurements across many copies of the underlying state and thus remain outside the realm of what is currently experimentally feasible. A natural question is whether one can match the copy complexity of such algorithms using only independent-but possibly adaptively chosen-measurements on individual copies. We answer this in the negative for arguably the most basic quantum testing problem: deciding whether a given$d$-dimensional quantum state is equal to or$\epsilon$-far in trace distance from the maximally mixed state. While it is known how to achieve optimal$O(d/\epsilon^{2})$copy complexity using entangled measurements, we show that with independent measurements,$\Omega(d^{4/3}/\epsilon^{2})$is necessary, even if the measurements are chosen adaptively. This resolves a question posed in [7]. To obtain this lower bound, we develop several new techniques, including a chain-rule style proof of Paninski's lower bound for classical uniformity testing, which may be of independent interest.

arXiv:2004.07869Annual Symposium on Foundations of Computer ScienceNov 1, 202037 citations

Non-iid hypothesis testing: from classical to quantum

Giacomo De Palma, Marco Fanizza, Connor Mowry +1 more

We study hypothesis testing (aka state certification) in the non-identically distributed setting. A recent work (Garg et al. 2023) considered the classical case, in which one is given (independent) samples from $T$ unknown probability distributions $p_1, \dots, p_T$ on $[d] = \{1, 2, \dots, d\}$ , and one wishes to accept/reject the hypothesis that their average $p_{\mathrm{avg}}$ equals a known hypothesis distribution $q$ . Garg et al. showed that if one has just $c = 2$ samples from each $p_i$ , and provided $T \gg \frac{\sqrt{d}}{ε^2} + \frac{1}{ε^4}$ , one can (whp) distinguish $p_{\mathrm{avg}} = q$ from $d_{\mathrm{TV}}(p_{\mathrm{avg}},q) > ε$ . This nearly matches the optimal result for the classical iid setting (namely, $T \gg \frac{\sqrt{d}}{ε^2}$ ). Besides optimally improving this result (and generalizing to tolerant testing with more stringent distance measures), we study the analogous problem of hypothesis testing for non-identical quantum states. Here we uncover an unexpected phenomenon: for any $d$ -dimensional hypothesis state $σ$ , and given just a single copy ( $c = 1$ ) of each state $ρ_1, \dots, ρ_T$ , one can distinguish $ρ_{\mathrm{avg}} = σ$ from $D_{\mathrm{tr}}(ρ_{\mathrm{avg}},σ) > ε$ provided $T \gg d/ε^2$ . (Again, we generalize to tolerant testing with more stringent distance measures.) This matches the optimal result for the iid case, which is surprising because doing this with $c = 1$ is provably impossible in the classical case. We also show that the analogous phenomenon happens for the non-iid extension of identity testing between unknown states. A technical tool we introduce may be of independent interest: an Efron-Stein inequality, and more generally an Efron-Stein decomposition, in the quantum setting.We study hypothesis testing (aka state certification) in the non-identically distributed setting. A recent work (Garg et al. 2023) considered the classical case, in which one is given (independent) samples from $T$ unknown probability distributions $p_1, \dots, p_T$ on $[d] = \{1, 2, \dots, d\}$, and one wishes to accept/reject the hypothesis that their average $p_{\mathrm{avg}}$ equals a known hypothesis distribution $q$. Garg et al. showed that if one has just $c = 2$ samples from each $p_i$, and provided $T \gg \frac{\sqrt{d}}{ε^2} + \frac{1}{ε^4}$, one can (whp) distinguish $p_{\mathrm{avg}} = q$ from $d_{\mathrm{TV}}(p_{\mathrm{avg}},q) > ε$. This nearly matches the optimal result for the classical iid setting (namely, $T \gg \frac{\sqrt{d}}{ε^2}$). Besides optimally improving this result (and generalizing to tolerant testing with more stringent distance measures), we study the analogous problem of hypothesis testing for non-identical quantum states. Here we uncover an unexpected phenomenon: for any $d$-dimensional hypothesis state $σ$, and given just a single copy ($c = 1$) of each state $ρ_1, \dots, ρ_T$, one can distinguish $ρ_{\mathrm{avg}} = σ$ from $D_{\mathrm{tr}}(ρ_{\mathrm{avg}},σ) > ε$ provided $T \gg d/ε^2$. (Again, we generalize to tolerant testing with more stringent distance measures.) This matches the optimal result for the iid case, which is surprising because doing this with $c = 1$ is provably impossible in the classical case. We also show that the analogous phenomenon happens for the non-iid extension of identity testing between unknown states. A technical tool we introduce may be of independent interest: an Efron-Stein inequality, and more generally an Efron-Stein decomposition, in the quantum setting.

arXiv:2510.06147Oct 7, 20250 citations

Quantum collision-resistance of non-uniformly distributed functions: upper and lower bounds

Ehsan Ebrahimi, Dominique Unruh

Quantum Information and ComputationDec 1, 20182 citations

Tight bounds on the convergence of noisy random circuits to uniform.

Abhinav Deshpande, Bill Fefferman, Alexey Vyacheslavovich Gorshkov +3 more

We study the properties of output distributions of noisy, random circuits. We obtain upper and lower bounds on the expected distance of the output distribution from the uniform distribution. These bounds are tight with respect to the dependence on circuit depth. Our proof techniques also allow us to make statements about the presence or absence of anticoncentration for both noisy and noiseless circuits. We uncover a number of interesting consequences for hardness proofs of sampling schemes that aim to show a quantum computational advantage over classical computation. Specifically, we discuss recent barrier results for depth-agnostic and/or noise-agnostic proof techniques. We show that in certain depth regimes, noise-agnostic proof techniques might still work in order to prove an often-conjectured claim in the literature on quantum computational advantage, contrary to what was thought prior to this work.We study the properties of output distributions of noisy, random circuits. We obtain upper and lower bounds on the expected distance of the output distribution from the uniform distribution. These bounds are tight with respect to the dependence on circuit depth. Our proof techniques also allow us to make statements about the presence or absence of anticoncentration for both noisy and noiseless circuits. We uncover a number of interesting consequences for hardness proofs of sampling schemes that aim to show a quantum computational advantage over classical computation. Specifically, we discuss recent barrier results for depth-agnostic and/or noise-agnostic proof techniques. We show that in certain depth regimes, noise-agnostic proof techniques might still work in order to prove an often-conjectured claim in the literature on quantum computational advantage, contrary to what was thought prior to this work.

Dec 1, 20213 citations

[d]

ε

-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

ε

-far from it. For both problems, the previous best known upper bound was

O(\min\{d^{1/3}/ε^{2},d^{1/2}/ε\})

. Here we improve the upper bound to

O(\min\{d^{1/3}/ε^{4/3}, d^{1/2}/ε\})

, which we conjecture is optimal.

d

-dimensional quantum state is equal to or

\epsilon

-far in trace distance from the maximally mixed state. While it is known how to achieve optimal

O(d/\epsilon^{2})

copy complexity using entangled measurements, we show that with independent measurements,

\Omega(d^{4/3}/\epsilon^{2})

is necessary, even if the measurements are chosen adaptively. This resolves a question posed in [7]. To obtain this lower bound, we develop several new techniques, including a chain-rule style proof of Paninski's lower bound for classical uniformity testing, which may be of independent interest.

T

unknown probability distributions

p_1, \dots, p_T

[d] = \{1, 2, \dots, d\}

, and one wishes to accept/reject the hypothesis that their average

p_{\mathrm{avg}}

equals a known hypothesis distribution

q

. Garg et al. showed that if one has just

c = 2

samples from each

p_i

, and provided

T \gg \frac{\sqrt{d}}{ε^2} + \frac{1}{ε^4}

, one can (whp) distinguish

p_{\mathrm{avg}} = q

from

d_{\mathrm{TV}}(p_{\mathrm{avg}},q) > ε

. This nearly matches the optimal result for the classical iid setting (namely,

T \gg \frac{\sqrt{d}}{ε^2}

). Besides optimally improving this result (and generalizing to tolerant testing with more stringent distance measures), we study the analogous problem of hypothesis testing for non-identical quantum states. Here we uncover an unexpected phenomenon: for any

d

-dimensional hypothesis state

σ

, and given just a single copy (

c = 1

) of each state

ρ_1, \dots, ρ_T

, one can distinguish

ρ_{\mathrm{avg}} = σ

from

D_{\mathrm{tr}}(ρ_{\mathrm{avg}},σ) > ε

provided

T \gg d/ε^2

. (Again, we generalize to tolerant testing with more stringent distance measures.) This matches the optimal result for the iid case, which is surprising because doing this with

c = 1

is provably impossible in the classical case. We also show that the analogous phenomenon happens for the non-iid extension of identity testing between unknown states. A technical tool we introduce may be of independent interest: an Efron-Stein inequality, and more generally an Efron-Stein decomposition, in the quantum setting.