Classical vs. quantum solution
To distinguish between a constant and a balanced function classically, you must query the function's inputs one at a time. In the worst case, an adversary who knows your testing strategy can force you to check half the inputs plus one before you can be certain of the answer. For a four-input function, that means three queries are always required classically. Deutsch and Jozsa's insight is that a quantum computer can instead pass a superposition of all four inputs at once, bypassing that sequential requirement entirely.
- The best-case classical scenario is two queries: if the first two results differ, you immediately know the function is balanced without checking further.
- The adversarial framing matters: the person designing the black box can tailor it to whichever inputs you test first, making worst-case analysis the honest measure of classical cost.
- For a four-input function specifically, the classical worst-case is three queries, not four, because a third identical result rules out balanced by elimination.
Transcript
This chapter, from the episode video's captions · 499 words
1:20:04classically na what I what I do first is I just test 0 >> and suppose I get a zero >> and I test 01 and suppose I get a zero. >> I cannot claim that it's balanced or constant >> because it could be both, right? It could be that the first two go to zero and the next two go to one >> and I've only checked the first two or it could be that all of them go to zero. So I need to check that fir third >> bit string at at this point after two there are arguments that it could be constant or it could be balanced because you've not yet had enough data to deter to uh rule out one or the other. >> Exactly. So I need to do that third
1:20:45query to check I I need to check one zero. And if one zero comes out as zero, >> then I know that it's constant, right? Because because I I only have those two choices and I've already queried three and they're all the same. So it has to be constant. On the other hand, if the third one comes out to be one, then I know that it's balanced because I know that the other guy is also going to be one. I don't need to check the other guy. Right? Now, you could say, well, what if what if um you know, in the case that it's balanced and and and the first and the third inputs go to go to zero and the second and the fourth go to one, right? Um worst case scenario, what what if I chose like what if I randomly picked like the other stuff and and I
1:21:25could choose, right? Well, in the worst case scenario, the the guy who's designing the black box knows exactly how you're going to check check the first few inputs, right? Right. And so and so if if you're trying to just get like the best case scenario is I just I just pick two and I get lucky. One of them is zero and one of them is one and then I'm like oh it has to be balanced because it's definitely not constant, >> right? And so I'm done. But the the guy who's building the black box could know exactly your schema of which bits you're which bit string you're going to test >> to make it maximally difficult for you to find the answer. >> Yeah. So, so worst case scenario, you always have to do exactly half >> plus one.
1:22:06>> Yeah. >> Right. >> Yeah. Okay. I get what you're saying. >> Okay. So, I I have to do three in this case where there's four bit strings. Okay. How would I do this with quantum mechanics? With quantum mechanics, what Deutsch Joa came up with is they said actually we could pass a superposition of all four versions.
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.