Slashdot Mirror
Separating Hope From Hype In Quantum Computing
pgptag writes "This talk by Dr. Suzanne Gilbert (video) explains why quantum computers are useful, and also dispels some of the myths about what they can and cannot do. It addresses some of the practical ways in which we can build quantum computers and gives realistic timescales for how far away commercially useful systems might be."
Upon observation, this post has collapsed into the first post state.
Would this sort of thing ever become useful for personal use? Or is Quantum Computing strictly a commercial endeavor?
Living With a Nerd
Oops. Thought this thread title was about Obama....sorrry.
What video? There's no video on that page, only a huge blank gap sponsored by Adobe.
We can't even get people to read the articles referenced in submissions. That's wildly optimistic to expect us to watch a video that is over 2 hours long.
This is begging for an "executive summary" from anyone who has time to watch it, if there is such a person.
The quantum computer is both a realistic ideal and vaporware hype, until a computer journalist examines the claims.
I'd position her qubits any day of the week!
Maybe in the future, a Quantum Computer running Windows x.x will be able to harness its power to show the contents of a folder in less than the 30 seconds it takes now.
When Fascism comes to America, it will call itself Anti-Fascism, and tell you to give up your guns.
Someone from D-wave is giving a talk called "separating hope from hype": http://arstechnica.com/hardware/news/2007/02/quantum.ars http://www.technologyreview.com/computing/20587/ http://en.wikipedia.org/wiki/D-Wave_Systems
The real question is if there's some significant use case not already covered by current methods, like RSA and AES for encryption. Sure quantum encryption have some nice theoretical properties, but most things are not 110% secure. You can still bribe people, extort people, plant spys, record passwords and so on. I doubt for almost any system that pure crypto is the weakest link in the chain anymore. Maybe, just maybe there's a quantum code cracking computer deep in the halls of the NSA but it won't be any of the "regular" attackers no matter how well funded and organized they are. Seriously, it's nice to be paranoid but the idea of a quantum attack on your encryption seems as unlikely as an asteroid impact taking out your main office.
Live today, because you never know what tomorrow brings
I think that either English is not your first language, or you don't know what a Beowulf cluster is.
I was going to listen, but the dude yakking in the background totally oblivious (well..not totally oblivious as he questioned himself as to why he can hear himself talking) to the fact that his mic is broadcasting right over the speaker. Dumb.
I took a class on Quantum computing, and studied many specific QC algorithms, so I know a little bit about them. If you don't want to RTFA, then read this: Quantum Computers are not super-computers. On a bit-for-bit (or qubit-for-qubit) scale, they're not necessarily faster than regular computers, they just process info differently. Since information is stored in a quantum "superposition" of states, as opposed to a deterministic state like regular computers, the qubits exhibit quantum interference around other qubits. Typically, your bit starts in 50% '0' and 50% '1', and thus when you measure it, you get a 50% chance of it being one or the other (and then it assumes that state). But if you don't measure, and push it through quantum circuits allowing them to interact with other qubits, you get the quantum phases to interfere and cancel out. If you are damned smart (as I realized you have to be, to design QC algorithms), you can figure out creative ways to encode your problem into qubits, and use the interference to cancel out the information you don't want, and leave the information you do want. For instance, some calculations will start with the 50/50 qubit above, and end with 99% '0' and 1% '1' at the end of the calculation, or vice versa, depending on the answer. Then you've got a 99% chance of getting the right answer. If you run the calculation twice, you have a 99.99% chance of measuring the correct answer. However, the details of these circuits which perform quantum algorithms are extremely non-intuitive to most people, even those who study it. I found it to require an amazing degree of creativity, to figure out how to combine qubits to take advantage of quantum interference constructively. But what does this get us? Well it turns out that quantum computers can run anything a classical computer can do, and such algorithms can be written identically if you really wanted to, but doing so gets the same results as the classical computer (i.e. same order of growth). But, the smart people who have been publishing papers about this for the past 20 years have been finding new ways to combine qubits, to take advantage of nature of certain problems (usually deep, pure-math concepts), to achieve better orders of growth than possible on a classical computer. For instance, factoring large numbers is difficult on classical computers, which is why RSA/PGP/GPG/PKI/SSL is secure. It's order of growth is e^( n^(1/3) ). It's not quite exponential, but it's still prohibitive. It turns out that Shor figured out how to get it to n^2 on a quantum computer (which is the same order of growth as decrypting with the private key on a classical computer!). Strangely, trying to guess someone's encryption key, normally O(n) on classical computers (where n is the number of possible keys encryption keys) it's only O(sqrt(n)) on QCs. Weird (but sqrt(n) is still usually too big). There's a vast number of other problems for which efficient quantum algorithms have been found. Unfortunately, a lot of these problems aren't particularly useful in real life (besides to the curious pure-mathematician). A lot of them are better, but not phenomenal. Like verifying that two sparse matrices were mulitplied correctly has order of growth n^(7/3) on a classical computer, n^(5/3) on a quantum computer. You can find a pretty extensive list by googling "quantum algorithm zoo." Unfortunately [for humanity], there is no evidence yet that quantum computers will solve NP-complete problems efficiently. Most likely, they won't. So don't get your hopes up about solving the traveling salesmen problem any time soon. But there is still a lot of cool stuff we can do with them. In fact, the theory is so far ahead of the technology, that we're anxiously waiting for breakthroughs like this, so we can start plugging problems through known algorithms.
That is obviously not the only thing it can do. In P time it can solve P problem (much like a classical computer, but potentially using $\sqrt{classical}$ time, if it meets the above requirements. You can use quantum computing to find (with any probability of your choice which is less than one) the solution to a BPP problem in P time, which is again just like classical computers. Something new here is the ability to solve BQP problems (with any chosen probality less than one) in P time.
That last one is the killer. That is because two of the "hard" problems we use in asymmetric cryptography are BQP, namely integer factroization and discrete logarithms
are in BQP.[1]
What we really want is asymmetric encryption based on an NP-complete problem where many instances can be shown to take no less time (asymptotically) than the hardest instances to solve (i.e. many instances are tied for the hardest), and an easy way to generate instances of this hardest problem, and corresponding solution. That is really tricky, as many FNP problems that are not optimization problems (not NPO) have many instances that can be solved in only P time.
Footnote:
[1] Actually that is not strictly true. The problems have more than a yes or no answer, making them FBQP problems. But FBQP-complete problems take no longer to solve than BQP-complete problems. So quantum computers can solve FBQP with any given probability of success in only P time.
Stylish sheet to fix many problems in Slashdot's D3: https://gist.github.com/801524
"Why do I hear my voice?" during a video conference.
Makes me feel hella smart. :D
You obviously don't know what a Beowulf cluster is.
The joke is "imagine a Beowulf cluster of those!" for a reason.
The quantum computers wouldn't run your Beowulf cluster, they would be your Beowulf cluster.
And the first ones will probably be slow as shit anyway (but catch up much faster than current tech).
Security is mostly a superstition... Avoiding danger is no safer in the long run than outright exposure. - Helen Keller
I think you are underestimating chess.
Yes it is solvable, but assuming one variation can be calculated in a single floating point operation (it probably can't, but who knows) with current tech (3 petaflop/s) it would take 10^97 years just to calculate the first move*. The next calculation is nearly as big as the first, with the calculations getting slightly smaller as the game goes on.
That means a computer that solves one chess move per year (for the first 10 moves or so, after that the calculations are a fraction of the size of the first calc) would need to be 10^97 times more powerful than the most powerful supercomputer we have. With that computer you could probably solve it in 5-10 years. If it's only 10^96 times as powerful, though, it would take well over 100 years to solve.
I've got bad news for you in that regard, because the current supercomputers (3 petaflop/s or less) are only 10^16 times more powerful than the Z3, the first turing complete computer, which was invented in 1941 and could only do one multiplication per three seconds. Assuming the same exponential rate of growth, and in 70 years we'll still be 10^81 times too weak to solve chess in any reasonable amount of time.
Add to that the fact that a quantum computer will almost certainly have absolutely no advantage in solving for each position than a classical computer (it's a simple accounting of each move, there aren't any computationally complex problems, just an assload of computations), and there is no reason to believe quantum computing will solve chess any time soon.
I know we'll do it eventually, I just can't see it happening for a couple hundred years. Once solved, though, Chess will be boring with regards to computers. It will become a simple "if this than this" operations. Humans still probably couldn't handle it, but any of today's computers would be unbeatable.
In other words, the game is solvable, but the amount of computational power necessary is absolutely staggering. It's so staggering that some have argued that computers (yes, even quantum computers) will run into the limits of physics long before they are ever powerful enough to truly solve chess. You run into the limits of the speed of light and quantum entanglement and the laws of thermodynamics and such at some point, and we are already nearing the physical limits of chipmaking for classical computers now (the reason we had to stop the GHZ expansion), just 70 years after the invention of the computer (of which we are only 10^16 times more powerful today).
*To get the first move, you need to calculate the entire tree, which has 10^120 variations for a 40 move (average) game, in order to know the the best possible move. From there the variations start to shrink (you've eliminated all the branches that don't start with your first move), but at this point the number is still nearly as large. Not until many moves in would the calculation time shrink to a reasonable level for that powerful of a computer. So far only limited 4 piece or fewer end game scenarios have been solved.
Security is mostly a superstition... Avoiding danger is no safer in the long run than outright exposure. - Helen Keller
Well, whether the technology will arrive may or may not be hype. I don't know. However, once and if it arrives, they will be able to do these things. That part, at least, is not hype.
I am no expert on the matter, but I was under the impression that chess is a problem that would benefit tremendously from quantum computer computations. I've read many sources online that claim this is the case, though none are academic papers. The staggering number of computations does not necessarily phase me because of how quantum computers work. Such staggering computations are more of a problem for classical computers.
Unless you're running a Beowulf cluster emulator on them, of course.
The Tao of math: The numbers you can count are not the real numbers.
These crooks from D-Wave just won't give up. 128 qubits quantum computer!? pics or it didn't happen.
For more info: http://en.wikipedia.org/wiki/D-Wave_Systems
entropy happens
The most common such belief seems to be the belief that a quantum computer can solve NP-complete problems in polynomial time.
Allow me to expand a bit on that.
There's a complexity class known as BQP which is defined to be what quantum computers can do in polynomial time (hence the Q and P; the B is for Bounded error probability, i.e. algorithms succeed with probability at least 2/3; if you want better: repeat and take majority voting).
It is known that BQP contains P and BPP (randomized poly-time turing machines), and is contained within PSPACE (which contains NP).
It is conjectured that P != NP and that BQP contains some but not all of (NP minus P), and is also not contained in NP.
Now, let's talk about factoring. It is known to be in NP (if I show you a candidate factoring, you can multiply it together rapidly and check whether I told the truth; you can even check primality in polynomial time). It's also in coNP---well, depending on how you turn factoring into a yes/no question. I lean towards "given n and k (in binary) does n have a non-trivial factor less than k". Then you can extract such a factor by binary search. It that case, it's easy to check proofs that a number _doesn't_ have a non-trivial factor less than k: give the full factorization as the proof, then verify the factorization as checking, and also check that no prime factor is less than k.
We don't know whether factoring is in P. Factoring is known to be in BQP, though!
This is due to Shor's algorithm. A very brief 10 kilofoot overview: it uses Fourier transformation to detect periodicity in functions. In cyclic groups, raising a generator element to exponents 1, 2, 3, ... has a periodicity to it. In particular, the RSA group has a periodicity to it; and you can factor n if you know phi(n), the order of the RSA group. (I'm told you can do "basically the same" to solve discrete logarithms).
I hope this helps someone.
It's well worth watching, considering that this is the future and the summary is comprehensive and all. However, the basic upshot is:
* some myths have built up around quantum computing, such as that classical crypto will be made obsolete. [ I'm not sure what her point was here; she seems to dismiss most these, but then never really goes back to it. Her other details seem to support these "myths" more than debunk them ]
* quantum computers fit reality better than classical computers, therefore we need them to understand and model our physical universe, almost regardless of how much "better" they are than classical computers in other ways [ Though this seems largely a performance thing to me ]
* building quantum computers is progressing; the company she works for (DWave) is producing 128-qubit chips now [ though they're specialised ]
* building stuff for quantum computers (such as refrigeration units to supercool them) is progressing in parallel [ supercoolers are available as desktop devices, will probably fit in a PC case like a PSU soon ]
* the chips they're building at DWave are specialised for pattern recognition and other energy reduction (simulated/quantum annealing) problems
* she expects quantum computing to be based around specialised co-processors (like GPUs, physics cards etc.) rather than general purpose CPUs
* there are lots of different ways to build quantum computers, each with their own pros and cons. We're nowhere near a standardised architecture (like Von Neumann) yet, for quantum computing.
* google have worked with DWave on an image recog project using their chip, and it's now performing better on their quantum chip(s?) than on google's previous hardware
* they used boink to generate known-good test results to compare with their quantum chip
* boink took ~1000 hours on ~1000 computers to do what their quantum chip does in something between a few seconds and a few minutes
* QC is still facing some major hurdles, not only of engineering and science, but of funding too.
* funding is the main obstacle
* one of the big funding problems is building a quantum computer in small labs/foundries that rivals the established, trillion-dollar industry of classical computing. Since foundries work better in large scale, it's hard to compete and prove the worth of QC
* she doesn't believe that academia has the necessary funding/project-time structure to allow non-commercial research/development at a higher level than the fundamental concepts