## Saturday, August 06, 2022

### How to compute with a computer that doesn't compute

[This is a transcript of the video embedded below. Some of the explanations may not make sense without the animations in the video.]

Thanks for clicking on this video, by which you’ve ruled out a possible world in which you never watched it. This alternative world has become a “counterfactual” reality. For us, counterfactuals are just things that could have happened but didn’t, like my husband mowing the lawn. In quantum mechanics, it’s more difficult. In quantum mechanics, events which could have happened but didn’t still have an influence on what actually happens. Yeah, that’s weird. What does quantum mechanics have to do with counterfactual reality? That’s what we’ll talk about today.

I have only recently begun working in the foundations of quantum mechanics. For the previous decade I have mostly worked on General Relativity, cosmology, dark matter, and stuff like this. And I have to say I quite like working on quantum mechanics because it’s simple. I like simple things. It’s why I have plastic plants instead of a dog.

In case you were laughing, this wasn’t a joke. I actually do have plastic plants, and quantum mechanics is indeed a simple theory – if you look at the mathematics. The difficult part is making sense of it. For General Relativity it’s the other way round, and all the maths in the world won’t help you make sense of dogs.

Okay, I can see you’re not entirely convinced that quantum mechanics is in some sense simple, but please give me a chance to convince you. In quantum mechanics we describe everything by a wave-function. It’s usually denoted psi, which is a Greek letter but maybe not coincidentally also the reaction I get from my friends when I go on about quantum mechanics.

We compute how the wave-function behaves from the Schrödinger equation, but for many cases we don’t need this. For many cases we just need to know that the Schrödinger equation is a kind of machine that takes in a wave-function and spits out another wave-function. And the wave-function is a device from which you calculate probabilities. To keep things simple, I’ll directly talk about the probabilities. This doesn’t always work, so please don’t think quantum mechanics is really just probabilities, but it’s good enough for our purposes.

Here is an example. Suppose we have a laser. Where did we get it from? Well, maybe it was on sale? Or we borrowed it from the quantum optics lab? Maybe the laser fairy brought it? Look, this is theoretical physics, let’s just assume we have a laser, and not ask where we got it, okay?

So, suppose we have a laser. The laser hits a beam splitter. A beam splitter, well, splits a beam. I told you, this isn’t rocket science! In the simplest case, the splitter splits the beam into half, but this doesn’t have to be the case. Could also be a third and two thirds or a tenth and nine tenth, so long as the fractions add up to 1. You get the idea. For now, let’s just take the case with a half-half split.

So far we’ve been talking about a laser beam, but the beam is made up of many quanta of light. The quanta of light are the photons. What happens with the individual quanta when they hit the beam splitter? The quanta are each described by a wave-function. Did I just hear you sigh?

The Schrödinger equation tells you something complicated happens to this wave-function, but let’s forget about this and just look at the outcome. So we say, the beam splitter is a machine that does something to this wave-function. What does it do?

It’s not that the photon which comes out of the beam splitter goes one way half of the time and the other way the other half. Instead, here it comes, the photon itself is split into half, kind of. We can describe this by saying the photon goes in with a wave-function going in this direction. And out comes a wave-function that is a sum of both paths.

I already told you that the wave-function is a device from which we calculate probabilities. More precisely we do this by taking the absolute square of the weights in the wave-function. Since the probabilities are ½ for each possibility, this means the weight for each path in the wave-function is one over square root two. If the beam splitter doesn’t split the beam half-half but, say 1/3 and 2/3, then the weights are square root of 1/3 and square root of 2/3 and so on.

We say that this sum of wave-functions is a “superposition” of both paths. That’s the simple part. The difficult part is the question whether the photon really is on both paths. I’ll not discuss this here, because we just talked about this some weeks ago, so check out my earlier video about this.

That the photon is now in a superposition of both paths tells you the probability to measure the particle on either path. But of course if you do measure the particle, you know for sure where it is. So this means if you measure the photon, it’s no longer in a superposition of both paths; the wave-function has “collapsed” on one of the paths like me after a long hike.

As long as you don’t measure the wave-function this beam splitter also works backwards. If you turn around the directions of those two photons, for example with mirrors, they’ll combine to a photon on one path. You can understand this by remembering that the photon is a wave, and waves can interfere constructively and destructively. So they interfere constructively on this output direction, but destructively on the other. Again, the nice thing here is that you don’t actually need to know this. The beam splitter is just a machine that converts some wave-functions into others.

Let’s look at something a little more useful. We’ll turn this around again, put two mirrors here and combine the two paths at another beam splitter. What happens? Well, this lower beam splitter is exactly the turned-around version of the upper beam splitter, which is what we just looked at. The superposition will recombine to one path, and the photon always goes into detector 2.

Well, actually, I should add this is only the case if the paths are exactly the same length. Because if you change the length of one path, that will shift the phase-relations, and so the interference may no longer be exactly destructive in detector 1. This means a device like this is extremely sensitive to changes in the lengths of the paths. It’s called an interferometer. If you change the orientation of those mirrors and move the second beam splitter near the first, then this is basically how gravitational wave interferometers work. If a gravitational wave comes through, this changes the relative lengths of the paths and that changes the interference pattern.

Okay, so we have an interferometer. It’s called a Mach-Zehnder interferometer by the way. Now let’s make this a little more complicated, which is what I said last time when I bought the 5000 piece puzzle that’s been sitting on the shelf for 5 years, but luckily we don’t need quite as many pieces.

We add two more beam splitters and another mirror. And then we need a third detector here. And, watch out, here’s an added complication. Those two outer beam splitters split a beam into fractions 1/3 and 2/3, and those two inner ones 1/2 each. Yeah, sorry about that, but otherwise it won’t work.

What happens if you send a photon into this setup? Well, this part that we just added here, that’s just another interferometer. So if something goes in up here, it’ll come out down here. So 2/3 chance the photon ends up in detector 3. And a 1/3 chance it goes down here, and then through the second beam splitter. And remember this splitter splits 2 to 1, so it’s 2/9 in detector 2 and 1/9 in detector 1.

Now comes the fun part. Suppose we have a computer, a really simple one. It can only answer questions with “yes” or no”. It’s a programmable device with some inner working that doesn’t need to concern us. It told me we can call it James, and it actually would prefer that we don’t ask any further questions. Only thing we need to know is that once you have programmed your computer, I mean James, you run it by inputting a single photon. If the answer is “yes” the photon goes right through, entirely undisturbed. If the answer is “no”, the photon just doesn’t come out. Keith Bowden suggested one could do this by creating a maze for the photon, where the layout of the maze encodes the program, though I’m not sure how James feels about this.

So let’s assume you have programmed the computer to once and for all settle the question whether it’s okay to put pineapple on pizza. Then you put your computer… here. What happens if you turn on your photon source this time? If the answer to the question is “yes, pineapple is okay” then nothing happens at the computer, and it’s just the same as we just talked about. The photon goes to detector 3 2/3 of the time, and in the other cases it splits up between detector 1 and 2.

But now suppose the answer is “no”. What happens then? Well, one thing that can happen is that the photon goes into the computer and doesn’t come out. Nothing ever appears in any detector, and you know the answer is “no, pineapples are bad, don’t put them on pizza”. This is the boring case and it happens 1/3 of the time, but at least you now know what to think about people who put pineapple on pizza.

Here is the more interesting case. If the photon is in the inner interferometer but does not go into the computer and gets stuck there, then it goes the upper path. But then when it reaches the next beam splitter, it has nothing to recombine with. So then, it gets split up again into a superposition. It either goes into detector 3, this happens 1/6 of the time, or it goes down here and then it recombines with the lower path from the outer interferometer. This happens in half of the cases, and if it happens, then the photon always goes to detector 2, and never to detector 1. This only comes out correctly if the beam splitters have the right ratios, which is why we need this.

Okay, so we see the maths is just adding up fractions, this is the simple part. But now let’s think about what this means. We have seen that the only way we can measure a photon in detector 1 is if the outcome of the computation is “yes”. But we have also seen that if the answer is “yes” and the photon actually goes through this inner part where the computer is located, it cannot reach detector 1. So we know that the answer is “yes” without ever having to run the computer. The photon that goes to detector 1 seems to know what would have happened, had it gone the other path. It knows its own counterfactual reality. In other words, if we had a quantum lawn then it still wouldn’t be mowed, but it’d know what my husband does when he doesn’t mow the lawn. I hope this makes sense now.

And no, this video isn’t a joke, at least not all of it. It’s actually true, you can compute with a computer that doesn’t compute. It’s called “counterfactual computation”. The idea was brought up in the late 1990s by Richard Josza and Graeme Mitchison. The example which we just discussed isn’t particularly efficient because it happens so rarely that you get your answer without running the computer that you’re better off guessing. But if you make the setup more complicated you can increase the probability for finding out what the computer did without running it.

That this indeed works was demonstrated in 2006 where the computer performed a simple search algorithm known as Grover’s algorithm. This doesn’t tell you whether pineapple on pizza is okay, but if you have an unsorted database with different entries, this algorithm will tell you which entry is the same as your input value.

Now, let me be clear, this is a table-top experiment that doesn’t calculate anything of use to anybody. I mean, not unless you want to count the use of publishing a paper about it. The database they used for this experiment had four entries in terms of polarized photons. You might argue that you don’t need an entire laboratory to search for one among the stunning number of four entries, and I would agree. But this experiment has demonstrated that counterfactual computation indeed works.

The idea has led to a lot of follow-up works, which include counterfactual quantum cryptography, and how to use counterfactual computation to speed up quantum computers and so on. There is a lot of controversy in the literature about what this all means, but no disagreement on how it works or that it works. And that pretty much tells you what the current status of quantum mechanics is. We agree on how it works. We just don’t agree on what it all means.