IBM Quantum Challenge 2020 - Part 1

I recently participated to the IBM Quantum Challenge 2020 and had a LOT of fun with the last exercise.

In a serie of 6 blog posts I will present you the solution I submitted and that granted me the 14^th place of the challenge that involved more than 1000 participants.

The serie will be organised as follow:

1. Introduction to the problem (this post).
2. Mathematical reformulation of the problem.
3. Unoptimised implementation of the solution.
4. How to optimise a quantum circuit?.
5. Optimising multi-controlled X gates.
6. Optimising the QRAM (Quantum Random Access Memory).

Without any transition, lets introduce the problem given to all the participants!

A small game about asteroids

Let say you have a $4\times 4$ board (quick maths: 16 cells). On this board, you can see 6 asteroids on 6 different cells.

Your goal: destroy all the asteroids!

But wait, how do you destroy asteroids? In this particular game, you have access to a particularly powerful laser beam that will vaporise all the asteroids it encounter, but this laser is quite limited:

1. You can only shoot on rows or columns of the $4\times 4$ board, no diagonal is possible.
2. Your power supply is low, and you only have 3 shots left.

Below are some examples of solvable and unsolvable boards.

A larger game about asteroids

Coming back to the IBM Quantum Challenge exercise, the problem we are asked to solve is the following: given a 16 boards configurations each containing 6 asteroids, find the index of the unique board that is not solvable.

With the game also come some rules participants should observe:

1. The solution should be 100% quantum. In particular, no pre-processing on a classical computer is allowed: the boards should be loaded on the quantum computer as provided.
2. The solution should use Grover’s algorithm with 1 iteration.
3. The solution should not use more than 28 qubits.

IBM mentors provided an example of input with 16 boards. I graphically represented this example below, are you able to spot the only board that is not solvable in 3 shots?

The solution to this problem will be given at the beginning of the next post, in which I will introduce a little bit of maths to understand better the problem we are asked to solve and to devise an efficient algorithm.