Yes. Grover's algorithm searches a disordered database in time sublinear in the number of elements, and provides a quadratic speedup over any possible classical algorithm. There are similar results for finding collisions etc. There is no proof, however, that quantum computers offer an exponential advantage on decision problems without some additional assumption, although this is widely believed to be the case, due in part to the exponential improvement of Shor's factoring algorithm compared to the best -known- classical algorithms.

> are we sure we will not need exponentially more energy or time to get the result of computation

The minimum free energy that must be expended to operate a computer is theoretically very close to zero, since it is not strictly necessary to use irreversible primitives[0], such as NAND gates, which is something that we do in traditional computers. For irreversible elements the theoretical requirement is about kT*ln(2) at temperature T. DNA uses about 100 kT per bit copied.

I really recommend that you take a look at Feynman's introduction to quantum computing[1].

[0] http://www.cs.princeton.edu/courses/archive/fall04/cos576/pa...

[1] http://www.cs.princeton.edu/courses/archive/fall05/frs119/pa...

Thanks for the links !

Quantum computing is not about making simultaneous or parallel computations. Its about taking advantage of quantum mechanics (constructive and destructive interference of quantum waves, etc) to obtain very efficient algorithms for some kinds of problems.