Despite quantum's gains, standard computers still rule

Jan 03, 2014 by Richard Ingham, Laurent Banguet
View of the National Security Agency (NSA) in the Washington suburb of Fort Meade, Maryland, 25 January 2006

Quantum computing is getting the headlines these days, with buzz among scientists of giga-powered number-crunching and unbreakable encryption.

The US National Security Agency (NSA) is reportedly advancing towards a quantum computer that could crack almost any conventional algorithm.

The NSA plans were leaked by contractor Edward Snowden and reported by The Washington Post on Thursday.

Details of its work remain sketchy, though. And the agency is only one of many players, both public and corporate, in a field that must overcome many hurdles before it can dethrone standard computing.

Conventional computers work by processing binary code—an information currency that exists in one of two states, either zero or 1.

Quantum computers, though, break free of the two-state constraints.

They harness the principle of quantum mechanics, when strange things occur through the state of an atom's spin, something called angular momentum.

In a quantum state, the atom goes into a condition called superposition. It can hold the value of zero or 1 or both values at the same time.

This juggling trick holds out the possibility of parallel processing on a massive scale.

An algorithm that a conventional supercomputer might take years to break could be cracked by so-called qubits, or quantum bits, in a fraction of the time.

"The special properties of qubits will allow quantum computers to work on millions of computations at once," says IBM. "For example, a single 250-qubit state contains more bits of information than there are atoms in the Universe."

Daunting engineering obstacles have to be overcome, though. In order to achieve the fragile quantum state, a cloud of atoms has to be cooled to near-absolute zero and controlled by pulses of laser.

Changes in temperature, electromagnetic waves and minute defects in material can all wreck the sought-after superposition that fuels the qubit.

Scaling up these computers from hugely expensive, highly protective labs represents "an enormous practical challenge," the Nobel jury said in 2012, when it awarded that year's physics prize for fundamental work on the quantum state.

Quantum's other big plus is a phenomenon called entanglement.

Particles created in a quantum state behave like psychic twins.

Even if they are far apart, a disturbance to one particle affects the other, a phenomenon that Einstein once called "spooky action at a distance."

Thus if a message sent in a quantum state is intercepted en route, the entanglement is destroyed—and alarm bells ring that someone is eavesdropping.

Achieving quantum cryptography

Entanglement is the big goal of quantum cryptography.

It holds out the possibility of creating a unique, one-time code shared only by sender and recipient that would be almost impossible to decrypt by an outsider. Better still, the message could not even be touched during transmission.

Even without entanglement, though, the quantum state can be useful in cryptography, said Philippe Grangier, a specialist in quantum optics at France's National Centre for Scientific Research (CNRS).

His team has done tests that sends a standard-encrypted message, along with a quantum-encrypted key, in squirts of light down a fibre-optic cable.

Once received, the key is then used to decode the message.

The technique uses the quantum signature in the key as a burglar alarm, Grangier said in a phone interview.

"Just the slightest interception of the data will reduce the size of the quantum key when it gets to the recipient, and the spy gets detected," said Grangier.

"The more the spy perseveres, the smaller the key becomes. Eventually, the connection is cut."

Their greatest length for transmission has been through a cable 80 kilometres (50 miles) long—a distance that is useful for local communications but still way too short for transcontinental use or more.

Going beyond this distance lies the conundrum of how to amplify a weakening light signal down a cable so that the data is repeated but does not lose its quantum state through interference.

Other techniques aim at overcoming the "repeater" problem by line of sight laser transmission, in theory to satellites in near-Earth orbit.

Explore further: NSA eyes encryption-breaking 'quantum' machine

add to favorites email to friend print save as pdf

Related Stories

NSA eyes encryption-breaking 'quantum' machine

Jan 03, 2014

The US National Security Agency is making strides toward building a "quantum computer" that could break nearly any kind of encryption, The Washington Post reported Thursday.

How losing information can benefit quantum computing

Nov 24, 2013

Suggesting that quantum computers might benefit from losing some data, physicists at the National Institute of Standards and Technology (NIST) have entangled—linked the quantum properties of—two ions ...

Scientists realize quantum bit with a bent nanotube

Jul 29, 2013

One of the biggest challenges in quantum science is to build a functioning quantum bit, the basic element for the quantum computer. An important theoretical candidate for such a quantum bit is using a bent ...

A single-atom light switch

Nov 05, 2013

With just a single atom, light can be switched between two fibre optic cables at the Vienna University of Technology. Such a switch enables quantum phenomena to be used for information and communication technology.

Recommended for you

How Paramecium protozoa claw their way to the top

Sep 19, 2014

The ability to swim upwards – towards the sun and food supplies – is vital for many aquatic microorganisms. Exactly how they are able to differentiate between above and below in often murky waters is ...

User comments : 20

Adjust slider to filter visible comments by rank

Display comments: newest first

domanite
4.5 / 5 (2) Jan 03, 2014
Quantum computing feels like fusion power - always on the horizon, but every problem solved leads to two more new ones.
Returners
1 / 5 (3) Jan 03, 2014
In a quantum state, the atom goes into a condition called superposition. It can hold the value of zero or 1 or both values at the same time.
This juggling trick holds out the possibility of parallel processing on a massive scale.


I would like to see a mechanical explanation of how you can make a circuit which can distinguish, in the case of the "both values at the same time" scenario, whether the "zero" value should go to the left hand circuit, or whether it should go to the right hand circuit.

If the qubit is holding two pieces of information simultaneously, how do you know which piece of information belongs in which data stream or process, since there is no apparent "Marker" to distinguish the two pieces of data from one another?

"For example, a single 250-qubit state contains more bits of information than there are atoms in the Universe."


Where is the math to explain this?

There are about 600 sextillion stars in the universe, each containing about 10^30 kg matter.
Returners
1 / 5 (3) Jan 03, 2014
now if each Qubit has 3 potential states: 0, 1, and "both", then for 250 cubits there are:

3^250 states, or about 2* 10^119 states..

I find there should be 3.6e80 atoms within Stars, however Stars don't even make up the majority of known matter in the universe, for example, the milky way is about 6 times more massive than all the stars it contains.

Additionally, any computer requires some "firmware," which is circuits which are always the same, therefore some of the states (an exponentially large portion of them,) represented in that calculation will never be available.

Anyway, I have never seen a demonstration of anyone sorting out for "parallel processing" the meaning of a "Both" signal on a cubit, and which state would go to which other processor or "memory".

You would need additional cubits sent along with the first, which would acts as "flags" to sort out the meaning of that, since there's no logical way to make that decision without additional information.
Returners
1.3 / 5 (4) Jan 03, 2014
How do you even know the difference between a "1" and a "both" anyway?

A "both" is a "1", but a "1," which you have just received, might well be a "both" and you just didn't realize it, because you were "looking for" a "1" and didn't check for a "0".

Additionally, uncertainty principle says you can't measure it without changing it.

Some math:

0 + 1 = 1

0 and 1 = both (quantum)

1 = 1

0 = 0

0 + 1 = 1, cannot be distinguished from 1 = 1, because it's not necessarily reversible, and that's just the classical operation. The quantum operation cannot be reversible, because that would violate uncertainty principle.

The quantum operations I've seen, in what little progress has been made, are so simple this doesn't matter, but this would surely begin to screw things up in more complicated applications.

Programming/Coding for this would be like trying to knit a sweater while blind-folded, because you'll spend far more time on error code than the actual problem being simulated.
shavera
5 / 5 (1) Jan 03, 2014
Returners, there's just so many things _wrong_ with your post I don't have the time to correct them. If you can, please trust me that really rather intelligent people _do_ know what they're doing about the subject. It really does require some basic knowledge of quantum mechanics to explain though.

Specifically that both is not the same as 1. For instance, a spin 1/2 particle may have a spin up state that we *label* as 1, and spin down as *zero* (ie, spin measured along an up down axis will either be up the axis or down the axis). A quantum particle will behave as if it is both *up* and *down* (plus some relative phase between these states) until it is measured. What we can then do is create a lot of logic gates that rotate or interfere these particles together, while in superposition, to perform quantum logic operations.

Then at the end, we measure, and the particles no longer act as if they're in both states, but in one state or the other, and that is our answer.
davidivad
not rated yet Jan 03, 2014
check out the d-wave 2 quantum computer for sale.
Eikka
3 / 5 (2) Jan 03, 2014
Then at the end, we measure, and the particles no longer act as if they're in both states, but in one state or the other, and that is our answer.


That is not the final answer though. The superposition collapses into a single state where all the other data except one possible combination vanishes. What comes out is simply a matter of luck.

The right answer is seen from the aggregate result of many thousand repetitions of the same calculation, where it is known that the quantum algorithm returns the right answer e.g. 50% of the time. From the distribution of answers, one then picks the one that seems to appear the correct number of times.

This means the quantum computer is limited in so far as it has to be "reloaded" with the data over and over, and so it becomes constrained by the data source that is used to encode the qubits. It would take eons to do a calculation involving something like the entire Google database.
baudrunner
3 / 5 (2) Jan 03, 2014
Better yet, @Returners, check out jQuantum, a Quantum Computer Simulator, here.. http://jquantum.s...dex.html

I don't think that @Eikka fully understands quantum computing. From the MIT Technology Review: "The most extensive quantum computation in history took just 270 milliseconds, say quantum physicists." here.. http://www.techno...-qubits/
Eikka
3 / 5 (2) Jan 03, 2014
The most extensive quantum computation in history took just 270 milliseconds


Although it is disputed whether the D-wave computer really is a quantum computer of just an analog computer similiar to how you can use soap bubbles to solve some optimization problems, because the "adiabatic quantum computer" works kinda like setting up the problem as pegs between two plates of glass immersed in soapy water, and then draining the water (lowering the temperature) to see where the films of soap find their lowest energy configurations and shapes.

Returners
2.3 / 5 (4) Jan 03, 2014
Well, I found D-Wave claims to be odd all along anyway, because it wasn't well received.

I have a nagging suspicion that real quantum computers will never be as good as the on-paper numbers suggest, because of a matter of design and flexibility. I think they probably aren't going to be much better than the best possible classical computers.

Better yet, @Returners, check out jQuantum, a Quantum Computer Simulator, here.. http://jquantum.s...dex.html


Eikka is describing what amounts to a probability distribution, which technically is very similar to some quantum algorithms. It doesn't necessarily produce a discreet solution. It produces a "best probability", for example, "the answer is probably 1."
davidivad
not rated yet Jan 04, 2014
the d wave is the first of a new class of computers. while it passes the test for entanglement, it really is barebones. the only question now is whether a full fledged quantum computer can be viable.
Eikka
5 / 5 (1) Jan 04, 2014
It doesn't necessarily produce a discreet solution. It produces a "best probability", for example, "the answer is probably 1."


That's the point.

That's what quantum computers do. The more times you repeat the calculation, the more confident you can be of the answer, which is why you have to compromize between precision and speed.

You can make incredibly fast calculations with vast datasets if you only care that the answer is right to the probability of flipping a coin. If you need simulations correct down to the 14th decimal place, the quantum computer slows down to a crawl.

while it passes the test for entanglement,


Does it now?
Returners
3 / 5 (2) Jan 04, 2014

That's the point....


Yet I've seen Quantum Computing lecture/seminars where the speaker spent most of the time trying to show how and why a Quantum Computer could solve discreetly the most perfect game for any turn based game. Not just an individual move, but all possible moves in all possible games simultaneously, in fewer steps than a classical computer could, and give the answer.

For example, the question might be regarding whether the rules of the game favor the first player or the second player in a turn-based game. In really complicated games this might be incredibly difficult or impossible to prove by experiment, because you also have to factor in skill gap and similar problems. Did the first player win because he's better, or did he win because the rules favor the first player?

Even after seeing the math of how that was supposed to be done, I could not convince myself that there was an actual circuit which could be constructed in reality to do what he said.
Zephir_fan
Jan 04, 2014
This comment has been removed by a moderator.
Telekinetic
not rated yet Jan 04, 2014
Quantum computing will make its predecessors seem like buggy whips- it's inevitable. What will happen, despite your whimpering impatience, is an effort akin to the Manhattan Project, where all of the resources of the world focus on building a practical working model because "information" is the most powerful weapon today.
skippy_skippys
5 / 5 (1) Jan 05, 2014
Even after seeing the math of how that was supposed to be done, I could not convince myself that there was an actual circuit which could be constructed in reality to do what he said.


But you didn't have any trouble convincing yourself that the Lurker Skippy was due for an upgrade? You should ask for your money back Skippy, the Returner Skippy is just as slow as the Lurker Skippy.


But twice as quick as the zephir_fan skippy.
big_hairy_jimbo
not rated yet Jan 06, 2014
I'm no expert in this area, but an analogy that I think about is this.

The double slit experiment, gives an outcome of ALL possible solutions, ie it produces an interference pattern. If you look which slit the photon went through, you disrupt the system, so don't look, and the system preserves its quantum de-coherence. Now if you fiddled this system a bit, you could ask the system, is the position I'm thinking about a part of the solution set? This device could yield a YES or NO answer to that question, without doing classical calculations to obtain the solution set. So Quantum Computers will be good at KNOWING the total solution set to a problem, you then can ask questions about specific data against that data set.
I believe D-Wave to be a machine designed just to compute problems to ONE kind of problem. Much like my double slit analogy above. A True Quantum Computer will hopefully be a GENERAL purpose computing device. A bit like the difference between a PC and a digital watch!!
baudrunner
not rated yet Jan 08, 2014
Although it is disputed whether the D-wave computer really is a quantum computer of just an analog computer similiar to how you can use soap bubbles to solve some optimization problems, because the "adiabatic quantum computer" works kinda like setting up the problem as pegs between two plates of glass immersed in soapy water, and then draining the water (lowering the temperature) to see where the films of soap find their lowest energy configurations and shapes.
(strokes chin)"You know what? nooo..., yeah..."

Eikka is jealous because D-Wave is not an American company. We got some smarts up here in Canada, you know.
Eikka
not rated yet Jan 17, 2014

Eikka is jealous because D-Wave is not an American company. We got some smarts up here in Canada, you know.


I am not American.
Nestle
not rated yet Jan 17, 2014
Quantum computing will make its predecessors seem like buggy whips- it's inevitable
The people believe, that the quantum computers QCs must be of highest speed and information density (particularly because lotta money is involved in QC research) - but IMO the computational power of QCs is limited with uncertainty principle in similar way, like this one of classical computers - just from opposite side of product of computational precision and speed. Briefly speaking, the QCs are fast but of low precision. To achieve the same precision, like the classical computing provides would require to repeat the quantum calculations multiple-times and to average the results, which would wipe out the advantage in speed. This theorem has been already proven for quantum communication.
Whydening Gyre
not rated yet Jan 17, 2014
quantum computing may be really fast, but as Eikka alluded to, it's the interfacing to our "real world" expectations that will slow it down...