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

On the quantum complexity of approximating median of continuous distribution

Maciej Goćwin

Published Nov 25, 2018• 0 citations
arXivHTMLPDF

Abstract

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))}$.

DOI
10.48550/arxiv.1811.10017

Related papers

On the quantum complexity of computing the median of continuous distributions

Maciej Goćwin

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.

Quantum Information and Computation•Sep 1, 2019•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

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

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

Quantum Complexity of the Approximation on the Classes B(Wrp([0, 1]d)) and B(Hrp([0, 1]d))

Peixin Ye

The optimal order of complexity of the approximation of the imbedding from anisotropic Sobolev classes B(Wpr([0, 1]d)) and Holder Nikolskii classes B(Hpr([0, 1]d)) into the Lq([0, 1]d) with q les p quantum computation model is obtained up to logarithmic factors. It shows that the quantum algorithms are not significantly better than the classical ones for this type of problems.

International Conference on Natural Computation (ICNC)•Jan 1, 2008•0 citations

Complexity of quantum integration on generalized Hölder classes

Wan Li, Peixin Ye

In this paper, we study the numerical integration problem of functions from the generalized Hölder class [Formula: see text], which is determined by a generalized modulus of smoothness [Formula: see text], in the quantum model of computation. We obtain the exact order of complexity of this problem. The results show that quantum algorithms have faster convergence rates than those of deterministic and randomized ones. Quantitatively, the improvement amounts to the factors [Formula: see text] for the deterministic case and [Formula: see text] for the randomized case, where [Formula: see text] is the number of function evaluations involved in the computational process. Furthermore, we apply our general results to the case [Formula: see text] with [Formula: see text] and [Formula: see text] and obtain the corresponding complexity.

Analysis and Applications•Feb 27, 2026•0 citations
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)).
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.
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ρ.
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 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​.
In this paper, we study the numerical integration problem of functions from the generalized Hölder class [Formula: see text], which is determined by a generalized modulus of smoothness [Formula: see text], in the quantum model of computation. We obtain the exact order of complexity of this problem. The results show that quantum algorithms have faster convergence rates than those of deterministic and randomized ones. Quantitatively, the improvement amounts to the factors [Formula: see text] for the deterministic case and [Formula: see text] for the randomized case, where [Formula: see text] is the number of function evaluations involved in the computational process. Furthermore, we apply our general results to the case [Formula: see text] with [Formula: see text] and [Formula: see text] and obtain the corresponding complexity.