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

Abstract

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.

Keywords:

• boundary value problems
• complexity
• worst-case setting
• randomized computing
• quantum computing

2000 AMS Subject Classifications :

• 68Q25
• 65L10
• 68W20

C.R. Category :

• G.1.7

Acknowledgements

The authors would like to thank the referees for many helpful suggestions. This research was partly supported by AGH grant No. 10.420.03.