Applied Physics

Quantum Problem Solvers

See allHide authors and affiliations

Science  30 Oct 2009:
Vol. 326, Issue 5953, pp. 645
DOI: 10.1126/science.326_645b

Quantum computers, when they become available, will harness the power of quantum mechanics to perform calculations and searches, outperforming classical computers at certain tasks. The development of quantum computers is two-pronged: Both hardware and software must be devised. The focus in the software realm is on which problems can be solved and how to do so. Solving a set of linear equations is a generic and important problem in many fields of science, engineering, and mathematics. On a classical computer the computational cost of extracting a solution grows linearly with the size of the system. Harrow et al. have developed a quantum algorithm that will solve the problem much more rapidly (scaling as the logarithm of the system size), requiring exponentially less time. Now we wait for the machinery to arrive.

Phys. Rev. Lett. 103, 150502 (2009).

Navigate This Article