Quantum Battleships | A Classical Game on a Quantum Computer!

When Battleship was first introduced in 1967, it soon became a classic game that everyone new about. Ever since this old-fashioned board game was released, there have been several adaptations to it. Whether it was adding lights and sound effects, or creating it in video game form, or even basing a movie off of it, this game was getting better and better!

But then someone did something different. They made another version. A quantum version.

Introducing Quantum Battleships!

 Yes, someone put it on a quantum computer!

If you don't know what a quantum computer is or how they work, click here. Now assuming that you got the gist of things, let's learn how to code a Quantum Battleship game!

Click here to access my code for the game. This article is going to walk you through what's going on within it and you can copy and paste it to run the game on your own computer.

Now before we start programming, we need to have a good place to code. I recommend using the Trinket platform but you can also use the Anaconda distribution too. Now let's have a look at my code!

Lines 1-10 are just importing all the necessary files. Lines 12-179 are defining all the functions. A function, in simple terms, is a reusable piece of code that gives different results based off of the inputs one puts in it. In our battleship program, examples of functions include ask_for_ships, ask_for_bombs, and display_grid. We'll talk more about these later on.

Now that we have gotten all of our functions set up, we need to call them. Lines 184-188 are calling some of the functions.

On line 194, we have this: bomb = [ [0]*5 for _ in range(2)] . This is creating an array, which is a group of values defined under one variable. For example, say we have a meals variable and within that variable there is an array of [salad] [beef] and [egg]. [salad] is defined as 1, [beef] is 2, and [egg] is 3. So, if we do this: print meals[1] , it will call the value defined as 1 within the array and print it, and in this case will print salad. In our example above, we have the bomb array, and within it is this: [0]*5 causes 5 "values" (in this case coordinates), initialized at zero, to be made. I visualize it like this:

We then get for_in range(2) , which says FOR those values, apply range(2). This causes the values above to double and "range out" by 2 like this:

This represents bomb[player] [position] in the code This array shows where each player places their bomb. The positions of where the bombs can be placed (the 5 values) are all initialized at 0 but are changed to the position the player inputs. If what the player puts in is not a valid position, the computer will say "That's not a valid position. Try again." Keep in mind though that bomb[player] [position] only represents this grid for one player, not both player one and 2 at the same time (as a side note, in the program, player 1 is represented as player 0 and player 2 is represented as player 1. That's just how python functions with numbers!).

In general, this array acts as a grid to place the bombs. There is another array above in the code in the ask_for_ships function: shipPos = [ [-1]*3 for _ in range(2)]. This creates another grid like this:

This represents shipPos[player] [position]. There are three values in this case because you are only allowed to place 3 ships down. They are initialized to [-1] because [-1] is an impossible state that the ships can't be in. They can be changed once the player's coordinates are in, however if someone puts in something that doesn't make sense, it will stay at -1, and the computer will know that something is wrong.

Now I want to make something clear that is very important: Within this program, there is just one grid, not 2, with one of them having 3 values and the other having 5. The grid that has the 5 values is created when doing bomb = [ [0]*5 for _ in range(2)]. You might be thinking but isn't the ask_for_ships function written earlier up in the code and therefore the 3 value grid created first? It does say in it if (position in [0,1,2,3,4]) do bla bla bla. Where does it create those 5 values? Well, those numbers don't represent coordinates. At least not yet. The code is just asking you to input a number. Later on in the code, once the bomb = [ [0]*5 for _ in range(2)] is written it will understand what the values are and be able to turn them into points on the array grid. So it's all just one grid. When the 3 value grid is "created", it is not creating a whole new grid, it is just saying, on that 5 value grid, I am restraining you to place your ships in 3 coordinates. The 3 grid is also called after the 5 grid in the later parts of the code.

Now before moving on, I just want to go into a bit more detail about why and how the code only allows 3 ships to be put down. Also, if you run the completed program, you will see that you are allowed to put down only one bomb at a time. I'll go over why this is too.

Starting with the former, the code says in the ask_for_ships function that the amount of ships you have to place is [0, 1, 2]. You have to use all three of these ships before you can move on. The computer is going to continue to loop over this certain part of the program and ask for a position for each ship, and keep asking until a valid answer is given.

               choosing = True

Once choosing is satisfied and all the ships [0, 1, 2] have been placed, choosing will be set to False and move on with the program.

When placing bombs however, the computer is going to continue looping over the code and keep asking until one valid answer (position for a bomb out of the five values) is given.

       choosing = True

Once choosing is satisfied and the one bomb is placed, it will also set choosing to False and move on with the program.

Now let's move on.

On line 197, it says shots = 1024. This is going to be a bit hard to explain at this state of the code, but it will be important to know for later on.

On line 205, it says bomb = ask_for_bombs( bomb ).  This is basically saying put the bomb array (what I just talked about bomb = [ [0]*5 for _ in range(2)] ) from above as an argument for the ask_for_bombs function. The function will use this array and do something with it (think about it like this: the function is like the car without the fuel and the argument is like the gas. The function is the frame and the argument is what powers it up). This is all then stored under a variable also called bomb.

We're now going to get into the quantum aspects of the code. Lines 208-216 say this:

The for player in range(2) states that two quantum program will run, each simulating the action on the grid of one player. The array qc will be used to hold these programs.

We then define all the bits we’ll need: quantum and normal (classical). q represents the qubit register or QuantumRegister, which is just a group of qubits in one system. There are 5 of them in this register. We refer to each of them as q[0]. All the qubits in this register are initialized at state 0, which is what we want. We also created a ClassicalRegister (represented by c), which is the same thing as a quantum register except it stores regular bits instead of qubits. We created this because once the qubit values are measured at the end of the code, they're "projected" onto a classical register, making it look like readable, normal information to humans.

We also created a QuantumCircuit which contains both the quantum and classical registers. Once we have the values that we need, it will be appended to the qc array. The program for the grid of a given player can be represented as qc[player] .

Before we move on, we need to understand how quantum NOT gates work.

Just as a review, a NOT gate turns a qubit from |0> to |1> and vice versa. When coding, we can represent a NOT gate in many ways, but the way we're going to it today is by writing this:

This looks kinda complicated, but we don't have to understand it fully. All that we got know from it is that it allows to not do full NOT gates. It can also do half NOT's, third NOT's, quarter NOT's, and so on.

In this current set up, we have math.pi, which represents a 180 degree turn. If we visualize this on the Bloch Sphere, a 180 degree turn would go from |0> to |1> (AKA, a full NOT gate).

We can represent a half NOT by replacing frac with 0.5, because 0.5 * math.pi (or 180 degrees) is equal to 90, or a 90 degree turn (half of a full NOT). This same principle can be applied to other types of non-full NOT's.

Something interesting is when using partial NOT gates on a qubit, it will put that qubit in a superposition state. For example, placing a half NOT on a qubit will make it: 1/√2 |0> + 1/√2 |1> or 50% |0> and 50% |1>.

On lines 225-229, it says:

The for ship in [0, 1, 2] is self-explanatory. It's just saying FOR the three ships you placed down, do the following.

We then have:

if ( position == shipPos[player] [ship] ): 

frac = 1/(ship+1)

This is saying that if position, which describes where the bomb was placed, was placed in shipPos[player] [ship], which represents the array for each of the player’s ships were located, set frac equal to 1 divided by ship, which has the number location of which ship out of the [0, 1, 2] got hit, and add 1 to the ship value.

After that we have:

qc[player].u3(frac * math.py, 0.0, 0.0, q[position] )

This says for whichever player in the qc array, either player 1 or player 2, apply a full NOT gate if frac equals 1, a half NOT if frac equals 0.5, and a third NOT if frac equals 0.333333 repeating. You can tell what frac is equal to from above. If the bomb hit ship 0, add 1 to that and then divide by 1. So 0 + 1 = 1 and then 1/1 = 1. One represents a full NOT gate. When a qubit is in state |0>, the ship is intact. When in |1>, the ship is destroyed. In this case with the full NOT gate, the first ship only needs 1 bomb to destroy it (1 NOT to turn it from |0> to |1>). For ship 1: 1 + 1 = 2, 1/2 = 0.5. 0.5 represents a half NOT gate. A half NOT means that in order to fully change the qubit from |0> to |1>, and in this case destroy ship 2, it will take two bombs (to half NOT's). For ship 2, 2 + 1 = 3, 1/3 = 0.3333333 repeating. 0.33333333 represents a third NOT gate. A third NOT means that in order to fully change the qubit from |0> to |1>, and in this case destroy a ship, it will take three bombs (three third NOT's). 

Now that we've applied all the gates, we're now going to measure the states of the qubit.

On lines 232-233, it says:

The for qubit in range(5): part is saying for those 5 qubits, do the following. The  qc[player].measure(q[qubit], c[qubit]) part is saying for whichever player in qc, measure the 5 qubits in the QuantumRegister and copy them over to the ClassicalRegister so people can actually be able to understand it. 

So far out of this code, the players will be able to pick ships, place bombs on their opponent's ships, and see the results (results being if you hit your opponent's ships, and if so, how much damage you did to it) on the grid.

And we're almost done! All we have to do is compile and run the program!

Now remember how I said that on line 197, it says shots = 1024? Well what it means is this. The quantum computer will run and look over the results of the game 1024 times. It will check the probability of the ships being |0> or |1> (intact or destroyed). For example, lets use the second ship, the one that needs two half NOT's to take down. Say the opponent hits this ship once and therefore a half NOT is applied. If the program runs the results to this 1024 times, it will most likely show (most likely because we are not always going to get perfect answers due to decoherence) something like this:   {499:00000 525:00100} . This group of zeros and ones is called a bits string. The reason that there is five bits in the string is that there are 5 possible locations to place our ships. This means that, in this instance, the player placed their second ship in the 3rd position because there is a 1 there.

The 1 in the rightmost bit string represents that the gate changed the state. We interpret the fraction of times a qubit is measured to be 1 as the percentage damage for our ship. Around half the time (499 times) the computer did not pick up any results (stayed at zero 00000 or stayed in the |0> state). The other half showed a 1 (00100). This implies that the ship was damaged around 50% of the 1024 times, representing that a half NOT was placed.

One thing to point out though is that despite 1 in the bit string representing that the half NOT gate was applied, the 1 is not saying that the qubit is in the |1> state. The 1 is just displaying that the gate was applied.

Another example would be this:

Let's say one player put their third ship, which takes 3 third NOT gates to destroy, at position 4. The other player then bombs it. The results will look something like.

{'00000': 740, '00010': 284}

Here 284 out of the 1024 runs found a 1 at position 4, showing that this ship did suffer some damage. 284 is about 1/3 of 1024, representing that the bomb damaged 1/3 of the ship (or placed a third NOT on the ship).

Now you might notice when you run your program that if you place, let's say, one half NOT on a ship, on the grid it shows 35% damage done. Since this ship is half way to being destroyed, you should have expected your results to be 50%. Why is this? The reason is advanced trigonometry that we don't need to worry about and that, due to decoherence, the results will never be 100% on point.

Whoa! That was a lot of information! But in any case, if you understood how the code works and why I wrote what I wrote, you'll be all set to play Quantum Battleships!

Thanks for reading! Like this article and follow me on Linkedin for quantum articles! https://www.dhirubhai.net/in/teddy-porfiris-91b93816a/