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 14th 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
- 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.
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.