# 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 \(N\) blog posts (\(N \in [4, \infty)\) for the moment,
subject to change when I will realise I have too much to say) 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:

- Introduction to the problem (this post).
- Mathematical reformulation of the problem.
- Unoptimised implementation of the solution.
- How to optimise a quantum circuit?.
- Optimising multi-controlled
`X`

gates. - Optimising the
`QRAM`

(Quantum Random Access Memory). - Optimising the oracle

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:

- You can only shoot on rows or columns of the \(4\times 4\) board, no diagonal is possible.
- 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.

**unique**property is an additional property enforced by IBM mentors in the provided board sets to simplify the problem.

With the game also come some rules participants should observe:

- 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.
- The solution should use Grover’s
algorithm
with
**1**iteration. - The solution should not use more than
**28 qubits**.

The restriction to **1** Grover iteration may be:

- To lower down the length of the submitted circuits in order to avoid congestion of the ibmq_qasm_simulator.
- To filter out solutions that were not amplifying correctly the searched state.

The **28 qubits** restriction corresponds to the simulation limit of
the ibmq_qasm_simulator backend.

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.