Football quantique : Comment les Qubits peuvent prédire l'Euro 2020

Comme des millions de personnes dans le monde, nous avons, chez Classiq, regardé de nombreux matchs du championnat d'Europe de football de l'UEFA au cours des deux dernières semaines. Cela nous a fait réfléchir : comment combiner notre passion pour le football avec notre passion pour l'informatique quantique ?

Nous avons donc mis de côté nos tableaux de tournoi pour un temps et pris nos braquets quantiques pour explorer la manière de créer un circuit quantique qui prédit le résultat.

Premières réflexions 

Nous aimerions construire un circuit quantique capable de prédire les résultats de l'ensemble du tournoi en une seule mesure. Le résultat de la mesure doit être un résultat valide du tournoi - par exemple, une seule équipe peut gagner un match donné dans la phase à élimination directe, et l'espace de mesure doit donc exclure les résultats avec deux vainqueurs ou aucun vainqueur. Nous aimerions également que le circuit soit paramétrique afin de pouvoir définir les probabilités de victoire de chaque équipe dans un match contre n'importe quelle autre équipe.

Il existe plusieurs façons de construire un tel circuit quantique. L'une d'entre elles consiste à construire simplement un circuit de pile ou face avec un qubit et une porte Rx, puis à mesurer le résultat de chaque jeu indépendamment - mais il n'y a vraiment rien de particulièrement intéressant à cela, et notre objectif est de n'utiliser qu'une seule mesure. Une autre solution consiste à utiliser des algorithmes de préparation d'état qui construisent efficacement une distribution de probabilité prédéterminée, mais nous devrions alors commencer par un calcul classique de la probabilité de chaque résultat possible. Cette solution est également moins intéressante pour nous.

Au lieu de cela, nous démontrons ici deux approches qui utilisent la logique quantique pour construire le circuit à partir de la base. Pour construire et visualiser les circuits, nous utiliserons Qiskit, le logiciel d'IBM pour l'informatique quantique.

Hypothèses de base 

Lors de la conception des circuits, nous avons fait une hypothèse importante : La probabilité de victoire pour chaque match entre deux équipes spécifiques est prédéterminée et connue. Dans la réalité, cette hypothèse peut être discutable : des joueurs se blessent ou restent sur le banc de touche en raison de cartons jaunes, les équipes ont le vent en poupe, etc. Une façon simple d'encoder cette probabilité dans un état quantique est d'utiliser un seul qubit pour décrire un seul match entre deux équipes. Il y aurait une probabilité p pour que la première équipe gagne, et donc une probabilité 1-p pour que la seconde équipe gagne. Bien entendu, 0 ≤ p ≤ 1. 

Nous désignons l'état de base |0> pour représenter la victoire de la première équipe, et |1> comme la victoire de la seconde équipe. Une porte de rotation unique sur l'axe Y (porte Ry) est appliquée sur le qubit avec un angle θ. L'état quantique est alors |psi> = cos(θ/2)*|0> +sin(θ/2)*|1>. Si nous choisissons θ = 2*arccos(√p), l'état quantique peut être écrit comme |psi> = √p*|0> + √(1-p)*|1>. Ainsi, la probabilité de mesurer le qubit dans l'état |0> est égale à p, ce qui correspond à ce que nous voulions.

Dans ce billet, nous montrons la construction explicite d'un tournoi qui commence à partir de l'état actuel des quarts de finale dans la phase d'élimination directe. Cependant, elle peut facilement être mise à l'échelle pour des tournois plus importants, et modélisée sur des ordinateurs physiques lorsque le nombre de qubits et leur temps de cohérence deviennent suffisamment importants.

Approche par cycles

Dans notre première approche, chaque qubit décrit le résultat d'un seul jeu. L'état des qubits décrivant les premiers jeux est tourné vers la superposition appropriée pondérée par les probabilités. Les résultats des jeux suivants dépendent de l'identité des gagnants des jeux précédents à l'aide de portes de rotation contrôlées. Le circuit quantique qui en résulte ressemble à ceci :

Les qubits représentant le quart de finale (qubits 1, 2, 4 et 5) sont accompagnés d'une simple porte Ry, chacune codant les probabilités connues pour l'étape du quart de finale. Chaque demi-finale est également codée par un seul gubit (qubits 3 et 6) et quatre portes Ry contrôlées consécutives avec deux qubits de contrôle. Ces portes se distinguent par le fait que chaque porte contrôlée représente un match possible entre les vainqueurs des quarts de finale. Enfin, le match final est codé avec un seul qubit (qubit 7) et 16 portes contrôlées consécutives avec quatre qubits de contrôle.

À quoi ressemblerait ce circuit si nous avions plus d'équipes et plus de tours ? Si nous partions des huitièmes de finale, nous aurions besoin de 15 qubits (un pour chaque match) et le match final aurait 64 portes Ry (pour toutes les combinaisons possibles du match final), chacune contrôlée par 6 qubits des matchs précédents correspondants. Pour N équipes, nous aurions besoin de N-1 qubits. Le qubit représentant le match final serait la cible de O(N²) portes Ry multicontrôlées, chacune contrôlée par O(log₂N) qubits.

Approche basée sur le matchup

Chez Classiq, nous comprenons l'importance d'adapter l'algorithme quantique à l'implémentation physique de l'ordinateur quantique. Le même algorithme quantique peut être implémenté dans de nombreux circuits différents avec des caractéristiques différentes, c'est pourquoi nous nous concentrons sur la fourniture d'une technologie de pointe pour construire des implémentations alternatives afin d'aider nos clients à répondre à leurs besoins et à leurs ressources disponibles. Dans ce cas, une approche alternative possible serait un circuit plus large mais moins profond, c'est-à-dire plus de qubits, moins de portes. En fonction des ressources disponibles, le passage d'une solution à l'autre peut permettre d'effectuer les mêmes calculs sur différents ordinateurs quantiques dotés de ressources différentes.

Dans l'approche basée sur les matchs, nous associons chaque match possible à deux qubits - un qubit code le résultat de ce match, comme précédemment (|0> : la première équipe a gagné, |1> : la seconde équipe a gagné), et un second qubit code si ce match a eu lieu - comme déterminé par les résultats des matchs précédents. Si une équipe a perdu un match lors d'un tour précédent, elle ne jouera plus dans ce tournoi. 

Prenons un exemple avec seulement quatre équipes : la Suisse, l'Espagne, la Belgique et l'Italie. Les demi-finales de cet exemple sont Suisse-Espagne et Belgique-Italie. Voici à quoi ressemble ce circuit :

La probabilité pour chaque équipe de gagner chaque match peut être ajustée par les portes de Ry, mais cela n'aura de sens que si le deuxième qubit de ce match est dans l'état |1>, ce qui indique que le match a effectivement eu lieu. Puisque les demi-finales doivent avoir eu lieu, le deuxième qubit pour Suisse-Espagne (qubit 2) et Belgique-Italie (qubit 4) est inversé. Les matchs suivants (les quatre finales possibles) dépendent des résultats du tour précédent et de la question de savoir s'ils ont eu lieu ou non - d'où les portes NOT multicontrôlées. Lorsque le circuit est finalement mesuré, il suffit de vérifier les résultats des matchs à l'aide d'un deuxième qubit dans l'état |1>.

Examinons un exemple de mesure : |110100001111> (le qubit le plus haut dans le diagramme est le plus à droite dans la mesure). Les premier et troisième qubits sont dans l'état |1>, ce qui signifie que l'Espagne et l'Italie ont remporté les demi-finales dans cet exemple. Nous pouvons voir que le dernier qubit - indiquant un match entre l'Espagne et l'Italie - est effectivement dans l'état |1>, tandis que les qubits 6, 8 et 10 sont dans l'état |0>, comme prévu. Étant donné que dans ce scénario, le 11e qubit est mesuré comme étant |1> - l'Italie a gagné !

Comment ce circuit se compare-t-il à la première option ? Si nous construisons un tournoi à élimination directe avec N équipes, nous aurons besoin de N-(N-1) qubits, soit le double du nombre de matchs possibles. Nous aurions également besoin du même nombre de portes Ry et de portes X multicontrôlées - une pour chaque match possible. Cependant, le nombre de qubits de contrôle pour chaque porte X multicontrôlée reste constant - 4 qubits de contrôle, car chaque correspondance ne dépend que de deux correspondances précédentes. Lorsque N est grand, bien que le nombre de qubits soit égal à O(N²), la complexité des portes reste constante. Ce circuit peut être beaucoup plus efficace en termes de portes que le premier circuit lorsque N est grand.

Résultats

Peut-on faire fonctionner ces circuits sur un ordinateur quantique physique ? Malheureusement, pas avec les appareils actuels. Le circuit rond ne nécessite que sept qubits, mais lorsqu'il est compilé pour utiliser les portes natives des ordinateurs quantiques disponibles, la profondeur du circuit grimpe à environ 1 000 ! C'est beaucoup plus que ce qu'il est actuellement possible d'exécuter avant que le bruit ne prenne le dessus. Le circuit basé sur l'appariement nécessiterait 52 qubits et le même nombre de portes X multicontrôlées, ce qui n'est pas non plus réalisable aujourd'hui.

Mais chez Classiq, nous ne laissons pas les restrictions physiques nous empêcher de chercher la vérité. Nous pouvons faire fonctionner le circuit à base de rounds en utilisant des simulateurs sans bruit pour trouver le vainqueur. En estimant la probabilité de victoire de chaque match en fonction de la cote des paris (au moment du calcul), nous avons simulé la prédiction quantique des résultats.

Classiq est fier de présenter la première prédiction quantique au monde pour l'équipe gagnante de l'EURO 2020 :

‍