It looks like you're new here. If you want to get involved, click one of these buttons!

- 6.1K All Categories
- 5.6K Nerdfighteria
- 272 Rules and Support
- 247 John's Books
- 522 Gatherings and Events
- 45 VidCon
- 29 LeakyCon
- 156 United States
- 35 Canada
- 86 Europe
- 22 Asia
- 30 Australia/New Zealand
- 9 Central/South America
- 5 Africa/Middle East
- 5 Everywhere Else
- 1.2K Projects, Creations, and Brain Crack!
- 33 Nerdfighter Writing Club
- 3.2K General Discussion
- 358 TV/Movies
- 332 Books & Literature
- 278 Music
- 199 Youtube
- 233 Gaming
- 70 Sports
- 51 Comics
- 191 Politics & Current Events
- 398 Forum Games
- 102 Not English
- 6 Dansk
- 15 Deutsch
- 11 Español
- 10 Français
- 4 Nederlands
- 2 Norsk
- 4 Português
- 3 Svenska
- 838 Video Discussion
- 157 Vlogbrothers
- 68 Crash Course
- 10 History
- 3 Science
- 42 SciShow & SciShow Space
- 1 Animal Wonders
- 3 The Art Assignment
- 7 The Brain Scoop
- 2 Emma Approved
- 65 HankGames
- 3 Healthcare Triage
- 2 How to Adult
- 46 Lizzie Bennet
- 1 Mental_Floss
- 441 Sexplanations

Ari_Rahikkala
Posts: **1** ✭

Quantum computers do not "try all of the possible solutions of a problem at the same time and choose the best one". It's a common misconception but, you know, not what they actually do. See
http://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf
for one popular treatment of the subject, or just make vague overtures in the general direction of Scott Aaronson because telling people to stop thinking that quantum computers are magical is what he seems to spend half of his time on anyway.

If you *do* want to find out what quantum computers actually can do... it turns out it's simpler than you might think! You do have to know a bit of linear algebra, but only the very basics - basically, if you're comfortable thinking in terms of vectors and matrices, and can multiply matrices together, you've got enough mathematical background to go right in. Umesh Vazirani runs a course on it, offline at UC Berkeley, online previously on Coursera, and on EdX this spring when I took the course - and he's going to give it again in the fall, although I'm not sure exactly where, so be on the lookout. Vazirani is one of the founders of the field (and Scott Aaronson's doctoral advisor, it turns out), so you can trust that the guy actually really knows this stuff. All of that crazy notation with the weird unbalanced brackets will start making a lot more sense very soon.

Also, just to clarify, the model taught in that course is the quantum circuit model, which is *not* what D-Wave Systems implements. D-Wave's computer can't do arbitrary computation and there's skepticism over whether they will be able to produce any speedup over classical ways to do the problem that their computer *does* solve. Actually people used to be skeptical over whether they made any use of quantum effects at all, but I believe that's mostly been resolved in their favor now. I seem to recall statements from D-Wave to the effect that the quantum circuit model is one of the worst things that ever happened to the field of quantum computation (presumably meaning that they don't believe that general-purpose quantum computers can be implemented anytime soon, and that their system is useful enough), so, there's probably going to be some fireworks there eventually.

I'm not entirely certain on how quantum information works, but as I understand it qubits don't actually hold any more classical information than classical bits do. Yes, a classical simulation of qubits takes a whole lot of classical bits - but you can't actually get classical information out of qubits without measuring them, and that collapses them into whatever state you measured them as being in, so any other "detail" is lost.

Also!!! The section on quantum networks is pretty inaccurate as well. Quantum cryptography has nothing to do with weak measurement, and it absolutely has nothing to do with the computer being "allowed" to see quantum states in a way that humans can't. At least quantum cryptography is reasonably easy to describe with a metaphor, though... but it'll be an incredibly lazy metaphor because IMO if you're actually interested you should just learn it mathematically anyway:

Alice and Bob want to decide on a common string of random bits. It doesn't actually matter what those bits are, only that both parties agree on them, and nobody else can see them - the point is that they'll be used as a shared key for doing classical cryptography with.

So, Alice makes up some bits and sends them to Bob in little trick boxes. The way a trick box works is that they have two handles and you can open them by pulling either at the top or the side. Each box can be configured by Alice to be either a top-box or a side-box - she makes a random choice for each box. If you open a top-box from the top or a side-box from the side, you get the bit that was sent; if you open a top-box from the side or a side-box from the top, you get a fresh random bit. Oh, and when you open it, the very fundamental existence of the universe conspires to irreversibly make the bit inside the one that you saw, so once you've opened the box, it's useless to guess again. And there's no way to know whether a box was made as a side-box or a top-box.

Bob receives those little trick boxes and, for each, randomly decides to open it either from the top or the side. Half of the time he gets it right and the bit he sees inside is the one Alice sent, half the time it's a random bit. Once he's opened all of the boxes, he finds out the difference simply by conferring with Alice over a public channel, where he tells which side he opened, and Alice tells which kind of box she sent. For each box, if they match, Bob accepts the bit, if not, he throws it away.

What makes this work so well for secrecy is that if there's an eavesdropper Eve in between Alice and Bob, trying to work out what the bits are, she will be found out. She can open a box and see what's inside it, and she can make more boxes and send them to Bob - but she doesn't know whether they were top-boxes or side-boxes, so if she guesses wrong, she's essentially going to be sending Bob random bits. Which means that if, at the end, Alice publicly reveals some of the bits that she sent and that Bob was supposed to receive, and they turn out not to match, then Bob will know that his guess of whether the bit was sent in a side-box or a top-box was correct - but Eve's wasn't, which implies that there was an Eve listening in. If the bits Bob received do match sufficiently well with the ones Alice published, then there was no Eve, and they can use the rest of the bits, trusting that there was no physical way they could have been intercepted in transmission.

So, yeah. Quantum stuff. Honestly, you kiiind of got most of it wrong, but hey, you've only got so much time to spend per episode. Still, it would be good to see some more research before you do the next quantum-related video.

If you *do* want to find out what quantum computers actually can do... it turns out it's simpler than you might think! You do have to know a bit of linear algebra, but only the very basics - basically, if you're comfortable thinking in terms of vectors and matrices, and can multiply matrices together, you've got enough mathematical background to go right in. Umesh Vazirani runs a course on it, offline at UC Berkeley, online previously on Coursera, and on EdX this spring when I took the course - and he's going to give it again in the fall, although I'm not sure exactly where, so be on the lookout. Vazirani is one of the founders of the field (and Scott Aaronson's doctoral advisor, it turns out), so you can trust that the guy actually really knows this stuff. All of that crazy notation with the weird unbalanced brackets will start making a lot more sense very soon.

Also, just to clarify, the model taught in that course is the quantum circuit model, which is *not* what D-Wave Systems implements. D-Wave's computer can't do arbitrary computation and there's skepticism over whether they will be able to produce any speedup over classical ways to do the problem that their computer *does* solve. Actually people used to be skeptical over whether they made any use of quantum effects at all, but I believe that's mostly been resolved in their favor now. I seem to recall statements from D-Wave to the effect that the quantum circuit model is one of the worst things that ever happened to the field of quantum computation (presumably meaning that they don't believe that general-purpose quantum computers can be implemented anytime soon, and that their system is useful enough), so, there's probably going to be some fireworks there eventually.

I'm not entirely certain on how quantum information works, but as I understand it qubits don't actually hold any more classical information than classical bits do. Yes, a classical simulation of qubits takes a whole lot of classical bits - but you can't actually get classical information out of qubits without measuring them, and that collapses them into whatever state you measured them as being in, so any other "detail" is lost.

Also!!! The section on quantum networks is pretty inaccurate as well. Quantum cryptography has nothing to do with weak measurement, and it absolutely has nothing to do with the computer being "allowed" to see quantum states in a way that humans can't. At least quantum cryptography is reasonably easy to describe with a metaphor, though... but it'll be an incredibly lazy metaphor because IMO if you're actually interested you should just learn it mathematically anyway:

Alice and Bob want to decide on a common string of random bits. It doesn't actually matter what those bits are, only that both parties agree on them, and nobody else can see them - the point is that they'll be used as a shared key for doing classical cryptography with.

So, Alice makes up some bits and sends them to Bob in little trick boxes. The way a trick box works is that they have two handles and you can open them by pulling either at the top or the side. Each box can be configured by Alice to be either a top-box or a side-box - she makes a random choice for each box. If you open a top-box from the top or a side-box from the side, you get the bit that was sent; if you open a top-box from the side or a side-box from the top, you get a fresh random bit. Oh, and when you open it, the very fundamental existence of the universe conspires to irreversibly make the bit inside the one that you saw, so once you've opened the box, it's useless to guess again. And there's no way to know whether a box was made as a side-box or a top-box.

Bob receives those little trick boxes and, for each, randomly decides to open it either from the top or the side. Half of the time he gets it right and the bit he sees inside is the one Alice sent, half the time it's a random bit. Once he's opened all of the boxes, he finds out the difference simply by conferring with Alice over a public channel, where he tells which side he opened, and Alice tells which kind of box she sent. For each box, if they match, Bob accepts the bit, if not, he throws it away.

What makes this work so well for secrecy is that if there's an eavesdropper Eve in between Alice and Bob, trying to work out what the bits are, she will be found out. She can open a box and see what's inside it, and she can make more boxes and send them to Bob - but she doesn't know whether they were top-boxes or side-boxes, so if she guesses wrong, she's essentially going to be sending Bob random bits. Which means that if, at the end, Alice publicly reveals some of the bits that she sent and that Bob was supposed to receive, and they turn out not to match, then Bob will know that his guess of whether the bit was sent in a side-box or a top-box was correct - but Eve's wasn't, which implies that there was an Eve listening in. If the bits Bob received do match sufficiently well with the ones Alice published, then there was no Eve, and they can use the rest of the bits, trusting that there was no physical way they could have been intercepted in transmission.

So, yeah. Quantum stuff. Honestly, you kiiind of got most of it wrong, but hey, you've only got so much time to spend per episode. Still, it would be good to see some more research before you do the next quantum-related video.

## Comments

1✭1✭