How to program a quantum computer - Part 2
Battleships with quantum measurements
This article has ‘Part 2’ in the title for good reason. There was a Part 1, in which we looked at the basis of writing and running quantum programs.
I’m going to assume that you read at least the first half of that before coming here.
Most of the actual coding knowledge you need for this tutorial was covered last time. This article will mostly focus on some of the stuff we can do with these commands.
How to look at qubits
In programs we have variables. At some point we will need to look at them.
This could be at the end of the program when we get the result. It could also be during the program, when we use the variable as part of a conditional statement. Either way, it happens a lot. And when programming non-quantum variables, it is a fairly unremarkable process.
This is because non-quantum variables have definite values. Looking at them just tells us, or other parts of the program, what the value is. Nothing about the variable itself will change.
This is not true of quantum variables, which can have indefinite values. They can be in a so-called quantum superposition, which lets them hold multiple contradictory values at once.
When we look at them, they have to give up on all this strangeness. They are forced to take a definite value, and then tell us what that value is. Since this is not just a passive process, it needs careful consideration. And it needs a name. We call it measurement.
In this article we will explore some of the properties of measurement. We’ll also use it as the basis of a game mechanic, and see exactly how to program it on a quantum computer. In the end we’ll have a new version of Battleships.
Mapping the world of a qubit
Before we really get started on measuring qubits, we should try to understand their world a little more. The best way to visualize a qubit is using a sphere. Any possible qubit state corresponds to a point on the surface of this sphere.
The states 0 and 1 are completely different, completely disjoint. They are the opposites of each other. They will therefore live on opposite sides of the sphere. We usually choose to put 0 at the north pole and 1 at the south.
Let’s pick a point that is equidistant between the two, somewhere along the equator. It can be anywhere you like. We’ll call it +. Why +? Why not?
The + state also has an opposite, as different from it as 0 is from 1. This lives on the opposite side, which will also be a point along the equator. We’ll call this state -.
With the points 0, 1, + and - now defined, another couple of points are begging for our attention. These are the ones that are equidistant between 0 and 1, and also equidistant between + and -. We’ll call these ↻ and ↺. Why? Because I once saw a guy who didn’t write The Da Vinci Code doing it, and I liked it.
We’ve now mapped the world of the qubit with six points. These are by no means the only ones we’ll ever use. They are simply the landmarks by which we will navigate.
Measuring a qubit
Any measurement is simply us asking a qubit to choose between two opposite points on the sphere.
The classical example is for our favourite pair of opposite states: 0 and 1. We ask the qubit to choose between the two. If it was already in state 0, it’ll go for 0. A qubit in state 1 will similarly give the result 1. For any other state, the outcome will be random, with the closest option being the most likely.
On the equator, it’s a 50/50 chance either way. So if our state was + or -, and we then ask whether it is 0 or 1, it will have to choose one or the other with equal probability.
The measurement based on 0 and 1 has a few names. We can call it a 0/1 measurement, for obvious reasons. It is also called a Z basis measurement, because of the special relationship that the 0 and 1 states have with an operation called z. More on that story another time.
The next most popular kind of measurement is the one for + and -. I’ll call this a +/- measurement, but you might also see it called an X basis measurement. It works the same way as before, but just for + and - instead of 0 and 1. So if you start with a qubit in state + and do this measurement, you’ll get the result +. But if you start with 0 and ask the same question, it will choose randomly.
We also have a measurement for the weird arrow things. This is called a Y basis measurement. No one likes Y basis measurements.
A bit is just a bit, even when it’s quantum
Measurement of non-quantum objects is a passive process. It tells you what the object is doing, but it doesn’t change it in any way. Measuring quantum things is very different. Quantum measurements don’t just change our knowledge about the variables. They change the variables themselves.
Suppose you have a qubit in state +, and then ask it whether it is 0 or 1. When it gives you a random result, it isn’t just fobbing you off. It isn’t telling you some nonsense because you asked the wrong question. Once it gives you a result, it will stick with it. It’s value will change to reflect the answer. If it tells you 0, it will be 0 for evermore (or until you mess with it again, at least). It will forget that it was ever +.
This means that a qubit can only ever be sure of its result to a single measurement. If it knows definitely whether it is 0 or 1, it is completely uncertain of whether it is + or — , and also completely uncertain whether it is ↻ or ↺. A qubit only has a limited amount of certainty to go around, limited by Heisenberg’s uncertainty principle.
This means that we only ever get one shot at getting information from a qubit. Once we extract a single binary result, everything the qubit ever knew before the measurement is forgotten. It only remembers the result it gave us. And so, despite the infinite number of possible qubit states, we can only ever extract a single bit of information. That’s why we think of it as the quantum version of a bit, rather than a quantum float or quantum 3 vector, etc.
The game mechanic
We are going to make a Battleships variant in which there will be two types of attack: bombs and torpedoes. Only one successful attack will be needed to sink a ship, but getting a successful attack is not always so easy. Some ships have such great defence against aircraft that no bomb will ever get near them. Others are great at repelling torpedoes.
To implement this on a normal computer, we could define two boolean variables for each ship. One would tell us whether the ship is immune to bombs, and the other for torpedoes. These can then be checked during attacks to see whether the ship sinks or not.
If this was the the implementation we use, it would be theoretically possible for a ship to be immune to both types of attack. This would be poor game design, since it makes it impossible for one player to win. A good implementation would need to prevent there being any indestructible ships.
One way to avoid making such ships is with a few simple lines of code. That’s not really our style, though. Instead, we’re going to fix it with quantum mechanics!
Specifically, we will try to squeeze these two booleans into a single qubit. Since they won’t quite fit, we’ll get some interesting quantum behaviour. This will add some interesting gameplay to the game, as well as preventing any ship from being indestructible.
We’ll implement this by associating a bomb attack with a 0/1 measurement. If we get the result 1, we say that the ship has sunk. For 0 we deduce that the ship is immune to bomb attacks. For torpedoes we instead do a +/- measurement, with - implying destruction and + implying immunity.
This method makes it impossible for a ship to be definitely immune to both types of attack. If we find out that an enemy ship is immune to bombs (i.e., its state is 0), we know that it must be completely uncertain about torpedoes (the outcome of a +/- measurement). Since a bomb attack would certainly fail, we should therefore attack with torpedoes next.
It might then turn out that the torpedo attack fails (the state becomes + after the +/- measurement). The ship would decide that is is definitely immune to them, and any further torpedo attack would fail. But all hope is not lost. By becoming certain about torpedoes, it has become uncertain about bombs. Attacking with them next (making a 0/1 measurement) could lead to victory.
If the bomb attack doesn’t succeed, we go back to torpedoes, and so on. The best tactic is to keep switching between the two until the ship finally sinks.
We’ll start the ships off as being uncertain about their immunity to both attacks. This can be done by initializing the qubit in one of the Y basis states. Let’s go for ↻. This is actually a state we met in Part 1, namely u3(0.5*pi,0,0) 0, so we already know how to make it.
Dealing with short-lived qubits
Implementing the game on a quantum processor is not going to be as easy as we might hope. We’ll take a look at all the problems that will get in our way, and see how to get around them.
Suppose a ship gets attacked by a bomb and survives. Then in the next round it gets hit by a torpedo.
If the game was run on a normal computer, and was simulated using normal bits, implementing this would be quite straightforward. The ship would be initialized when the game begins, and then wait around in memory until the player decides what to do with it. Once the player sends a bomb, the corresponding operations would be applied to see whether it is destroyed. If it survives, it waits again until the next attack.
This won’t work for us. Qubits can’t sit around waiting for human timescales. A few seconds are more than enough time to for them to crash and burn, at least with current technology.
The alternative is to run a new quantum process every time an attack is made. The first job will be initialized with the ↻ state, so that the results will be random for both a 0/1 measurement (bomb attack) or a +/- measurement (torpedo attack). The result of the measurement is then recorded and stored in memory on the normal computer. When the next attack happens, another job is created to see what happens. It will be initialized with the result of the last measurement, and so it continues.
Doing a +/- measurement
So far I’ve written a whole load of words, but not a single line of code. Let’s start by recalling how a 0/1 measurement is implemented in QASM code.
measure q[0] -> c[0];The role of c[0] here important to revisit. It is the output of the measurement process. It is the normal bit on which the result of the measurement is stored. For a 0/1 measurement the result is 0 or 1.
This is all pretty straightforward for a 0/1 measurement. But it’s +/- measurements we are looking at now. How do we get the information out of one of them?
We’ll still want to store the result in a normal bit c[0]. Since it is a normal bit, it has no knowledge of the strange states + and -. It knows only normal binary. We therefore choose to report the result + as c[0]=0, and - as c[0]=1. The fact that these will look the same as the results of a 0/1 measurement won’t be a problem. As in any computer program, we should know what we have programmed, and so we should know how to interpret the results.
Now we know how to get the results out of a +/- measurement. But we haven’t yet found out how to actually do one. This is because we need to be sneaky about it. We need to hack the process that does 0/1 measurements and made it do a +/- one instead.
The key to our hack is an operation called the Hadamard. Applying this to a qubit q[0] in QASM code looks like this.
h q[0];The command we use in Python to add this line to a QASM file called gridScript is
gridScript.h(q[0])The effect of the Hadamard is to swap Z basis states with X basis ones and vice-versa. It is a rotation of the Sphere that moves the turns a qubit state 0 into a +, and + to 0. Similarly, 1 is rotated to - and vice-versa.
This means that story we can tell about a qubit in terms of 0 and 1 before the Hadamard, we must tell with + and - after it. And any story of + and - becomes one of 0 and 1.
This is exactly what we need. It means that a+/- measurement on a qubit q[0] can be done by the following QASM code.
h q[0];
measure q[0] -> c[0];
h q[0];To see why this works, let’s go through a few examples. The qubit q[0] will start off freshly declared in each, and so will be in its default initial value of 0.
Example Zero:
measure q[0] -> c[0];The qubit starts off in the state 0. It is asked whether it is 0 or 1 and tells c[0] the answer. The result will always be c[0]=0.
Example One:
x q[0];measure q[0] -> c[0];
The qubit starts in state 0 and then gets rotated to 1. It is then asked whether it is 0 or 1. It always answers 1.
Example +:
h q[0];measure q[0] -> c[0];
The qubit starts in state 0 and immediately gets rotated to +. It is then asked whether its state is 0 or 1. It randomly chooses one or the other, and its state is updated with the answer.
Now we’ve done a few trivial examples, let’s do something more complex.
Example ++:
h q[0];h q[0];
measure q[0] -> c[0];
h q[0];
The qubit starts in state 0 and then gets rotated to +. After that, there are two equivalent ways that we can continue the story.
One is to say that the three final lines collectively make an +/- measurement. They ask the qubit whether it is + or -. For + they return the result c[0]=0, and for - they return c[0]=1. Since the qubit goes into the measurement with state + in this example, it is always measured as a +. It therefore comes out of the measurement still in this state.
For the other story we look at the effects of the lines one-by-one. The second Hadamard undoes the effect of the first, and so rotates the qubit back to state 0. It is then asked whether its state is 0 or 1, and so always answers 0. A further Hadamard rotates it again to +.
Both stories agree on the observable effects. They agree that the output c[0] will always be 0, and they agree that the qubit state at the end will be +. They just disagree on how it happened. Both interpretations are equally valid.
If you want some jargon to look things up on Wikipedia, these are examples of the Schrödinger and Heisenberg pictures of quantum mechanics.
Example +1:
x q[0];h q[0];
measure q[0] -> c[0];
h q[0];
Here is another example for which we have two equivalent stories. We can say that q[0] starts off as 0 and then gets rotated to 1. This is then rotated t0 - before going through a 0/1 measurement. It randomly decides one or the other, gives the output c[0]=0 or c[0]=1 and has its state updated accordingly. If it decided 0, the final Hadamard rotates it to +. Otherwise it will end up as -.
Alternatively we could say that after being rotated to 1, the qubit goes through a +/- measurement. It randomly decides between these two options, giving the output c[0]=0 for + and c[0]=0 for -. The state is updated accordingly, ending up in either the state + or -.
Again, these two stories are equally valid and agree on all observable effects. If we want to think of the three lines
h q[0];
measure q[0] -> c[0];
h q[0];as an +/- measurement, we are free to do so. If we want to think of it as a Hadamard followed by a 0/1 measurement followed by a Hadamard, that’s fine too.
There’s one important thing to note before we move on. IBM’s API doesn’t currently let us do anything to a qubit after we’ve measured it. This is not a general rule for quantum computers. Usually we’d expect to be able to keep measuring and manipulating qubits for as long as we’d like. But we can’t do it at the moment.
This doesn’t pose us any problems. Since qubits can’t sit around while players make choices anyway, we already have to completely recreate the state after each measurement round. The second Hadamard will effectively turn up in the next job, acting on the reincarnated version of the state.
All other possible measurements can be achieved by similar hacks. We just need to do some operations beforehand to cue up our alternative measurement, and then (if the API allows) do the opposite operations just after.
Dealing with errors
Current quantum technology is not perfect. The qubits don’t always do what they should. If your qubit is 0 and you make a 0/1 measurement, the result should always be 0. Always. But with current quantum devices, there is a chance it’ll be 1. It might be because an x operation snuck in while we weren’t looking. It might be because the measurement is lying to us. Events like these are rare, but they happen.
There are two ways we might deal with the errors. One is to ignore them. We can write them in to the narrative of the game. There are great storms upon the sea. These sometimes lead a ship to be destroyed by an attack even if it is immune. Or surviving an attack that should have destroyed it.
The second way to deal with errors is to try to remove their effects. If many qubits were available, we could do this with quantum error correction. Unfortunately, that’s still a few years away.
Instead we’ll do some statistics. For that we need probabilities, which we get by running each job many times and seeing what how often each possible result comes up.
In the noiseless case, the probabilities would all be 0%, 100% or 50%. A result is either impossible (like getting a 1 if the state is 0), certain (like getting a + if the state is +) or completely random (like getting a 0 when the state is +).
Noise will mess these up a bit. When we do a 0/1 measurement of a 0, we might find that the result 0 occurs only 98% of the time, with 2% going for 1 instead. To correct for this we will do something fairly arbitrary. We will decide that anything with less than a 5% probability should never have happened. Anything with more than a 95% probability should have been certain.
Putting it all together
This article has covered the broad strokes of the game mechanic for this version of Battleships, and how to implement it with a quantum computer. Rather than go through all the nitty-gritty details here, I’ll leave that for the comments in the actual source code.
If there is anything you think needs more explanation, feel free to let me know.
