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:2608.00741

Quantum Speedups for Testing Similar Means

Chengshen Gao, Yongzhen Xu, Shenggen Zheng, Lvzhou Li

quant-phSubmitted Aug 1, 2026• Announced Aug 4, 2026• 0 citations
arXivHTMLPDF

Abstract

Property testing of distributions is a central topic in information theory, learning theory, and statistics. While quantum algorithms are known to offer significant speedups for property testing of a single distribution or a pair of distributions, it is unclear whether quantum algorithms provide speedups for property testing of $m$ ($m\geq 3$) distributions. This work focuses on quantum algorithms for testing whether $m$ distributions have similar means or are $ε$-far from mean similarity under two models. In the query model, the algorithm can choose which distribution to sample from, whereas in the sampling model, the distributions are selected uniformly. We design quantum algorithms with complexities $\tilde{O}(1/ε)$ (the $\tilde{O}$ notation hides poly-logarithmic factors) and $\tilde{O}(\sqrt{m}/ε)$ in the query and sampling models, respectively, achieving quadratic speedups over the classical counterparts. We further establish quantum lower bounds of $Ω\left(1/ε\right)$ and $Ω\rbra{m^{1/3}+\frac{m^{1/4}}ε}$ for the query model and the sampling model, demonstrating the optimality of our quantum algorithms in terms of the dependence on $ε$ up to logarithmic factors.

Related papers

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•4 citations

A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting

Kean Chen, Qisheng Wang, Zhicheng Zhang

Quantum sample-to-query lifting, a relation between quantum sample complexity and quantum query complexity presented in Wang and Zhang (SIAM J. Comput. 2025), was significantly strengthened by Tang, Wright, and Zhandry (2025) to the case of state-preparation oracles. In this paper, we compile a list of quantum lower and upper bounds for property testing that are obtained by quantum sample-to-query lifting. The problems of interest include testing properties of probability distributions and quantum states, such as entropy and closeness. This collection contains new results, as well as new proofs of known bounds. In total, we present 49 complexity bounds, where 41 are new and 18 are (near-)optimal.

quant-pharXiv:2512.01971•Dec 2, 2025•0 citations

Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants

Andrew M. Childs, Tongyang Li, Jin-Peng Liu +2 more

Given a convex function $f\colon\mathbb{R}^{d}\to\mathbb{R}$, the problem of sampling from a distribution $\propto e^{-f(x)}$ is called log-concave sampling. This task has wide applications in machine learning, physics, statistics, etc. In this work, we develop quantum algorithms for sampling log-concave distributions and for estimating their normalizing constants $\int_{\mathbb{R}^d}e^{-f(x)}\mathrm{d} x$. First, we use underdamped Langevin diffusion to develop quantum algorithms that match the query complexity (in terms of the condition number $κ$ and dimension $d$) of analogous classical algorithms that use gradient (first-order) queries, even though the quantum algorithms use only evaluation (zeroth-order) queries. For estimating normalizing constants, these algorithms also achieve quadratic speedup in the multiplicative error $ε$. Second, we develop quantum Metropolis-adjusted Langevin algorithms with query complexity $\widetilde{O}(κ^{1/2}d)$ and $\widetilde{O}(κ^{1/2}d^{3/2}/ε)$ for log-concave sampling and normalizing constant estimation, respectively, achieving polynomial speedups in $κ,d,ε$ over the best known classical algorithms by exploiting quantum analogs of the Monte Carlo method and quantum walks. We also prove a $1/ε^{1-o(1)}$ quantum lower bound for estimating normalizing constants, implying near-optimality of our quantum algorithms in $ε$.

arXiv:2210.06539•neural information processing systems•Jan 1, 2022•0 citations

A Unified Complexity Framework for Quantum Property Testing

Qisheng Wang

We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form $\mathcal{L}_φ(ρ) = \operatorname{tr}(φ(dρ))/d$, where $ρ$ is an unknown $d$-dimensional quantum state and $φ$ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating $\mathcal{L}_φ(ρ)$ from properties of $φ$, combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting. The framework yields (nearly) tight bounds for a broad class of problems, including entropy estimation (von Neumann, Rényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is \[ Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)\max\{1, \varepsilon\log^2(d)\}} + \frac{\log^2(d)}{\varepsilon^2}\right), \] and the sample complexity of spectrum estimation is \[ Θ\!\left(\frac{d^2}{\varepsilon^2\log^2(d)\max\{1, \varepsilon^2\log^2(d)\}}\right). \] In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.

quant-pharXiv:2608.02600•Aug 4, 2026•0 citations

Quantum Lower Bounds by Sample-to-Query Lifting

Qisheng Wang, Zhicheng Zhang

Abstract. The polynomial method by Beals, Buhrman, Cleve, Mosca, and de Wolf (FOCS 1998; [ J. ACM, 48 (2001), pp. 778–797]) and the adversary method by Ambainis (STOC 2000; [ J. Comput. System Sci., 64 (2002), pp. 750–767]) and the compressed oracle method by Zhandry [ Proceedings of the 39 th CRYPTO, 2019, pp. 239–268] have been shown to be powerful in proving quantum query lower bounds for a wide variety of problems. In this paper, we propose a new method for proving quantum query lower bounds by a quantum sample-to-query lifting theorem, which is from an information theory perspective. Using this method, we obtain the following new results: (1) A quadratic relation between quantum sample and query complexities regarding quantum property testing, which is optimal and saturated by quantum state discrimination. Here, the sample complexity is measured given sample access to the quantum state to be tested, while the query complexity is measured given query access to an oracle that block-encodes the quantum state. (2) A matching lower bound [Formula: see text] for quantum Gibbs sampling at inverse temperature [Formula: see text] ([Formula: see text] suppresses logarithmic factors), showing that the quantum Gibbs sampler by Gilyén, Su, Low, and Wiebe [ Proceedings of the 51 st STOC, 2019, pp. 193–204] is optimal. (3) A new lower bound [Formula: see text] for the entanglement entropy problem with gap [Formula: see text], which was recently studied by She and Yuen [ Proceedings of the 14 th ITCS, 2023, pp. 96:1–96:17]. (4) A series of quantum query lower bounds for matrix spectrum testing, based on the sample lower bounds for quantum state spectrum testing by O’Donnell and Wright (STOC 2015; [ Comm. Math. Phys., 387 (2021), pp. 1–95]). In addition, we provide unified proofs for some known lower bounds that have been proven previously via different techniques, including those for phase/amplitude estimation and Hamiltonian simulation.

arXiv:2308.01794•SIAM Journal on Computing•Oct 10, 2025•3 citations

Quantum Proofs of Proximity

Marcel Dall’Agnol, Tom Gur, Subhayan Roy Moulick +1 more

We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity (QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proof and are required to accept inputs having a property Π and reject inputs that are ε -far from Π , while only probing a minuscule portion of their input.We investigate the complexity landscape of this model, showing that QMAPs can be exponentially stronger than both classical proofs of proximity and quantum testers. To this end, we extend the methodology of Blais, Brody, and Matulef (Computational Complexity, 2012) to prove quantum property testing lower bounds via reductions from communication complexity. This also resolves a question raised in 2013 by Montanaro and de Wolf (cf. Theory of Computing, 2016).Our algorithmic results include a purpose an algorithmic framework that enables quantum speedups for testing an expressive class of properties, namely, those that are succinctly decomposable . A consequence of this framework is a QMA algorithm to verify the Parity of an n -bit string with O(n2/3) queries and proof length. We also propose a QMA algorithm for testing graph bipartitneness, a property that lies outside of this family, for which there is a quantum speedup.

arXiv:2105.03697•Quantum•Oct 13, 2022•2 citations
Property testing of distributions is a central topic in information theory, learning theory, and statistics. While quantum algorithms are known to offer significant speedups for property testing of a single distribution or a pair of distributions, it is unclear whether quantum algorithms provide speedups for property testing of mmm (m≥3m\geq 3m≥3) distributions. This work focuses on quantum algorithms for testing whether mmm distributions have similar means or are εεε-far from mean similarity under two models. In the query model, the algorithm can choose which distribution to sample from, whereas in the sampling model, the distributions are selected uniformly. We design quantum algorithms with complexities O~(1/ε)\tilde{O}(1/ε)O~(1/ε) (the O~\tilde{O}O~ notation hides poly-logarithmic factors) and O~(m/ε)\tilde{O}(\sqrt{m}/ε)O~(m​/ε) in the query and sampling models, respectively, achieving quadratic speedups over the classical counterparts. We further establish quantum lower bounds of Ω(1/ε)Ω\left(1/ε\right)Ω(1/ε) and Ω\rbram1/3+m1/4εΩ\rbra{m^{1/3}+\frac{m^{1/4}}ε}Ω\rbram1/3+εm1/4​ for the query model and the sampling model, demonstrating the optimality of our quantum algorithms in terms of the dependence on εεε up to logarithmic factors.
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.
Quantum sample-to-query lifting, a relation between quantum sample complexity and quantum query complexity presented in Wang and Zhang (SIAM J. Comput. 2025), was significantly strengthened by Tang, Wright, and Zhandry (2025) to the case of state-preparation oracles. In this paper, we compile a list of quantum lower and upper bounds for property testing that are obtained by quantum sample-to-query lifting. The problems of interest include testing properties of probability distributions and quantum states, such as entropy and closeness. This collection contains new results, as well as new proofs of known bounds. In total, we present 49 complexity bounds, where 41 are new and 18 are (near-)optimal.
Given a convex function f ⁣:Rd→Rf\colon\mathbb{R}^{d}\to\mathbb{R}f:Rd→R, the problem of sampling from a distribution ∝e−f(x)\propto e^{-f(x)}∝e−f(x) is called log-concave sampling. This task has wide applications in machine learning, physics, statistics, etc. In this work, we develop quantum algorithms for sampling log-concave distributions and for estimating their normalizing constants ∫Rde−f(x)dx\int_{\mathbb{R}^d}e^{-f(x)}\mathrm{d} x∫Rd​e−f(x)dx. First, we use underdamped Langevin diffusion to develop quantum algorithms that match the query complexity (in terms of the condition number κκκ and dimension ddd) of analogous classical algorithms that use gradient (first-order) queries, even though the quantum algorithms use only evaluation (zeroth-order) queries. For estimating normalizing constants, these algorithms also achieve quadratic speedup in the multiplicative error εεε. Second, we develop quantum Metropolis-adjusted Langevin algorithms with query complexity O~(κ1/2d)\widetilde{O}(κ^{1/2}d)O(κ1/2d) and O~(κ1/2d3/2/ε)\widetilde{O}(κ^{1/2}d^{3/2}/ε)O(κ1/2d3/2/ε) for log-concave sampling and normalizing constant estimation, respectively, achieving polynomial speedups in κ,d,εκ,d,εκ,d,ε over the best known classical algorithms by exploiting quantum analogs of the Monte Carlo method and quantum walks. We also prove a 1/ε1−o(1)1/ε^{1-o(1)}1/ε1−o(1) quantum lower bound for estimating normalizing constants, implying near-optimality of our quantum algorithms in εεε.
We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form Lφ(ρ)=tr⁡(φ(dρ))/d\mathcal{L}_φ(ρ) = \operatorname{tr}(φ(dρ))/dLφ​(ρ)=tr(φ(dρ))/d, where ρρρ is an unknown ddd-dimensional quantum state and φφφ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating Lφ(ρ)\mathcal{L}_φ(ρ)Lφ​(ρ) from properties of φφφ, combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting. The framework yields (nearly) tight bounds for a broad class of problems, including entropy estimation (von Neumann, Rényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is Θ ⁣(d2εlog⁡2(d)max⁡{1,εlog⁡2(d)}+log⁡2(d)ε2), Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)\max\{1, \varepsilon\log^2(d)\}} + \frac{\log^2(d)}{\varepsilon^2}\right), Θ(εlog2(d)max{1,εlog2(d)}d2​+ε2log2(d)​), and the sample complexity of spectrum estimation is Θ ⁣(d2ε2log⁡2(d)max⁡{1,ε2log⁡2(d)}). Θ\!\left(\frac{d^2}{\varepsilon^2\log^2(d)\max\{1, \varepsilon^2\log^2(d)\}}\right). Θ(ε2log2(d)max{1,ε2log2(d)}d2​). In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.
Abstract. The polynomial method by Beals, Buhrman, Cleve, Mosca, and de Wolf (FOCS 1998; [ J. ACM, 48 (2001), pp. 778–797]) and the adversary method by Ambainis (STOC 2000; [ J. Comput. System Sci., 64 (2002), pp. 750–767]) and the compressed oracle method by Zhandry [ Proceedings of the 39 th CRYPTO, 2019, pp. 239–268] have been shown to be powerful in proving quantum query lower bounds for a wide variety of problems. In this paper, we propose a new method for proving quantum query lower bounds by a quantum sample-to-query lifting theorem, which is from an information theory perspective. Using this method, we obtain the following new results: (1) A quadratic relation between quantum sample and query complexities regarding quantum property testing, which is optimal and saturated by quantum state discrimination. Here, the sample complexity is measured given sample access to the quantum state to be tested, while the query complexity is measured given query access to an oracle that block-encodes the quantum state. (2) A matching lower bound [Formula: see text] for quantum Gibbs sampling at inverse temperature [Formula: see text] ([Formula: see text] suppresses logarithmic factors), showing that the quantum Gibbs sampler by Gilyén, Su, Low, and Wiebe [ Proceedings of the 51 st STOC, 2019, pp. 193–204] is optimal. (3) A new lower bound [Formula: see text] for the entanglement entropy problem with gap [Formula: see text], which was recently studied by She and Yuen [ Proceedings of the 14 th ITCS, 2023, pp. 96:1–96:17]. (4) A series of quantum query lower bounds for matrix spectrum testing, based on the sample lower bounds for quantum state spectrum testing by O’Donnell and Wright (STOC 2015; [ Comm. Math. Phys., 387 (2021), pp. 1–95]). In addition, we provide unified proofs for some known lower bounds that have been proven previously via different techniques, including those for phase/amplitude estimation and Hamiltonian simulation.
We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity (QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proof and are required to accept inputs having a property Π and reject inputs that are ε -far from Π , while only probing a minuscule portion of their input.We investigate the complexity landscape of this model, showing that QMAPs can be exponentially stronger than both classical proofs of proximity and quantum testers. To this end, we extend the methodology of Blais, Brody, and Matulef (Computational Complexity, 2012) to prove quantum property testing lower bounds via reductions from communication complexity. This also resolves a question raised in 2013 by Montanaro and de Wolf (cf. Theory of Computing, 2016).Our algorithmic results include a purpose an algorithmic framework that enables quantum speedups for testing an expressive class of properties, namely, those that are succinctly decomposable . A consequence of this framework is a QMA algorithm to verify the Parity of an n -bit string with O(n2/3) queries and proof length. We also propose a QMA algorithm for testing graph bipartitneness, a property that lies outside of this family, for which there is a quantum speedup.