IBM Quantum Challenge 2020 - Part 2
This post is part of a serie of posts on my experience with the IBM Quantum Challenge 2020.
The serie is organised as follow:
- Introduction to the problem.
- Mathematical reformulation of the problem (this post).
- Unoptimised implementation of the solution.
- How to optimise a quantum circuit?.
- Optimising multi-controlled
Xgates. - Optimising the
QRAM(Quantum Random Access Memory).
In the end of the previous post I included the test dataset provided by IBM mentors to all the participants, advising you to try to solve it by hand.
The solution to this problem is shown below.
In this post I will dig a little bit in the possible mathematical formulations of the problem and try to reformulate this problem to something more convenient for a quantum computer.
This blog post is here to explain the solution I used and that made it to the 14th place of the challenge.
After the end of the challenge some of the participants shared quickly their approach and I realised that another interesting approach was possible.
I might cover this different approach in a following blog post, but this will not be covered in the main serie.
Ryoko hint
The IBM Quantum Challenge took place with a narative background: our quantum computing mentor, Ryoko, was trapped in the quantum world and the only way of saving her was to solve the 3rd problem presented in the first post of this serie.
But as a mentor, Ryoko also gave the contestants the possibility to have a hint on how to solve the problem. This hint is available on the quantum challenge github repository.
In a nutshell, the hint tells us that the problem of whether or not a board is solvable can be reformulated as a vertex-coverwiki problem where:
- Each row and column is mapped to a node of the graph
- Each asteroid is an edge between the nodes representing its row and column
Reformulation of the problem
Our goal is now to try to answer to the question “is there a vertex cover of this graph that uses 3 or less nodes?” or specifically to find the unsolvable board: “what board cannot be covered with 3 or less nodes?”.
It is not obvious how we could solve this problem easily on a quantum computer within the given constraints, so lets try to reformulate again the problem.
Reading the Vertex cover Wikipedia page teach us that in general the vertex-cover problem is NP-complete except when the graph we consider is bipartite or a tree.
The graph we constructed to represent our board is bipartite because each edge links a node that represents a row of the board to a node that represents a column of the board.
In other words, the two disjoint and independent sets of nodes are:
- the nodes representing rows of the board
- the nodes representing columns of the board
We can also read that, when the graph is bipartite, Kőnig’s theorem is applicable.
By using this theorem, we can reformulate our problem which becomes “which board does not admit a maximum matching containing 4 edges?”.
Coming back to the board
We just reformulated our problem of finding the board that is not solvable in 3 or less shots as a maximum matching problem on a graph.
It is now time to step back and think about what our reformulation implies on the actual board.
Remember how we defined our graph following Ryoko’s hint:
- Nodes are columns or rows
- Edges are asteroids
- If an asteroid is located at the cell $(i, j)$ then there is an edge between the node representing the row $i$ and the node representing the column $j$.
A maximum matching is a set of edges (i.e. asteroids) that do not share any of their nodes (i.e. row / column).
We want to find the board that “does not admit a maximum matching containing 4 edges”, i.e. on which we cannot find 4 asteroids on 4 different rows and 4 different columns.
Those of you who are familiar with linear algebra and matrices might already have guessed the key idea that arise from these reformulations and for the others: permutation matrices!
It turns out that the only way a board could be unsolvable in 3 shots is if it “includes” a permutation matrix.
The final reformulation of our problem is then “find the only board that includes a permutation matrix”.
The “include” word is not really standard in linear algebra. The real mathematical reformulation would be:
Find the only board that can be written as $P + A$ where $P$ is a $4\times 4$ permutation matrix and $A$ is a $4\times 4$ matrix with only two non-zero entries with the value $1$.
In the following post I will show how to implement the naive algorithm arising from the reformulation devised in this post. The next blog post will then show the iterative improvements I performed to the naive implementation in order to optimise the cost of my circuit.
Adrien Suau
Entrepreneur in Quantum Computing
I am an entrepreneur in quantum computing. I also do business consulting, so feel free to reach out!