 |
|
Subscribers:
to view the full text of a paper, click on the title of the paper. If you
have any problem to access the full text, please check with your librarian
or contact
qic@rintonpress.com
To subscribe to QIC, please click
Here.
|
Quantum
Information and Computation
ISSN: 1533-7146
published since 2001 |
|
Vol.23 No.7&8 May 2023 |
|
On the quantum complexity of integration of a function with unknown singularity
(pp603-613)
Maciej Go\`{c}win
doi:
https://doi.org/10.26421/QIC23.7-8-4
Abstracts:
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$.
Key Words:
integration, unknown
singularities, quantum algorithms,
optimality, complexity |
กก |
