Geekly articles weekly

游戏中的量子计算，或发疯的趋势

如果您生活在疯狂之中，那么您必须学会自己疯狂

您是否曾经尝试过“学会疯狂”？ 非平凡的任务。 您甚至都找不到正常的技术，因为每个人都以自己的方式发疯。 我的第一个尝试：阴谋论。 该理论不涉及实践，这意味着您不必努力工作。 再有，在任何情况下，没有人会受苦。

如何创建阴谋论？
建立阴谋论相对简单。 我们需要一个足够简单的想法，以使90％的人口可以接受。 应该引起争议的是，有5％的人口可以解释90％的白痴。 最后，我们需要一些这95％的人不理解的研究，但有90％的人将其用作“人们比我们更聪明……”的论点。

量子计算是进行此类研究的重要领域。 您可以汇总一个简单的方案，但是“量子”一词会增加结果的权重。

学习的对象是游戏，因为学习的对象是简单而熟悉的青年。 谁参与量子计算和游戏？ 谷歌

因此，这是一种异端理论：五年后，佩奇和格林将决定谁将成为Google的主要业务，他们将使用游戏来实现这一目标。 他们每个人都有一组研究人员。 AlphaGo团队以其战斗神经网络吸引了Go中的竞争对手。 反对者被迫寻找新方法，但仍然找到了一种完全优越的工具：量子计算。

我可以在游戏中使用量子计算吗？ 很简单 让我们举例说明游戏“ fox hunter”可以通过6个动作“解决”。 为了信誉起见，我们将自己限制在15个量子位（在线编辑器怪胎最多模拟15个），为简单起见，我们忽略了处理器体系结构和纠错的限制。

规则


非常简单。 一排有五个孔（我们将其编号为0-1-2-3-4）。 其中一只是狐狸。 每天晚上，狐狸都会左右移动到下一个水貂。 每天早晨，猎人可以检查一个洞供您选择。 猎人的任务是捉住狐狸。 狐狸的任务是生存。 从理论上讲，狐狸可以永远逃离猎人。 实际上，有一个制胜法宝：检查孔1-2-3-1-2-3。 我只会测试这种策略。

建立方案


让我们从0-1-2-3-4（5孔）的量子位开始。 在这里您可以编辑


实际上，在启动之后，我们有一个系统，在测量之后，严格来说，一个量子位将是单个。 每个量子位的“统一”概率是不同的，但是在我们的情况下，这并不重要。 我们必须留出空间讨论该方案（同时讨论我们的理论）。

在Q＃上，我们得到如下代码：

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将测试我们的策略1-2-3-1-2-3，InitFoxHoles（）仅负责启动狐洞。 让我们检查一下启动。 复制TestStrategy，开始初始化，测量前5个量子位并返回其值。

  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); } }

我们将运行测试一千次（多次运行是量子算法的典型，在某些地方甚至是必要的）。 通话代码-在扰流板下方，结果：在以下屏幕上。

快速测试启动
  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]}"); } }




出了点问题。 预期几乎均匀的分布。 原因很简单：在步骤3中，我反转了第三个qubit，而不是第一个：（受控（X））（[寄存器[0]，寄存器[2]]，寄存器[3]）； 不是很好的旧复制粘贴。

我们修复代码，运行测试：

更正的启动
  // 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]); } } }




已经更好了。 该代码可以在芜菁的Commit 1版本中看到。

狐狸在哪里跑？


选择狐狸当前方向下的第五个量子比特（从上面开始编号）。 我们同意零表示向下运动，单位表示向上运动。 显然，如果狐狸已经在零孔中-它应该向下移动。 如果狐狸在第四个孔中，它将向上移动。 在其他情况下，狐狸可以上下移动。 根据这些简单的规则，我们可以将“当前方向的量子比特”设置为0、1或零和一的叠加。 我们查看存储库中的代码Commit 2 。


编辑器中的方案。

编码与测试
 // 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()}"); } }





机芯

由受控的SWAP实施。 如果控制量子位是单个-向下交换。 如果控制量子位为零，我们交换。


在编辑方案中 。

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＃：测试语句
  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); } }


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()}"); } }


可以在提交3中查看该代码。

我们走了6步


最后，选择第六个qubit作为游戏状态（狐狸是免费的/狐狸不是免费的）。 单位对应于自由狐狸。 我们将仅使用单个状态qubit进行进一步的移动。

量子比特7,8,9,10,11将保留移动的历史。 每次移动之后，我们都将其中一个与当前方向的量子比特交换（这将使我们能够存储移动的历史记录，并在每次移动之前重置当前方向的量子比特）。

方案附后 。

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＃：测试语句
  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＃：测试
  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}"); } }


我们看一下Commit 4 。

画龙点睛


我们的电路有错误。 由于我们测试了策略1-2-3-1-2-3，因此我们对每个孔进行了两次检查。 因此，在第一步中抓住了狐狸之后，我们将经历两次状态qubit（第一步，第四次）。

为了避免这种情况，我们在移动4-5-6之后使用12个量子位来固定状态。 另外，我们添加了胜利的定义：如果至少一个状态量子位变为零，我们就赢了。

最终方案 。

Q＃：修复6移动运算符
  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＃：修复操作员测试策略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＃：运行最终检查
  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"); }



提交5 。

随之而来的


原则上，可以在量子位数量和操作数量上优化该方案。 对qubit数量的简单优化是摆脱qubit-13，仅返回6和12。操作优化-在启动后立即进行第一枪。 不过，让我们将这项工作留给Google工程师进行。

如您所见，任何对量子计算有初步了解的人都可以安全地扮演“狐狸猎人”的角色。 如果我们还有更多的量子位，我们可以找到最佳解决方案，而不用检查现有的解决方案。 井字游戏（及其量子版本），跳棋，国际象棋，围棋很有可能会在接下来跌落。

同时，DotA，Starcraft和Doom等游戏的“可解决性”问题仍然存在。 对于量子计算，特征是整个点击历史记录的存储。 我们将APM（每分钟操作数）设为500，乘以玩家人数，乘以分钟数，再加上游戏本身的随机性-存储所有信息所需的qubit数量增长得太快。

因此，在布林和佩奇之间的小规模竞争中选择一款游戏可以起决定性作用。 但是，为经典计算机和量子计算机开发“同样困难”的游戏值得其自己的理论。

Source: https://habr.com/ru/post/zh-CN437352/

More articles:


All Articles