14 ms·

'Unprecedented' discovery could propel quantum computers to reality

106 points by pairing 14y ago

hexagonal 14y ago
Flagged.
- freehunter 14y ago
  If you're going to take the time to make a comment, how about making a comment worth reading? "Flagged" doesn't mean anything useful.
Difwif 14y ago
We always hear about the ramifications a quantum computer would have if used to crack enterprise level security. Does there exist encryption that would be troublesome even for a quantum computer to crack or are we just SOL if one of these falls into the wrong hands?
- dvdkhlng 14y ago
  Lattice-based cryptography (https://en.wikipedia.org/wiki/Lattice-based_cryptography https://en.wikipedia.org/wiki/Lattice-based_cryptography) is currently believed to be quantum-computer resistant (i.e. requires super-polynomial time to break even on a sufficiently large quantum computer). There are only very few problems were quantum computers achieve an exponential speedup vs. classical computers, factoring being one example.
- caf 14y ago
  I believe that quantum computers only give a square root speedup for bruteforcing symmetric encryption algorithms, so we'd just have to double the key length of those. Asymmetric algorithms based on the hardness of factoring or calculating discrete logarithms are broken, though.
- redwood 14y ago
  Quantum communication is unbreakable right?
- m0nastic 14y ago
  It's a little pricey (I think it's meant as a textbook), but DJB has a book on post-quantum cryptography‡ He also has an intro paper (which is probably more along the lines of what you're looking for)‡ Hash-based cryptography, code-based cryptography, lattice-based cryptography, and multivariate-quadratic-equations cryptography are all methods that should hold up in a post-quantum world. RSA will be screwed though. ‡ http://www.amazon.com/Post-Quantum-Cryptography-Daniel-J-Bernstein/dp/3642100198/ref=sr_1_1?ie=UTF8&qid=1341593867&sr=8-1&keywords=post+quantum+cryptography http://www.amazon.com/Post-Quantum-Cryptography-Daniel-J-Ber... ‡ http://www.pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf http://www.pqcrypto.org/www.springer.com/cda/content/documen...
deleted 14y ago
[deleted]
imrehg 14y ago
I'm nitpicking just a little, but isn't discovery always about something unprecedented? Otherwise it's not that different from the rest of the scientific work people do. As a disclosure, I'm a physicist, having worked on quantum computing during my PhD. I think it's really cool, though long qubit lifetime doesn't take you far, the devil is in the details, for example good (reliable, low noise and tunable) qubit-qubit interaction (how in this case?), and reproducible devices (not at all in this case, every diamond will be different).
- sp332 14y ago
  I think a discovery that improves the storage time of qubits by 6 orders of magnitude is unprecedented. Also, even if this technique has terrible qubit-qubit interaction properties, it would still be useful for storage. You could just read the qubit out, do computation in a different medium, and store the result back.
swombat 14y ago
There's something really awesome and science-fiction-like about the idea that when we finally build super-awesome AIs (like Iain M Banks' "Minds"), who then either destroy us or become our best pals in the whole universe, their brains will be built of diamond.
- dvanduzer 14y ago
  The bar is set pretty low so far. All the diamond has to do is factorize 21.
tux1968 14y ago
"For qubits, they can hold a value of “1” or “0” as well as both values at the same time. Described as superposition,"... Am a bit frustrated reading that same description for years and still having no clue what it really means. Both values at the same time... huh? What is the physical property that is existing in two states at once? And how does that feature translate into speedier computation? Is it so hard to understand that it can't be explained to a layman in a bit more depth? Would appreciate any references since everything i've managed to find is either way too technical, or too vacuous.
- snapdata 14y ago
  In Search of Schrodinger's Cat by John Gribbin (http://www.amazon.com/Search-Schrodingers-Cat-John-Gribbin/dp/0552125555 http://www.amazon.com/Search-Schrodingers-Cat-John-Gribbin/d...) is a good starting point for the layman. Some things like the Higgs Boson are abstruse, but superpositions aren't extremely complex.
  - jahnu 14y ago
    Schrödinger's Kittens and the Search for Reality the follow up book is also excellent
- adrianN 14y ago
  Think of a qbit as a 2D vector. You can express it as a(1,0)+b(0,1), where (1,0) is the "1" state and (0,1) is the "0" state. In quantum mechanics a and b are complex numbers. When you measure the qbit the quantum state by magic collapses to (1,0) with probability a^2 or to (0,1) with probability b^2. The power of quantum computers come from the fact that transformations or your qbits act on the superpositioned state, not the collapsed state. So in principle you operate on all possible classical states of your qbits simultaneously when operating on the superposition. This magic doesn't grant you unlimited powers however, since you need to look at the state to get an answer and there you only measure one definite state. The trick to quantum algorithms is then to make the "right" answer as probable as possible.
  - 14y ago
tete 14y ago
Can someone maybe describe the details of "could propel" and what exactly "reality" mean? I've always been told "when quantum computers become reality you can forget about everything you learned on computer science". For me reality would be that one can use it in production, even if it's a complete niche. In other words is it "we got a step closer" or "we potentially solved our only (major) problem"?
- freehunter 14y ago
  Quantum computers are used in production, as you say in a complete niche. Lockheed Martin bought a quantum computer (and associated research & development) from D-Wave for use in their "most complex computations". [1] There's no further notice of what Lockheed has done with it, but at least there's one quantum computer in private hands designed to do production work. [1] http://www.marketwire.com/press-release/d-wave-systems-sells-its-first-quantum-computing-system-lockheed-martin-corporation-1518805.htm http://www.marketwire.com/press-release/d-wave-systems-sells...
  - riffraff 14y ago
    in my understanding the jury is still out on whether D-Wave actually has a quantum computer or not, e.g. http://www.scottaaronson.com/blog/?p=954 http://www.scottaaronson.com/blog/?p=954
- zaptheimpaler 14y ago
  As far as we know, its definitely just "we got a step closer". The advances that we will need to make about our understanding of quantum systems are probably significant, but quantum computers themselves don't seem that promising as of now for one important reason - we have had a very hard time coming up with algorithms that run faster on quantum computers (asymptotically) compared to classical computers. The only significant ones right now are Shor's algorithm (factoring numbers in log(n)^3 time) and Grover Search (searching through N unsorted values in sqrt(n) time). So it's definitely a niche for now, but with two qualifications: 1. Search is a very important niche, it comes up everywhere and could effectively let us say "fuck it, lets brute force it" in a lot of places where we currently use complex algorithms. 2. The knowledge that we gain while trying to build one will probably be useful somewhere. As for "could propel". There is a set of five criteria (or 7 if you consider networking) called the DiVincenzo criteria that roughly state the properties a system needs to satisfy to be a viable quantum computer. One of these is "long decoherence times compared to gate operation times", which means how long the system of qubits can store quantum information before the noisy environment collapses it to classical information. We compare this to gate operation times because the relative times are what is important. If you have a decoherence time of 2 seconds, but it takes 3 seconds for a CNOT gate to operate, its not very useful. I don't know about the gate operation times of quantum computers based on diamonds. Even so, decoherence times are usually on the order of ms, so a 2 second time is probably a very significant achievement in that criterion. That's also been one of the difficult criteria to crack, so that adds to it. Additionally, theres no need to use this medium as the "RAM" or cache of a computer, this could potentially be used as the equivalent of a HDD on a quantum computer.
kokey 14y ago
Apart from the fairly wonderful applications in computing, it will be interesting to see what it does for the enhancement of synthetic diamond technology. I am not going to invest my pension in De Beers, unless they're going large in the synthetic diamond business.
- hessenwolf 14y ago
  I developed the system years ago that De Beers used to track the recipes for all of their synthetic diamonds. Small world.
tete 14y ago
It's always a bit creepy to see this. I mean, if one is really close to this it could mean NSA or DARPA could have the know how and especially the money to already have one. Well it's actually just the money. Money to buy knowhow, researchers, facilities and what else they'd need. It's not only about such things, but if you see how EFF built the DES cracker with donations or a group of security researchers breaks stuff with playstations and then see how much money and power government organizations without any transparency have then it's really creepy. It's also a bit creepy how much power the bosses of such institutions potentially have when compared to something like a president. No wonder there are so many conspiracy theories.
- borlak 14y ago
  have you read Cryptonomicon? :) you might like it
perlgeek 14y ago
Original publication at http://www.sciencemag.org/content/336/6086/1283.full http://www.sciencemag.org/content/336/6086/1283.full (not sure if it's behind a paywall, I can read it but I'm in a University network right now).
vasco 14y ago
If you can store values for a given time frame with such time frame higher than the delay of the circuit, why don't we just build a latch and extend the time frame indefinitely? Or are these diamonds only settable once, and then you have to build another one?
- Sharlin 14y ago
  Because when you read a qubit, you collapse the superposition and end up with a boring old 0 or 1. Which is what you want when the algorithm is completed, but during the execution of the algorithm you want to do operations on the superpositions. So you cannot read the value and feed it back because in the process, you destroy it.
loceng 14y ago
This I believe is how certain aspects of the mind exists, information being temporarily stored and interactive with other systems. Theoretically then systems of the brain/mind should be able to be duplicated. This would allow for managing of large amounts of information, at very high speed, with no-heat generation. The only heat generated would be through the support systems / foundation - I suppose much like how the brain functions as a foundation for the mind. A brain made out of a diamond? Indiana Jones anyone?
- darkstalker 14y ago
  It reminds me of scifi movies where computers are made of crystals
- Bakkot 14y ago
  Not sure if you meant to imply the brain is an inherently quantum system or not, but if so: > Theoretically then systems of the brain/mind should be able to be duplicated. http://en.wikipedia.org/wiki/No-cloning_theorem http://en.wikipedia.org/wiki/No-cloning_theorem It's actually theoretically impossible.
  - loceng 14y ago
    Interesting. I wasn't implying it's a quantum system, not through entanglement anyhow. I'm not sure it would need to be linked in such a way for it to play its role in overall functioning.
rsanchez1 14y ago
Qubits in the Sky with Diamonds If they can achieve two seconds with diamonds, you have to wonder what they will be able to achieve with graphene, another allotrope of carbon. Maybe they will be able to find metamaterials that can store information in qubits indefinitely. This is indeed an exciting development.

106 points by pairing 14y ago

hexagonal 14y ago

Flagged.

freehunter 14y ago
If you're going to take the time to make a comment, how about making a comment worth reading? "Flagged" doesn't mean anything useful.

Difwif 14y ago

We always hear about the ramifications a quantum computer would have if used to crack enterprise level security. Does there exist encryption that would be troublesome even for a quantum computer to crack or are we just SOL if one of these falls into the wrong hands?

dvdkhlng 14y ago
Lattice-based cryptography (https://en.wikipedia.org/wiki/Lattice-based_cryptography https://en.wikipedia.org/wiki/Lattice-based_cryptography) is currently believed to be quantum-computer resistant (i.e. requires super-polynomial time to break even on a sufficiently large quantum computer). There are only very few problems were quantum computers achieve an exponential speedup vs. classical computers, factoring being one example.
caf 14y ago
I believe that quantum computers only give a square root speedup for bruteforcing symmetric encryption algorithms, so we'd just have to double the key length of those. Asymmetric algorithms based on the hardness of factoring or calculating discrete logarithms are broken, though.
redwood 14y ago
Quantum communication is unbreakable right?
m0nastic 14y ago
It's a little pricey (I think it's meant as a textbook), but DJB has a book on post-quantum cryptography‡ He also has an intro paper (which is probably more along the lines of what you're looking for)‡ Hash-based cryptography, code-based cryptography, lattice-based cryptography, and multivariate-quadratic-equations cryptography are all methods that should hold up in a post-quantum world. RSA will be screwed though. ‡ http://www.amazon.com/Post-Quantum-Cryptography-Daniel-J-Bernstein/dp/3642100198/ref=sr_1_1?ie=UTF8&qid=1341593867&sr=8-1&keywords=post+quantum+cryptography http://www.amazon.com/Post-Quantum-Cryptography-Daniel-J-Ber... ‡ http://www.pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf http://www.pqcrypto.org/www.springer.com/cda/content/documen...

deleted 14y ago

[deleted]

imrehg 14y ago

I'm nitpicking just a little, but isn't discovery always about something unprecedented? Otherwise it's not that different from the rest of the scientific work people do. As a disclosure, I'm a physicist, having worked on quantum computing during my PhD. I think it's really cool, though long qubit lifetime doesn't take you far, the devil is in the details, for example good (reliable, low noise and tunable) qubit-qubit interaction (how in this case?), and reproducible devices (not at all in this case, every diamond will be different).

sp332 14y ago
I think a discovery that improves the storage time of qubits by 6 orders of magnitude is unprecedented. Also, even if this technique has terrible qubit-qubit interaction properties, it would still be useful for storage. You could just read the qubit out, do computation in a different medium, and store the result back.

swombat 14y ago

There's something really awesome and science-fiction-like about the idea that when we finally build super-awesome AIs (like Iain M Banks' "Minds"), who then either destroy us or become our best pals in the whole universe, their brains will be built of diamond.

dvanduzer 14y ago
The bar is set pretty low so far. All the diamond has to do is factorize 21.

tux1968 14y ago

"For qubits, they can hold a value of “1” or “0” as well as both values at the same time. Described as superposition,"... Am a bit frustrated reading that same description for years and still having no clue what it really means. Both values at the same time... huh? What is the physical property that is existing in two states at once? And how does that feature translate into speedier computation? Is it so hard to understand that it can't be explained to a layman in a bit more depth? Would appreciate any references since everything i've managed to find is either way too technical, or too vacuous.

snapdata 14y ago
In Search of Schrodinger's Cat by John Gribbin (http://www.amazon.com/Search-Schrodingers-Cat-John-Gribbin/dp/0552125555 http://www.amazon.com/Search-Schrodingers-Cat-John-Gribbin/d...) is a good starting point for the layman. Some things like the Higgs Boson are abstruse, but superpositions aren't extremely complex.
- jahnu 14y ago
  Schrödinger's Kittens and the Search for Reality the follow up book is also excellent
adrianN 14y ago
Think of a qbit as a 2D vector. You can express it as a(1,0)+b(0,1), where (1,0) is the "1" state and (0,1) is the "0" state. In quantum mechanics a and b are complex numbers. When you measure the qbit the quantum state by magic collapses to (1,0) with probability a^2 or to (0,1) with probability b^2. The power of quantum computers come from the fact that transformations or your qbits act on the superpositioned state, not the collapsed state. So in principle you operate on all possible classical states of your qbits simultaneously when operating on the superposition. This magic doesn't grant you unlimited powers however, since you need to look at the state to get an answer and there you only measure one definite state. The trick to quantum algorithms is then to make the "right" answer as probable as possible.
- 14y ago

tete 14y ago

Can someone maybe describe the details of "could propel" and what exactly "reality" mean? I've always been told "when quantum computers become reality you can forget about everything you learned on computer science". For me reality would be that one can use it in production, even if it's a complete niche. In other words is it "we got a step closer" or "we potentially solved our only (major) problem"?

freehunter 14y ago
Quantum computers are used in production, as you say in a complete niche. Lockheed Martin bought a quantum computer (and associated research & development) from D-Wave for use in their "most complex computations". [1] There's no further notice of what Lockheed has done with it, but at least there's one quantum computer in private hands designed to do production work. [1] http://www.marketwire.com/press-release/d-wave-systems-sells-its-first-quantum-computing-system-lockheed-martin-corporation-1518805.htm http://www.marketwire.com/press-release/d-wave-systems-sells...
- riffraff 14y ago
  in my understanding the jury is still out on whether D-Wave actually has a quantum computer or not, e.g. http://www.scottaaronson.com/blog/?p=954 http://www.scottaaronson.com/blog/?p=954
zaptheimpaler 14y ago
As far as we know, its definitely just "we got a step closer". The advances that we will need to make about our understanding of quantum systems are probably significant, but quantum computers themselves don't seem that promising as of now for one important reason - we have had a very hard time coming up with algorithms that run faster on quantum computers (asymptotically) compared to classical computers. The only significant ones right now are Shor's algorithm (factoring numbers in log(n)^3 time) and Grover Search (searching through N unsorted values in sqrt(n) time). So it's definitely a niche for now, but with two qualifications: 1. Search is a very important niche, it comes up everywhere and could effectively let us say "fuck it, lets brute force it" in a lot of places where we currently use complex algorithms. 2. The knowledge that we gain while trying to build one will probably be useful somewhere. As for "could propel". There is a set of five criteria (or 7 if you consider networking) called the DiVincenzo criteria that roughly state the properties a system needs to satisfy to be a viable quantum computer. One of these is "long decoherence times compared to gate operation times", which means how long the system of qubits can store quantum information before the noisy environment collapses it to classical information. We compare this to gate operation times because the relative times are what is important. If you have a decoherence time of 2 seconds, but it takes 3 seconds for a CNOT gate to operate, its not very useful. I don't know about the gate operation times of quantum computers based on diamonds. Even so, decoherence times are usually on the order of ms, so a 2 second time is probably a very significant achievement in that criterion. That's also been one of the difficult criteria to crack, so that adds to it. Additionally, theres no need to use this medium as the "RAM" or cache of a computer, this could potentially be used as the equivalent of a HDD on a quantum computer.

kokey 14y ago

Apart from the fairly wonderful applications in computing, it will be interesting to see what it does for the enhancement of synthetic diamond technology. I am not going to invest my pension in De Beers, unless they're going large in the synthetic diamond business.

hessenwolf 14y ago
I developed the system years ago that De Beers used to track the recipes for all of their synthetic diamonds. Small world.

tete 14y ago

It's always a bit creepy to see this. I mean, if one is really close to this it could mean NSA or DARPA could have the know how and especially the money to already have one. Well it's actually just the money. Money to buy knowhow, researchers, facilities and what else they'd need. It's not only about such things, but if you see how EFF built the DES cracker with donations or a group of security researchers breaks stuff with playstations and then see how much money and power government organizations without any transparency have then it's really creepy. It's also a bit creepy how much power the bosses of such institutions potentially have when compared to something like a president. No wonder there are so many conspiracy theories.

borlak 14y ago
have you read Cryptonomicon? :) you might like it

perlgeek 14y ago

Original publication at http://www.sciencemag.org/content/336/6086/1283.full http://www.sciencemag.org/content/336/6086/1283.full (not sure if it's behind a paywall, I can read it but I'm in a University network right now).

vasco 14y ago

If you can store values for a given time frame with such time frame higher than the delay of the circuit, why don't we just build a latch and extend the time frame indefinitely? Or are these diamonds only settable once, and then you have to build another one?

Sharlin 14y ago
Because when you read a qubit, you collapse the superposition and end up with a boring old 0 or 1. Which is what you want when the algorithm is completed, but during the execution of the algorithm you want to do operations on the superpositions. So you cannot read the value and feed it back because in the process, you destroy it.

loceng 14y ago

This I believe is how certain aspects of the mind exists, information being temporarily stored and interactive with other systems. Theoretically then systems of the brain/mind should be able to be duplicated. This would allow for managing of large amounts of information, at very high speed, with no-heat generation. The only heat generated would be through the support systems / foundation - I suppose much like how the brain functions as a foundation for the mind. A brain made out of a diamond? Indiana Jones anyone?

darkstalker 14y ago
It reminds me of scifi movies where computers are made of crystals
Bakkot 14y ago
Not sure if you meant to imply the brain is an inherently quantum system or not, but if so: > Theoretically then systems of the brain/mind should be able to be duplicated. http://en.wikipedia.org/wiki/No-cloning_theorem http://en.wikipedia.org/wiki/No-cloning_theorem It's actually theoretically impossible.
- loceng 14y ago
  Interesting. I wasn't implying it's a quantum system, not through entanglement anyhow. I'm not sure it would need to be linked in such a way for it to play its role in overall functioning.

rsanchez1 14y ago

Qubits in the Sky with Diamonds If they can achieve two seconds with diamonds, you have to wonder what they will be able to achieve with graphene, another allotrope of carbon. Maybe they will be able to find metamaterials that can store information in qubits indefinitely. This is indeed an exciting development.