Image: Courtesy of IBM Research
-
The Best Science Writing Online 2012
Showcasing more than fifty of the most provocative, original, and significant online essays from 2011, The Best Science Writing Online 2012 will change the way...
Read More »
From Simons 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 that’s 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 researchers prove the security of 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 to a 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 as a refutation of an old, erroneous algorithm that 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 are a number of classical problems that 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.
Currently, it is estimated that fewer than 5 percent of theoretical computer scientists study quantum computing. But researchers say that recent success from “thinking quantumly” has led a growing number of theorists to brush up on their physics. “These very striking spinoffs of quantum computing have actually drawn classical computer scientists into learning something about quantum computing,” said Scott Aaronson, a theoretical computer scientist at the Massachusetts Institute of Technology.
See what we're tweeting about
8 Comments
Add Comment"As quantum techniques become more popular among computer scientists, they will likely produce more classical results."
Reply | Report Abuse | Link to thisI think only classical results are interesting actually since in a classical way you have predictability necessary to machine construction and in many 'Quantum phenomena' classical ways are necessary to check if the entanglement was or not achieved but what is the gain of such a system or how much worth is it? Can really information go out trough the channel? Can computation really go out of the computer? Is it quantum mechanics really a fundamental principle of nature or just we did no get there yet? Many experiments in the past were anomalies to (I remember one with a rotating mirror that was published in the 80s) the theory and may we need to rethink everything.
What do you mean, "while operations on classical computers use only nonnegative real numbers"? I figure you are trying to refer to one of two things: either the fundamental binary ("digital") nature of classical computation - in which case the "real number" part is incorrect (classical computers can really only compute on integers and rational numbers (or other, countably-infinite representations), which are used as approximations to real numbers); or some limitation in software - in which case I would say, what makes you think classical computers are limited to non-negative numbers? Take for example software packages that compute quite effectively, with arbitrary precision or symbolically, over real numbers, complex numbers, or any other Field (in the abstract algebra sense) you might be interested in. Mathematics packages like Mathematica, Maple, and Matlab are easy examples of this - but most programming languages directly provide the ability to compute with negative "real" numbers (in quotes because of the typical fixed-precision nature). Even if the particular language doesn't offer those capabilities (there are some languages that only natively do natural-numbers or integers, or even lower-level "Peano-arithmetic" or "Church-numeral" style computation), as long as it's Turing complete (as all practical languages are), support for such computation can be implemented in the language.
Reply | Report Abuse | Link to thisSo, I ask again, why "non-negative real numbers"?
Actually I think they probably are overlooking important aspects of quantum mechanics. Traditionally it is said in the traditional approach to quantum mechanics that a particle can be in two places at once. This seems to be a misunderstanding or oversimplification of quantum mechanics.
Reply | Report Abuse | Link to thisRather than being in two places at once, a quantum particle can be in many places at once, and in fact, could probably be in an infinite number of places at the same time.
If this understanding of quantum mechanics is applied, then it will simplify understanding of the universe and its components.
Probably all computers utilize some components of quantum mechanics in ordinary operations.
To really apply quantum mechanics to computing, it may be necessary to introduce interdimensional mechanics.
I wonder if there is a way to use a spreadsheet program like Excel and program a certain number of cells to each act like a qbit. Would they be able to interact with each other like a quantum computer? I know it would be slow and clunky to use but I wonder if it would give us a framework to start with.
Reply | Report Abuse | Link to thisJust an idea. Maybe not a good one but an idea nun the less
A system which combines classical and quantum technology is already operational since 2007. On https://wuala.com/FreemoveQuantumExchange you can find more information.
Reply | Report Abuse | Link to thisAlso a lot of applications of using Quantum Randomness are already operational. On https://wuala.com/QuantumRandomnessApplications you can find some examples.
The article is glossing over a lot here. The author is trying to say that classical (randomized) computers can be thought of as having a state that is a probability distribution. Let's be concrete and consider an 8-bit computer (meaning a computer with 8 bits of memory total, unlike a typical computer with billions of bits of memory). This computer has 256 states: 00000000, 00000001, ..., 11111111. If the computer can make random choices, then we can think of its state as a list of 256 nonnegative real numbers summing to 1; i.e. a probability distribution over these 256 states. An 8-qubit quantum computer's state is in fact described by a list of 256 complex numbers whose absolute values squared sums to one.
Reply | Report Abuse | Link to thisNote that none of this discussion has anything to do with whether the bits of the computer are used to represent positive integers, negative numbers, real numbers, Greek letters or anything else.
It is possible for classical computers to simulate quantum computers (and quantum mechanics in general), but at an exponential cost. That is, simulating n qubits (i.e. n of the smallest nontrivial quantum systems) requires memory and computational time scaling like 2^n. This is in the worst case, but there are also specific families of examples where a simulation can be done more cheaply. One such family is given by the Gottesman-Knill theorem (see wikipedia for details).
Reply | Report Abuse | Link to thisSorry, one more comment. I really like this article, and didn't mean to criticize when I said it glossed over the point about nonnegative numbers; rather I think that skipping those details is an inevitable compromise given the space.
Reply | Report Abuse | Link to this