Slashdot Mirror
Experts Hail Quantum Computer Memory Stability Breakthrough
cold fjord writes "The BBC reports, 'A fragile quantum memory state has been held stable at room temperature for a "world record" 39 minutes — overcoming a key barrier to ultrafast computers. 'Qubits' of information encoded in a silicon system persisted for almost 100 times longer than ever before. ... "This opens the possibility of truly long-term storage of quantum information at room temperature," said Prof Thewalt ... unofficially, the previous best for a solid state system was 25 seconds at room temperature, or three minutes under cryogenic conditions. ... What's more, they found they could manipulate the qubits as the temperature of the system rose and fell back towards absolute zero. At cryogenic temperatures, their quantum memory system remained coherent for three hours. "Having such robust, as well as long-lived, qubits could prove very helpful for anyone trying to build a quantum computer," said co-author Stephanie Simmons of Oxford University's department of materials. ... "We've managed to identify a system that seems to have basically no noise." However she cautions there are still many hurdles to overcome before large-scale quantum computations can be performed. ... "This result represents an important step towards realizing quantum devices," said David Awschalom, professor in Spintronics and Quantum Information, at the University of Chicago. "However, a number of intriguing challenges still remain." — Abstract for the paywalled academic paper."
That's probably the most common misconception about quantum computers... They do not solve all NP problems efficiently, only a subset called BQP: "bounded error, quantum, polynomial time". It is believed that this is completely disjoint from the "NP complete" subset.
The second they perfect this, they will be able to try all the keys at once and the right one will be solved instantly. All of our current generation of encryption relies on n-p complete algorithms and will become worthless
There is a lot wrong with this.
First of all, quantum computers cannot as far as we know solve NP-complete problems efficiently. There's no known way for that to happen, and most experts expect they cannot. What they can do, is solve specific classes of problems more efficiently than classical computers. The most obvious example of this is factoring integers, which seems to be very difficult for a classical machine, but which can be done quickly by a quantum computer using Shor's algorithm. http://en.wikipedia.org/wiki/Shor's_algorithm
Second, none of these algorithms are instantaneous or even remotely so, but rather scale wit the size of the input, generally with a polynomial.
Third, while many forms of crypto would be vulnerable, including RSA and elliptic curve cryptography, not all forms of cryptography have known vulnerabilities. This connects with the earlier issue of NP completeness. No form of crypto relies at this point on an NP complete problem. Factoring for example is in NP (which means roughly that one can easily convince someone that one actually has the factorization), but it is likely not NP complete. A problem is NP complete if (roughly speaking) it lives in NP, and if you have access to a black box that solves the problem then you can solve all NP problems. At this point, factoring is strongly suspected not to be NP complete, because that would lead to the collapse of the polynomial hierarchy http://en.wikipedia.org/wiki/Polynomial_hierarchy, which is strongly conjectured to occur.
Quantum computers will likely have real world consequences if we ever get them to work on a large scale, and some of those consequences will be cryptographic. But thinking that they'll somehow blow up all cryptography is just hype. If you want to read a good book, without hype, that does a good job of explaining how quantum computing actually works, I recommend "Quantum Computing Since Democritus" by Scott Aaaronson. The book does assume some slight comfort with linear algebra, a very tiny amount of group theory, and some calculus, but that's it. It is aimed at people in technical fields other than quantum computing to understand what it is about. It is highly readable, and I strongly recommend it.
I am just amazed at the technology that is going into making this new qubit.
First off it is "...built with a highly purified form of silicon" and one qubit requires "... the spins of the 10 billion or so phosphorus ions..."
Now THAT is engineering!
I fail to see how KFC can leverage this technology... unless of course... they can make the elusive "n" down sandmich. O now that is ebil.
I would assume that the NSA is at least a decade ahead of open academia on all problems relevant to them.
More likely, there would suddenly be a huge demand for unbreakable quantum encryption, followed by massive investment in developing quantum computing technologies.
Unless they mean something rather different by 'quantum encryption' than the present usage, it won't be of much use.
If you are particularly paranoid, and operate on the theory that your fiber isn't being tapped, quantum encryption comes in at a price that compares favorably to having trusted guys with guns stand around keeping people away from your fiber. If, however, you don't have the luxury of a continuous run between you and the destination (like, oh, almost everybody), the fact that a third party has access to your photons isn't news, it's how the network networks.
Er, "strongly conjectured to occur" should be "strongly conjectured to *not occur*. Need to proofread more when using preview. Also, as long as I'm replying to myself, note that the set of problems which can be solved easily by a quantum computer is BQP http://en.wikipedia.org/wiki/BQP, but it is likely that for many practical applications, one will want the set of problems where a quantum computer can quickly convince a classical computer that it really has a solution, and this set, ZBQP, is likely much much smaller https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Z#zbqp. Factoring lives in this smaller set because the classical computer can check the quantum computer's work essentially by just multiplying together the factors given by the quantum machine.
I would guess 15-20, more or less, depending on the specific application. The history of the NSA's involvement with the DES encryption algorithm is instructive.
NSA's involvement in the design (of DES)
I would also highlight the last sentence in the section: " Bruce Schneier observed that "It took the academic community two decades to figure out that the NSA 'tweaks' actually improved the security of DES."[12] "
much of left-wing thought is a kind of playing with fire by people who don't even know that fire is hot - George Orwell
I think another chain beat them to it. Isn't there an Arby-Qbit sandwich?
much of left-wing thought is a kind of playing with fire by people who don't even know that fire is hot - George Orwell
Hard to say. Anyone can come up with a new idea, but only the spooks get to see everything they have plus what academia produces. As the biggest employer of mathematicians they have the potential to take a new idea and explore or develop it quickly. But it is also the case that math breakthroughs can hinge on the breakthrough insights of a single gifted (or gifted and dogged) individual. It is also the case that the details of a particular technology matter. If you compare the gross scheme of the Enigma to the US SIGABA systems, they are in many ways comparable. But the SIGABA was a much more secure system than Enigma. The Germans never made a dent in it, and it was good enough to be used for years after WW2.
much of left-wing thought is a kind of playing with fire by people who don't even know that fire is hot - George Orwell
I actually went to a talk by a Prof. Michelle Simmons on this last night, and asked that question. My understanding is that it would just does all the calculations at once, in a massively parallel operation (which obviously isn't efficient). I'm no computer scientist (just a mechanical and mechatronic engineer) and I don't really know anything behind quantum mechanics, but the other thing mentioned in the talk about a quantum computer is that it would have perfect security (her words), because, and now i'm relying on memory, a quantum computer doesn't store data like a classic computer, as it can't be perfectly replicated, so the quantum computer needs to keep the qubits active for as long as possible in the computer (hence the importance of the coherence time, as stated in the article). Because a quantum computer is an adiabatic system, it sends the 'energy' from one place to another. Eavesdropping would mean you reroute that energy, and it doesn't go to its intended place.
A lot of it went over my head, so take this with a spoon of salt, as I could have botched it up, but that's the gist of my understanding, and off-topic info
A couple of decades ago, even discussions on the factorisation of integers would be discouraged by the FBI, and exports of software that did 128-bit encryption and above required an official federal application for an export license.
Vintage computer adverts: http://www.vintageadbrowser.com/computers-and-software-ads
39 minutes.....that's long enough to run Windows between BSODs
We are also testing the boundaries of the physical universe in a completely new realm.
The number of states in a quantum-entangled set of particles goes exponentially with the number of particles. For 10 particles (entangled) it takes 2^10 states for the universe to represent the possible outcomes. For 1,000 entangled particles, the number of states is 2^1000.
The number of particles in the entire universe is only about 2^80.
Managing 1,000 entangled particles would require the universe to keep track of a staggering amount of information. Does the underlying machinery have information-space this big? No one knows.
For the first time, we can measure the boundaries of the physical mechanism that underlies the universe in a completely different realm: information capacity. This is analogous to a program probing the limits of RAM memory by seeing how much it can allocate.
Here's hoping that we don't find a buffer overflow.
It's about 10^80, not 2^80.
I think we'll find that the amount of energy required to hold X entangled particles in coherence will be exponential in X. This would make quantum computing essentially worthless.
If not, wake me when we get to 2048 qubits, for the original Xbox's public key and I have some unfinished business from last decade...
"Screw Sun, cross-platform will never work. Let's move on and steal the Java language." - Visual J++ Product Manager