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

Quantum Information and Computation

On the quantum complexity of computing the median of continuous distributions

Maciej Goćwin

Published Sep 1, 2019• 0 citations
Publisher

Abstract

We study the approximation of the median of an absolutely continuous distribution with respect to the Lebesgue measure given by a probability density function f. We assume that f has r continuous derivatives, with derivative of order r being H\"older continuous with the exponent \rho. We study the quantum query complexity of this problem. We show that the \ve-complexity up to a logarithmic factor is of order \ve^{-1/(r+\rho+1)}. We also extend the results to the problem of computing the vector of quantiles of an absolutely continuous distribution.

DOI
10.26421/qic19.11-12-4

Related papers

On the quantum complexity of approximating median of continuous distribution

Maciej Goćwin

We consider approximating of the median of absolutely continuous distribution given by a probability density function $f$. We assume that $f$ has $r$ continuous derivatives, with derivative of order $r$ being Hölder continuous with the exponent $ρ$. We study the $ε$-complexity of this problem in the quantum setting. We show that the $ε$-complexity up to logarithmic factor is of order $ε^{-1/((r+ρ+1))}$.

arXiv:1811.10017•Nov 25, 2018•0 citations

On the quantum complexity of integration of a function with unknown singularity

Maciej Goćwin

In this paper we study the quantum complexity of the integration of a function with an unknown singularity. We assume that the function has $r$ continuous derivatives, with the derivative of order $r$ being H\"older continuous with the exponent $\rho$ on the whole integration interval except the one singular point. We show that the $\ve$-complexity of this problem is of order $\ve^{-1/(r+\rho+1)}$. Since the classical deterministic complexity of this problem is $\ve^{-1/(r+\rho)}$, quantum computers give a speed-up for this problem for all values of parameters $r$ and $\rho$.

Quantum Information and Computation•May 1, 2023•0 citations

Distributional Quantum Query Complexity

Shalev Ben-David, M. H. Ebtehaj

Quantum query complexity enjoys a variety of pleasing joint computation properties: for example, a composition theorem asserting $Q(f\circ g)=Θ(Q(f)Q(g))$ for all Boolean functions $f$ and $g$; a direct sum theorem asserting that computing $k$ copies of a function (or search problem) costs $Ω(k)$ times as much as the cost of computing one copy; and a direct product theorem asserting that for Boolean functions, even succeeding at the direct sum problem with exponentially small probability still requires $Ω(k)$ times the cost of computing one copy to bounded error. However, all of these results are strictly for worst-case quantum query complexity. For example, if we have a fixed distribution $μ$ over inputs, the direct sum theorem says nothing about the quantum query complexity of computing $k$ copies of $f$ when the input comes from the product distribution $μ^k$ instead of being worst-case. (Note that while a standard Yao-type minimax theorem guarantees a hard distribution for the direct sum problem, there's no guarantee that this hard distribution is a product distribution.) A similar problem occurs for the direct product theorem and the composition theorem: none of these results respect distributions. In this work, we give distributional joint computation lower bounds for the composition, direct sum, and direct product problems. Along the way, we introduce some new tools for handling quantum query lower bounds, including (a) a new ``multiplicative'' variant of the $γ_2$ norm (which we use in place of the multiplicative adversary method for proving the direct product theorem), and (b) a new ``Shaltiel-free'' measure of quantum query complexity, which we show characterizes the composition behavior of distributional quantum query complexity and satisfies pleasing properties.

quant-pharXiv:2610.06835•Oct 6, 2026•0 citations

The quantum query complexity of approximating the median and related statistics

Ashwin Nayak, Felix Wu

Let X = (z,, , z,-,) be a sequence of n numbers.For 6 > 0, we say that 5; is an e-approximate median if the number of elements strictly less than zi and the number of elements strictly greater than zi are each less than (1 + 6):.We consider the quantum query complexity of computing an c-approximate median, given the sequence X as an oracle.We prove a lower bound of n(min{t,n}) queries for any quantum algorithm that computes an r-approximate median with any constant probability greater than l/2.We also show how an c-approximate median may be computed with 0( $ log(t) log log( $)) oracle queries, which rep resents an improvement over an earlier algorithm due to Grover [ll, 121.Thus, the lower bound we obtain is essentially optimal.The upper and the lower bound both hold in the comparison tree model as well.Our lower bound result is an application of the polynomial paradigm recently introduced to quantum complexity theory by Be& et ol.[l].The main ingredient in the proof is a polynomial degree lower bound far real multilinear polynomials that "approximate" symmetric partial boolean functions.The degree bound extends a result of Patti[15] and also immediately yields lower bounds for the problems of approximating the kth-smallest element, approximating the mean of a sequence of numbers, and approximately counting the number of ones of a boolean function.All bounds obtained come within a polylogarithmic factor of the optimal (as we show by presenting algorithms where no such optimal or near optimal algorithms were known), thus demonstrating the power of the polynomial method.

arXiv:quant-ph/9804066•ACM Symposium on Theory of Computing (STOC)•May 1, 1999•178 citations

Tight bounds for hybrid quantum-classical query algorithms

Andris Ambainis, András Gilyén, Martins Kokainis

We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most $q$ oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision $ε$ requires $Θ(\frac{1}{q ε^2})$ queries; (ii) (Unbiased) Amplitude estimation up to a precision $ε$ requires $Θ(\frac{p(1-p)}{q ε^2})$ queries; (iii) Search among $N$ items requires $Θ(\frac{N}{q})$ queries; (iv) Two level AND-OR tree (AND of $m$ ORs, with $n$ inputs to each OR) requires $Θ(\frac{nm}{q})$ queries. All of these bounds are optimal up to a constant factor, for all $q$ from 1, corresponding to the classical complexity, to $Q(f)$, the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.

quant-pharXiv:2610.06803•Oct 6, 2026•0 citations

Quantum Complexity of the Integration Problem for Anisotropic Classes

Xiao-Fei Hu, Pei-Xin Ye

We obtain the optimal order of high-dimensional integration complexity in the quantum computation model in anisotropic Sobolev classes $W_{\infty}^{\bf r}([0,1]^d)$ and Hölder Nikolskii classes $H_{\infty}^{\bf r}([0,1]^d)$. It is proved that for these classes of functions there is a speed-up of quantum algorithms over deterministic classical algorithms due to factor $n^{-1}$ and over randomized classical methods due to factor $n^{-1/2}$. Moreover, we give an estimation for optimal query complexity in the class $H_{\infty}^{\Lambda}(D)$ whose smoothness index is the boundary of some complete set in $\mathbb{Z}_+^d$.

Journal of Computational Mathematics•Jun 2, 2005•0 citations
We study the approximation of the median of an absolutely continuous distribution with respect to the Lebesgue measure given by a probability density function f. We assume that f has r continuous derivatives, with derivative of order r being H"older continuous with the exponent \rho. We study the quantum query complexity of this problem. We show that the \ve-complexity up to a logarithmic factor is of order \ve^{-1/(r+\rho+1)}. We also extend the results to the problem of computing the vector of quantiles of an absolutely continuous distribution.
We consider approximating of the median of absolutely continuous distribution given by a probability density function fff. We assume that fff has rrr continuous derivatives, with derivative of order rrr being Hölder continuous with the exponent ρρρ. We study the εεε-complexity of this problem in the quantum setting. We show that the εεε-complexity up to logarithmic factor is of order ε−1/((r+ρ+1))ε^{-1/((r+ρ+1))}ε−1/((r+ρ+1)).
In this paper we study the quantum complexity of the integration of a function with an unknown singularity. We assume that the function has rrr continuous derivatives, with the derivative of order rrr being H\"older continuous with the exponent ρ\rhoρ on the whole integration interval except the one singular point. We show that the $\ve$-complexity of this problem is of order $\ve^{-1/(r+\rho+1)}$. Since the classical deterministic complexity of this problem is $\ve^{-1/(r+\rho)}$, quantum computers give a speed-up for this problem for all values of parameters rrr and ρ\rhoρ.
Quantum query complexity enjoys a variety of pleasing joint computation properties: for example, a composition theorem asserting Q(f∘g)=Θ(Q(f)Q(g))Q(f\circ g)=Θ(Q(f)Q(g))Q(f∘g)=Θ(Q(f)Q(g)) for all Boolean functions fff and ggg; a direct sum theorem asserting that computing kkk copies of a function (or search problem) costs Ω(k)Ω(k)Ω(k) times as much as the cost of computing one copy; and a direct product theorem asserting that for Boolean functions, even succeeding at the direct sum problem with exponentially small probability still requires Ω(k)Ω(k)Ω(k) times the cost of computing one copy to bounded error. However, all of these results are strictly for worst-case quantum query complexity. For example, if we have a fixed distribution μμμ over inputs, the direct sum theorem says nothing about the quantum query complexity of computing kkk copies of fff when the input comes from the product distribution μkμ^kμk instead of being worst-case. (Note that while a standard Yao-type minimax theorem guarantees a hard distribution for the direct sum problem, there's no guarantee that this hard distribution is a product distribution.) A similar problem occurs for the direct product theorem and the composition theorem: none of these results respect distributions. In this work, we give distributional joint computation lower bounds for the composition, direct sum, and direct product problems. Along the way, we introduce some new tools for handling quantum query lower bounds, including (a) a new ``multiplicative'' variant of the γ2γ_2γ2​ norm (which we use in place of the multiplicative adversary method for proving the direct product theorem), and (b) a new ``Shaltiel-free'' measure of quantum query complexity, which we show characterizes the composition behavior of distributional quantum query complexity and satisfies pleasing properties.
Let X = (z,, , z,-,) be a sequence of n numbers.For 6 > 0, we say that 5; is an e-approximate median if the number of elements strictly less than zi and the number of elements strictly greater than zi are each less than (1 + 6):.We consider the quantum query complexity of computing an c-approximate median, given the sequence X as an oracle.We prove a lower bound of n(min{t,n}) queries for any quantum algorithm that computes an r-approximate median with any constant probability greater than l/2.We also show how an c-approximate median may be computed with 0( $ log(t) log log( $)) oracle queries, which rep resents an improvement over an earlier algorithm due to Grover [ll, 121.Thus, the lower bound we obtain is essentially optimal.The upper and the lower bound both hold in the comparison tree model as well.Our lower bound result is an application of the polynomial paradigm recently introduced to quantum complexity theory by Be& et ol.[l].The main ingredient in the proof is a polynomial degree lower bound far real multilinear polynomials that "approximate" symmetric partial boolean functions.The degree bound extends a result of Patti[15] and also immediately yields lower bounds for the problems of approximating the kth-smallest element, approximating the mean of a sequence of numbers, and approximately counting the number of ones of a boolean function.All bounds obtained come within a polylogarithmic factor of the optimal (as we show by presenting algorithms where no such optimal or near optimal algorithms were known), thus demonstrating the power of the polynomial method.
We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most qqq oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision εεε requires Θ(1qε2)Θ(\frac{1}{q ε^2})Θ(qε21​) queries; (ii) (Unbiased) Amplitude estimation up to a precision εεε requires Θ(p(1−p)qε2)Θ(\frac{p(1-p)}{q ε^2})Θ(qε2p(1−p)​) queries; (iii) Search among NNN items requires Θ(Nq)Θ(\frac{N}{q})Θ(qN​) queries; (iv) Two level AND-OR tree (AND of mmm ORs, with nnn inputs to each OR) requires Θ(nmq)Θ(\frac{nm}{q})Θ(qnm​) queries. All of these bounds are optimal up to a constant factor, for all qqq from 1, corresponding to the classical complexity, to Q(f)Q(f)Q(f), the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.
We obtain the optimal order of high-dimensional integration complexity in the quantum computation model in anisotropic Sobolev classes W∞r([0,1]d)W_{\infty}^{\bf r}([0,1]^d)W∞r​([0,1]d) and Hölder Nikolskii classes H∞r([0,1]d)H_{\infty}^{\bf r}([0,1]^d)H∞r​([0,1]d). It is proved that for these classes of functions there is a speed-up of quantum algorithms over deterministic classical algorithms due to factor n−1n^{-1}n−1 and over randomized classical methods due to factor n−1/2n^{-1/2}n−1/2. Moreover, we give an estimation for optimal query complexity in the class H∞Λ(D)H_{\infty}^{\Lambda}(D)H∞Λ​(D) whose smoothness index is the boundary of some complete set in Z+d\mathbb{Z}_+^dZ+d​.