Software said to match quantum computing speed

IDG News Service - While work continues on developing the fundamentals for super-fast quantum computers, a group of researchers has shown that, at least for some sorts of problems, classical computing could match the eventual speed of a working quantum computer -- with the correct software algorithms in place.

"We're putting lots of money into building quantum computers, but we shouldn't underestimate the power of algorithms," said John Watrous, who works at the Institute for Quantum Computing at the University of Waterloo at Ontario, Canada.

As a by-product of studying the predicted performance of quantum computing, Watrous and other researchers have shown how an algorithm little used in today's software could provide a new level of problem-solving performance in traditional computers, one that could match, in theory anyway, speeds obtained by quantum computers.

Their work was published in the latest edition of the Communications of the ACM, the flagship publication of the Association for Computing Machinery.

"One striking implication of this characterization is that it implies quantum computing provides no increase in computational power whatsoever over classical computing in the context of interactive proof systems," the paper notes.

In June, an earlier version of this paper won the Best Paper Award at the esteemed Symposium on Theory of Computing for 2010. The award shows that the work has major implications for the field of computer science, especially given that STOC judges rarely award quantum computing work, noted Scott Aaronson, an associate professor of electrical engineering and computer science at Massachusetts Institute of Technology, who was not involved in the work.

Quantum computing is often touted as the next stage of computer technology, one that could offer large-scale performance improvements after Moore's Law has been exhausted.

Taking advantage of the properties of quantum mechanics, a quantum computer could conceivably offer "exponential parallelism" in the aid of solving problems, Aaronson points out in a commentary accompanying Watrous' paper.

No quantum computers have been built yet, though companies such as IBM are beginning to develop the basic building blocks that could one day make such a computer.

The work of Aaronson and his colleagues seemingly settles a debate over whether or not one group of mathematical problems, called quantum interactive proof systems, are more or less difficult to solve than another set of problems, called classical interactive proof systems.

They are not, the paper asserts. But, due to the fact that these sets of problems are theoretical, the finding itself says little about quantum computing, beyond its ability to solve such abstract problems, Watrous admitted.

In order to set up the study, however, the researchers used an algorithm to evaluate potential speed in classical computation. Called the matrix multiplicative weights update method, it was developed from research in two mathematical fields of study, combinatorial optimization and learning theory.