• United States



U.S. Correspondent

Software Said to Match Quantum Computing Speed

Dec 23, 20104 mins
Build AutomationComputers and PeripheralsCPUs and Processors

Researchers have found a parallel computing algorithm that could offer quantum computer-speed performance.

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.

The algorithm provided a way to solve a problem using parallel processes, the kind easily executable with today’s multi-core processors and computer clusters. It provided a way to match the efficiency of quantum computing, for this set of problems.

Surprisingly, this matrix-based method hasn’t been applied to parallel computing before, Watrous said.

“It has never been considered to my knowledge in a parallel setting,” he said of the method. “We had to show that this method could be parallelized, and we couldn’t find any reference to anyone doing that.”

Watrous, while stating that he does not work in the commercial field of computer science, speculates that more work could be done in finding and adopting other mathematical algorithms that could speed the computational performance of hardware available today.

“We could try to build quantum computers to solve problems but we could also just design new algorithms to solve problems,” he said.

Aaronson said that the algorithm could be used in commercial fields of computing, particularly in the field of semi-definite programming, which looks at ways of solving optimization problems. “These are very common in industrial optimization,” he said.

The researchers showed that “for a certain class of semi-definite programs you can get not the exact answer but a very good approximate answer, using a very small amount of memory,” he said.

Joab Jackson covers enterprise software and general technology breaking news for The IDG News Service. Follow Joab on Twitter at @Joab_Jackson. Joab’s e-mail address is