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.
- Improving IT Efficiencies: Four Advantages of Multi-Tenant Data Centers Increasing demands on IT are forcing organizations to rethink their data center options. For many organizations, that means turning to the flexibility afforded...
- Accelerating Cloud Deployment and Operations with Managed Services Companies that do not have sufficient in-house expertise to either deploy or maintain an IaaS cloud should turn to Managed Service Providers .
- Rethinking IT Operations in the Cloud This paper breaks down the challenges that often prevent the cloud from delivering the fast, flexible and affordable infrastructure companies seek - and...
- Gartner Magic Quadrant for Cloud-Enabled Managed Hosting, North America Cloud-enabled managed hosting brings cloudlike consumption and provisioning attributes to the traditional managed hosting market
- NSS Labs & Cisco Present: Evaluating Leading Breach Detection Systems Today's constantly evolving advanced malware and APTs can evade point-in-time defenses to penetrate networks. Security professionals must evolve their strategy in lockstep to...
- Will the Real Endpoint Threat Detection and Response Please Stand Up? This webinar explores new technologies & process for protecting endpoints from advanced attackers as well as the innovations that are pushing the envelope... All Processors White Papers | Webcasts