Tractability of Approximation for Weighted Korobov Spaces on Classical and Quantum Computers

Details Tractability of Approximation for Weighted Korobov Spaces on Classical and Quantum Computers Tractability of Approximation for Weighted Korobov Spaces on Classical and Quantum Computers

2002-06-04

arxiv.org/abs/quant-ph/0206023v2

Physics

Quantum Physics

37 pages

Scientific paper

The paper studies quantum complexity, tractability, and strong tractability for high dimensional multivariate approximation. We study a space of functions important in many applications. A function space is weighted if certain variables are more important than others; the weights show the relative importance of the variables. In an unweighted space all variables are equally important and multivariate approximation is intractable. We want to study when the complexity of multivariate approximation is independent of the number of variables and depends polynomially on 1/E. The main conclusions are: Multivariate approximation on a quantum computer can be solved roughly (1/E)^(1+r) times faster than on a classical computer using randomization. Here, r is a positive parameter that depends on the weights and may be large. This means that the speed-up of quantum over classical computers may be much larger than quadratic. Multivariate approximation on a quantum computer is exponentially faster than on a classical computer with a worst case assurance even if the sum of weights is infinite but a certain power of them is finite. We have designed a quantum algorithm with error at most E that uses about d+log(1/E) qubits. Hence, we have only linear dependence on the dimension d and logarithmic dependence on 1/E. Therefore, for some applications the number of qubits is quite modest.

Affiliated with

Also associated with

No associations

Rating

Tractability of Approximation for Weighted Korobov Spaces on Classical and Quantum Computers 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 Tractability of Approximation for Weighted Korobov Spaces on Classical and Quantum Computers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tractability of Approximation for Weighted Korobov Spaces on Classical and Quantum Computers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-96107