Classical Computing Embraces Quantum Ideas

"Thinking quantumly" can lead to new insights into long-standing problems in classical computer science, mathematics and cryptography, regardless of whether quantum computers ever materialize

Courtesy of IBM Research

FromSimons Science News(find original story here).

Someday, quantum computers may be able to solve complex optimization problems, quickly mine huge data sets, simulate the kind of physics experiments that currently require billion-dollar particle accelerators, and accomplish many other tasks beyond the scope of present-day computers. That is, if they are ever built. But even as daunting technical challenges keep the dream at bay, theorists are increasingly putting the ideas and techniques of quantum computing to work solving deep, long-standing problems in classical computer science, mathematics and cryptography.

There are quite vigorous debates about whether quantum computers will ever actually be built, said Chris Peikert, a cryptographer and computer scientist at Georgia Institute of Technology. But thats a separate question from whether quantum techniques or quantum algorithms can help you solve problems in new ways.

In recent years, quantum ideas have helped researchersprove the securityof promising data encryption schemes called lattice-based cryptosystems, some applications of which can shroud users sensitive information, such as DNA, even from the companies that process it. A quantum computing proof also led toa formula for the minimum length of error-correcting codes, which are safeguards against data corruption.

Quantum ideas have also inspired a number of important theoretical results, such asa refutation of an old, erroneous algorithmthat claimed to efficiently solve the famously difficult traveling salesman problem, which asks how to find the fastest route through multiple cities.

If it only happened once it would be a coincidence, but there are so many instances when we think quantumly and come up with a proof, said Oded Regev, a computer scientist at New York University.

This recurring theme has led some researchers to argue that quantum computing is not an esoteric subfield of computer science, but rather a generalization of classical computing, in much the same way that polygons are a generalization of triangles. Just as polygons can have any number of sides while triangles only have three, quantum computers can perform operations represented by any numbers (positive or negative, real or imaginary), while operations on classical computers use only nonnegative real numbers.

As the more general case, quantum ideas are a powerful tool in developing more specific classical computing proofs. There area number of classical problemsthat have nothing to do with quantum, but that are most easily analyzed by generalizing to the quantum level, proving something using quantum information theory, and scaling back the result to the classical level, said Ronald de Wolf, a theoretical computer scientist at the Dutch Centre for Mathematics and Computer Science.

Go here to see the original:
Classical Computing Embraces Quantum Ideas