How interference performs a computation
Quantum interference is what makes the Deutsch-Jozsa algorithm work. Using a four-slit analogy where crystals in the slits flip the phase of passing arrows by 180 degrees, the chapter shows that a constant function produces constructive interference at the detector center, while a balanced function like XOR produces destructive interference there. A single measurement at that center point is enough to distinguish the two cases, something a classical computer would need an exponentially growing number of queries to do.
- The crystal placement in the slit analogy directly encodes the function being evaluated: crystals sit only in the slits whose inputs map to one, so a balanced function gets exactly half the slits fitted with crystals.
- For a constant function, the direction of the final probability arrow reverses depending on whether all slits have crystals or none do, but the area of the circle, and therefore the detection probability, stays identical either way.
- Deutsch designed the algorithm specifically to prove to skeptics that a computational problem exists which a quantum computer can solve in one shot where a classical computer provably cannot.
- The reversible part of the computation, applying Hadamard gates to create superpositions and entangling the qubits, must be completed before measurement, because measurement itself is irreversible and collapses the quantum state.
Transcript
This chapter, from the episode video's captions · 1,888 words
1:36:16>> So now let's consider instead of two slits, four slits. You see where this is going? Yeah. Our our slits are the function in some sense, right? And we've we've we've created a superposition. Each of the superp positions is represented by the four holes. Okay. And I've got an electron gun. Okay. This is I think how Fineman might have like if he if if he was around to to do science communication now maybe this is how he would have done it. Right. So I've got I've got my four holes and those four holes represent the four binary digits that can go through. Okay. Now let's see
1:36:57what happens. The function itself is going to be implemented by some kind of crystal >> that I'm going to put in the in the um in those holes. Okay. >> And depending on where the crystals are, that's going to tell me which output goes to one and which output goes to zero. >> It's the idea that the crystal refracts the light. >> Yeah. Yeah. It's No, what it's going to do is flip. >> Flip. Got it. >> Okay. Whatever direction the arrow came in into that hole, it's just going to add a pi pulse. It's going to add 180°. So in this case this particular function this iteration of the function maps the first and the last 0 0 and 1 1 into zero
1:37:38>> and 0 1 and 1 0 into one. So this is the exor function that I'm looking at right now. The exor function would have the two crystals that are doing the I don't know whatever type of crystal it is but the two crystals are going to be in the second and the third slits because those are the ones that are getting mapped to one. Okay. In this case this is a balanced function right? Yeah. >> And so that's where I would but the point is somebody put the slits there with the holes and put the holes. In this case we do, right? But the now now let's go to the next one. Now suppose that it is a constant. >> Meaning either there's no crystals in either of the >> in any of the four >> fs or there's crystals in all four of
1:38:20them. >> Right? >> Okay. In that case what would happen? If there's nothing, then they would all take the red the red line. Yeah. >> And all four of the arrows would point in the same direction, right? Because they're all constructively interfering. >> This would be four pluses. >> Yeah. This would be four pluses. And and and the resulting arrow would be really long. On the other hand, if there's four crystals then I'm going to add a 180. And so, no matter where I ended up before, I I I have the 180 added by the crystal. And so, they're all going to be pointing in the opposite direction. the phase is going to be pointing in the opposite direction but the circle that I make is going to be the same >> right so I will still detect a particle
1:39:02>> this this is fascinating again in in this constant function whether either no crystals or all four crystals um our our arrow length is the same but in opposite directions >> but it doesn't matter in the context of the probabilities yes >> because the surf The C the in the Fineman construction the area of the circle will be identical. The phase direction is irrelevant in that context. >> Yes. Because the detector only cares about what is the area of the circle. Right. And so the detector is still going to register a bunch of electrons coming through. Okay. Or a bunch of photons or whatever the whatever the thing. >> And the idea is that the because it when
1:39:42it's constructive which is that center point which is a higher probability >> uh constructive interference. Yeah. It's like a constructive interference. That's why the area is so large. And then when you get further to the past the other side of the there's like a line of deconstructive interference. >> Yeah. And then Well, I mean, if I were to move the detector somewhere or the other, then one of the path lengths will be different from the others, right? And so some of the arrows will be pointing this way, but the other one that came here and traveled farther is going to like >> travel more and start like pointing in the other direction. here in this case it's like it's like those two traveled at exactly the right amount to be to be
1:40:22pointed at at in the same direction right now. So this is for a constant function. Now let's look at what a balanced function would do like the exor. >> Yep. >> In the exor the top two >> are going to have arrows pointing in one direction but because the middle two have the crystals they're going to add a phase factor and so they're going to have arrows pointing in the opposite direction. And so I'm going to get destructive interference in the middle where I once had constructive. if there was all crystals or no crystals. >> Yes. >> Right. So, if I put a detector in the middle there, >> right, and all I do is have a one shot. I send uh I I I do a oneshot and I see do I see a particle or not, >> right?
1:41:04>> That'll tell me exactly what the crystal can like what type of filter the the person has put. Is it a balanced filter with only two or is it a or is it a um a constant? Crucially, it doesn't matter where I put these crystals. As long as there's two, >> as long as there's two, two of the green arrows are going to two of the arrows are going to be pointing in the opposite direction because I've made that sign flip >> cuz the phase again doesn't matter. >> Yeah. Um, it >> like if I if I were to put the crystal on the top one, then one of the bottom arrows of the one of the bottom red arrows would flip and one of the top green arrows would flip, but at the end
1:41:44of the day, the sum of the two would still be zero. >> Yeah. Yeah. This is this is so good. And this is so good because it it goes back to what it makes me think of again, and correct me if I'm thinking about it. This gives this idea of that reversible uh function concept we talked about at the beginning, right? like we're able to take the result the arrows on the right >> and then look back to construct what the filter what the crystal construction was in the middle because we are able to look at the or am I mixing >> metaphor I think you're mixing metaphor I'm mixing >> metaphors yeah yeah the the reversible part of stuff is happening like when we implement the function itself like the
1:42:26reversible part is happening and that's when we we we we have to get into the weeds about like how we actually implement ment this like function in a quantum computer like yeah we have we need like a we need like an ancillary bit it's I think it's called an ancilla bit that like keeps track of all of the information that stuff here it's still it's still um you're still losing information though here right because there's four inputs coming in and only one like thing that I'm think like >> I got you yes no no that makes sense I got you >> yeah and like remember quantum mechanics the observation is not reversible. It destroys whatever
1:43:06thing is happening in the magic box. >> Yes. Right. And here we're doing an observation. >> And so that is definitely not reversible. >> No, that that's right. That's right. The whatever is is the reversible part's happening before we make the observation. Yeah. Yeah. The reversible part is how we implement whatever the oracle and like how we create superp positions because like we're going to start with 00 0 and then what you do is apply like a hatamard gate that will make okay now I put in a superp position of 0 and 1 0 and 1 0 and 1 and then I entangle them. So now I get all of the different products. So you can imagine for like n different binary digits, right? This is going to scale like crazy for a classical computer, but for a
1:43:47quantum computer, all I have to do is one shot. >> It's time inside the brackets of the equation that we were looking at earlier. >> Yeah. It happens inside of the you start the cubits, then you do all the nonsense. All of the nonsense >> has to be reversible, >> right? Right. >> Before we make the observation at the very end. >> No, that that makes sense. And and that's a good distinction because there there's just so many levels to this. So, thank you for that correction. And so I'm just trying to make sure I'm tracking connecting the ideas we built at the beginning and bringing them down now into but I I think the way you explain this is between looking at the math structure of balanced versus
1:44:27constant >> and then correlating it to the experimental architecture of the double slit experiment as a way to visualize the idea of what we're trying to say is happening. in the magic box. >> Yeah. Yeah. That's it's the double slit experiment is kind of showing you this interference stuff, right? I mean, in practice, of course, it's a lot more complicated, right? But um the main point that I want to say is >> the reason why the Doza algorithm works is because it uses interference. >> Mhm. >> Okay. Mhm. >> It's it's like it the the the problem itself is this kind of useless problem
1:45:07of like, oh, there's a function that's like either balanced or constant. Find out what it is. And like because it's contrived that way, right? We can use quantum mechanics to like figure it out. And part of the reason why this this was the first algorithm is because it's designed to use quantum interference, right? Deutsch Deutschin Deutsch was literally thinking about how do I prove to these people that there is a problem that exists right a computational problem that I could solve with a quantum computer in a one shot that would require a classical computer um an exponential amount of time this is a like this is a perfectly valid um problem right why you would want to solve it who knows right
1:45:48>> other than it's it's a very good mental exercise and it shows you some of the um and it and it actually proved to the world that okay there is a computational problem out there that definitely a
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.