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.
- API Playbook: Drive API Adoption Through Developer Engagement Learn the best practices of how to engage developers, whether your goal is to attract external developers to your public APIs or improve...
- Leverage the Power of APIs to Turbocharge Your Mobile Strategy: 7 Steps to a Successful API Program In this guide, Intel® Services-which offers industry-leading API management solutions for over 150 top enterprises, including Best Buy, Netflix, Expedia, ESPN, and The...
- Troubleshooting Common Issues in VoIP Learn more about Voice over Internet Protocol (VoIP), including common VoIP metrics used, best practices in VoIP management and tips and tricks for...
- IDG Research Survey: Are you Paying Too Much for Your NMS? Feel like you're paying too much for network monitoring? You're not alone. This survey brief summarizes findings from research recently fielded by IDG...
- API Management: The Key to Improving the Consumer Travel Experience Join PhoCusWright's Senior Technology Analyst, Norm Rose, as he shares his insights on how travel suppliers and intermediaries can improve industry data flow...
- Tips to Simplify Database Administration and Development Make your job easier while getting the most from the leading productivity tool for database professionals. Learn tips from Dell Software's Oracle® ACE,... All Processors White Papers | Webcasts