Deutsch–Jozsa: the first quantum algorithm
The Deutsch-Jozsa problem asks whether a black-box function is constant (always outputs 0 or always outputs 1) or balanced (outputs 0 for exactly half its inputs and 1 for the other half). A classical computer must query the black box repeatedly, and in the worst case the number of required queries grows exponentially with the number of input bits. A quantum computer can answer in a single query, making this the clearest early demonstration that quantum algorithms can offer an exponential speedup over classical ones.
- David Deutsch designed the original algorithm in 1985, and Richard Jozsa expanded it in a 1992 paper published in the Proceedings of the Royal Society.
- For a two-bit input there are exactly eight valid functions: two constant ones and six balanced ones, with the six balanced cases arising from the combinatorial count of four-choose-two.
- One concrete example of a balanced function is XOR: it outputs 1 when the two input bits differ and 0 when they are the same, guaranteeing exactly half zeros and half ones across all inputs.
- The function is treated as a black box deliberately, meaning the solver has no access to the internal mapping rule and can only learn about the function by feeding in inputs and observing outputs.
Transcript
This chapter, from the episode video's captions · 1,202 words
1:14:21algorithm that really shows this okay and he designs the first quantum algorithm in 1985 and it's expanded alongside with um Richard Jose in 1992 this is the paper that comes out again proceedings of Royal Society um it's a simple enough problem that I think I could describe it in enough detail on this podcast and not lose some of the essence of what's going on in the quantum solution. Okay? And I'm going to go ahead and give you the punch line. >> It's a toy problem, >> but it's one where a classical computer would take exponentially an amount of time to get to an answer with respect to the size of the input. But a quantum computer can oneshot it.
1:15:03>> Okay. So, we're going from exponential to one shot. >> One shot. >> Okay. using a quantum algorithm. Here's the problem. Okay, so you're given a blackbox function and this blackbox function is going to take inputs of ndigit binary numbers and give back a single digit either a zero or a one. So if n is like two, it can give it it takes in as input you know either 0 0 1 1 0 1 1 and it spits out either a zero or a one. Now, in in essence, this could be any nd-digit binary number. N could be very large. So, N could be like that giant matrix of zeros and ones that goes into this blackbox function. I don't know how this
1:15:44black box function works. Okay, it's it's a black box. >> I stick an input and I get an output of either zero or one. >> This is similar to the and gate we talked about at the beginning in terms of you have two then you only have one input on the other. It's so it's not reversible. >> Yes. Yeah. This is not reversible. Yes. Very good. And an ANDgate would be like um 0 0 goes to zero. 01 goes to zero. This even worse because it only goes to one answer. >> Yeah. It only goes to one answer and no matter how big the the thing is and I don't know if it's an andgate, >> right? We Yeah. Right. Right. >> It's a black box. I don't know what it's doing in there. >> That's the point. The black box replaces this concept of an ANDgate in terms of
1:16:24being able to be well defined. >> Yeah. Andgate. I know exactly what the truth table is here. I don't know what the truth table is, right? So I want I want to make it simple. So let's just consider n equals 2. >> Okay. >> As I was saying, right? Yep. So in n equals 2, we'll go to the next overlay. So at n equals 2, there's four different numbers that I can feed in. I can either feed in 0 0 1 1 0 or 1 1. Those are going to go in one at a time into this black box. And that black box is going to make an output. And it's going to tell me, hey, if you give me this input, the output is either zero or one, depending on whatever I gave as input. I'm given another promise. Okay, I'm given a promise that this function is
1:17:05either constant or it's balanced. What do I mean by that? So, it's either a constant function in the sense that no matter what the input is, my output is always going to be zero or it's always going to be one. There's only two such functions, right? It's either all ones. So, no matter what my input is, it's it's going to give out a one. No matter what my input is, it's going to give out a zero, right? It's one of these two or it is balanced. A balanced function means that exactly half of the inputs map to zero and exactly half of the inputs map to one. There's several there's not several there's only six examples for a two cubit for a two um
1:17:45bit input like cuz you know it's it's four choose two is going to give you six. Um two of these I've described over here. There's the first one I think is like first bit only. Basically, whatever the first bit is is, that's what it's going to output. So for 0 0, the first bit is 0. This black box is going to output zero. For 0 1, it's going to output zero. For 1 0, the first bit is now one. So it's going to output one. For 1 one, it's going to output one. Notice there's two zeros that come out and there's two ones that come out of the four. >> Because the first input is is >> whatever the thing is. And the and the function doesn't even look at what the second input is. It's just like, oh, the first one is zero. I'm just going to spit that out. So that's one version of a balanced function. Another version of
1:18:27a balanced function is an exor, exclusive or, meaning the bits are different. >> So if the bits are different, I'm going to output a one. If the bits are the same, I'm going to output a zero. Notice if it's 0 0, I I output a zero because they're the same. If it's 1 one, I output a zero because they're the same. If it's 0 1 or 1 0, I output a one. Okay? So again, this is balanced because there's two zeros and two ones. There's six such functions. I've only shown you two. >> Got it? Okay. So these are two examples of >> these are two examples and here there's like a systematic rule but imagine for like n digits you don't need a systematic rule there could just be whoever designed the black box chose half of the inputs at random and be like these guys map to zero and half of the inputs these guys map to one okay
1:19:09>> it has it basically mapping key that is whatever >> yes there's a map exactly there's a mapping key that we don't know okay that's the point your job is to figure out who am I am I balanced or am I constant? I gave you two choices, right? I'm either balanced or I'm constant. And I give you this black box to play with where all you can do is put in stuff and you get out an answer. The question is, how many queries how many times do I need to press play on the black box with whatever input I give it to determine >> if it's >> if it's balanced or constant. That's the idea. That's that's the problem. Y >> So, how would I do it classically?
1:19:49>> Yep. If I if I want to do it classically, it's actually I mean there's only one choice that I have, right? It's like I feed in a number, I get an output, I use my logical brain to figure out what it is. Um,
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.