UW CSE’s Dave Bacon has the cover article in this month’s Communications of the ACM.
“It is impossible to imagine today’s technological world without algorithms: sorting, searching, calculating, and simulating are being used everywhere to make our everyday lives better. But what are the benefits of the more philosophical endeavor of studying the notion of an algorithm through the perspective of the physical laws of the universe? This simple idea, that we desire an understanding of the algorithm based upon physics seems, upon first reflection, to be nothing more than mere plumbing in the basement of computer science. That is, until one realizes that the pipes of the universe do not seem to behave like the standard components out of which we build a computer, but instead obey the counterintuitive laws of quantum theory. And, even more astoundingly, when one puts these quantum parts together, one gets a notion of the algorithm—the quantum algorithm—whose computational power appears to be fundamentally more efficient at carrying out certain tasks than algorithms written for today’s, nonquantum, computers. Could this possibly be true: that there is a more fundamental notion of algorithmic efficiency for computers built from quantum components? And, if this is true, what exactly is the power of these quantum algorithms?”
Read the full article here. Read Dave’s Quantum Pontiff blog here.