Quantum Complexity of Integration

Details Quantum Complexity of Integration Quantum Complexity of Integration

2000-08-29

arxiv.org/abs/quant-ph/0008124v3

Journal of Complexity, 17 (2001), 2-16

Physics

Quantum Physics

13 pages, some minor corrections

Scientific paper

It is known that quantum computers yield a speed-up for certain discrete problems. Here we want to know whether quantum computers are useful for continuous problems. We study the computation of the integral of functions from the classical Hoelder classes with d variables. The optimal orders for the complexity of deterministic and (general) randomized methods are known. We obtain the respective optimal orders for quantum algorithms and also for restricted Monte Carlo (only coin tossing instead of general random numbers). To summarize the results one can say that (1) there is an exponential speed-up of quantum algorithms over deterministic (classical) algorithms, if the smoothness is small; (2) there is a (roughly) quadratic speed-up of quantum algorithms over randomized classical methods, if the smoothness is small.

Affiliated with

Also associated with

No associations

Rating

Quantum Complexity of Integration does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Complexity of Integration, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Complexity of Integration will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-269217