Quantum computing! Brought to you by Google, Goldman Sachs, the NSA...
December 8, 2015 6:05 PM Subscribe
Google successfully tests the first commercially available quantum computer. Google/NASA's Quantum Computing / AI lab has verified that D-Wave Systems recently announced 1000+ qubit quantum computer works as designed: really, really, really fast. "A 100,000,000x leap in computing power", one of their board members claims. In addition to Google, NASA, and government grants, D-Wave's CEO, the former CTO of Goldman Sachs, also obtained large initial investments from the financial industry. One of their first customers? Los Alamos National Laboratory, "a multidisciplinary research institution engaged in strategic science on behalf of national security." This obviously has huge implications for public key encryption, scientific research... everything, really.
As I read the text of this fpp my eyebrows went higher and higher. And then I said, "Wwwwwhoa."
This is big news. Boy, we'll spend a long time figuring out how big. Holy cow.
posted by town of cats at 6:11 PM on December 8, 2015 [2 favorites]
This is big news. Boy, we'll spend a long time figuring out how big. Holy cow.
posted by town of cats at 6:11 PM on December 8, 2015 [2 favorites]
Is there a link to the actual announcement instead of the 9to5 wrapper?
posted by macrael at 6:12 PM on December 8, 2015
posted by macrael at 6:12 PM on December 8, 2015
Yes, there is! I went with the other link as being more understandable by the layman, but It was linked to in the announcement by the person on their board of directors.
posted by markkraft at 6:16 PM on December 8, 2015 [2 favorites]
posted by markkraft at 6:16 PM on December 8, 2015 [2 favorites]
An aside:
One step closer to the singularity.
I think Zeno might take issue with the idea of taking "steps" toward the Singularity. But whatever, point taken. Not to derail.
posted by wormwood23 at 6:21 PM on December 8, 2015 [8 favorites]
One step closer to the singularity.
I think Zeno might take issue with the idea of taking "steps" toward the Singularity. But whatever, point taken. Not to derail.
posted by wormwood23 at 6:21 PM on December 8, 2015 [8 favorites]
This obviously has huge implications for public key encryption
Bruce Schneier - NSA Plans for a Post-Quantum World [August 2015]:
Practical quantum computation doesn't mean the end of cryptography. There are lesser-known public-key algorithms such as McEliece and lattice-based algorithms that, while less efficient than the ones we use, are currently secure against a quantum computer. And quantum computation only speeds up a brute-force keysearch by a factor of a square root, so any symmetric algorithm can be made secure against a quantum computer by doubling the key length.
He also asserts, however, that "My guess has been that we'll see a practical quantum computer within 30 to 40 years, but not much sooner than that."
This gave me a little chill:
The NSA is worried enough about advances in the technology to start transitioning away from algorithms that are vulnerable to a quantum computer. Does this mean that the agency is close to a working prototype in their own classified labs? Unlikely. Does this mean that they envision practical quantum computers sooner than my 30-to-40-year estimate? Certainly.
posted by ryanshepard at 6:21 PM on December 8, 2015 [11 favorites]
Bruce Schneier - NSA Plans for a Post-Quantum World [August 2015]:
Practical quantum computation doesn't mean the end of cryptography. There are lesser-known public-key algorithms such as McEliece and lattice-based algorithms that, while less efficient than the ones we use, are currently secure against a quantum computer. And quantum computation only speeds up a brute-force keysearch by a factor of a square root, so any symmetric algorithm can be made secure against a quantum computer by doubling the key length.
He also asserts, however, that "My guess has been that we'll see a practical quantum computer within 30 to 40 years, but not much sooner than that."
This gave me a little chill:
The NSA is worried enough about advances in the technology to start transitioning away from algorithms that are vulnerable to a quantum computer. Does this mean that the agency is close to a working prototype in their own classified labs? Unlikely. Does this mean that they envision practical quantum computers sooner than my 30-to-40-year estimate? Certainly.
posted by ryanshepard at 6:21 PM on December 8, 2015 [11 favorites]
Can't wait to play the new nethack on it.
posted by Quonab at 6:22 PM on December 8, 2015 [29 favorites]
posted by Quonab at 6:22 PM on December 8, 2015 [29 favorites]
And yet even this thing can't pull 60 FPS in Fallout 4 on Ultra.
posted by Pope Guilty at 6:23 PM on December 8, 2015 [6 favorites]
posted by Pope Guilty at 6:23 PM on December 8, 2015 [6 favorites]
But seriously though, the dwarvenhomes resound with cheers at the news.
posted by Drexen at 6:24 PM on December 8, 2015 [9 favorites]
posted by Drexen at 6:24 PM on December 8, 2015 [9 favorites]
Please help us English major types for whom this is like dogs trying to understand algebra. Does this at its most basic level simply mean really really really fast computers?
posted by bassomatic at 6:28 PM on December 8, 2015 [5 favorites]
posted by bassomatic at 6:28 PM on December 8, 2015 [5 favorites]
Imagine a Beowulf cluster of these.
posted by furtive at 6:30 PM on December 8, 2015 [52 favorites]
posted by furtive at 6:30 PM on December 8, 2015 [52 favorites]
Spoilers P = NP.
posted by humanfont at 6:35 PM on December 8, 2015 [21 favorites]
posted by humanfont at 6:35 PM on December 8, 2015 [21 favorites]
Unless it's something newly disclosed today, D-Wave's computer doesn't run Shor's Algorithm, the one that would effectively break RSA encryption.
posted by the antecedent of that pronoun at 6:36 PM on December 8, 2015 [15 favorites]
posted by the antecedent of that pronoun at 6:36 PM on December 8, 2015 [15 favorites]
Please help us English major types for whom this is like dogs trying to understand algebra. Does this at its most basic level simply mean really really really fast computers?
Basically, as I understand it, the idea with quantum computing is to take advantage of quantum superposition to perform multiple calculations simultaneously instead of sequentially. So for certain operations, yes, much faster (apparently, a square root faster).
posted by dis_integration at 6:36 PM on December 8, 2015 [3 favorites]
Basically, as I understand it, the idea with quantum computing is to take advantage of quantum superposition to perform multiple calculations simultaneously instead of sequentially. So for certain operations, yes, much faster (apparently, a square root faster).
posted by dis_integration at 6:36 PM on December 8, 2015 [3 favorites]
Bassomatic, no, speed is not the issue here. The issue is being able to solve different kinds of problems than current computers can address.
posted by rikschell at 6:36 PM on December 8, 2015 [2 favorites]
posted by rikschell at 6:36 PM on December 8, 2015 [2 favorites]
Important note: this isn't a "real" quantum computer. I mean it is a computer that (apparently/hopefully) takes advantage of quantum effects to solve a certain optimization problem, into which a lot of other useful problems can be reduced.
But it can't factor numbers, can't do Grover search, basically can't do any of the things that make quantum computation so crazy exciting. (It was never intended to do these things.)
posted by vogon_poet at 6:37 PM on December 8, 2015 [26 favorites]
But it can't factor numbers, can't do Grover search, basically can't do any of the things that make quantum computation so crazy exciting. (It was never intended to do these things.)
posted by vogon_poet at 6:37 PM on December 8, 2015 [26 favorites]
"Does this at its most basic level simply mean really really really fast computers?"
Yes, but more than that.
Quantum computing, as I understand it, can basically use these fluctuating quantum states to, instead of finding an answer, find all possible answers at once, and find the right / best answer among the lot.
This is why public key cryptography will be killed by a sophisticated enough quantum computer. Solutions that would take a normal computer many, many. many years to solve, given many, many iterations, are solved basically just like that.
Likewise, it could have huge impacts on things like scientific research. Remember the "Folding at home" screensaver, which uses numerous private computers running screensavers to try to find ways to fold proteins that could be medically useful for solving all sorts of ailments? Well, what if instead of a massive, iterative brute force attempt to find these solutions, you were just able to run all the calculations at once and pick the best solutions?
That is the potential promise of quantum computing.
posted by markkraft at 6:37 PM on December 8, 2015 [13 favorites]
Yes, but more than that.
Quantum computing, as I understand it, can basically use these fluctuating quantum states to, instead of finding an answer, find all possible answers at once, and find the right / best answer among the lot.
This is why public key cryptography will be killed by a sophisticated enough quantum computer. Solutions that would take a normal computer many, many. many years to solve, given many, many iterations, are solved basically just like that.
Likewise, it could have huge impacts on things like scientific research. Remember the "Folding at home" screensaver, which uses numerous private computers running screensavers to try to find ways to fold proteins that could be medically useful for solving all sorts of ailments? Well, what if instead of a massive, iterative brute force attempt to find these solutions, you were just able to run all the calculations at once and pick the best solutions?
That is the potential promise of quantum computing.
posted by markkraft at 6:37 PM on December 8, 2015 [13 favorites]
Please help us English major types for whom this is like dogs trying to understand algebra. Does this at its most basic level simply mean really really really fast computers?
Less "Fast computers" and more that there's different types of computational/math problems out there. Some are easier than others for traditional computers to work with. There's a lot of research that gets done trying to show that harder problems can be rearranged to actually be easier problems (and vice versa).
Sometimes we want problems to be easy. Things like computer vision (Getting computers to be able to analyze images and figure out what they see) we want to be as easy as possible, because that means we can do more of it.
Sometimes we want problems to be hard. Encryption is the standard "problem we want to be hard", because if it were easy, people could open up encrypted things without knowing the key.
Quantum computers, in theory, have a different set of problems they're good at and problems they're bad at. One of the problems they could be good at is encryption. So if Google or other companies are able to get a quantum computer to work effectively, a lot of people have to rethink a lot of assumptions we've made.
posted by CrystalDave at 6:38 PM on December 8, 2015 [8 favorites]
Less "Fast computers" and more that there's different types of computational/math problems out there. Some are easier than others for traditional computers to work with. There's a lot of research that gets done trying to show that harder problems can be rearranged to actually be easier problems (and vice versa).
Sometimes we want problems to be easy. Things like computer vision (Getting computers to be able to analyze images and figure out what they see) we want to be as easy as possible, because that means we can do more of it.
Sometimes we want problems to be hard. Encryption is the standard "problem we want to be hard", because if it were easy, people could open up encrypted things without knowing the key.
Quantum computers, in theory, have a different set of problems they're good at and problems they're bad at. One of the problems they could be good at is encryption. So if Google or other companies are able to get a quantum computer to work effectively, a lot of people have to rethink a lot of assumptions we've made.
posted by CrystalDave at 6:38 PM on December 8, 2015 [8 favorites]
Please help us English major types for whom this is like dogs trying to understand algebra. Does this at its most basic level simply mean really really really fast computers?
It's pretty hard to explain - a quantum computer is fundamentally different from a traditional computer and can solve some problems vastly more efficiently while being fairly useless for others. And as people are finally popping in to say this looks the same as other D-Wave products which is to say it's actually a "quantum annealer," which is interesting but doesn't actually do the really exciting/scary things that a full-on quantum computer would.
posted by atoxyl at 6:40 PM on December 8, 2015 [4 favorites]
It's pretty hard to explain - a quantum computer is fundamentally different from a traditional computer and can solve some problems vastly more efficiently while being fairly useless for others. And as people are finally popping in to say this looks the same as other D-Wave products which is to say it's actually a "quantum annealer," which is interesting but doesn't actually do the really exciting/scary things that a full-on quantum computer would.
posted by atoxyl at 6:40 PM on December 8, 2015 [4 favorites]
For the real nitty gritty, I found this paper via Slashdot.
posted by dis_integration at 6:41 PM on December 8, 2015 [3 favorites]
posted by dis_integration at 6:41 PM on December 8, 2015 [3 favorites]
One of the problems they could be good at is encryption.
Does this mean encryption as in encrypting things? Or decryption? Or both?
posted by nevercalm at 6:43 PM on December 8, 2015
Does this mean encryption as in encrypting things? Or decryption? Or both?
posted by nevercalm at 6:43 PM on December 8, 2015
Quantum computing, as I understand it, can basically use these fluctuating quantum states to, instead of finding an answer, find all possible answers at once, and find the right / best answer among the lot.
This makes it sound like it does nondeterministic computing, and while I have very little understanding of quantum computing I know it doesn't do that. What it does do is offer much faster algorithms for certain problems otherwise considered to be hard - prime factorization being the most famous.
posted by atoxyl at 6:44 PM on December 8, 2015 [3 favorites]
This makes it sound like it does nondeterministic computing, and while I have very little understanding of quantum computing I know it doesn't do that. What it does do is offer much faster algorithms for certain problems otherwise considered to be hard - prime factorization being the most famous.
posted by atoxyl at 6:44 PM on December 8, 2015 [3 favorites]
Please help us English major types for whom this is like dogs trying to understand algebra. Does this at its most basic level simply mean really really really fast computers?
So, here's my best swing at this: Let's say you're looking through an old-timey card catalog at a library. You know what the call number is for the book you're looking for, but you don't know the title. (Let's forget for a moment that you could go find the book in the stacks.) In a normal algorithm, on normal hardware, you would have to look through each card in each drawer, and it would take a long time. With a quantum computer, you can kind of say "show me only the right card", and you can get that in the same time it would take to say "show me any card".
That's kind of a big operational leap from the classical example, which is factoring a large composite number (it being difficult to find the prime factors of a really big number is the basis of modern cryptography), but the amount of time wasted and pain-in-the-assfulness are analogous.
So, to be clear, it's not so much about being really fast as it is about having this great new function. Everything else this thing does could be woefully slow, but being able to skip ahead on some big problems means good things for some computing tasks.
(I hope I've been vague and sketchy enough not to crap right in the middle of this analogy.)
posted by wormwood23 at 6:45 PM on December 8, 2015 [2 favorites]
So, here's my best swing at this: Let's say you're looking through an old-timey card catalog at a library. You know what the call number is for the book you're looking for, but you don't know the title. (Let's forget for a moment that you could go find the book in the stacks.) In a normal algorithm, on normal hardware, you would have to look through each card in each drawer, and it would take a long time. With a quantum computer, you can kind of say "show me only the right card", and you can get that in the same time it would take to say "show me any card".
That's kind of a big operational leap from the classical example, which is factoring a large composite number (it being difficult to find the prime factors of a really big number is the basis of modern cryptography), but the amount of time wasted and pain-in-the-assfulness are analogous.
So, to be clear, it's not so much about being really fast as it is about having this great new function. Everything else this thing does could be woefully slow, but being able to skip ahead on some big problems means good things for some computing tasks.
(I hope I've been vague and sketchy enough not to crap right in the middle of this analogy.)
posted by wormwood23 at 6:45 PM on December 8, 2015 [2 favorites]
Quantum computing, as I understand it, can basically use these fluctuating quantum states to, instead of finding an answer, find all possible answers at once, and find the right / best answer among the lot.
I hate to be pedantic but this isn't right. It's true that you have all possible answers among the fluctuating quantum states, but at the end you don't get to pick the best one, you get given one randomly. Which wouldn't be that useful -- you could get the exact same effect with a normal computer and a random number generator! (So called "Monte Carlo" algorithms are widely used today and actually do take this approach.)
Where the spooky quantum weirdness comes in is that you can kind of juke the odds a little bit by getting possible incorrect answers to sort of cancel each other out, if you're clever and the problem is amenable. That way you can increase the likelihood of getting handed a correct answer at the end -- for some limited problems, you might be guaranteed a correct answer.
posted by vogon_poet at 6:45 PM on December 8, 2015 [18 favorites]
I hate to be pedantic but this isn't right. It's true that you have all possible answers among the fluctuating quantum states, but at the end you don't get to pick the best one, you get given one randomly. Which wouldn't be that useful -- you could get the exact same effect with a normal computer and a random number generator! (So called "Monte Carlo" algorithms are widely used today and actually do take this approach.)
Where the spooky quantum weirdness comes in is that you can kind of juke the odds a little bit by getting possible incorrect answers to sort of cancel each other out, if you're clever and the problem is amenable. That way you can increase the likelihood of getting handed a correct answer at the end -- for some limited problems, you might be guaranteed a correct answer.
posted by vogon_poet at 6:45 PM on December 8, 2015 [18 favorites]
Any normal computer can do encrypting, which is basically like multiplying two large numbers together.
A quantum computer, though, can do decrypting especially well, by being able to look at a big number and rapidly calculate all the possible numbers that could be multiplied together to achieve that large number.
The whole point of public key cryptography is so you can take that large number and find the two numbers multiplied together... the message. Quantum computing can allow you to solve the problem without needing anyone's keys to unlock it, basically.
posted by markkraft at 6:45 PM on December 8, 2015 [1 favorite]
A quantum computer, though, can do decrypting especially well, by being able to look at a big number and rapidly calculate all the possible numbers that could be multiplied together to achieve that large number.
The whole point of public key cryptography is so you can take that large number and find the two numbers multiplied together... the message. Quantum computing can allow you to solve the problem without needing anyone's keys to unlock it, basically.
posted by markkraft at 6:45 PM on December 8, 2015 [1 favorite]
Does this mean encryption as in encrypting things? Or decryption? Or both?
Both really in different ways - it breaks some important forms of encryption but also offers some new approaches I believe to those who *have* a quantum computer - hopefully somebody else can explain this because I don't have the time right now.
posted by atoxyl at 6:46 PM on December 8, 2015
Both really in different ways - it breaks some important forms of encryption but also offers some new approaches I believe to those who *have* a quantum computer - hopefully somebody else can explain this because I don't have the time right now.
posted by atoxyl at 6:46 PM on December 8, 2015
1) How many qbits?
2) This may be why the NSA specifically abandoned Elliptical Curve cryptography and public key systems as a class.
posted by eriko at 6:47 PM on December 8, 2015 [1 favorite]
2) This may be why the NSA specifically abandoned Elliptical Curve cryptography and public key systems as a class.
posted by eriko at 6:47 PM on December 8, 2015 [1 favorite]
OK, so how long does my diceware password need to be now?
posted by ChurchHatesTucker at 6:49 PM on December 8, 2015
posted by ChurchHatesTucker at 6:49 PM on December 8, 2015
can't do Grover search
But isn't he at the end of this book?
posted by Faint of Butt at 6:52 PM on December 8, 2015 [61 favorites]
But isn't he at the end of this book?
posted by Faint of Butt at 6:52 PM on December 8, 2015 [61 favorites]
"Both really in different ways"
Yes. The properties of quantum computing could allow you to securely send messages between those who have access to quantum computers... but for all practical purposes, that is unlikely to mean any of us, any time soon.
It could actually be far more problematic for the average person than not... though complete, guaranteed anonymity has its risks too.
posted by markkraft at 6:54 PM on December 8, 2015
Yes. The properties of quantum computing could allow you to securely send messages between those who have access to quantum computers... but for all practical purposes, that is unlikely to mean any of us, any time soon.
It could actually be far more problematic for the average person than not... though complete, guaranteed anonymity has its risks too.
posted by markkraft at 6:54 PM on December 8, 2015
But can you play Witcher 3 on the highest video settings on it?
posted by Fizz at 6:55 PM on December 8, 2015
posted by Fizz at 6:55 PM on December 8, 2015
And I bet Chrome still runs like garbage on it when more than two tabs (and/or Flash) are open.
posted by pipian at 6:56 PM on December 8, 2015 [2 favorites]
posted by pipian at 6:56 PM on December 8, 2015 [2 favorites]
So why is the financial industry interested in this? To explore all possible universes where they can front-run the market even faster?
posted by JoeZydeco at 6:57 PM on December 8, 2015 [1 favorite]
posted by JoeZydeco at 6:57 PM on December 8, 2015 [1 favorite]
The properties of quantum computing could allow you to securely send messages between those who have access to quantum computers...
Perhaps you're thinking of quantum key distribution?
posted by escape from the potato planet at 6:58 PM on December 8, 2015
Perhaps you're thinking of quantum key distribution?
posted by escape from the potato planet at 6:58 PM on December 8, 2015
This is quantum annealing, and to my knowledge doesn't make breaking crypto any easier, or particularly closer. It's a lot of qubits but they're not arranged in such a way to perform factoring algorithms.
posted by BungaDunga at 6:59 PM on December 8, 2015 [2 favorites]
posted by BungaDunga at 6:59 PM on December 8, 2015 [2 favorites]
Sorry, markkraft—I just saw your earlier messages upthread and realized that, yes, you're probably already familiar with it :)
posted by escape from the potato planet at 7:00 PM on December 8, 2015
posted by escape from the potato planet at 7:00 PM on December 8, 2015
Not a cryptographer nor even a well-informed layman, but this is my understanding of quantum computing's effects on encryption: it will halve effective key-size for symmetric algorithms (AES, 3DES, etc, the single secret key type) and completely break some/most/all(?) of our current asymmetric algorithms (the public key + private key type, such as RSA).
Right now, with "normal" computing, AES with a 128 bit key is impossible to brute-force (try all possible keys until you find the right one and decrypt the ciphertext) and will remain so forever; with quantum computing, that 128 becomes equivalent to 64 with normal computing and thus potentially brute-forceable with large effort, while AES-256 effectively becomes the same as AES-128, ie, forever safe, quantum computers or not.
Note that according to better informed posters than me, this isn't an actual quantum computer yet, so none of what I wrote above applies to this announcement.
OK, so how long does my diceware password need to be now?
Assuming it's at least 80 bits already, exactly the same. Crypto is bypassed, not defeated.
posted by Bangaioh at 7:03 PM on December 8, 2015 [2 favorites]
Right now, with "normal" computing, AES with a 128 bit key is impossible to brute-force (try all possible keys until you find the right one and decrypt the ciphertext) and will remain so forever; with quantum computing, that 128 becomes equivalent to 64 with normal computing and thus potentially brute-forceable with large effort, while AES-256 effectively becomes the same as AES-128, ie, forever safe, quantum computers or not.
Note that according to better informed posters than me, this isn't an actual quantum computer yet, so none of what I wrote above applies to this announcement.
OK, so how long does my diceware password need to be now?
Assuming it's at least 80 bits already, exactly the same. Crypto is bypassed, not defeated.
posted by Bangaioh at 7:03 PM on December 8, 2015 [2 favorites]
Your high end games system / graphics card is best at spitting out brute force calculations needed for all the cool graphics.
Quantum computers are designed for taking a look at complex problems with a lot of potential answers, and finding the right answer in a way that's much quicker than, say:
posted by markkraft at 7:03 PM on December 8, 2015
Quantum computers are designed for taking a look at complex problems with a lot of potential answers, and finding the right answer in a way that's much quicker than, say:
10 IF I =ANSWER print "I've solved the problem!"
20 LET I = I+1
30 GOTO 10posted by markkraft at 7:03 PM on December 8, 2015
it can't be that much bigger of a mindfuck to program than Haskell
posted by indubitable at 7:10 PM on December 8, 2015 [10 favorites]
posted by indubitable at 7:10 PM on December 8, 2015 [10 favorites]
It's also mostly an engineering problem. We already have lots of interesting quantum algorithms, but we don't actually have very powerful quantum computers, because it relies on entanglement and entanglement is fragile and hard to manipulate. Shor's algorithm is 20 years old but the largest number it has factored in practice is 21, because building quantum computers is hard.
posted by BungaDunga at 7:11 PM on December 8, 2015 [4 favorites]
posted by BungaDunga at 7:11 PM on December 8, 2015 [4 favorites]
Does it come with a jungle soundtrack by Clint Mansell ?
posted by lmfsilva at 7:12 PM on December 8, 2015 [4 favorites]
posted by lmfsilva at 7:12 PM on December 8, 2015 [4 favorites]
in related news: Spy Agency Bets on IBM for Universal Quantum Computing
posted by p3on at 7:13 PM on December 8, 2015
posted by p3on at 7:13 PM on December 8, 2015
How would one program a quantum problem solver?
Like, how would instructions be given to the computer, and how would answers be given out?
posted by alex_skazat at 7:14 PM on December 8, 2015
Like, how would instructions be given to the computer, and how would answers be given out?
posted by alex_skazat at 7:14 PM on December 8, 2015
As I read the text of this fpp my eyebrows went higher and higher.
as i read the text of this fpp my eyebrows went higher and lower simultaneously.
posted by quonsar II: smock fishpants and the temple of foon at 7:18 PM on December 8, 2015 [24 favorites]
as i read the text of this fpp my eyebrows went higher and lower simultaneously.
posted by quonsar II: smock fishpants and the temple of foon at 7:18 PM on December 8, 2015 [24 favorites]
Shor's algorithm is 20 years old but the largest number it has factored in practice is 21, because building quantum computers is hard.
Which is a 40% improvement over the previous record!
posted by vogon_poet at 7:18 PM on December 8, 2015
Which is a 40% improvement over the previous record!
posted by vogon_poet at 7:18 PM on December 8, 2015
alex_skazat:
http://cstheory.stackexchange.com/questions/9381/what-would-a-very-simple-quantum-program-look-like
posted by nickggully at 7:19 PM on December 8, 2015 [5 favorites]
http://cstheory.stackexchange.com/questions/9381/what-would-a-very-simple-quantum-program-look-like
posted by nickggully at 7:19 PM on December 8, 2015 [5 favorites]
My analogy is cars vs. airplanes, with airplanes being quantum computing. Sure, comparing raw miles-per-hour speed is an easy numeric comparison, but airplanes are pretty useless if there's no airport or runway. Similarly, quantum computers can't run normal programs/games, so the joke about current-day programs still running slow on them misses the point.
If your diceware password is being plugged into a security system based on factorization, then it doesn't matter how long your password is, a machine that is capable of running Shor's Algorithm means that security system is now broken. DWave's system cannot run Shor's algorithm, however.
The sky isn't (publicly) falling, however. In terms of the airplane analogy though, this isn't the Wright Brother's first flight either (DWave's been around since 1999). Digital computers will still be around for the foreseeable future, and the 100 million leap in computing speed is PR more than anything (it's probably more like a 100,000 speed up). 56,153 is the largest number quantum computers have been able to factor, and that's just a 16-bit number. Most systems have a key length of several thousand bits.
posted by fragmede at 7:19 PM on December 8, 2015 [1 favorite]
If your diceware password is being plugged into a security system based on factorization, then it doesn't matter how long your password is, a machine that is capable of running Shor's Algorithm means that security system is now broken. DWave's system cannot run Shor's algorithm, however.
The sky isn't (publicly) falling, however. In terms of the airplane analogy though, this isn't the Wright Brother's first flight either (DWave's been around since 1999). Digital computers will still be around for the foreseeable future, and the 100 million leap in computing speed is PR more than anything (it's probably more like a 100,000 speed up). 56,153 is the largest number quantum computers have been able to factor, and that's just a 16-bit number. Most systems have a key length of several thousand bits.
posted by fragmede at 7:19 PM on December 8, 2015 [1 favorite]
The big threat though isn't that it's a fast computer. It's all the potential problems people entities might choose to solve with it, at the public expense.
It could mean breaking your security... or finding ways for financial institutions to make money / manipuate markets in ways that hurt people, and disadvantage those who don't have similar access. Or simply give companies even more power to control others.
It could bring new answers and new solutions, certainly... but the question is whether those solutions are designed for the benefit of all the rest of us.
posted by markkraft at 7:20 PM on December 8, 2015 [1 favorite]
It could mean breaking your security... or finding ways for financial institutions to make money / manipuate markets in ways that hurt people, and disadvantage those who don't have similar access. Or simply give companies even more power to control others.
It could bring new answers and new solutions, certainly... but the question is whether those solutions are designed for the benefit of all the rest of us.
posted by markkraft at 7:20 PM on December 8, 2015 [1 favorite]
it can't be that much bigger of a mindfuck to program than Haskell
I have some good news for you!
posted by vogon_poet at 7:21 PM on December 8, 2015 [3 favorites]
I have some good news for you!
posted by vogon_poet at 7:21 PM on December 8, 2015 [3 favorites]
Probably also useful for people trying to understand this is the Simulated Annealing page on wikipedia. The algorithm being implemented in the D-Wave computer is "Quantum Annealing" -- a quantum-ized version of same.
posted by wormwood23 at 7:21 PM on December 8, 2015 [3 favorites]
posted by wormwood23 at 7:21 PM on December 8, 2015 [3 favorites]
Huh, I had not heard that143 and 56153 had been factored.
I don't know what to make of the idea that it was "undiscovered" that the computer factored some other larger number in the same operation. I mean, if you write a program to print digits of pi and later discovered that it had also printed e, I'm not sure that really counts.
posted by the antecedent of that pronoun at 7:23 PM on December 8, 2015 [4 favorites]
In April 2012, the factorization of 143 was achieved, although this used adiabatic quantum computation rather than Shor's algorithm.[9] It was discovered in November 2014 that this adiabatic quantum computation in 2012 had in fact also factored larger numbers, the largest being 56153, which is currently the record for the largest integer factored on a quantum device.[10][11] (wikipedia)Most people have been repeating the earlier factorization of 21 as the best result for Shor's.
I don't know what to make of the idea that it was "undiscovered" that the computer factored some other larger number in the same operation. I mean, if you write a program to print digits of pi and later discovered that it had also printed e, I'm not sure that really counts.
posted by the antecedent of that pronoun at 7:23 PM on December 8, 2015 [4 favorites]
I bet you still gotta flip the USB stick around like five times before it fits in though. Wake me up when they got quantum USB sticks that change their state to fit the jack.
posted by turbid dahlia at 7:46 PM on December 8, 2015 [9 favorites]
posted by turbid dahlia at 7:46 PM on December 8, 2015 [9 favorites]
This is an extremely pedantic response to something that was a joke but as always I will say - neither the existence of a quantum computer *nor* of an honest-to-God nondeterministic computer in a black box would in itself demonstrate P = NP.
posted by atoxyl at 7:52 PM on December 8, 2015 [4 favorites]
posted by atoxyl at 7:52 PM on December 8, 2015 [4 favorites]
indubitable: it can't be that much bigger of a mindfuck to program than Haskell
I've got bad news for you.
(It's an experimental programming language for quantum computation based on Haskell plus extensions. It can be compiled to run on ordinary machines right now for experimental purposes, and theoretically, could be compiled into two parts: machine code for a normal computer and a quantum circuit for a "quantum coprocessor", both working together to run the program. It's hard to read.)
posted by traveler_ at 7:55 PM on December 8, 2015 [2 favorites]
I've got bad news for you.
(It's an experimental programming language for quantum computation based on Haskell plus extensions. It can be compiled to run on ordinary machines right now for experimental purposes, and theoretically, could be compiled into two parts: machine code for a normal computer and a quantum circuit for a "quantum coprocessor", both working together to run the program. It's hard to read.)
posted by traveler_ at 7:55 PM on December 8, 2015 [2 favorites]
I think the ability to solve new types problems is probably very exciting and good.
posted by I Foody at 7:59 PM on December 8, 2015
posted by I Foody at 7:59 PM on December 8, 2015
Wake me up when they got quantum USB sticks that change their state to fit the jack.
Good news!
posted by CrystalDave at 8:00 PM on December 8, 2015
Good news!
posted by CrystalDave at 8:00 PM on December 8, 2015
Spoiler alert: 42
posted by dances_with_sneetches at 8:01 PM on December 8, 2015 [8 favorites]
posted by dances_with_sneetches at 8:01 PM on December 8, 2015 [8 favorites]
> Bassomatic, no, speed is not the issue here. The issue is being able to solve different kinds of problems than current computers can address.
It's unfortunately that this untrue statement is right at the top...
These new machines solve exactly the same problems as current computers - indeed, all current computer (and perhaps any possible computers) solve exactly the same set of problems, see here. It is just that these new machines solve some specific problems much faster than conventional computation devices.
posted by lupus_yonderboy at 8:15 PM on December 8, 2015 [3 favorites]
It's unfortunately that this untrue statement is right at the top...
These new machines solve exactly the same problems as current computers - indeed, all current computer (and perhaps any possible computers) solve exactly the same set of problems, see here. It is just that these new machines solve some specific problems much faster than conventional computation devices.
posted by lupus_yonderboy at 8:15 PM on December 8, 2015 [3 favorites]
indubitable: it can't be that much bigger of a mindfuck to program than Haskell
vogon_poet: I have some good news for you!
traveler_: I've got bad news for you.
That's news to me.
posted by biogeo at 8:25 PM on December 8, 2015
vogon_poet: I have some good news for you!
traveler_: I've got bad news for you.
That's news to me.
posted by biogeo at 8:25 PM on December 8, 2015
These new machines solve exactly the same problems as current computers - indeed, all current computer (and perhaps any possible computers) solve exactly the same set of problems, see here. It is just that these new machines solve some specific problems much faster than conventional computation devices.
This is of course true but rather pedantic (join the club) since the interesting part is the application to problems that are currently *practically* intractable.
posted by atoxyl at 8:27 PM on December 8, 2015 [5 favorites]
This is of course true but rather pedantic (join the club) since the interesting part is the application to problems that are currently *practically* intractable.
posted by atoxyl at 8:27 PM on December 8, 2015 [5 favorites]
Clearly the news is in a superposition of "good" and "bad" states. You have to write Hello World in Quipper to collapse the wavefunction and find out for yourself.
posted by traveler_ at 8:29 PM on December 8, 2015 [10 favorites]
posted by traveler_ at 8:29 PM on December 8, 2015 [10 favorites]
It's actually kind of bittersweet, as this is an absolute limit. They will never go faster.
posted by Chitownfats at 8:31 PM on December 8, 2015
posted by Chitownfats at 8:31 PM on December 8, 2015
The way I hear people describe quantum computers makes it sound like the equivalent of a massively parallel computer.
I get how parallel vs. iterative computing works, as a computer science student (ie, parallel is great for brute forcing hashes or working with lots of data, but also introduces potential race conditions). So assume I know that. How is it different from parallel computing, other than it's really hard to build, weird to program, and unearthly fast at stuff like factoring?
posted by mccarty.tim at 8:32 PM on December 8, 2015
I get how parallel vs. iterative computing works, as a computer science student (ie, parallel is great for brute forcing hashes or working with lots of data, but also introduces potential race conditions). So assume I know that. How is it different from parallel computing, other than it's really hard to build, weird to program, and unearthly fast at stuff like factoring?
posted by mccarty.tim at 8:32 PM on December 8, 2015
I don't want to be misleading; 56,153 wasn't factored using Shor's algorithm but it was factored using a quantum computer. (Phys.org)
posted by fragmede at 8:36 PM on December 8, 2015
posted by fragmede at 8:36 PM on December 8, 2015
It's actually kind of bittersweet, as this is an absolute limit. They will never go faster.
posted by Chitownfats
640 Qbits should be enough for anyone
posted by DoctorFedora at 8:38 PM on December 8, 2015 [14 favorites]
posted by Chitownfats
640 Qbits should be enough for anyone
posted by DoctorFedora at 8:38 PM on December 8, 2015 [14 favorites]
How is it different from parallel computing, other than it's really hard to build, weird to program, and unearthly fast at stuff like factoring?
Can I ask if you find this explanation helpful above? I'm seriously asking because I would like to refine my ability to explain this to people, especially with my limited knowledge.
posted by vogon_poet at 8:40 PM on December 8, 2015
Can I ask if you find this explanation helpful above? I'm seriously asking because I would like to refine my ability to explain this to people, especially with my limited knowledge.
posted by vogon_poet at 8:40 PM on December 8, 2015
i think this is basically equivalent to verifying that Nvidia's latest absurdly expensive GPU actually hits the specially tuned Nvidia benchmarks on the side of the box... which is at least something.
posted by ennui.bz at 8:47 PM on December 8, 2015 [1 favorite]
posted by ennui.bz at 8:47 PM on December 8, 2015 [1 favorite]
It's actually kind of bittersweet, as this is an absolute limit. They will never go faster.
unearthly fast at stuff like factoring
The dwave is not a true general purpose quantum computer and is not capable of factoring faster than conventional computers. It is a special purpose device that can allegedly solve a very narrow class of optimization problems, a class that does not include prime factorization, faster than conventional computers.
Previously it was disputed whether the dwave was even using quantum effects at all, and this rather thin press release is not especially convincing. Independent confirmation from parties who aren't investors in this venture would be welcome.
posted by Pyry at 8:49 PM on December 8, 2015 [11 favorites]
unearthly fast at stuff like factoring
The dwave is not a true general purpose quantum computer and is not capable of factoring faster than conventional computers. It is a special purpose device that can allegedly solve a very narrow class of optimization problems, a class that does not include prime factorization, faster than conventional computers.
Previously it was disputed whether the dwave was even using quantum effects at all, and this rather thin press release is not especially convincing. Independent confirmation from parties who aren't investors in this venture would be welcome.
posted by Pyry at 8:49 PM on December 8, 2015 [11 favorites]
This is not as interesting as it looks.
posted by Coventry at 9:08 PM on December 8, 2015 [4 favorites]
The design of next generation annealers must facilitate the embedding of problems of practical relevance. For instance, we would like to increase the density and control precision of the connections between the qubits as well as their coherence.It's basically a really, really positive way of admitting defeat. They haven't been able to get the "qubits" to cohere in the way assumed by Shor's algorithm. They've basically shown that D-WAVE is a physical system which their simulation software can simulate 108 times slower than reality on a single-core machine.
posted by Coventry at 9:08 PM on December 8, 2015 [4 favorites]
My totally non-expert understanding is that attempting to compare quantum computing to iterative vs. parallel computing is kind of approaching the question at the wrong level, in that both of those are just different ways of structuring digital algorithms, whereas the quantum vs. digital computing division is more fundamental. The most familiar comparison I can latch onto (and admittedly it's probably not that familiar to most of us) is digital vs. analog computing. Digital computing, whether iterative or parallel, is ultimately about how you convert a problem into something solvable by logic gates. Analog computing is ultimately about how you convert a problem into something solvable by analog circuit elements (e.g., calculating the derivative of a function by representing it as a time-varying voltage and using a high-pass filter). You can actually solve certain kinds of problems very efficiently using analog computation, but it's much easier to write software and do general-purpose computing with digital computers, so we don't see analog computers that much.
So the difference between quantum and digital computing is more like the difference between digital and analog computing; it's about converting a problem into something solvable by a quantum system, rather than by logic gates. But where the class of problems for which analog computers are sufficiently better than digital computers to be worth the trouble seems to be relatively limited*, the physics of quantum entanglement allows for certain kinds of problems, like prime number factorization, which are difficult to solve efficiently with logic gates, to be solved very efficiently and easily. So it's not about iterative vs. parallel per se, but rather the nature of the physical unit performing the computation.
* But some computational neuroscientists, myself included, would argue that the brain can be understood as a complex analog, not digital, computing system, and the fact that humans almost effortlessly solve problems that our most powerful digital supercomputers still cannot may well be related to that fact. I have marginally more confidence in this statement than I do in my hand-wavy understanding of quantum computing.
posted by biogeo at 9:09 PM on December 8, 2015 [5 favorites]
So the difference between quantum and digital computing is more like the difference between digital and analog computing; it's about converting a problem into something solvable by a quantum system, rather than by logic gates. But where the class of problems for which analog computers are sufficiently better than digital computers to be worth the trouble seems to be relatively limited*, the physics of quantum entanglement allows for certain kinds of problems, like prime number factorization, which are difficult to solve efficiently with logic gates, to be solved very efficiently and easily. So it's not about iterative vs. parallel per se, but rather the nature of the physical unit performing the computation.
* But some computational neuroscientists, myself included, would argue that the brain can be understood as a complex analog, not digital, computing system, and the fact that humans almost effortlessly solve problems that our most powerful digital supercomputers still cannot may well be related to that fact. I have marginally more confidence in this statement than I do in my hand-wavy understanding of quantum computing.
posted by biogeo at 9:09 PM on December 8, 2015 [5 favorites]
I agree that based just on this report, I would not be totally convinced that this was quantum computing rather than a mildly-quick piece of hardware specialized for (non-simulated) annealing. Showing that you're faster than simulated annealing (even by 10^8) is itself not necessarily revolutionary, since as I understand it, simulated annealing is a relatively slow machine learning algorithm these days. (I'm no computer scientist, but I know you would be laughed at these days if you introduced an new ML algorithm that you trumpeted as "faster than simulated annealing!") It's possible they're doing the annealing/optimization faster than a purpose-built piece of silicon could do it, but until they do the impossible, there's always this doubt that it's either not quantum, or quantum in some way that is not impossible to achieve classically. (Though my hope remains that it is indeed quantum, albeit not a full quantum computer.)
posted by chortly at 9:20 PM on December 8, 2015 [1 favorite]
posted by chortly at 9:20 PM on December 8, 2015 [1 favorite]
If the CTO of Goldman Sachs says so, surely this needs no "academic" external judge to verify the claims.
posted by benzenedream at 10:12 PM on December 8, 2015 [1 favorite]
posted by benzenedream at 10:12 PM on December 8, 2015 [1 favorite]
Hate to discover it so late, but Google released a rather complicated paper on this today, that the experts among you can pick over and hopefully find something noteworthy to share.
posted by markkraft at 10:39 PM on December 8, 2015 [1 favorite]
posted by markkraft at 10:39 PM on December 8, 2015 [1 favorite]
vogon_poet, your explanation is actually pretty great! I didn't see it before writing my post, I'm embarrassed to say. The parts I don't get probably boil down to quantum behavior making little sense in the first place. So I guess the idea is for problems where the best solution might take lots of random inputs to get a useful result, quantum computing can hone in on the more "interesting" or "useful" inputs. I infer that would mean at the high level, someone engineering a quantum computing solution would program the algorithm, designed along with what they think the output should be. (so for folded@home, a specific shape of protein, or for PGP cracking, a public key) And somehow, quantum computing means that instead of just brute forcing with random input numbers, quantum weirdness can find "good numbers" or at least rule out enough bad numbers to improve the probability.
biogeo, the analogy between analog and digital computing makes a lot of sense, too. Especially in the context of Quipper "compiling to quantum circuits."
posted by mccarty.tim at 11:12 PM on December 8, 2015
biogeo, the analogy between analog and digital computing makes a lot of sense, too. Especially in the context of Quipper "compiling to quantum circuits."
posted by mccarty.tim at 11:12 PM on December 8, 2015
TLDR: Still not faster than classical methods; the next one might be.
From the paper:
From the paper:
Based on the results presented here, one cannot claimposted by ethansr at 11:17 PM on December 8, 2015 [4 favorites]
a quantum speedup for D-Wave 2X, as this would require
that the quantum processor in question outperforms the
best known classical algorithm. This is not the case for
the weak-strong cluster networks. This is because a variety
of heuristic classical algorithms can solve most instances
of Chimera structured problems much faster than
SA, QMC, and the D-Wave 2X [...]
However, we believe that such solvers will become
ineffective for the next generation of annealers currently
being designed. The primary motivation for this optimism
is that the connectivity graphs of future annealers
will have higher degree. For example, we believe that
a 10-dimensional cubic lattice is an engineerable
architecture.
Here's an explanation of the famous quantum algorithm (Shor's) for factorization, by Scott Aaronson - yes, the same guy who has recently and sadly made himself known for some embarrassing opinions on feminism but this is his field of legitimate expertise.
posted by atoxyl at 11:30 PM on December 8, 2015 [1 favorite]
posted by atoxyl at 11:30 PM on December 8, 2015 [1 favorite]
As somebody with, let's say, an intermediate amount of mathematical knowledge looking up Shor's algorithm at first I was like "what the hell are they doing to my Fourier transforms?" But then I saw "period finding" so I'm just thinking of "quantum Fourier transforms" as the same thing but quantum which actually kind of makes sense.
posted by atoxyl at 11:56 PM on December 8, 2015
posted by atoxyl at 11:56 PM on December 8, 2015
My potentially out-to-lunch metaphor is of an uneven floor. A traditional computer finds the low spot by mapping it with height measurements and picking the smallest value. A quantum computer sloshes a bucket of water over it and picks the puddle.
I think part of our brain works by leveraging quantum interaction.
posted by five fresh fish at 12:39 AM on December 9, 2015 [1 favorite]
I think part of our brain works by leveraging quantum interaction.
posted by five fresh fish at 12:39 AM on December 9, 2015 [1 favorite]
Scott Aaronson is also known as the Chief D-Wave Skeptic, so he'll likely have something to say about this soon. It's important to note that D-Wave has made similarly incredible claims before, but people have managed to close the quantum-to-classical-simulated annealing gap. That is, while it was certainly good research, it was a little premature to claim a speedup.
So at least until someone has taken a good look at the paper, it's better to take the press release with a grain of salt.
posted by maskd at 12:58 AM on December 9, 2015 [2 favorites]
So at least until someone has taken a good look at the paper, it's better to take the press release with a grain of salt.
posted by maskd at 12:58 AM on December 9, 2015 [2 favorites]
Ok, so how about this? If a 'traditional' computer is like riding a (or even several, simultaneously) bicycle down the street, quantum computing is like riding a T-Rex that is still in a state of temporal flux because your time machine is one of the cheap ones and so one the one hand you're riding a T-Rex! And on the other you're just running down the street in your tighty-whities shouting, 'woo hoo! Check out me riding a fucking T-Rex you losers!'
I might have this pretty fundamentally wrong but I felt compelled to try and be helpful.
Interesting links, though the opacity to a layman is mildly disconcerting - like that Steve Martin joke about Findlay sprinkler...
posted by From Bklyn at 1:28 AM on December 9, 2015 [3 favorites]
I might have this pretty fundamentally wrong but I felt compelled to try and be helpful.
Interesting links, though the opacity to a layman is mildly disconcerting - like that Steve Martin joke about Findlay sprinkler...
posted by From Bklyn at 1:28 AM on December 9, 2015 [3 favorites]
JoeZydeco: "So why is the financial industry interested in this? To explore all possible universes where they can front-run the market even faster?"
Think how fast it will serve ALL the AdWords
posted by chavenet at 1:43 AM on December 9, 2015 [1 favorite]
Think how fast it will serve ALL the AdWords
posted by chavenet at 1:43 AM on December 9, 2015 [1 favorite]
What makes learning how to program a quantum computer so difficult is that you don't know which world you're saying hello to.
posted by ardgedee at 4:06 AM on December 9, 2015 [8 favorites]
posted by ardgedee at 4:06 AM on December 9, 2015 [8 favorites]
My understanding of this is that the qbits in the Dwave machine are connect to each other in a tree like structure, so that each bit can effect only certain other bits, which means that you can't just assign connectivity between any two qubits... and it is this fact that makes it a non-general purpose quantum computer.
My understanding is that it'll be nearly impossible to make a device that is fully interconnected.
posted by MikeWarot at 4:23 AM on December 9, 2015
My understanding is that it'll be nearly impossible to make a device that is fully interconnected.
posted by MikeWarot at 4:23 AM on December 9, 2015
b1tr0t: Quantum computing will change some things and leave others the same.
Actually, it will both change things and leave them the same until observed.
posted by dr_dank at 4:35 AM on December 9, 2015 [1 favorite]
Actually, it will both change things and leave them the same until observed.
posted by dr_dank at 4:35 AM on December 9, 2015 [1 favorite]
Any of the mefites who've done a good job of explaining quantum computing in this thread, want to take a stab at explaining annealing or simulated annealing, and what distinguishes that/them from the forms of computing already discussed?
posted by ardgedee at 5:10 AM on December 9, 2015
posted by ardgedee at 5:10 AM on December 9, 2015
Imagine a computer that knows every possible answer, but doesn't understand questions. That's quantum computing.
posted by blue_beetle at 5:42 AM on December 9, 2015
posted by blue_beetle at 5:42 AM on December 9, 2015
I assume there is a version of FreeBSD that runs on it....
I kid, but the FreeBSD 9 Release Notes sure looked like someone was paying for a lot of development in BSD that might be useful in Utah, if you know what I mean.
posted by dglynn at 5:47 AM on December 9, 2015 [3 favorites]
I kid, but the FreeBSD 9 Release Notes sure looked like someone was paying for a lot of development in BSD that might be useful in Utah, if you know what I mean.
posted by dglynn at 5:47 AM on December 9, 2015 [3 favorites]
Experts doubt Google’s claim about its quantum computer’s speed
posted by graymouser at 6:12 AM on December 9, 2015
posted by graymouser at 6:12 AM on December 9, 2015
I wouldn't read too much into the fact that people like Google, the NSA and Big Money is investing in QC. It's an extremely cool (ho ho) field, they've got lots of money to spend, and there's a theoretical chance that at some point it'll be really important. That's a very easy sell to the people writing the cheques - the quantum woo factor doesn't just apply to pseudoscience.
And who wouldn't want to play with this, given a chance? I would.
None of this is much of a predicative factor for if or when this stuff will actually blow the doors off the gaffe. It's far easier to predict the periodic emission of gee-whizz PR, which is what I suspect we have here.
None of this is bad per se, not bad science and not a bad thing to be doing. I'm just wary of assigning significance to any particular announcement that doesn't lead with "We have done X, where X was impossible or impracticable before, and the immediate consequences are Y, where Y is significant". QC has particularly wide gaps between proof of concept and useful technology, and there are many monsters therein, and they are not yet all slain.
posted by Devonian at 6:27 AM on December 9, 2015 [1 favorite]
And who wouldn't want to play with this, given a chance? I would.
None of this is much of a predicative factor for if or when this stuff will actually blow the doors off the gaffe. It's far easier to predict the periodic emission of gee-whizz PR, which is what I suspect we have here.
None of this is bad per se, not bad science and not a bad thing to be doing. I'm just wary of assigning significance to any particular announcement that doesn't lead with "We have done X, where X was impossible or impracticable before, and the immediate consequences are Y, where Y is significant". QC has particularly wide gaps between proof of concept and useful technology, and there are many monsters therein, and they are not yet all slain.
posted by Devonian at 6:27 AM on December 9, 2015 [1 favorite]
a stab at explaining annealing or simulated annealing, and what distinguishes that/them from the forms of computing already discussed
Well, annealing is what blacksmiths do with their hammers. Simulated annealing is not really a form of computing but an optimization algorithm, or more generally a technique, inspired by the behavior of molecules in cooling metal. For example, you could use it to find a pretty good route that visits all the breweries in the U.S. (i.e. Traveling Salesman problem). But it's an approximation -- you are not guaranteed to find the best answer but usually a "pretty good" answer by searching through many different possibilities.
(I'm not up enough on quantum computing to know if this thing could in theory find an exact answer to such problems)
posted by RobotVoodooPower at 7:12 AM on December 9, 2015 [1 favorite]
Well, annealing is what blacksmiths do with their hammers. Simulated annealing is not really a form of computing but an optimization algorithm, or more generally a technique, inspired by the behavior of molecules in cooling metal. For example, you could use it to find a pretty good route that visits all the breweries in the U.S. (i.e. Traveling Salesman problem). But it's an approximation -- you are not guaranteed to find the best answer but usually a "pretty good" answer by searching through many different possibilities.
(I'm not up enough on quantum computing to know if this thing could in theory find an exact answer to such problems)
posted by RobotVoodooPower at 7:12 AM on December 9, 2015 [1 favorite]
I kid, but the FreeBSD 9 Release Notes sure looked like someone was paying for a lot of development in BSD that might be useful in Utah, if you know what I mean.
A group with a three letter abbreviated name, I imagine -- the LDS is very serious about their ancestry database.
posted by nathan_teske at 7:33 AM on December 9, 2015 [3 favorites]
A group with a three letter abbreviated name, I imagine -- the LDS is very serious about their ancestry database.
posted by nathan_teske at 7:33 AM on December 9, 2015 [3 favorites]
The thing people don't have their heads around with quantum computing is that, generally speaking, quantum computers are not Universal Turing Machines. That is, given an input and a program, they can't find any solution. They are instead single-solution generators: given an input, they can provide an output. So a quantum computer is never going to run Chrome or Minecraft or whatever people are running. That's not their point. They have a given function and return output relative to that function, and don't really do anything else.
From what I understand, the quantum annealing that D-Wave is trying to accomplish is basically used to solve things like the traveling salesman problem. You give the quantum computer a structured set of data (in the traveling salesman problem, a set of cities and their locations that the salesman will visit) and the computer, using certain quantum properties of its registers, comes up with a solution similar to the shortest-path (really lowest-energy) distances between the data points. The real question with D-Wave is whether or not it's actually a major advance in this. For certain types of optimization, it would be a step forward, but it's hard to say whether it is.
What D-Wave isn't, is a step toward a quantum computer of the sort that comes up in Shor's algorithm. That's because annealing is fundamentally different from the transforms in Shor's algorithm (the one that breaks RSA encryption). In annealing, it's a quantum property of each individual register that is being used. With Shor, it is a transform done to a series of entangled registers that, because of the entanglement, allows the computer to factor large numbers. D-Wave have not taken us any closer to solving that problem.
The D-Wave people have not been dishonest about what their computer does, but they also have not dissuaded anyone of the "quantum computer!" hype. It's a computer, and it uses quantum registers, but it's not the kind of quantum computer that most people use the term to indicate.
posted by graymouser at 7:38 AM on December 9, 2015 [2 favorites]
From what I understand, the quantum annealing that D-Wave is trying to accomplish is basically used to solve things like the traveling salesman problem. You give the quantum computer a structured set of data (in the traveling salesman problem, a set of cities and their locations that the salesman will visit) and the computer, using certain quantum properties of its registers, comes up with a solution similar to the shortest-path (really lowest-energy) distances between the data points. The real question with D-Wave is whether or not it's actually a major advance in this. For certain types of optimization, it would be a step forward, but it's hard to say whether it is.
What D-Wave isn't, is a step toward a quantum computer of the sort that comes up in Shor's algorithm. That's because annealing is fundamentally different from the transforms in Shor's algorithm (the one that breaks RSA encryption). In annealing, it's a quantum property of each individual register that is being used. With Shor, it is a transform done to a series of entangled registers that, because of the entanglement, allows the computer to factor large numbers. D-Wave have not taken us any closer to solving that problem.
The D-Wave people have not been dishonest about what their computer does, but they also have not dissuaded anyone of the "quantum computer!" hype. It's a computer, and it uses quantum registers, but it's not the kind of quantum computer that most people use the term to indicate.
posted by graymouser at 7:38 AM on December 9, 2015 [2 favorites]
I read the announcement and the rebuttal (but not the paper) and I'm still confused.
The biggest question about D-Wave was whether it was actually using quantum effects. The result Google/NASA published says that the D-Wave machine's performance curve is much like a simulated quantum algorithm, suggesting the D-Wave is acting like a quantum algorithm. Also it's hugely faster on this toy problem than a conventional computer, so the assumption is that actual quantum effects are at work, it's not just a normal CPU in a fancy box.
But has anyone demonstrated that physically, at the hardware level, it's actually doing quantum physics? IIRC there was some squirrely thing where D-Wave wouldn't let anyone look inside the box. Absent that, is it possible that inside is just a conventional ASIC that's doing a simulated quantum computing super fast because even though it's classical physics, it's purpose-built to run the quantum simulator?
I guess I'm just baffled that there's so much ambiguity around what should be a really clear, ironclad demonstration of a radical new form of computation. If this company really has a working quantum computer that can be used on practical problems, why is it so confusing?
posted by Nelson at 8:51 AM on December 9, 2015 [1 favorite]
The biggest question about D-Wave was whether it was actually using quantum effects. The result Google/NASA published says that the D-Wave machine's performance curve is much like a simulated quantum algorithm, suggesting the D-Wave is acting like a quantum algorithm. Also it's hugely faster on this toy problem than a conventional computer, so the assumption is that actual quantum effects are at work, it's not just a normal CPU in a fancy box.
But has anyone demonstrated that physically, at the hardware level, it's actually doing quantum physics? IIRC there was some squirrely thing where D-Wave wouldn't let anyone look inside the box. Absent that, is it possible that inside is just a conventional ASIC that's doing a simulated quantum computing super fast because even though it's classical physics, it's purpose-built to run the quantum simulator?
I guess I'm just baffled that there's so much ambiguity around what should be a really clear, ironclad demonstration of a radical new form of computation. If this company really has a working quantum computer that can be used on practical problems, why is it so confusing?
posted by Nelson at 8:51 AM on December 9, 2015 [1 favorite]
Yeah so if this is just simulated annealing but REALLY FAST, then I'm surprised to see Google and some bank rather than a list of major logistics companies as investors. I wonder if UPS et al have just come up with enough tricks to make it good enough with more conventional computers.
posted by indubitable at 10:01 AM on December 9, 2015
posted by indubitable at 10:01 AM on December 9, 2015
But it can't factor numbers, can't do Grover search, basically can't do any of the things that make quantum computation so crazy exciting. (It was never intended to do these things.)
So, it's sort of like a hoverboard with wheels?
posted by mule98J at 10:03 AM on December 9, 2015 [3 favorites]
"But has anyone demonstrated that physically, at the hardware level, it's actually doing quantum physics?"
Physically demonstrating quantum computing must be like watching this video while blinking.
posted by markkraft at 10:33 AM on December 9, 2015 [1 favorite]
Physically demonstrating quantum computing must be like watching this video while blinking.
posted by markkraft at 10:33 AM on December 9, 2015 [1 favorite]
Yeah so if this is just simulated annealing but REALLY FAST, then I'm surprised to see Google and some bank rather than a list of major logistics companies as investors.
It's a long-term investment. The finance industry is interested in solving certain problems like real-time option pricing. The spooks are buying them to make really, really, sure that no one is able to factor large numbers faster than they can.
posted by RobotVoodooPower at 11:18 AM on December 9, 2015
It's a long-term investment. The finance industry is interested in solving certain problems like real-time option pricing. The spooks are buying them to make really, really, sure that no one is able to factor large numbers faster than they can.
posted by RobotVoodooPower at 11:18 AM on December 9, 2015
A system error may or may not have occurred. Press "OK" to do all possible next steps at once.
posted by w0mbat at 1:47 PM on December 9, 2015 [1 favorite]
posted by w0mbat at 1:47 PM on December 9, 2015 [1 favorite]
D-Wave wouldn't let anyone look inside the box
Just think what that would do to the cat.
posted by Gerald Bostock at 1:56 PM on December 9, 2015 [5 favorites]
Just think what that would do to the cat.
posted by Gerald Bostock at 1:56 PM on December 9, 2015 [5 favorites]
A quantum computer sloshes a bucket of water over it and picks the puddle.
This is exactly how I conceptualize it. As I understand it, quantum systems naturally evolve towards the lowest energy state, just as water rearranges itself so that it lies as low and flat as possible. A puddle doesn't need to test every conceivable arrangement of molecules one by one. The simultaneous interactions between all the water molecules results in the system "finding" the best arrangement, much faster than a (molecular-level) computer simulation could manage. Water is very, very good at solving this narrowly-defined problem, but it's abilities are not really generalizable.
I think part of our brain works by leveraging quantum interaction.
There are quantum effects involved in many different aspects of biochemistry (e.g. enzyme reactions and the electron transport chain), but I don't think the brain is exceptional in this regard. Just about all the mechanics of neurons can be found in other cell types (e.g., cardiac muscle cells, which have voltage-gated ion channels and depolarize in very organized ways), they just aren't used to do information processing per se.
posted by dephlogisticated at 2:18 PM on December 9, 2015
This is exactly how I conceptualize it. As I understand it, quantum systems naturally evolve towards the lowest energy state, just as water rearranges itself so that it lies as low and flat as possible. A puddle doesn't need to test every conceivable arrangement of molecules one by one. The simultaneous interactions between all the water molecules results in the system "finding" the best arrangement, much faster than a (molecular-level) computer simulation could manage. Water is very, very good at solving this narrowly-defined problem, but it's abilities are not really generalizable.
I think part of our brain works by leveraging quantum interaction.
There are quantum effects involved in many different aspects of biochemistry (e.g. enzyme reactions and the electron transport chain), but I don't think the brain is exceptional in this regard. Just about all the mechanics of neurons can be found in other cell types (e.g., cardiac muscle cells, which have voltage-gated ion channels and depolarize in very organized ways), they just aren't used to do information processing per se.
posted by dephlogisticated at 2:18 PM on December 9, 2015
We do not believe that quantum computers mean really really fast computers per se, bassomatic, but they do mean new models of computation can be realized, which means some algorithms get faster.
We'd never make such a big deal about quantum computers, except Shor's algorithm breaks all the public key cryptography commonly in use today.
We care about public key cryptography because all electronic communications depends upon it for security of bank transactions, etc. And more importantly for any privacy in personal communications :
In this case, we've an announcement of apparently a big but fixed factor performance boost using quantum annealing, not necessarily an asymptotic speedup, and not the stronger models of quantum computation theoreticians like. We believe quantum annealing cannot aid with Shor's algorithm, but this still makes us nervous.
In addition, Google claims quantum annealing can help them with hard AI problems, like maybe discovering what product's your parents can be convinced to buy. I'd rank this as not too surprising.
It's afaik false that the NSA abandoned public key systems, merely they abandoned Elliptical Curve cryptography algorithms with small key sizes by going with older public key algorithms like RSA that require painfully large key sizes. I'd consider their announcement perfectly consistent with increasing their long term threat assessment for quantum computers.
posted by jeffburdges at 2:50 PM on December 9, 2015 [3 favorites]
We'd never make such a big deal about quantum computers, except Shor's algorithm breaks all the public key cryptography commonly in use today.
We care about public key cryptography because all electronic communications depends upon it for security of bank transactions, etc. And more importantly for any privacy in personal communications :
“But we discovered something. Our one hope against total domination. A hope that with courage, insight and solidarity we could use to resist. A strange property of the physical universe that we live in. The universe believes in encryption.” - Julian AssangeIn short, if quantum computers work, then we're all significantly more likely to be enslaved by oligarchs. And if you beleived in God then you might start to think that he's a fascist fuck.
In this case, we've an announcement of apparently a big but fixed factor performance boost using quantum annealing, not necessarily an asymptotic speedup, and not the stronger models of quantum computation theoreticians like. We believe quantum annealing cannot aid with Shor's algorithm, but this still makes us nervous.
In addition, Google claims quantum annealing can help them with hard AI problems, like maybe discovering what product's your parents can be convinced to buy. I'd rank this as not too surprising.
It's afaik false that the NSA abandoned public key systems, merely they abandoned Elliptical Curve cryptography algorithms with small key sizes by going with older public key algorithms like RSA that require painfully large key sizes. I'd consider their announcement perfectly consistent with increasing their long term threat assessment for quantum computers.
posted by jeffburdges at 2:50 PM on December 9, 2015 [3 favorites]
There are many reasons why D-Wave might keep their box so secret, like maybe the NSA asks anyone doing anything around quantum computation hide the details from the Russians and Chinese. It's even possible D-Wave is a hoax by the NSA to discredit public key cryptography.
posted by jeffburdges at 3:09 PM on December 9, 2015
posted by jeffburdges at 3:09 PM on December 9, 2015
In short, if quantum computers work, then we're all significantly more likely to be enslaved by oligarchs. And if you beleived in God then you might start to think that he's a fascist fuck.
There are also "quantum-safe" approaches to asymmetric crypto - they are just less efficient and convenient as I understand and therefore not widely deployed at all at this point - or one could even potentially use the current standard algorithms but with huge keys. So the situation to really worry about is one in which someone secretly has a device that can run Shor's, while the rest of the world is unaware of the need to transition to new ciphers.
posted by atoxyl at 3:45 PM on December 9, 2015
There are also "quantum-safe" approaches to asymmetric crypto - they are just less efficient and convenient as I understand and therefore not widely deployed at all at this point - or one could even potentially use the current standard algorithms but with huge keys. So the situation to really worry about is one in which someone secretly has a device that can run Shor's, while the rest of the world is unaware of the need to transition to new ciphers.
posted by atoxyl at 3:45 PM on December 9, 2015
If you read the link about NTRU it actually says that particular algorithm is more efficient than RSA. Does anyone know more about it? Just too new to catch on/be fully trusted?
posted by atoxyl at 3:47 PM on December 9, 2015
posted by atoxyl at 3:47 PM on December 9, 2015
Google, D-Wave, and the case of the factor-10^8 speedup for WHAT? by Scott Aaronson with guest paper by Matthias Troyer and other experts from ETH Zürich. I don't have time to read this closely, but on first blush Aaronson seems to be saying that a quantum effect is demonstrated but that the computation model it implements may not be generally useful.
posted by Nelson at 3:50 PM on December 9, 2015 [4 favorites]
posted by Nelson at 3:50 PM on December 9, 2015 [4 favorites]
I still have no idea when and if we’ll have a practical, universal, fault-tolerant QC, capable of factoring 10,000-digit numbers and so on. But it’s now looking like only a matter of years until Gil Kalai, and the other quantum computing skeptics, will be forced to admit they were wrong—which was always the main application I cared about anyway!That's when things will get interesting. I strongly suspect the skeptics will be right, but interesting new physics will come out of the failure.
posted by Coventry at 6:25 PM on December 9, 2015
Just fyi, a quasipolynomial time algorithm for graph isomorphism was recently announced by László Babai, atoxyl. It's a staggering result that works in part by analyzing the character theory of automorphism groups of graphs using the classification of the finite simple groups, which itself is basically the hardest result in all of mathematics.
Afaik that does not directly impact any public key cryptosystems, but graph isomorphism was previously one of the non-abelian hidden subgroup problems for which we lacked even quantum algorithms. All these lattice based crypto-systems like NTRU and Ring-LWE are also non-abelian hidden subgroup problems. Yes, they appears fine for now, but landslide did just took out part of the house they live in.
Also, Shor's algorithm is a quantum polynomial time solution for the abelian case of the hidden subgroup problem, that's why it solves factoring, discrete log, etc. It's vaguely plausible that if clever people work with Babai's methods long enough then maybe some interesting non-abelian hidden subgroup problems will fall, not directly to quasipolynomial time algorithms like graph isomorphism, but to quantum algorithms that go way beyond Shor.
I'll just recently got talked into contributing a talk at 32c3 this month where I'm planning on arguing for the Axolotl ratchet using curve25519 for size and speed with long-term forward-secrecy, but introduce side key material or encrypt the Axolotl header using quantum algorithms whenever it's convenient. If you do not mind maintaining that ratchet state forever, and inconveniencing multi-device access, then you can basically encrypt with all the algorithms while being as small and fast as curve25519 most of the time.
posted by jeffburdges at 6:51 PM on December 9, 2015 [3 favorites]
Afaik that does not directly impact any public key cryptosystems, but graph isomorphism was previously one of the non-abelian hidden subgroup problems for which we lacked even quantum algorithms. All these lattice based crypto-systems like NTRU and Ring-LWE are also non-abelian hidden subgroup problems. Yes, they appears fine for now, but landslide did just took out part of the house they live in.
Also, Shor's algorithm is a quantum polynomial time solution for the abelian case of the hidden subgroup problem, that's why it solves factoring, discrete log, etc. It's vaguely plausible that if clever people work with Babai's methods long enough then maybe some interesting non-abelian hidden subgroup problems will fall, not directly to quasipolynomial time algorithms like graph isomorphism, but to quantum algorithms that go way beyond Shor.
I'll just recently got talked into contributing a talk at 32c3 this month where I'm planning on arguing for the Axolotl ratchet using curve25519 for size and speed with long-term forward-secrecy, but introduce side key material or encrypt the Axolotl header using quantum algorithms whenever it's convenient. If you do not mind maintaining that ratchet state forever, and inconveniencing multi-device access, then you can basically encrypt with all the algorithms while being as small and fast as curve25519 most of the time.
posted by jeffburdges at 6:51 PM on December 9, 2015 [3 favorites]
Appears Nelson just won the thread, thanks for that link!
posted by jeffburdges at 7:00 PM on December 9, 2015
posted by jeffburdges at 7:00 PM on December 9, 2015
Just fyi, a quasipolynomial time algorithm for graph isomorphism was recently announced by László Babai, atoxyl. It's a staggering result that works in part by analyzing the character theory of automorphism groups of graphs using the classification of the finite simple groups, which itself is basically the hardest result in all of mathematics.
Wait "some have suggested it should be NP complete" - more like "generally thought not to be NP complete, but not definitively proved," right? Because a QP algorithm for an NP complete problem would be... big. (Obviously that's not the only detail of the situation the blurb doesn't quite understand but so it goes.)
posted by atoxyl at 12:09 PM on December 10, 2015
Wait "some have suggested it should be NP complete" - more like "generally thought not to be NP complete, but not definitively proved," right? Because a QP algorithm for an NP complete problem would be... big. (Obviously that's not the only detail of the situation the blurb doesn't quite understand but so it goes.)
posted by atoxyl at 12:09 PM on December 10, 2015
Actually there was an earlier argument that graph isomorphism is not NP-complete in the sense that, if it were NP-complete, then at least some complexity classes that people suspect to be different must actually be equal.
In fact, wikipedia says "[Graph isomorphism] is one of only two, out of 12 total, problems listed in Garey & Johnson (1979) whose complexity remains unresolved, the other being integer factorization. It is however known that if the problem is NP-complete then the polynomial hierarchy collapses to a finite level."
I learned about Babai's result from http://www.scottaaronson.com/blog/?p=2521 and http://people.cs.uchicago.edu/~laci/quasipoly.html btw, vastly more reliable than phys.org.
posted by jeffburdges at 5:49 PM on December 10, 2015
In fact, wikipedia says "[Graph isomorphism] is one of only two, out of 12 total, problems listed in Garey & Johnson (1979) whose complexity remains unresolved, the other being integer factorization. It is however known that if the problem is NP-complete then the polynomial hierarchy collapses to a finite level."
I learned about Babai's result from http://www.scottaaronson.com/blog/?p=2521 and http://people.cs.uchicago.edu/~laci/quasipoly.html btw, vastly more reliable than phys.org.
posted by jeffburdges at 5:49 PM on December 10, 2015
Actually there was an earlier argument that graph isomorphism is not NP-complete in the sense that, if it were NP-complete, then at least some complexity classes that people suspect to be different must actually be equal.
Right, and if it were NP-complete *and* had a QP-time algorithm that would of course imply that they all do, so I think smart betting would take this result more as a further indication that the problem is not NP-complete. I was just annoyed by the writeup in that first link, which threw that bit in (and references to TSP etc.) while clearly not understanding what they mean.
posted by atoxyl at 7:35 PM on December 10, 2015
Right, and if it were NP-complete *and* had a QP-time algorithm that would of course imply that they all do, so I think smart betting would take this result more as a further indication that the problem is not NP-complete. I was just annoyed by the writeup in that first link, which threw that bit in (and references to TSP etc.) while clearly not understanding what they mean.
posted by atoxyl at 7:35 PM on December 10, 2015
« Older Thirty-five years ago, during the Dolphins vs... | The emperor was naked, and so is this. Newer »
This thread has been archived and is closed to new comments
posted by slater at 6:10 PM on December 8, 2015 [23 favorites]