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."

Re:Who is going to watch this?

[JoshuaZ]

I don't have time to watch this right now, but if I have to make a guess, the primary points are going to be about the common misconceptions about quantum computers. The most common such belief seems to be the belief that a quantum computer can solve NP-complete problems in polynomial time. This is false although many problems which are believed to be in NP are believed to be not in P are solvable with quantum computer. The most prominent example is integer factoring since the difficulty of factoring large integers is something many crypto systems depend on (such as RSA). There's probably some addressing also that consciousness probably has nothing to do with any quantum effects in the human brain because structures there are generally too warm and too large to have meaningful quantum entanglement.

Irony?

[gotfork]

Someone from D-wave is giving a talk called "separating hope from hype": http://arstechnica.com/hardware/news/2007/02/quantum.ars [arstechnica.com] http://www.technologyreview.com/computing/20587/ [technologyreview.com] http://en.wikipedia.org/wiki/D-Wave_Systems [wikipedia.org]

Second Life Presentations suck

[Danathar]

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.

W/O RTFA

[mathimus1863]

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.

Re:Who is going to watch this?

[pgptag]

@gandhi re added value of avatar on virtual stage: this is an online talk with a participative audience in realtime telepresence. The second half of the video shows a very lively Q/A session and discussion, with a lot of people asking a lot of questions.

Re:Who is going to watch this?

[pgptag]

@mcgrew - here is Suzanne's blog: http://physicsandcake.wordpress.com/2010/09/02/online-seminar-on-quantum-computing/#comments [wordpress.com] in the comments she says she will post the slides of the presentation.

Re:Summarizing...

[Tacvek]

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.

Re:Post with unknown state

[Anonymous Coward]

The direct link appears:

http://blip.tv/file/get/Telexlr8-vbSuzanneGildertOnQuantumComputingInTeleplaceSeptember4640.flv

Comment removed

[account_deleted]

Comment removed based on user account deletion

Oh not again

[iris-n]

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 [wikipedia.org]

Re:Who is going to watch this?

[pgptag]

Not only that, but whatever crappy player they're using doesn't seem to want to let you seek. No matter where you move the marker, the whole presentation just starts over from the beginning -- complete with the audience jabbering right over the speaker.

Go to the source http://telexlr8.blip.tv/file/4083093/ [telexlr8.blip.tv] open the Files and Links box in the right column and download the original .mp4 video file.

Re:Oh not again

[Anonymous Coward]

You mean the 22 peer reviewed publications describing the processor in its entirety aren't enough?