# 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

The goal of quantum computing is to harness the peculiar behavior of particles at the quantum scale in order to perform calculations that aren’t believed to be feasible with conventional computers. An ordinary computer stores “bits” of information in transistors, which, like switches, can be configured in one of two states, represented by “1” or “0.” A quantum computer stores “qubits” of information in subatomic particles, such as electrons or photons, which can exist in state 1 or 0, or in a superposition of both states, and which can become entangled with one another, so that the state of one qubit decides the state of another.

Superposition and entanglement cause qubits to behave very differently from bits. Whereas a two-bit circuit in a conventional computer can be in only one of four possible states (0 and 0, 0 and 1, 1 and 0, or 1 and 1), a pair of qubits can be in a combination of all four. As the number of qubits in the circuit increases, the number of possible states, and thus the amount of information contained in the system, increases exponentially. A quantum computer with just a few hundred qubits would be able to solve certain problems more quickly than today’s supercomputers.

The only problem is that no one has managed to construct a quantum circuit with more qubits than you can count on both hands. Chris Lirakis, a physicist in the superconducting quantum computation group at IBM Research, explained that in order to keep the delicate entanglement of a system of qubits from collapsing, the system must be isolated and cooled to a temperature near absolute zero. At the same time, the qubits must be spaced about a centimeter apart to prevent an operation performed on one qubit from altering the states of neighboring ones. This challenge would make a thousand-qubit system far too large to fit into the kinds of refrigerators that can achieve such extreme cooling.

“There are a lot of really serious engineering challenges that need to be brought to bear in order to make the system scalable,” Lirakis said. “It’s this tug-of-war between all these different issues.”

Regev, who worked with Peikert in using quantum ideas to prove the security of lattice-based cryptosystems, says he hopes quantum computers will be built in his lifetime so he can see them in action. “But quantum has made such a great impact that even if quantum computers are never built, I wouldn’t care too much,” he said.

As quantum techniques become more popular among computer scientists, they will likely produce more classical results. “It’s these results that convince me that even if the universe had not been quantum mechanical,” Aaronson said, “eventually computer scientists would have invented quantum computing as a proof tool.”

Reprinted with permission from Simons Science News, an editorially independent division of SimonsFoundation.org whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the computational, physical and life sciences.

View
1. 1. juniorsa 10:53 AM 12/28/12

"As quantum techniques become more popular among computer scientists, they will likely produce more classical results."

I 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.

2. 2. allpowerful32 01:25 PM 12/28/12

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.

So, I ask again, why "non-negative real numbers"?

3. 3. Steven 06:09 PM 12/28/12

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.
Rather 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.

4. 4. joenn 10:31 PM 12/28/12

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.

Just an idea. Maybe not a good one but an idea nun the less

5. 5. Freemove 04:47 AM 12/29/12

A system which combines classical and quantum technology is already operational since 2007. On https://wuala.com/FreemoveQuantumExchange you can find more information.

Also a lot of applications of using Quantum Randomness are already operational. On https://wuala.com/QuantumRandomnessApplications you can find some examples.

6. 6. harrow in reply to allpowerful32 02:14 AM 1/5/13

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.

Note 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.

7. 7. harrow in reply to joenn 02:22 AM 1/5/13

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).

8. 8. harrow 02:28 AM 1/5/13

Sorry, 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.

9. 9. bellJay 02:04 PM 8/26/13

Interesting article. Thanks. With the development of quantum computing, it will become more and more likely and feasible that someday we will be able to create computer simulated universes, which would then advance the idea that we ourselves reside within a simulation and even a simulation within a simulation. There is a fascinating new book on the subject, entitled "On Computer Simulated Universes". It takes on this topic from more of a philosophical perspective but discusses the implications on Free Will and our concepts of immortality.

http://www.amazon.com/Computer-Simulated-Universes-Mark-Solomon/dp/0989832511

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Click one of the buttons below to register using an existing Social Account.

## More from Scientific American

• Scientific American Magazine | 45 minutes ago

### How Brain Scans Might Change the Way Doctors Diagnose Alzheimer’s

• Octopus Chronicles | 14 hours ago

### Octopus In Space: Why the Latest U.S. Spy Rocket Is More Appropriate Than the NRO Knows

• TechMediaNetwork | 14 hours ago | 5

### Radiation on Mars 'Manageable' for Manned Mission, Curiosity Rover Reveals

• News | 14 hours ago | 3

### Powder Rive Basin Coal on the Move

• TechMediaNetwork | 15 hours ago | 1

More »

## Latest from SA Blog Network

• ### Freezing, Boiling, Dehydration and Starvation

Image of the Week | 1 hour ago
• ### Helen's Choice: Female Multiple Mating in the Natural World

The Primate Diaries | 2 hours ago
• ### Tuesday Tune: They Might Be Giants

Rosetta Stones | 4 hours ago
• ### Found: The Coldest Place on Earth

Observations | 7 hours ago
• ### Octopus In Space: Why the Latest U.S. Spy Rocket Is More Appropriate Than the NRO Knows

STAFF
Octopus Chronicles | 15 hours ago

## Science Jobs of the Week

Classical Computing Embraces Quantum Ideas

X

Give a 1 year subscription as low as \$14.99

X

X

###### Welcome, . Do you have an existing ScientificAmerican.com account?

No, I would like to create a new account with my profile information.

X

Are you sure?

X