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

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•8 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.

arXiv:1811.10017•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•2 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•1 citation

On the complexity of a two-point boundary value problem in different settings

Maciej Goćwin, Marek Szczęsny

We study the complexity of a two-point boundary value problem. We concentrate on the linear problem of order k with separated boundary conditions. Right-hand side functions are assumed to be r times differentiable with all derivatives bounded by a constant. We consider three models of computation: deterministic with standard and linear information, randomized and quantum. In each setting, we construct an algorithm for solving the problem, which allows us to establish upper complexity bounds. In the deterministic setting, we show that the use of linear information gives us a speed-up of at least one order of magnitude compared with the standard information. For randomized algorithms, we show that the speed-up over standard deterministic algorithms is by 1/2 in the exponent. For quantum algorithms, we can achieve a speed-up by one order of magnitude. We also provide lower complexity bounds. They match upper bounds in the deterministic setting with the standard information, and almost match upper bounds in the randomized and quantum settings. In the deterministic setting with the linear information, a gap still remains between the upper and lower complexity bounds.

International Journal of Computer Mathematics•Nov 5, 2010•2 citations

Optimal query complexity for fractional quantum evolution

Anthony Yuezhang Liu, Adam Wesołowski, Jayne Thompson +2 more

Given oracle access to an unknown unitary $U=e^{iH}$ , the fractional query problem asks how many queries are required to implement a noninteger power $U^t=e^{itH}$, $0<t<1$, when the spectrum is separated from the branch cut by a gap $δ$. Quantum singular value transformation gives an upper bound of $O\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$ queries for approximation error $\varepsilon$. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any $N$-query circuit to the approximation of $e^{itθ}$ by a trigonometric polynomial with degree bounded by $O(N)$, together with Remez inequality. This allows us to establish the lower bound of $Ω_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$. Consequently, the optimal query complexity for fractional query problem is $Θ_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$, showing that the known QSVT construction is asymptotically optimal. We also give an alternative lower bound proof based on constructing a linear functional that annihilates the approximant space, yielding a $Ω_τ\!\left(\log\frac{1}{\varepsilon}\right)$ bound uniform to $δ$.

quant-pharXiv:2610.01940•Oct 2, 2026•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 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.
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.
We study the complexity of a two-point boundary value problem. We concentrate on the linear problem of order k with separated boundary conditions. Right-hand side functions are assumed to be r times differentiable with all derivatives bounded by a constant. We consider three models of computation: deterministic with standard and linear information, randomized and quantum. In each setting, we construct an algorithm for solving the problem, which allows us to establish upper complexity bounds. In the deterministic setting, we show that the use of linear information gives us a speed-up of at least one order of magnitude compared with the standard information. For randomized algorithms, we show that the speed-up over standard deterministic algorithms is by 1/2 in the exponent. For quantum algorithms, we can achieve a speed-up by one order of magnitude. We also provide lower complexity bounds. They match upper bounds in the deterministic setting with the standard information, and almost match upper bounds in the randomized and quantum settings. In the deterministic setting with the linear information, a gap still remains between the upper and lower complexity bounds.
Given oracle access to an unknown unitary U=eiHU=e^{iH}U=eiH , the fractional query problem asks how many queries are required to implement a noninteger power Ut=eitHU^t=e^{itH}Ut=eitH, 0<t<10<t<10<t<1, when the spectrum is separated from the branch cut by a gap δδδ. Quantum singular value transformation gives an upper bound of O ⁣(1δlog⁡1ε)O\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)O(δ1​logε1​) queries for approximation error ε\varepsilonε. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any NNN-query circuit to the approximation of eitθe^{itθ}eitθ by a trigonometric polynomial with degree bounded by O(N)O(N)O(N), together with Remez inequality. This allows us to establish the lower bound of Ωτ ⁣(1δlog⁡1ε)Ω_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)Ωτ​(δ1​logε1​). Consequently, the optimal query complexity for fractional query problem is Θτ ⁣(1δlog⁡1ε)Θ_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)Θτ​(δ1​logε1​), showing that the known QSVT construction is asymptotically optimal. We also give an alternative lower bound proof based on constructing a linear functional that annihilates the approximant space, yielding a Ωτ ⁣(log⁡1ε)Ω_τ\!\left(\log\frac{1}{\varepsilon}\right)Ωτ​(logε1​) bound uniform to δδδ.