3 ms·

Is there any theoretical proof that quantum computing is inherently more efficient than current technology ? We can theoretically make a lot of simultaneous co

by Rexxar 10y ago

Is there any theoretical proof that quantum computing is inherently more efficient than current technology ? We can theoretically make a lot of simultaneous computations but are we sure we will not need exponentially more energy or time to get the result of computation when we add more qubits in future quantum computers ?

irljf 10y ago
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.
davorb 10y ago
> 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/papers/bennett73.html http://www.cs.princeton.edu/courses/archive/fall04/cos576/pa... [1] http://www.cs.princeton.edu/courses/archive/fall05/frs119/papers/feynman85_optics_letters.pdf http://www.cs.princeton.edu/courses/archive/fall05/frs119/pa...
- Rexxar 10y ago
  Thanks for the links !
ufo 10y ago
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.

by Rexxar 10y ago

irljf 10y ago

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.

davorb 10y ago

> 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/papers/bennett73.html http://www.cs.princeton.edu/courses/archive/fall04/cos576/pa... [1] http://www.cs.princeton.edu/courses/archive/fall05/frs119/papers/feynman85_optics_letters.pdf http://www.cs.princeton.edu/courses/archive/fall05/frs119/pa...

Rexxar 10y ago
Thanks for the links !

ufo 10y ago

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.