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 integration of a function with unknown singularity

Maciej Goćwin

Published May 1, 2023• 0 citations
Publisher

Abstract

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

DOI
10.26421/qic23.7-8-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

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

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

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

QUANTUM COMPLEXITY OF THE INTEGRATION PROBLEM FOR ANISOTROPIC CLASSES

Xiao-feiHu, Pei-xinYe

We obtain the optimal order of high-dimensional integration complexity in the quantumcomputation model in anisotropic Sobolev classes W∞^r ([0, 1]^d) and Hǒlder Nikolskii classes 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^-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∞^∧ (D) whose smoothness index is the boundary of some complete set in Z+^d.

Journal of Computational Mathematics•Jan 1, 2005•7 citations

Quantum Algorithms and Complexity for Continuous Problems

Anargyros Papageorgiou, Joseph F. Traub

Most continuous mathematical formulations arising in science and engineering can only be solved numerically and therefore approximately. We shall always assume that we're dealing with a numerical approximation to the solution. There are two major motivations for studying quantum algorithms and complexity for continuous problems. 1. Are quantum computers more powerful than classical computers for important scientific problems? How much more powerful? 2. Many important scientific and engineering problems have continuous formulations. To answer the first question we must know the classical computational complexity of the problem. Knowing the classical complexity of a continuous problem we obtain the quantum computation speedup if we know the quantum complexity. If we know an upper bound on the quantum complexity through the cost of a particular quantum algorithm then we can obtain a lower bound on the quantum speedup. Regarding the second motivation, in this article we'll report on high-dimensional integration, path integration, Feynman path integration, the smallest eigenvalue of a differential equation, approximation, partial differential equations, ordinary differential equations and gradient estimation. We'll also briefly report on the simulation of quantum systems on a quantum computer.

arXiv:0712.1211•Dec 7, 2007•0 citations
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\ve\ve-complexity of this problem is of order \ve−1/(r+ρ+1)\ve^{-1/(r+\rho+1)}\ve−1/(r+ρ+1). Since the classical deterministic complexity of this problem is \ve−1/(r+ρ)\ve^{-1/(r+\rho)}\ve−1/(r+ρ), quantum computers give a speed-up for this problem for all values of parameters rrr and ρ\rhoρ.
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 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​.
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 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.
We obtain the optimal order of high-dimensional integration complexity in the quantumcomputation model in anisotropic Sobolev classes W∞^r ([0, 1]^d) and Hǒlder Nikolskii classes 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^-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∞^∧ (D) whose smoothness index is the boundary of some complete set in Z+^d.
Most continuous mathematical formulations arising in science and engineering can only be solved numerically and therefore approximately. We shall always assume that we're dealing with a numerical approximation to the solution. There are two major motivations for studying quantum algorithms and complexity for continuous problems. 1. Are quantum computers more powerful than classical computers for important scientific problems? How much more powerful? 2. Many important scientific and engineering problems have continuous formulations. To answer the first question we must know the classical computational complexity of the problem. Knowing the classical complexity of a continuous problem we obtain the quantum computation speedup if we know the quantum complexity. If we know an upper bound on the quantum complexity through the cost of a particular quantum algorithm then we can obtain a lower bound on the quantum speedup. Regarding the second motivation, in this article we'll report on high-dimensional integration, path integration, Feynman path integration, the smallest eigenvalue of a differential equation, approximation, partial differential equations, ordinary differential equations and gradient estimation. We'll also briefly report on the simulation of quantum systems on a quantum computer.