Quantum computation in 84 short lines

I made the first ever game that runs on a quantum computer!

How to program a quantum computer

The fancy version of this game includes some messages that pop up as you wait for things to run. They tell the story of quantum computers, and how to run Battleships on one.

Here are those messages for your reading pleasure. I would advise you imagine that you are playing Battleships while reading them.

• Your ships and bombs have now turned into a quantum program.
• That program is in a queue to be processed by a real quantum device.
• It is the ibmqx2, made by IBM.
• You can also play with it using the IBM Quantum Experience.
• It is the world’s only publicly accessible quantum computer (in July 2017).
• So we could be in the queue for a minute or two.
• I’ll use that time to tell you about quantum computers, and how this program works.
• You can also find all this stuff at
  https://medium.com/@decodoku/quantum-computation-in-84-short-lines-d9c7c74be0d0
• Firstly, let’s make sure we all know what a normal computer is.
• Information is stored using lots of bits. Each can be either 0 or 1.
• These are manipulated using logic gates, built from transistors.
• The simplest logic gate is the NOT. It turns a 0 to a 1, and vice-versa.
• Another fun logic gate is AND. It takes two bits and looks whether both are 1.
• There are also others, like XOR, but they can all be built from NOTs and ANDs.
• In fact, any program can be compiled into a whole bunch of NOTs and ANDs.
• They are the building blocks of computing.
• But some programs need LOADS of these blocks.
• This means they’d need a huge computer, and it would need to run for ages.
• If a program could only run with a planet sized supercomputer…
• …which needs to run for the age of the universe…
• …running it would be practically impossible.
• Unless we find better building blocks!
• That’s what quantum computers promise to do.
• These are based on quantum bits, or ‘qubits’
• A qubit can either be 0 or 1. But it can also be a quantum superposition of the two.
• We can think of these as states that exist partway between 0 and 1.
• There are infinitely many kinds of these superpositions.
• They’ll all act a bit differently when we apply gates to them.
• At the end of the program, we look at whether each qubit is 0 or 1.
• Since these are the only two options, superpositions will have to decide one way or the other.
• The choice will always be random, but some superpositions are biased towards 0…
• …and some are biased towards 1.
• The existence of the superpositions allow us to do many more gates.
• We could do half a NOT, for example.
• Instead of going all the way from 0 to 1, we could park in a superposition halfway.
• There’s also different routes we could take through the superpositions between 0 and 1.
• Each gives us a different kind of NOT.
• The AND will also get more interesting when the qubits it compares are in superpositions.
• Any fraction of an AND is also possible
• So are types of gate that are completely different to those on normal computers.
• The building blocks of computation become a lot more malleable with qubits.
• That means we can build software in completely new ways.
• Problems that are currently practically impossible to solve will become easy.
• All we need is to build a powerful enough quantum computer.
• The device we are using here is a five qubit processor.
• We’ll need a few more than that to solve big problems.
• But for now, we can play Battleships!
• In this game, each of the five positions corresponds to a qubit on the processor.
• For positions that hold a ship, we use 0 to mean that it is intact and 1 for destroyed.
• For the weakest ships, the bomb is implemented with a NOT gate.
• One of these goes all the way from smooth sailing to swimming with the fishes.
• We use a particular kind of quantum NOT called an X.
• For the ships need two bombs to sink, each bomb is done with half an X.
• One of these rotates the ship to a superposition half way between 0 and 1.
• If the program ends at this point, the qubit will randomly choose between 0 and 1.
• Both options will be equally likely.
• By running the program many times, we’ll find half the results for this ship are 0…
• …and the other half are 1. We say that this has 50% damage.
• But if the qubit gets second half X before the program ends…
• …it will carry on all the way to 1, and the ship is destroyed!
• If it then gets another half X, it will start the journey back to 0.
• Probably best not to resurrect ships like this if you want to win!
• For the ship that needs three bombs, we use a third of an X.
• So with a single quantum bit, and a type of quantum NOT gate…
• …we can simulate a ship that needs three bombs to be destroyed.
• If we used a normal computer, a single bit and some NOT gates wouldn’t be enough.
• We’d need at least two bits for a such a ship, with something like 00 for intact…
• …01 for partly damaged, 10 for mostly destroyed, and 11 for sunk.
• Implementing the bombs would not just need NOT gates…
• …since what you need to do to one bit depends on what the other is doing.
• This would require XOR gates as well as NOTs.
• An AND would also be needed to check if the ship is sunk.
• It’s a lot more complex than just a qubit and some NOTs.
• This is a small example of how quantum programs can be more efficient.
• The effect is much more dramatic for other examples.
• But they aren’t so fun!
• If you want to know more about how to play with quantum programming…
• …check us out at decodoku.com.
• That’s all I have to tell you.
• This message will repeat in 5…
• …4…
• …3…
• …2…
• …1…