-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.

DOI: 10.4230/lipics.tqc.2025.7

Related papers

Uniformity Testing When You Have the Source Code

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

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}/ε²,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}/ε²,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.

Jan 1, 20250 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

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

Mean estimation when you have the source code; or, quantum Monte Carlo methods

Robin Kothari, Ryan O’Donnell

Suppose y is a real random variable, and one is given access to “the code” that generates it (for example, a randomized or quantum circuit whose output is y). We give a quantum procedure that runs the code O(n) times and returns an estimate for μ = E[y] that with high probability satisfies , where σ = stddev[y]. This dependence on n is optimal for quantum algorithms. One may compare with classical algorithms, which can only achieve the quadratically worse . Our method improves upon previous works, which either made additional assumptions about y, and/or assumed the algorithm knew an a priori bound on σ, and/or used additional logarithmic factors beyond O(n). The central subroutine for our result is essentially Grover's algorithm but with complex phases. * The full version of the paper can be accessed at https://arxiv.org/abs/2208.07544Suppose y is a real random variable, and one is given access to “the code” that generates it (for example, a randomized or quantum circuit whose output is y). We give a quantum procedure that runs the code O(n) times and returns an estimate for μ = E[y] that with high probability satisfies , where σ = stddev[y]. This dependence on n is optimal for quantum algorithms. One may compare with classical algorithms, which can only achieve the quadratically worse . Our method improves upon previous works, which either made additional assumptions about y, and/or assumed the algorithm knew an a priori bound on σ, and/or used additional logarithmic factors beyond O(n). The central subroutine for our result is essentially Grover's algorithm but with complex phases. * The full version of the paper can be accessed at https://arxiv.org/abs/2208.07544

arXiv:2208.07544Society for Industrial and Applied Mathematics eBooksJan 1, 202311 citations

Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy

Michael J. Bremner, Richard Jozsa, Dan J. Shepherd

We consider quantum computations comprising only commuting gates, known as IQP computations, and provide compelling evidence that the task of sampling their output probability distributions is unlikely to be achievable by any efficient classical means. More specifically, we introduce the class post-IQP of languages decided with bounded error by uniform families of IQP circuits with post-selection, and prove first that post-IQP equals the classical class PP. Using this result we show that if the output distributions of uniform IQP circuit families could be classically efficiently sampled, either exactly in total variation distance or even approximately up to 41 per cent multiplicative error in the probabilities, then the infinite tower of classical complexity classes known as the polynomial hierarchy would collapse to its third level. We mention some further results on the classical simulation properties of IQP circuit families, in particular showing that if the output distribution results from measurements on only lines then it may, in fact, be classically efficiently sampled.We consider quantum computations comprising only commuting gates, known as IQP computations, and provide compelling evidence that the task of sampling their output probability distributions is unlikely to be achievable by any efficient classical means. More specifically, we introduce the class post-IQP of languages decided with bounded error by uniform families of IQP circuits with post-selection, and prove first that post-IQP equals the classical class PP. Using this result we show that if the output distributions of uniform IQP circuit families could be classically efficiently sampled, either exactly in total variation distance or even approximately up to 41 per cent multiplicative error in the probabilities, then the infinite tower of classical complexity classes known as the polynomial hierarchy would collapse to its third level. We mention some further results on the classical simulation properties of IQP circuit families, in particular showing that if the output distribution results from measurements on only lines then it may, in fact, be classically efficiently sampled.

arXiv:1005.1407Proceedings of the Royal Society A Mathematical Physical and Engineering SciencesAug 11, 2010308 citations

Testing quantum machine learning claims in practice: a classical benchmark from random circuits and a five-step test for variational regression

Satish G. Prajapati

Oct 29, 20260 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.

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.