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
"I hope this thing is really fast running my Beowulf cluster" or "oh man, these things will run a Beowulf cluster 10000x faster than today's machines! "
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.
For those who don't currently have 1.5 hours to WTFV?
Y'know, like _what_ is she actually saying, rather than just stating a fact she happens to be saying something.
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.
Or both at the same time.
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.
Quantum computers are useful for the following class of problem:
1. The only way to solve it is to guess answers repeatedly and check them,
2. There are n possible answers to check,
3. Every possible answer takes the same amount of time to check, and
4. There are no clues about which answers might be better: generating possibilities randomly is just as good as checking them in some special order.
If your problem doesn't look like that then quantum computers won't help.
(source: wikipedia )
No sig today...
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 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.
"Why do I hear my voice?" during a video conference.
Makes me feel hella smart. :D
Hype = D-Wave
Hope = !D-Wave
Quantum computers will bring an end to the competitiveness of AI vs Human chess games. They will be able to completely solve the game, meaning that they can produce a series of moves that will guarantee a win (or tie if the human player plays perfectly) from any position on the board. On the other hand, we will leap frog centuries of moore's law in bioinformatics algorithms. Goodbye protein folding problem!
http://blip.tv/file/get/Telexlr8-vbSuzanneGildertOnQuantumComputingInTeleplaceSeptember4640.flv
Her name is Gildert not Gilbert in case you are trying to find her blog...
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
..quantum computer will never need any more than 640 qubits!
The presentation was ok, but something anyone could have put together using internet resources alone, so meh.
Also, crappy multi-video feed, and general crappy implementation of quantum computing, crappy world really
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.