Choix du problème et architecture de l’oracle
Le programme de 12 semaines commence par la sélection d’un problème dont la vitesse quantique dépend d’un oracle exploitable. L’oracle doit être implémenté sur un QPU capable de réduire le nombre d’échantillons nécessaires pour estimer une moyenne, contrairement à un CPU ou GPU qui nécessitent davantage de tirages. Le cours montre que, pour un jeu de Go sur un plateau 32×32, l’écart de probabilité exploitable est de l’ordre de 10⁻⁴, ce qui impose une précision d’amplitude estimation de ε≈10⁻⁴. La même forme d’oracle s’applique à un modèle épidémique, démontrant la généralité du design.
Conception réversible et gestion des qubits
Chaque circuit est construit de façon réversible afin d’éviter la perte d’information. La méthode de Bennett – calculer, copier, dé‑calculer – est appliquée pour nettoyer les registres temporaires. Le nombre maximal de qubits « scratch » détermine la taille du registre : pour un oracle de 12 bits, le cours atteint 20 qubits d’entrée pour n’en retenir que 13 après nettoyage. Dans un exemple concret, un jeu 3×3 avec deux tours nécessite 169 qubits, incluant un qubit de gain et les bits de déplacement. La mesure en base X proposée par Gidney remplace un Toffoli par une opération AND†, réduisant de moitié le nombre de portes T requises dans un additionneur.
Méthodes de vérification et de test
Le cours introduit les circuits à preuve intégrée. Les tables de vérité ne capturent pas les phases ; ainsi, la vérification complète exige 2ⁿ évaluations, mais le système propose des certificats vérifiés par le noyau Lean en millisecondes. Les tests se limitent à des mesures de qubits individuels : un dispositif correct passe chaque test, alors qu’un dispositif avec q qubits de mémoire échoue avec une probabilité exponentielle si q est insuffisant. Cette approche permet d’auditer les revendications d’accélération quantique sans accéder au code source de l’oracle.
Implications pratiques et limites
Les leçons soulignent que le coût de l’oracle ne peut être masqué derrière l’hypothèse « accès oracle ». Le cours montre que le nombre de copies n’amortit pas la mémoire quantique : la mémoire requise reste nulle ou linéaire en n, avec un facteur minimal de 0,03 qubit par copie (théorème SHIFTS). De plus, la chaîne de compilation Qiskit ne garantit pas le respect des conventions de réutilisation des registres, ce qui impose aux développeurs de déclarer explicitement les classes de scratch (propre, emprunté, conditionnellement propre). Enfin, le programme insiste sur la distinction entre le nombre de requêtes d’oracle et le temps d’exécution réel, rappelant que le gain de Grover sur une base de données peut être annulé par le coût de chargement des données.
