The biggest misconception about quantum computers
The popular claim that quantum computers solve problems by trying every solution in parallel is misleading. If that were literally true, quantum computers would solve every problem instantly, collapsing P vs NP to constant time, which they cannot. Quantum speedups only apply to specific problem types that let you exploit the mathematical properties of quantum mechanics, and encryption is cited as one of the rare cases where the parallel-processing intuition is actually close to accurate.
- The Deutsch-Jozsa algorithm is the example the hosts plan to use as a teaching tool, chosen because it is simple enough to explain on a podcast even though it has little practical use beyond illustration.
- Shor's algorithm will also be mentioned but not explained in depth, because it requires a separate full episode.
Transcript
This chapter, from the episode video's captions · 366 words
8:43used um that you know quantum quantum computing tries every solution in parallel and it finds the right answer. And I mean like kind of but like honestly not really. Okay? Because if that were actually true, if quantum computing was just like finding was was like doing all of the solutions in parallel, then every single problem ever could just be done on a quantum computer in parallel, right? Like every problem has a myriad of possible solutions. Okay, just try all of them in parallel and then what? You just solve everything. So what? P doesn't equal NP equals constant, right? Just constant time. You press it on a quantum computer, you're done. Um this is a big
9:24argument when people talk about like encryption specifically. Yeah. And it's like, oh, what would take a trillion years >> can be run in parallel on a quantum computer and can be done in >> Yeah. >> seconds. and encryption is maybe the only thing >> where it's true >> where it's actually true. Everything else though uh maybe not right so that's that's kind of what I'm trying to get into it. What ends up happening is there's only very specific types of questions where you can exploit the the properties of quantum mechanics. Okay. And um in this episode we're going to explore one of the famous algorithms called the Deutsch Joa algorithm. It's probably the simplest algorithm to understand. I don't think it's very useful
10:05except as a teaching tool to understand how quantum algorithms actually work. Okay, it's simple enough that I think I could do a good job on this podcast to explain at least some of the magic behind um why what's actually happening and we will talk about Shor's algorithm. Don't worry about it. But um we're not going to like go into detail because that's going to require another full deep dive. I just have to say Deutsch Deutsch Joseph sounds like a starter for Liverpool. >> It totally does. Yeah. Um so so that's the preview. >> Yep. >> All right. And now let's get into it. We begin in 1964 with the formulation of Bell's theorem.
From How Quantum Computing Actually Works (Part 1)
Part I of our quantum computing deep dive traces the field from Bell and Feynman to Deutsch and Shor—and explains what quantum computers actually do differently from classical machines.