CACM Coverage: Progress in Quantum Algorithms

February 3, 2010

UCSB Computer Science Prof. Wim van Dam describes latest progress in quantum algorithms.

In the February 2010 issue of Communications of the ACM, UC Santa Barbara’s Wim van Dam and Dave Bacon of the University of Washington give an overview of the recent progress in the design of new quantum algorithms. Unlike our current computers, the behavior of a quantum computer cannot be described by classical physics and therefore also require non-classical algorithms.

In 1994 it was discovered that there is an efficient quantum algorithm that can efficiently factor integers and calculate discrete logarithms, thus potentially breaking almost all public key cryptography protocols. Ever since this discovery, computer scientists, physicists and mathematicians have been working on designing other, new quantum algorithms that outperform classical algorithms. As Bacon and Van Dam write in this review, this is difficult research as we do not yet have a fully working quantum computer: “Designing quantum algorithms for a quantum computer is like building a car without having a road or gas to take it for a test drive.” Despite these difficulties, the past years several new and exciting quantum algorithms have been found, and the article explains some of most surprising ones.

Communications of the ACM is the monthly journal of the Association for Computing Machinery; members of the ACM and UCSB students can read the article by Bacon and Van Dam at http://doi.acm.org/10.1145/1646353.1646375 Recently, Van Dam together with Andrew Childs from the University of Waterloo, also published a more detailed and comprehensive review on quantum algorithms in the scientific journal Reviews of Modern Physics (Vol. 82, January 2010).