How to make Battleships from quantum NOT gates
by Dr. James Wootton on May 9, 2017

Quantum computers are a weird new kind of computer. They burn through unthinkable numbers of parallel universes to run programs faster, and use principles that confounded even Einstein. They are the magical miracle boxes that will leave your stupid boxes of transistors in the dust.

That’s what popular science articles will probably tell you, anyway. They doubtless succeed in making this new technology sound exciting. But they can also make quantum computation seem like an arcane art, entrusted to only the cleverest of scientists. Certainly not something for the wider programming public to concern themselves with!

I don’t think this is true at all. And with companies like IBM and Google actually making quantum devices, the time to start playing with quantum programming is now.

You don’t need to do anything fancy at the beginning. You can start your journey into quantum programming at the same place as many of us start our journey into normal programming: by making games.

Don’t worry, having your own quantum computer will not be required. Simple quantum programs can easily be simulated on a normal computer. We can also borrow some time on a real quantum device, thanks to the IBM Q Experience.

This is a first in a series of articles in which I describe some simple programs made using IBM’s quantum SDK. Each will be a self-contained version of Battleships, with simple quantum processes used to implement the basic game mechanic.

These are among the first games made for a quantum computer. I’ll show you the gory details of the code behind the game, so that hopefully you can start experimenting with quantum programming too.

What is a quantum computer?

Before we start on the program, we need some background information. I won’t tell you everything about quantum computing. We’ll just get enough to understand what goes on in our game.

A normal computer is based on bits: variables which have just two possible values. We often call them `0` and `1`, though in the context of Boolean algebra we might call them `True` and `False`. It doesn’t matter what we call them. The important point is that there are just two states.

With bits we can do simple Boolean operations, like NOT, AND and OR. These are the basic building blocks of computation. With these we can do anything. Any variable more complex than a bit (like an int or float) is just collection of many bits. Any operation more complex than an AND or NOT is actually just many of them stuck together. At its most basic level, this is what a normal computer is.

Quantum computers are based on quantum bits, or qubits. These also have two possible values which we can call `0` and `1`. But the laws of quantum mechanics also allow other possibilities, which we call superposition states.

In some sense, the superposition states are values that exist part way between the extremes of `0` and `1`. We can picture a qubit as a sphere, with `0` and `1`sitting on opposing poles. The superposition states are all the other possible points on the surface.

As well as 0 and 1, this image also flags up a couple of important superposition states. One is called `u3(0.5*pi,0,0) |0⟩`. Admittedly it’s not a very catchy name, but we’ll look at what it actually means during this article.

This way of thinking about qubits makes them seem a bit like continuous variables. We can represent any point on the surface of a sphere (like the point ψ in the image) using polar coordinates with a just couple of angles (θ and φ). So you’d be forgiven for thinking that a qubit is just a pair of floats. In a sense, they are. But in another more accurate sense, they are not.

An important difference is that we can never extract more than a binary piece of information from a qubit. The laws of physics themselves prevent us from finding out what exactly they are doing. We can’t ask a qubit for the exact details of its superposition state. We can only ever force it to choose between two opposite points on the sphere (like `0` and `1`). If it is anything other than these two states, it will just have to randomly decide one or the other.

So a qubit has some properties of a continuous variable, and some properties of a discrete one. In truth it is neither. It is a quantum variable.

What will we do with the qubits?

The Battleships game we are making today is based on a Japanese variant. In this, all ships take up only a single square, but some take more hits to sink than others. We’ll have one ship that can be sunk by a single bomb, one that needs two and one that needs three.

To simulate this on a quantum computer, we can use a qubit for each ship. The state `0` can be identified with a fully intact ship, and `1` with one that has been destroyed. The superposition states will then correspond to a ship’s journey towards destruction.

A ship destroyed by a single hit will be pretty easy to simulate. We can initialize it in state `0`, and then apply a NOT when it gets hit. When we find it in state `1`, we’ll know it has been destroyed.

Let’s look at how to implement just this simple process on a quantum computer. We won’t worry about any other ships, or inputs and outputs at the moment.

To do this we’ll use the QISKit quantum SDK to set up a quantum program. Here’s a script that initializes a ship, bombs it, and then looks at whether it is still afloat.

`q = QuantumRegister(1) \\ Initialize a register with a single qubitc = ClassicalRegister(1) \\ Initialize a register with a normal bitqc = QuantumCircuit(q, c) \\ Create and empty quantum program`
`qc.u3(math.pi,0,0, q[0]) \\ apply a NOT to the qubit`
`qc.measure( q[0], c[0] ) \\ measure the qubit`

First this defines all the bits we’ll need: both quantum and normal. In this example we have defined a single qubit in a register called `q`. We refer to this qubit in code as `q[0]`. Since outputs have to be in nice, human-readable normal information, we also define a single normal bit in a register called `c`.

The qubit `q[0]` is automatically initialized in the state `0`. Since that’s the state we want to start with, no further preparation is required.

Next we want to take this `q[0] = 0`, a fully intact ship, and perform a NOT. With a normal bit and a normal programming language, we might implement this as `q[0] = !q[0]` (for C++) or `q[0] = not q[0]` (for Python). In QISKit it can be done in multiple ways. The simplest is to use operations called `x` and `y`. Here are some examples of how to use them, with the equivalent C++ and Python lines for comparison.

``q[0] = !q[0]; \\ A C++ style NOT``
``q[0] = not q[0] ``
`qc.x( q[0] ) `\\ A QISKit style NOT``
`qc.y( q[0] ) `\\ Another QISKit style NOT``

There are some differences between `x` and `y` that we’ll have to deal with one day. But not today.

You’ll probably have noticed that neither `x` nor `y` appear in the earlier QISKit snippet. Instead we have u3(pi,0,0). This is another way to implement a NOT.

`qc.u3(math.pi,0,0, q[0]) `\\ Yet another QISKit style NOT``

This operation is completely equivalent to a `y`. But `u3` is a more complex operation in general. It has three arguments, and by changing them we can do other things.

Note that when actually implementing this operation in QISKit it gets a fourth argument, which is the qubit we are applying it to.

The first argument is an angle expressed in radians. It is the angle by which we are going to turn the sphere of our qubit around. The angle pi (or `math.pi`when implemented in Python) corresponds to 180°. This means we turn the sphere completely upside down. `0` moves to `1` and `1` moves to `0`, which is why this operation acts as a NOT. To do half a NOT we could simply use half this angle: `u3(0.5*pi,0,0)`.

So now we have yet another way to perform a NOT on our qubit: We could do half a NOT twice.

``\\ Another QISKit style NOT`qc.u3(math.pi/2,0,0, q[0])qc.u3(math.pi/2,0,0, q[0])`

We could also do a third of a not thrice, or a quarter of a NOT following by half a NOT and then two eighths of a NOT. You get the idea.

The last line of our QISKit snippet is

`qc.measure( q[0], c[0] )`

In this we measure the qubit. We tell `q[0]` that it has to decide what to be: `0`or `1`. The result is then stored in `c[0]`, ready to be looked at by our non-quantum brains, or processed by our non-quantum computers. The value of `c[0]` is then the output of this computation.

If we did nothing between initialization and measurement…

`q = QuantumRegister(1)c = ClassicalRegister(1)qc = QuantumCircuit(q, c)`
`qc.measure( q[0], c[0] )`

…the result should always be `c[0] = 0`.

If we did a NOT…

`q = QuantumRegister(1)c = ClassicalRegister(1)qc = QuantumCircuit(q, c)`
`qc.u3(math.pi,0,0, q[0])`
`qc.measure( q[0], c[0] )`

..the result should always be `c[0]=1`.

If we did just half a NOT…

`q = QuantumRegister(1)c = ClassicalRegister(1)qc = QuantumCircuit(q, c)`
`qc.u3(0.5*math.pi,0,0, q[0])`
`qc.measure( q[0], c[0] )`

`q[0]` will be halfway between 0 and 1 when it is measured. In fact it will be the superposition state we called `u3(0.5*pi,0,0) |0⟩` earlier. Measuring whether this is `0` or `1` will force it to randomly choose one or the other, with equal probabilities.

This probabilistic nature will crop up a fair bit in quantum calculations. Additional randomness is also present in current devices due to noise. Though this is at a usuably low level, we still have to keep its existence in mind. So we will sometimes get a `1` when we should get a `0`, and vice-versa.

For these reasons, it is usual to run a quantum program many times. This process then returns a list of all the outputs that were generated during these many samples, and the number of times each occurred.

Making a game

Now let’s use these many paths toward a NOT to make a game on a quantum computer.

First, I’ll let you into a secret. Quantum computers will always be hybrid devices, partly quantum and partly normal. The latter is required to handle inputs and outputs, in order to interface with the lumbering apes who want to use the device.

For this reason, quantum SDKs are typically embedded in a standard programming language. QISKit uses Python, so we can use a Python program to deal with both the normal parts of the program, and to construct and run jobs for the quantum part.

It’s important to note that everything is still evolving. And all of us making quantum programs in these early days will inevitably guide that evolution.

To run the program, you’ll need Jupyter installed, as well as the dependencies of the SDK. You can find out more here.QISKit/qiskit-tutorial
qiskit-tutorial – A collection of Jupyter notebooks using QISKitgithub.com

Now let’s look at the code!

Firstly, everything we need to run code on the IBM’s Quantum Experience needs to be imported.

`from qiskit import ClassicalRegister, QuantumRegisterfrom qiskit import QuantumCircuit, execute`

Next we need to register with the API so that we can actually run jobs on the real quantum device.

`from qiskit import registerimport Qconfigqx_config = {    "APItoken": Qconfig.APItoken,    "url": Qconfig.config['url']}register(qx_config['APItoken'], qx_config['url'])`

This references the `Qconfig` file, which you’ll need an account with IBM to set up. Don’t worry, it’s free! See here for the specifics.

Next we import a bunch of functions designed to handle all the boring inputs and outputs. Since this isn’t part of the quantum programming, we won’t go into any details on these.

`from battleships_engine import *`

The first thing we need to do is decide on the device that will be used for the quantum part of the program.

`device = ask_for_device()from qiskit import get_backendbackend = get_backend(device)`

The `ask_for_device()` function simply asks the player whether or not to use the real device. If they respond `y`, the device chosen is `ibmqx4`: a real five qubit quantum processor in IBM’s labs. If they respond `n`, a simulator is chosen instead.

Another important thing to set is the number of times each job will be run. This is because we use many samples to calculate statistics on the possibly random outputs that we get.

`shots = 1024`

There is no magical reason for 1024. You can change it if you want.

Next we come to setting up the boards, with each player choosing where to put three ships. Five possible positions are available, corresponding to the five qubits on IBM’s ibmqx4 device. I visualize the grid like this

`4       0|\     /|| \   / ||  \ /  ||   2   ||  / \  || /   \ ||/     \|3       1`

The numbers are the names I use for each position. They are also the names IBM uses, so `2` is the position of qubit `q[2]`, for example.

The choices made by the players are stored in shipPos. This has an entry for each of the two players (`player=0` for the first player, `player=1` for the second), and each of the three ships they place. The entry `shipPos[player][ship]` holds the position (`0``1``2``3` or `4`) for the ship numbered `ship`belonging to `player`.

Now it’s time for the main game loop. In this we will ask both players where on their opponent’s grid they’d like to bomb. This is then added into `bomb[player][position]`, which counts how many times `player` has bombed `position` over the course of the game.

We now have enough information to set up the quantum program. We know which qubits are supposed to be ships and where to bomb. So now it is time to set to the corresponding jobs with QISKit.

In each round we’ll have two quantum programs to run: each simulating the action on the grid of one player. We’ll use the array `qc` to hold these programs.

`qc = []for player in range(2):    q = QuantumRegister(5)    c = ClassicalRegister(5)    qc.append( QuantumCircuit(q, c) )`

Each program is initialized with a register of five quantum and classical bits, to cover the whole grid. The program for the grid of a given player can be adressed with `qc[player]`, though note that player 1 is here referred to as `player=0`, and player 2 as `player=1`.

Now suppose we want to apply a certain fraction of a NOT to a certain qubit. We do this with the following line

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

but with `frac` and `position` replaced by actual numbers.

Using this we can add all the bombs that the opposing player is firing at this grid. For the grid of `player` we loop over all three positions where there is a ship. We then add a line to `qc[player]` for every bomb that has been sent here.

I mentioned earlier that the three ships in this game will all have different strengths. The first one placed by the player will be sunk by a single bomb, but the second one will need two to be destroyed and the third will need three.

In terms of qubits, this means that a bomb that hits the first ship applies a whole NOT. A bomb that hits the second ship applies, half a NOT, and one on the third ship applies a third of a NOT. The fraction `frac` is then determined by what ship is getting hit. For this we simply use `frac = 1/(ship+1)`.

Once the bombing is over, it’s time to see what happened. For that we need to add the measurement commands. Each qubit in the register is measured, and the results copied to a corresponding normal bit. This is done with

`for qubit in range(5):    qc[player]t.measure(q[qubit], c[qubit])`

Now we have a pair of quantum programs, it’s time to run them. This is done using

`job = execute(qc, backend, shots=shots)`

Here `backend` was defined earlier when we asked the player which device to run on.

Once the job has been submitted, we can try to extract the data.

`for player in range(2):    grid[player] = job.result().get_counts(qc[player])`

Here I copy the results over to `grid`, with the results for the bombing of `player`’s ships in `grid[player]`.

Note that the call to `job.result()` will wait until the job has actually stopped running. If you are in a queue behind others using the device, this could take a good few minutes.

The results are stored in `grid[player]` as a dictionary. The keys are bit strings, and so look something like `110`. The rightmost bit is `c[0]`, and so `c[0]=0` in this example bit string. By processing the results we can work out how many runs got the each result (`0` or `1`) for each of the normal bits.

We interpret the fraction of times a qubit is measured to be 1 as the percentage damage for our ship. We can’t expect 100% damage due to the effects of noise (or weather, if you want an in-universe explanation) so we count damage greater than 95% as meaning the ship has sunk.

Let’s check out some example outputs from the quantum process. Suppose one player put their third ship at position 2. The other player then bombs it. The results will look something like.

`{'00000': 734, '00100': 290}`

Here 290 of the 1024 runs found a `1` at position 2, showing that this ship did indeed suffer some damage.

Another example: one player put their first ship at position 1, and their second at 2. The other player then bombs position 1 in the first round and position 2 in the second. The results would be

`{'00110': 532, '00010': 492}`

Here all results have a `1` on the second slot to the right (the one for position 1). That ship was destroyed by a single bomb. The one at position 2 was only half damaged, though, so half the results have a `1` for that.

These example results were nice and clean, so we can tell that they were done on the simulator. On the real device you can expect to find a few `1` results for ships that weren’t even bombed, and for qubits that aren’t ships.

The processing of bit strings is not something unique to quantum computing, so I won’t presume to tell you how to do it. If you are interested in the method I hacked together you’ll find it in the code.

Once the damage percentages are calculated, they are presented to the players. For example, if only the ship at position 2 has been hit, and it has 50% damage, this would be shown as.

` ?       ?  |\     /| | \   / | |  \ /  | |  50%  | |  / \  | | /   \ | |/     \| ?       ?`

The game continues to ask for bombs and running the scenario until one player has lost all their ships. At that point the other player wins.

You might notice that bombing the third ship of a player gives a damage of around 25%. Since this ship is a third of the way to destruction, you might have expected 33%. The reason is trigonometry. There’s no need to dwell on it too much at this point.

It is important to note that the whole scenario is rerun every time. If the amount of time between turns might only be about minute, but that’s almost an eternity for qubits. Even at a temperature of 0.02 Kelvin, the information would have burned away long before the next turn. Also, our need to extract information will also disturb all the lovely quantumness in the system. For these reasons, any process that needs human interaction throughout will need the quantum parts to be rerun from scratch for each new input.

So that was it. Battleships running on a quantum computer. Not the fanciest use of a quantum computer, or the fanciest version of Battleships. But for me, combining the two is half the fun!

The full source code can be accessed below.QISKit/qiskit-tutorial
qiskit-tutorial – A collection of Jupyter notebooks using Qiskitgithub.com

And here’s a video of the game in action.

The story continues with another version of Battleships in part 2.

`Collected at: https://medium.com/qiskit/how-to-program-a-quantum-computer-982a9329ed02?fbclid=IwAR1jt_7y1SAmTCF38mbWAtpeg8olEfiY7sy7HEPfcqTj9mGorO7IdITno_k`