Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2411.04972 · Leibniz international proceedings in informatics

Uniformity Testing When You Have the Source Code

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

Published Nov 7, 2024• 6 citations
arXivHTMLPDF

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 $ε$-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

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

arXiv:2208.07544•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2023•34 citations

Automatic Generation of Testing Circuits for Deterministic Quantum Algorithms

Antonio García de la Barrera, Manuel Serrano, Ignacio García‐Rodríguez de Guzmán +2 more

•Jan 1, 2023•2 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.

arXiv:1005.1407•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Aug 11, 2010•465 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.

arXiv:2304.12916•IEEE Transactions on Information Theory•Apr 25, 2024•12 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, 2026•0 citations

Discriminating quantum states: The multiple Chernoff distance

Ke Li

We consider the problem of testing multiple quantum hypotheses $\{\rho_{1}^{\otimes n},\ldots,\rho_{r}^{\otimes n}\}$, where an arbitrary prior distribution is given and each of the $r$ hypotheses is $n$ copies of a quantum state. It is known that the minimal average error probability $P_{e}$ decays exponentially to zero, that is, $P_{e}=\exp\{-\xi n+o(n)\}$. However, this error exponent $\xi$ is generally unknown, except for the case that $r=2$. In this paper, we solve the long-standing open problem of identifying the above error exponent, by proving Nussbaum and Szkoła’s conjecture that $\xi=\min_{i\neq j}C(\rho_{i},\rho_{j})$. The right-hand side of this equality is called the multiple quantum Chernoff distance, and $C(\rho_{i},\rho_{j}):=\max_{0\leq s\leq1}\{-\log\operatorname{Tr}\rho_{i}^{s}\rho_{j}^{1-s}\}$ has been previously identified as the optimal error exponent for testing two hypotheses, $\rho_{i}^{\otimes n}$ versus $\rho_{j}^{\otimes n}$. The main ingredient of our proof is a new upper bound for the average error probability, for testing an ensemble of finite-dimensional, but otherwise general, quantum states. This upper bound, up to a states-dependent factor, matches the multiple-state generalization of Nussbaum and Szkoła’s lower bound. Specialized to the case $r=2$, we give an alternative proof to the achievability of the binary-hypothesis Chernoff distance, which was originally proved by Audenaert et al.

arXiv:1508.06624•The Annals of Statistics•Jul 7, 2016•61 citations
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][d][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⁡{d1/3/ε2,d1/2/ε})O(\min\{d^{1/3}/ε^{2},d^{1/2}/ε\})O(min{d1/3/ε2,d1/2/ε}). Here we improve the upper bound to O(min⁡{d1/3/ε4/3,d1/2/ε})O(\min\{d^{1/3}/ε^{4/3}, d^{1/2}/ε\})O(min{d1/3/ε4/3,d1/2/ε}), which we conjecture is optimal.
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.07544
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 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 consider the problem of testing multiple quantum hypotheses {ρ1⊗n,…,ρr⊗n}\{\rho_{1}^{\otimes n},\ldots,\rho_{r}^{\otimes n}\}{ρ1⊗n​,…,ρr⊗n​}, where an arbitrary prior distribution is given and each of the rrr hypotheses is nnn copies of a quantum state. It is known that the minimal average error probability PeP_{e}Pe​ decays exponentially to zero, that is, Pe=exp⁡{−ξn+o(n)}P_{e}=\exp\{-\xi n+o(n)\}Pe​=exp{−ξn+o(n)}. However, this error exponent ξ\xiξ is generally unknown, except for the case that r=2r=2r=2. In this paper, we solve the long-standing open problem of identifying the above error exponent, by proving Nussbaum and Szkoła’s conjecture that ξ=min⁡i≠jC(ρi,ρj)\xi=\min_{i\neq j}C(\rho_{i},\rho_{j})ξ=mini=j​C(ρi​,ρj​). The right-hand side of this equality is called the multiple quantum Chernoff distance, and C(ρi,ρj):=max⁡0≤s≤1{−log⁡Tr⁡ρisρj1−s}C(\rho_{i},\rho_{j}):=\max_{0\leq s\leq1}\{-\log\operatorname{Tr}\rho_{i}^{s}\rho_{j}^{1-s}\}C(ρi​,ρj​):=max0≤s≤1​{−logTrρis​ρj1−s​} has been previously identified as the optimal error exponent for testing two hypotheses, ρi⊗n\rho_{i}^{\otimes n}ρi⊗n​ versus ρj⊗n\rho_{j}^{\otimes n}ρj⊗n​. The main ingredient of our proof is a new upper bound for the average error probability, for testing an ensemble of finite-dimensional, but otherwise general, quantum states. This upper bound, up to a states-dependent factor, matches the multiple-state generalization of Nussbaum and Szkoła’s lower bound. Specialized to the case r=2r=2r=2, we give an alternative proof to the achievability of the binary-hypothesis Chernoff distance, which was originally proved by Audenaert et al.