Quantum Football: How Qubits Can Predict Euro 2020

Joining millions around the globe, we at Classiq have been watching a lot of the UEFA European Football Championship games in the last couple of weeks. This got us thinking: how can we combine our passion for football with our passion for quantum computing?

So we put aside our tournament brackets for a while and picked up our quantum brakets to explore how to create a quantum circuit that predicts the outcome.

Initial thoughts 

We would like to build a quantum circuit that predicts the results of the entire tournament in a single measurement. The measurement result must be a valid tournament outcome - for instance, only one team can win any given match in the knockout stage, and thus the measurement space must exclude results with two winners or no winners. We would also like the circuit to be parametric so we can define the probabilities of each team winning in a match against any other team.

There are several ways we can go about building such a quantum circuit. One way is to simply construct a coin-flip circuit with one qubit and one Rx gate and then measure the result for each game independently - but there really isn't anything particularly interesting about that, and our goal is to only use a single measurement. Another way is to use state-preparation algorithms that efficiently build a predetermined probability distribution, but then we would have to start with a classical calculation of the probability of every possible outcome. This is also less interesting to us.

Instead, we demonstrate here two approaches that use quantum logic to build the circuit from the ground up. For building and visualizing the circuits, we will be using Qiskit - IBM’s package for quantum computation.

Base assumptions 

In designing the circuits, we made one important assumption: The winning probability for each match between two specific teams is predetermined and known. In real life, this might be a questionable assumption - players get injured or sit out because of yellow cards, teams have momentum, etc., but for now let’s assume that these probabilities are known in advance. An easy way to encode this probability into a quantum state is by using a single qubit to describe a single game between two teams. There would be a probability p for the first team to win, and thus probability 1-p for the second team to win. Of course, 0 ≤ p ≤ 1. 

We denote base state |0> to represent the victory of the first team, and |1> as the victory of the second team. A single Y-axis rotation gate (Ry gate) is applied on the qubit with angle θ. Now the quantum state is |psi> = cos(θ/2)*|0> +sin(θ/2)*|1>. If we choose θ = 2*arccos(√p), the quantum state can be written as |psi> = √p*|0> + √(1-p)*|1>. Thus the probability to measure the qubit in state |0> equals to p, which is what we wanted.

In this post, we show the explicit construction for a tournament which begins from the current state of the quarter finals in the knockout stage. However, it can easily be scaled up for larger tournaments, and modeled on physical computers when the number of qubits and their coherence time gets sufficiently large.

Round-based approach

Our first approach has each qubit describe the result of a single game. The state of the qubits describing the first games are rotated to the appropriate probability weighted superposition. The results of subsequent games depend on the identities of the winners from previous games using controlled rotation gates. The resulting quantum circuit looks like this:

The qubits depicting the quarter-final (qubits 1, 2, 4 and 5) are accompanied by a simple Ry gate, each encoding the known probabilities for the quarterfinal stage. Each semifinal is also encoded by a single gubit (qubits 3 and 6), and four consecutive controlled-Ry gates with two control qubits. These gates differ by the state that each controlled gate represents a possible match between the winners of the quarterfinals. Finally the final match is encoded with a single qubit (qubit 7) and 16 consecutive controlled gates with four control qubits.

What would that circuit look like if we had more teams and more rounds? If we started from the Round of 16, we would need 15 qubits (one for each game) and the final match would have 64 Ry gates (for every possible combination of the final match), each controlled by 6 qubits of the relevant previous matches. For N teams, we would need N-1 qubits. The qubit representing the final match would be the target of O(N²) multi-controlled-Ry gates, each controlled by O(log₂N) qubits.

Matchup-based approach

Here at Classiq, we understand the importance of fitting the quantum algorithm to the physical implementation of the quantum computer. The same quantum algorithm can be implemented in many different circuits with different characteristics, so we focus on providing cutting-edge technology to build alternative implementations to help our customers meet their needs and available resources. A possible alternative approach in this case would be one that results in a wider but shallower circuit - i.e. more qubits, fewer gates. Depending on available resources, switching between these alternatives can allow the same computations to be carried out on different quantum computers with different resources.

In the matchup-based approach, we associate each possible match with two qubits - a qubit encodes the result of that match, as before (|0> : the first team won, |1> : the second team won), and a second qubit encodes whether that match took place - as determined by the results of prior games. If a team lost a its match in a prior round, it won’t be playing again in this tournament. 

Let's see an example with only four teams - Switzerland, Spain, Belgium and Italy. The semi-finals in this example are Switzerland-Spain and Belgium-Italy. Here is what this circuit looks like:

The probability of each team to win each match can be adjusted by the Ry gates, but it will only be meaningful if that match’s second qubit is in the |1> state - indicating that the match actually took place. Since the semi-finals must have taken place, the second qubit for Switzerland-Spain (qubit 2) and Belgium-Italy (qubit 4) is flipped. The next round of matches (the four possible Final games) depend on the results of the previous round, and whether they took place at all - hence the multi-controlled NOT gates. When the circuit is finally measured, we only need to check the results of the matches with a second qubit in the |1> state.

Let’s look at an example measurement: |110100001111> (the uppermost qubit in the diagram is the rightmost in the measurement). The first and third qubits are in the |1> state, therefore Spain and Italy won the semi finals in this example. We can see that the last qubit - indicating a match between Spain and Italy indeed is in the |1> state, while qubits 6, 8, 10 are |0>, as expected. Since in this scenario the 11th qubit is measured as |1> - Italy won!

How does this circuit compare to the first option? If we construct a knockout-style tournament with N teams, we would need N·(N-1) qubits - twice the number of possible matches. We would also need the same number of Ry and multi-controlled-X gates - one for each possible match. However, the number of control qubits for each multi-controlled-X gate stays constant - 4 control qubits, because each match depends only on two previous matches. When N is large, although the number of qubits scales as O(N²), the complexity of the gates stays constant. This can be much more gate-efficient compared to the first circuit when N is large.

Results

Can we run these circuits on a physical quantum computer? Unfortunately, not with current-day devices. The round-based circuit needs only seven qubits, but when compiled to use the native gates of available quantum computers, the circuit depth balloons to around 1000! This is much larger than is currently possible to run before noise takes over. The matchup-based circuit would need 52 qubits, and the same number of multi-controlled-X gates - also not feasible today.

But here at Classiq, we do not let physical restrictions prevent us from seeking the truth. We can run the round-based circuit using noiseless simulators to find the winner. By estimating each match’s winning probability according to the betting odds (taken at the moment of calculation), we simulated the quantum prediction for the results.

Classiq is proud to present the world’s first quantum prediction for the winning team of EURO 2020:

‍