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

- 6.1K All Categories
- 5.5K Nerdfighteria
- 250 Rules and Support
- 242 John's Books
- 515 Gatherings and Events
- 45 VidCon
- 29 LeakyCon
- 152 United States
- 35 Canada
- 86 Europe
- 22 Asia
- 29 Australia/New Zealand
- 9 Central/South America
- 5 Africa/Middle East
- 5 Everywhere Else
- 1.2K Projects, Creations, and Brain Crack!
- 31 Nerdfighter Writing Club
- 3.1K General Discussion
- 352 TV/Movies
- 330 Books & Literature
- 276 Music
- 192 Youtube
- 226 Gaming
- 69 Sports
- 51 Comics
- 185 Politics & Current Events
- 397 Forum Games
- 101 Not English
- 6 Dansk
- 15 Deutsch
- 11 Español
- 9 Français
- 4 Nederlands
- 2 Norsk
- 4 Português
- 3 Svenska
- 834 Video Discussion
- 156 Vlogbrothers
- 68 Crash Course
- 10 History
- 3 Science
- 41 SciShow & SciShow Space
- 1 Animal Wonders
- 3 The Art Assignment
- 7 The Brain Scoop
- 2 Emma Approved
- 65 HankGames
- 1 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✭It's also worth noting that V&V is typically >25% of the R&D cost of projects like jets and missiles.

The D-Wave can get you quantum speedup for a range of tasks that humans are good at, but that classical computers (the digital ones, at least) are bad at. I have my own suspicions about the physical reasons for this, but suffice it to say that most of our cognition boils down to running a single algorithm that doesn't scale well on any of the hardware we've tried so far. Historically, we solved problems that required this algorithm (and, pre-digital revolution, problems requiring any kind of algorithm) by coming up with a cultural role and sticking a person in it (painter, blacksmith, photographer, architect, hunter, gatherer, etc.). When cheap digital microprocessors became ubiquitous they didn't fulfill the

corecomputational requirements that had necessitated the creation of these roles, but they did speed up the rate at which old roles were replaced by new ones. This is because much of the instruction and training that defined previous roles involved getting people to do stuff that computers are naturally good at (hippies call this "left brained nincompoopery") and as computers got good at making computers gooder (Moore's law and such) cultural roles were more frequently changed to continue making efficient use of the capacities of the new machines.This would be fine, except someone along the way (probably a compsci major) decided that every practical problem of human importance

mustbe solvable with a turing machine, and we merely have yet to find all the proper algorithms for doing so (i.e. either P=NP or nothing in NP is practical). This is an absurd and silly belief (biology and physics are rife with examples of classically impracticable stuff with real-world applicability) but it's also awidespreadbelief, so most people assume digital systems will be the only places where quantum speedup is useful. People don't generally think of image recognition when they hear of quantum computers, and when they do it's always in terms of the most common types of classical algorithms that already perform the same task (as opposed to an annealing approach, quantum or otherwise).This lecture Q&A (3/5/13) has a short summary of some of the more recent evidence of entanglement in a D-Wave chip.

Edit: PunctuationEdit 2: /r/dwave has more info on AQCEdit 3: Added link to Penrose's lecture at Google, Dr. Lidar's lecture at USC, and Geordie's lecture at Caltech