👩🏾‍🤝‍👨🏿 👈🏾 👨🏾‍🤝‍👨🏽 L'informatique quantique dans les jeux, ou devenir fou au sérieux 🤽🏿 ✨ 🔬

Si vous vivez parmi les fous, vous devez apprendre à être fou vous-même

Avez-vous déjà essayé "d'apprendre à être fou"? Tâche non triviale. Vous ne trouverez même pas une technique normale, car tout le monde devient fou à sa manière. Ma première tentative: la théorie du complot. La théorie n'implique pas la pratique, ce qui signifie que vous n'avez pas à travailler dur. Encore une fois, dans n'importe quelle situation, personne ne souffrira.

Comment créer des théories du complot?

Créer une théorie du complot est relativement simple. Nous avons besoin d'une idée suffisamment simple pour être acceptée par 90% de la population. Cela devrait être controversé pour que 5% de la population puisse expliquer à 90% quels idiots ils sont. Enfin, nous avons besoin de recherches que ces 95% de personnes ne comprennent pas, mais qui sont utilisées par 90% comme argument "les gens se sont montrés plus intelligents que nous ...".

L'informatique quantique est un grand domaine pour une telle étude. Vous pouvez regrouper un schéma simple, mais le mot «quantique» ajoutera du poids aux résultats.

L'objet d'étude est un jeu, car l'objet est dû à la jeunesse simple et familière. Qui est impliqué dans l'informatique quantique et les jeux? Google

Donc, théorie hérétique: après 5 ans, Page et Green décideront qui sera l'élément principal de Google, et ils le feront à l'aide du jeu. Chacun d'eux a un groupe de chercheurs. L'équipe AlphaGo avec ses réseaux de neurones de ~~combat a~~ attiré des rivaux à Go. Les opposants ont été contraints de chercher de nouvelles méthodes et ont tout de même trouvé un instrument de supériorité ~~totale~~ : l'informatique quantique.

Puis-je utiliser l'informatique quantique pour les jeux? C'est facile. Montrons par exemple que le jeu "fox hunter" peut être "résolu" en 6 coups. Pour des raisons de crédibilité, nous nous limitons à 15 qubits (l'éditeur en ligne quirk n'émule pas plus de quinze), pour des raisons de simplicité, nous ignorons les limites de l'architecture du processeur et la correction des erreurs.

Les règles

Extrêmement simple. Il y a cinq trous disposés dans une rangée (nous les numérotons comme 0-1-2-3-4). Dans l'un d'eux est un renard. Chaque nuit, le renard se déplace vers le vison suivant à gauche ou à droite. Chaque matin, le chasseur peut cocher un trou au choix. La tâche du chasseur est d'attraper le renard. La tâche du renard est de survivre. En théorie, un renard peut fuir un chasseur pour toujours. En pratique, il y a une stratégie gagnante: vérifier les trous 1-2-3-1-2-3. Seule cette stratégie sera testée.

Construire un schéma

Commençons par l'initiation des qubits 0-1-2-3-4 (5 trous). Ici vous pouvez éditer

En fait, après l'initiation, nous avons un système dans lequel, après la mesure, strictement un qubit sera unique. Les probabilités d '«unité» diffèrent pour chaque qubit, mais dans notre cas, ce n'est pas critique. Nous devons laisser la place à la discussion du schéma (et de notre théorie en même temps).

Sur Q #, nous obtenons un code comme celui-ci:

operation TestStrategy () : (Result) { let res = Zero; using(qubits=Qubit[16]) { // 0..4 - holes // 5 - current movement direction. Zero means "go down", One means "go up" // 6 - Game status. 1 means "fox is free, go further" // 7,8,9,10, 11 - movements history InitFoxHoles(qubits); ResetAll(qubits); // ALWAYS clean after yourself } return Zero; } // Inits fox holes, with almost equal probabilities operation InitFoxHoles(register: Qubit[]) : Unit { body { ResetAll(register); // Step 1 H(register[0]); H(register[2]); // Step 2 (Controlled (X))([register[0],register[2]], register[3]); // Step 3 X(register[0]); X(register[2]); (Controlled (X))([register[0],register[2]], register[3]); X(register[0]); X(register[2]); // Step 4 CNOT(register[3], register[0]); CNOT(register[3], register[2]); // Step 5 (Controlled (H))([register[3]], register[4]); // Step 6 CNOT(register[4], register[3]); } }

TestStrategy testera notre stratégie 1-2-3-1-2-3, InitFoxHoles () est uniquement responsable de l'initiation des trous de renard. Vérifions l'initiation. Copiez TestStrategy, démarrez l'initiation, mesurez les 5 premiers qubits et renvoyez leurs valeurs.

  operation TestInit(): (Result, Result, Result, Result, Result) { body { mutable res0 = Zero; mutable res1 = Zero; mutable res2 = Zero; mutable res3 = Zero; mutable res4 = Zero; using(qubits=Qubit[16]) { // 0..4 - holes // 5 - current movement direction. Zero means "go down", One means "go up" // 6 - Game status. 1 means "fox is free, go further" // 7,8,9,10, 11 - movements history InitFoxHoles(qubits); set res0 = M(qubits[0]); set res1 = M(qubits[1]); set res2 = M(qubits[2]); set res3 = M(qubits[3]); set res4 = M(qubits[4]); ResetAll(qubits); // ALWAYS clean after yourself } return (res0, res1, res2, res3, res4); } }

Nous exécuterons le test mille fois (plusieurs exécutions sont typiques des algorithmes quantiques, parfois même nécessaires). Code d'appel - sous le spoiler, résultats: sur l'écran ci-dessous.

Tester rapidement l'initiation

  static void TestInitiation() { using (var sim = new QuantumSimulator()) { var initedQubitsValues = Enumerable.Range(0, 5) .ToDictionary(qubitIndex => qubitIndex, oneMesaured => 0); for (int i = 0; i < 1000; i++) { (Result, Result, Result, Result, Result) result = TestInit.Run(sim).Result; if (result.Item1 == Result.One) { initedQubitsValues[0]++; } if (result.Item2 == Result.One) { initedQubitsValues[1]++; } if (result.Item3 == Result.One) { initedQubitsValues[2]++; } if (result.Item4 == Result.One) { initedQubitsValues[3]++; } if (result.Item5 == Result.One) { initedQubitsValues[4]++; } } Console.WriteLine($"Qubit-0 initiations: {initedQubitsValues[0]}"); Console.WriteLine($"Qubit-1 initiations: {initedQubitsValues[1]}"); Console.WriteLine($"Qubit-2 initiations: {initedQubitsValues[2]}"); Console.WriteLine($"Qubit-3 initiations: {initedQubitsValues[3]}"); Console.WriteLine($"Qubit-4 initiations: {initedQubitsValues[4]}"); } }

Quelque chose a mal tourné. Une distribution presque uniforme était attendue. La raison est simple: à l'étape 3, j'ai inversé le troisième qubit, au lieu du premier: (Contrôlé (X)) ([registre [0], registre [2]], registre [3]); ~~pas~~ bon vieux copier-coller.

Nous corrigeons le code, exécutons le test:

Initiation corrigée

  // Inits fox holes, with almost equal probabilities operation InitFoxHoles(register: Qubit[]) : Unit { body { ResetAll(register); // Step 1 H(register[0]); H(register[2]); // Step 2 (Controlled (X))([register[0],register[2]], register[3]); // Step 3 X(register[0]); X(register[2]); (Controlled (X))([register[0],register[2]], register[1]); X(register[0]); X(register[2]); // Step 4 CNOT(register[3], register[0]); CNOT(register[3], register[2]); // Step 5 (Controlled (H))([register[3]], register[4]); // Step 6 CNOT(register[4], register[3]); } } }

Déjà mieux. Le code peut être vu dans le navet, version Commit 1 .

Où faire courir le renard?

Sélectionnez le cinquième qubit (la numérotation commence par le haut) sous la direction actuelle du renard. Nous convenons que zéro signifie un mouvement vers le bas, une unité signifie un mouvement vers le haut. Évidemment, si le renard est déjà dans le trou zéro - il devrait descendre. Si le renard est dans le quatrième trou, il remonte. Dans d'autres cas, le renard peut monter et descendre. Selon ces règles simples, nous pouvons définir le «qubit de la direction actuelle» à 0, 1, ou une superposition de zéro et un. Nous regardons le code dans le référentiel, Commit 2 .

Schéma dans l'éditeur.

Code et test

 // Select next Fox movement direction, updating qubit 5 // 1 means go up (4 -> 3, 3 -> 2, ... 1 -> 0) // 0 means go down (0 -> 1, 1 -> 2, ... 3 -> 4) operation SetupMovementDirection(qubits: Qubit[]) : Unit { body { // Step 1 CNOT(qubits[4], qubits[5]); // Step 2 (Controlled (H))([qubits[3]], qubits[5]); // Step 3 (Controlled (H))([qubits[2]], qubits[5]); // Step 4 (Controlled (H))([qubits[1]], qubits[5]); } } operation TestMovementDirectionSetup(): (Result, Result, Result, Result, Result, Result) { body { mutable res0 = Zero; mutable res1 = Zero; mutable res2 = Zero; mutable res3 = Zero; mutable res4 = Zero; mutable res5 = Zero; using(qubits=Qubit[16]) { InitFoxHoles(qubits); SetupMovementDirection(qubits); set res0 = M(qubits[0]); set res1 = M(qubits[1]); set res2 = M(qubits[2]); set res3 = M(qubits[3]); set res4 = M(qubits[4]); set res5 = M(qubits[5]); ResetAll(qubits); // ALWAYS clean after yourself } return (res0, res1, res2, res3, res4, res5); } }

  static void TestMovementDirectionSetup() { using (var sim = new QuantumSimulator()) { List<string> results = new List<string>(); string initedCubit = null; string moveDirection = null; for (int i = 0; i < 1000; i++) { (Result, Result, Result, Result, Result, Result) result = Quantum.FoxHunter.TestMovementDirectionSetup.Run(sim).Result; if (result.Item1 == Result.One) { initedCubit = "0"; } if (result.Item2 == Result.One) { initedCubit = "1"; } if (result.Item3 == Result.One) { initedCubit = "2"; } if (result.Item4 == Result.One) { initedCubit = "3"; } if (result.Item5 == Result.One) { initedCubit = "4"; } if (result.Item6 == Result.One) { moveDirection = "1"; } else { moveDirection = "0"; } results.Add($"{initedCubit}{moveDirection}"); } foreach(var group in results .GroupBy(result => result) .OrderBy(group => group.Key)) { Console.WriteLine($"{group.Key} was measured {group.Count()} times"); } Console.WriteLine($"\r\nTotal measures: {results.Count()}"); } }

Mouvement

Implémenté par SWAP contrôlé. Si le qubit de contrôle est unique, permutez vers le bas. Si le qubit de contrôle est nul, nous échangeons.

Schéma dans l'éditeur .

Opérateur Q #

  // Makes a movement based on the 5'th qubit value // 1 means go up (4 -> 3, 3 -> 2, ... 1 -> 0) // 0 means go down (0 -> 1, 1 -> 2, ... 3 -> 4) operation MakeMovement(qubits: Qubit[]) : Unit { body { // Code movement Up // Step 1 mutable qubitsToSwap = [qubits[0], qubits[1]]; (Controlled(SwapReverseRegister))([qubits[5]],qubitsToSwap); // Step 2 set qubitsToSwap = [qubits[1], qubits[2]]; (Controlled(SwapReverseRegister))([qubits[5]],qubitsToSwap); // Step 3 set qubitsToSwap = [qubits[2], qubits[3]]; (Controlled(SwapReverseRegister))([qubits[5]],qubitsToSwap); // Step 4 set qubitsToSwap = [qubits[3], qubits[4]]; (Controlled(SwapReverseRegister))([qubits[5]],qubitsToSwap); // COde movement down X(qubits[5]); // Invert direction qubit for the ZeroControlled operations // Step 5 set qubitsToSwap = [qubits[3], qubits[4]]; (Controlled(SwapReverseRegister))([qubits[5]],qubitsToSwap); // Step 6 set qubitsToSwap = [qubits[2], qubits[3]]; (Controlled(SwapReverseRegister))([qubits[5]],qubitsToSwap); // Step 7 set qubitsToSwap = [qubits[1], qubits[2]]; (Controlled(SwapReverseRegister))([qubits[5]],qubitsToSwap); // Step 8 set qubitsToSwap = [qubits[0], qubits[1]]; (Controlled(SwapReverseRegister))([qubits[5]],qubitsToSwap); X(qubits[5]); // Back-invert for the direction qubit } }

Q #: instruction pour les tests

  operation TestFirstMovement(): (Result, Result, Result, Result, Result, Result) { body { mutable res0 = Zero; mutable res1 = Zero; mutable res2 = Zero; mutable res3 = Zero; mutable res4 = Zero; mutable res5 = Zero; using(qubits=Qubit[16]) { InitFoxHoles(qubits); SetupMovementDirection(qubits); MakeMovement(qubits); set res0 = M(qubits[0]); set res1 = M(qubits[1]); set res2 = M(qubits[2]); set res3 = M(qubits[3]); set res4 = M(qubits[4]); set res5 = M(qubits[5]); ResetAll(qubits); // ALWAYS clean after yourself } return (res0, res1, res2, res3, res4, res5); } }

Code C #

  static void TestFirstMove() { using (var sim = new QuantumSimulator()) { List<string> results = new List<string>(); string initedCubit = null; string moveDirection = null; for (int i = 0; i < 1000; i++) { (Result, Result, Result, Result, Result, Result) result = Quantum.FoxHunter.TestFirstMovement.Run(sim).Result; if (result.Item1 == Result.One) { initedCubit = "0"; } if (result.Item2 == Result.One) { initedCubit = "1"; } if (result.Item3 == Result.One) { initedCubit = "2"; } if (result.Item4 == Result.One) { initedCubit = "3"; } if (result.Item5 == Result.One) { initedCubit = "4"; } if (result.Item6 == Result.One) { moveDirection = "1"; } else { moveDirection = "0"; } results.Add($"{initedCubit}{moveDirection}"); } // Holes measurements foreach (var group in results .GroupBy(result => result[0]) .OrderBy(group => group.Key)) { Console.WriteLine($"{group.Key} hole was measured {group.Count()} times"); } // Directions measuremetns foreach (var group in results .GroupBy(result => result[1]) .OrderBy(group => group.Key)) { Console.WriteLine($"{group.Key} direction was measured {group.Count()} times"); } Console.WriteLine($"\r\nTotal measures: {results.Count()}"); } }

Le code peut être consulté dans Commit 3 .

Nous faisons 6 mouvements

Enfin, nous sélectionnons le sixième qubit pour l'état du jeu (le renard est libre / le renard n'est pas libre). L'unité correspond à un renard libre. Nous n'effectuerons de nouveaux déplacements qu'avec un seul qubit de statut.

Les qubits 7,8,9,10,11 conserveront un historique des mouvements. Après chaque mouvement, nous allons échanger l'un d'eux avec un qubit de la direction actuelle (cela nous permettra de stocker l'historique des mouvements et de réinitialiser le qubit de la direction actuelle avant chaque mouvement).

Schéma ci-joint .

Opérateur Q #

  /// Make 6 movements. Every movement is controlled by the 6'th qubit. /// After the every qubit we check if the fox has been captured and invert the 6'th qubit /// Reminder: 6'th qubit equal to One means "Fox is free, go further" operation MakeSixMovements(qubits: Qubit[]) : Unit { body { // Move 1 (Controlled(SetupMovementDirection))([qubits[6]],(qubits)); (Controlled(MakeMovement))([qubits[6]],(qubits)); CNOT(qubits[1], qubits[6]); // Reverse Fox State if it's shot // Move 2 SwapReverseRegister([qubits[5], qubits[7]]); // Move the first move direction to the qubit 7, qubit 5 is Zero again (Controlled(SetupMovementDirection))([qubits[6]],(qubits)); (Controlled(MakeMovement))([qubits[6]],(qubits)); CNOT(qubits[2], qubits[6]); // Move 3 SwapReverseRegister([qubits[5], qubits[8]]); (Controlled(SetupMovementDirection))([qubits[6]],(qubits)); (Controlled(MakeMovement))([qubits[6]],(qubits)); CNOT(qubits[3], qubits[6]); // Move 4 SwapReverseRegister([qubits[5], qubits[9]]); (Controlled(SetupMovementDirection))([qubits[6]],(qubits)); (Controlled(MakeMovement))([qubits[6]],(qubits)); CNOT(qubits[1], qubits[6]); // Move 5 SwapReverseRegister([qubits[5], qubits[10]]); (Controlled(SetupMovementDirection))([qubits[6]],(qubits)); (Controlled(MakeMovement))([qubits[6]],(qubits)); CNOT(qubits[2], qubits[6]); // Move 6 SwapReverseRegister([qubits[5], qubits[11]]); (Controlled(SetupMovementDirection))([qubits[6]],(qubits)); (Controlled(MakeMovement))([qubits[6]],(qubits)); CNOT(qubits[3], qubits[6]); } }

Q #: instruction pour les tests

  operation TestSixMovements(): (Result) { body { mutable res = Zero; using(qubits=Qubit[16]) { ResetAll(qubits); InitFoxHoles(qubits); X(qubits[6]); // At the beginning of the game our fox is alive MakeSixMovements(qubits); set res = M(qubits[6]); ResetAll(qubits); // ALWAYS clean after yourself } return (res); } }

C #: test

  static void TestMovements() { using (var sim = new QuantumSimulator()) { int zerosCount = 0; for (int i = 0; i < 1000; i++) { Result result = Quantum.FoxHunter.TestSixMovements.Run(sim).Result; if(result == Result.Zero) { zerosCount++; } } Console.WriteLine($"\r\nTotal zeroes: {zerosCount}"); } }

Nous regardons Commit 4 .

Touche finale

Nous avons une erreur dans le circuit. Puisque nous testons la stratégie 1-2-3-1-2-3, nous vérifions chaque trou deux fois. En conséquence, après avoir attrapé le renard au premier mouvement, nous allons passer par le qubit de statut deux fois (au premier mouvement et au quatrième).

Pour éviter cette situation, nous utilisons 12 qubits pour corriger l'état après les mouvements 4-5-6. De plus, nous ajoutons la définition de la victoire: si au moins l'un des qubits de statut devient nul, nous gagnons.

Le schéma final .

Q #: correction de l'opérateur 6 mouvements

  operation MakeSixMovements(qubits: Qubit[]) : Unit { body { // Move 1 (Controlled(SetupMovementDirection))([qubits[6]],(qubits)); (Controlled(MakeMovement))([qubits[6]],(qubits)); CNOT(qubits[1], qubits[6]); // Reverse Fox State if it's shot // Move 2 SwapReverseRegister([qubits[5], qubits[7]]); // Move the first move direction to the qubit 7, qubit 5 is Zero again (Controlled(SetupMovementDirection))([qubits[6]],(qubits)); (Controlled(MakeMovement))([qubits[6]],(qubits)); CNOT(qubits[2], qubits[6]); // Move 3 SwapReverseRegister([qubits[5], qubits[8]]); (Controlled(SetupMovementDirection))([qubits[6]],(qubits)); (Controlled(MakeMovement))([qubits[6]],(qubits)); CNOT(qubits[3], qubits[6]); // Move 4 SwapReverseRegister([qubits[5], qubits[9]]); (Controlled(SetupMovementDirection))([qubits[6], qubits[12]],(qubits)); (Controlled(MakeMovement))([qubits[6], qubits[12]],(qubits)); CNOT(qubits[1], qubits[12]); // Move 5 SwapReverseRegister([qubits[5], qubits[10]]); (Controlled(SetupMovementDirection))([qubits[6], qubits[12]],(qubits)); (Controlled(MakeMovement))([qubits[6], qubits[12]],(qubits)); CNOT(qubits[2], qubits[12]); // Move 6 SwapReverseRegister([qubits[5], qubits[11]]); (Controlled(SetupMovementDirection))([qubits[6], qubits[12]],(qubits)); (Controlled(MakeMovement))([qubits[6], qubits[12]],(qubits)); CNOT(qubits[3], qubits[12]); } }

Q #: correction de la stratégie de test des opérateurs 1-2-3-1-2-3

  operation TestStrategy () : (Result) { // 0..4 - holes // 5 - current movement direction. Zero means "go down", One means "go up" // 6 - Game status. 1 means "fox is free, go further" // 7,8,9,10, 11 - movements history // 12 - another qubit of the fox live. 1 means "fox is still free, go further" // 13 Result qubit. If it's zero, the fox is alive body { mutable res = Zero; using(qubits=Qubit[14]) { ResetAll(qubits); // Init fox positions and the fox' live InitFoxHoles(qubits); X(qubits[6]); // At the beginning of the game our fox is alive X(qubits[12]); // The second qubit of the fox live. If it's one - the fox is alive. // Make moves MakeSixMovements(qubits); // Measure results. If the 13'th qubit is zero the fox is alive X(qubits[6]); X(qubits[12]); CNOT(qubits[6], qubits[13]); CNOT(qubits[12], qubits[13]); CCNOT(qubits[6], qubits[12], qubits[13]); set res = M(qubits[13]); ResetAll(qubits); // ALWAYS clean after yourself } return (res); } }

C #: exécuter la vérification finale

  static void RunFoxHunt() { Stopwatch sw = new Stopwatch(); sw.Start(); using (var sim = new QuantumSimulator()) { var foxSurvives = 0; var hunterWins = 0; for (int i = 0; i < 1000; i++) { var result = (Result)(TestStrategy.Run(sim).Result); if (result == Result.Zero) { foxSurvives++; } else { hunterWins++; } } Console.WriteLine($"Fox survives: \t{foxSurvives}"); Console.WriteLine($"Hunter wins: \t{hunterWins}"); } sw.Stop(); Console.WriteLine($"Experiment finished. " + $"Time spent: {sw.ElapsedMilliseconds / 1000} seconds"); }

Valider 5 .

Ce qui en découle

En principe, le schéma peut être optimisé à la fois en nombre de qubits et en nombre d'opérations. L'optimisation triviale du nombre de qubits consiste à se débarrasser de qubit-13, renvoyant seulement 6 et 12. Optimisation par opérations - pour faire le premier tir immédiatement après l'initiation. Cependant, laissons ce travail aux ingénieurs de Google.

Comme vous pouvez le voir, quiconque est superficiellement familier avec l'informatique quantique peut jouer en toute sécurité le "chasseur de renards". Si nous avions un peu plus de qubits, nous pourrions trouver la solution optimale et ne pas vérifier la solution existante. Il est tout à fait possible que le tic-tac-toe (et leur version quantique), les dames, les échecs, Go tombent ensuite.

Dans le même temps, la question de la «solvabilité» de jeux comme DotA, Starcraft et Doom reste ouverte. L'informatique quantique se caractérise par le stockage de l'historique complet des clics. Nous prenons APM (Actions par minute) de 500, multiplions par le nombre de joueurs, multiplions par le nombre de minutes, ajoutons le caractère aléatoire du jeu lui-même - le nombre de qubits requis pour stocker toutes les informations augmente trop rapidement.

Ainsi, choisir un jeu dans une petite compétition entre Brin et Page peut jouer un rôle décisif. Cependant, la génération d'un jeu «tout aussi difficile» pour les ordinateurs classiques et quantiques mérite sa propre théorie.

L'informatique quantique dans les jeux, ou devenir fou au sérieux