A "Photon Machine Gun" For Quantum Computers 143
An anonymous reader writes "Generating entangled photons in a reliable way is impossible right now, stalling the development of the optical quantum computers that would use entangled photons as quantum bits (qubits). Because entangled photons can only be produced at random — which takes time — the most powerful optical quantum computing device use only 6 qubits. UK and Israeli quantum physicists have designed a blueprint for a 'quantum machine gun' that fires out barrages of entangled photons on demand. They think within a few years this device will be built, and could lead to quantum computing using 20 to 30 qubits. Every additional qubit doubles the computing power, so these quantum computers could outperform any existing classical computer, the researchers say. The quantum machine gun is described as 'one of the most exciting theoretical proposals I've read in five years' by a leading quantum physicist." The research was published in Physical Review Letters earlier this month.
For certain problems. (Score:5, Interesting)
Every additional qubit doubles the computing power, so these quantum computers could outperform any existing classical computer, the researchers say.
But only for probabilistic algorithms. It's not going to be faster at everything.
Re:Qubit does not double power in traditional sens (Score:3, Interesting)
I thought that the "power doubling" was not in a traditional sense.. the qubit is fantastic at pattern matching and search functions
Which is all that really matters for breaking encryption, and is the whole reason we have computers in the first place.
So my question is how many bits of encryption do I need to keep a 20~30 qbit computer out of my truecrypt partition?
Re:Not particularly useful against an insurgency (Score:2, Interesting)
It's a sad world we live in, that in the presence of scientific breakthroughs and ingenuity, one of the first thoughts that arises is of the fighting that surrounds that part of the world. I suppose Yom Kippur is a surprisingly appropriate time for reflection on that though.
Explain the hype, please? (Score:2, Interesting)
Ok, so on this site bursting with intelligent, educated folk, the following question(s) might make me look like a village idiot, but what the hell. It's damn interesting stuff and I want to know!
Exactly how does quantum computing work? I have a fleeting grip the basic stuff; qubits existing with states 0, 1 and "superposition" (i.e. all possible states) and that by actively measuring it's state (sending a photon or whatever bumping into it) you collapse it, and it's entangled mate, into a "classical state". If I place a shot glass in a dark room and tell you it could be empty, full or anything in between but the only way for you to find out is to A) Take the shot, or B) dump another 4cc of Tequila into the glass and see if it spills over, is the shot glass a cubit? To you, it is in a "superstate" until you actively measure it, an act that in itself makes the glass full or empty.
How does this equate to computing? I might just have spent too much time with Proteus fiddling about with gates and stuff trying to make a very basic functional computing device, but isn't some sort of computing device needed to compute something? Even with Quantum Gates [wikipedia.org], 30 qubits seem like a very insignificant amount of building blocks to compute anything..
Lastly, how would/will qubits be used to revolutionize storage? I get the allure of storing bits on a subatomic level but if the whole hype is about storage density, it sort of kills the magic for me.
Re:Qubit does not double power in traditional sens (Score:1, Interesting)
Alright, here's how it works: A quantum computer can efficiently execute algorithms the class BQP, which means "Bounded error, quantum, polynomial time". Since all quantum algorithms are probabilistic, "bounded error" means just that - that you can, basically speaking, run the algorithm as many times as you want to get the error as low as you want. Polynomial time means the time you have to wait increases relatively slowly with respect to the size of the input[1].
What the previous comments seem to be talking about here is either EXPTIME (things that take exponential time, period, like solving chess when the input to the problem is the size of the board), or NP (puzzles where, if someone gives you a potential solution, you can check whether it's right rather quickly). Let's be clear, ahead of all: BQP is not EXPTIME. Whether BQP contains NP is an unsolved question, but so is whether P == NP (that is, whether you can use an ordinary computer to solve puzzles where you can recognize a solution quickly, for any sort of such puzzle).
The short of it is: for some algorithms, like Shor's algorithm (which cracks certain types of public key cryptography), there will be an exponential speedup. Quantum computers can break RSA. However, this does not mean that quantum computers will be of much help in breaking AES[2]. Some public key algorithms may also be resistant to cracking by quantum computers - the Lamport signature definitely is (but can be only used once, or a finite number of times in a tree configuration), while other candidates without this finite-use limit include McEliece [wikipedia.org] and NTRU [wikipedia.org].
[1] Yes, I know about how 1.0001^n is, in practice, efficient, while n^10000 is not, but you'll rarely happen upon such algorithms.
[2] Grover's algorithm means you have to double the number of bits in your key to get the same security given the same power, but I find it very unlikely that we're going to see quantum computers as fast as the quickest deterministic code cracking machines (no quantum Deep Crack yet), so this most likely isn't a threat.
Re:Anglo-Saxon and Jewish Intelligence (Score:2, Interesting)
"Note that Japan is a barren rock without any natural resources. "
It has a huge amount of sea, same as Ancient Athens, same as the Roman Empire, same as Phoenicia and Venice and Great Britain and America, but unlike most of the African nations. (Egypt had its river).
History tells us that it's the sea-abundant civilizations that created the greatest amounts of culture -- contrast Athens to Sparta, Venice to Prussia, America to the Soviet Union -- and yeah Japan to Africa.
One of the reasons is because the sea-bordered nations have *natural* borders, thus they can spend less of their time in border-defense or neighbour-conquests and more of their time in other pursuits.
Barren rocks prosper when they have lots of sea around them. Jungles and savannahs don't. It's geography, not skin-color, that forms national destiny.
As for the IQ difference, you have it backwards: it's an advanced civilization that creates the IQ difference, not the IQ difference that creates the advanced civilization.
Re:no peeking (Score:2, Interesting)
One (*err* more) thing I don't get.. How do they know quantum entanglement even happens? They entangle a pair of particles. Then they measure the state of one, causing the other to collapse into the same state with no regard to distance between the two.
However, as it is impossible to measure the quantum properties of these particles without collapsing them into a non-super state, how do we know that the entanglement wasn't just the two particles gaining the same properties at the moment of entanglement? Obviously, this would result in them having the same properties once measured.
How do we know that this super state exists, when it is impossible to measure? If a piece of equipment paints two balls a random color and puts them in separate boxes aren't the balls, by the same definition, in a super state as we can't know their color until we open the box? And can they be said to be entangled, as once you open the first box and observe that the ball inside is for example red, the other ball will also be red even though it has yet to be "measured"?
This might be a bit of a Captain Obvious statement, but I don't freaggin get it! =(
Re:Not particularly useful against an insurgency (Score:3, Interesting)
How Shor's algorithm works (the problem with QC) (Score:3, Interesting)
In fact, I first studied Shor's algorithm in order to understand why good programmers weren't looking at it, generalizing it, and writing a million more algorithms. I was disappointed to learn that we are not far enough along to describe a universal quantum computer and are still in the mode of building special-purpose machines. Like the early bomb dropping "computers" of WW2, results are still being generated but without a concept of universality.
We don't have the math for universal quantum computation since it is still unknown what they are capable of (what their universe consists of). Until the math arrives, we're stuck with this scatter-shot approach.
Re:no peeking (Score:3, Interesting)
The relevant theory here is Bell's Theorem [wikipedia.org] (or Bell's Inequality.) The principle of entanglement has been shown experimentally using some clever approaches based on probability.
If you measure a specific property of two entangled particles, you are correct in saying that there is no way we could know if the result of the measurement was predetermined. However, experiments were set up in which a large number of pairs of particles were measured. Each measurement recorded one of several possible properties, chosen at random. Sometimes the same property would be measured for both particles, and sometimes different properties would be measured for each particle.
It can be shown mathematically that if the particle properties were predetermined, we would see certain probabilities emerge. In other words, for each pair of measurements, the same result would be found N% of the time. However, if the particle properties are determined at the time of measurement, the math changes, and we expect instead for the results to correlate P% of the time. This latter result is what was observed.
That is just a quick overview of the concept. I suggest reading Brian Greene's "The Fabric of the Cosmos", which provides a great explanation involving Mulder and Scully. (Really!)
I also found a nice, clear explanation of the probabilities involved here [theworld.com].