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:

  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).
  7. 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!

An example of board with 6 asteroids.
An example of board with 6 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.

Example of solvable board. The 3 beams have been shot on the second and third rows and on the second column.
Example of solvable board. The 3 beams have been shot on the second and third rows and on the second column.
Example of a unsolvable board. 4 beams are **required** to destroy all the asteroids
Example of a unsolvable board. 4 beams are required to destroy all the asteroids

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.

The 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:

  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.

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?

Test dataset given by IBM mentors. Can you find the unsolvable board?
Test dataset given by IBM mentors. Can you find the unsolvable board?

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.

PhD student in Quantum Computing

I am a doctoral student currently involved in a PhD on quantum computing algorithms and how they can be applied to speed-up scientific computing.

Next

Related