用于“智多星”游戏中秘密学习的量子算法

《Science China-Physics Mechanics & Astronomy》：Quantum algorithm for secret learning in Mastermind game

量子算法在Mastermind游戏中的查询复杂度优化，使用黑数、?p距离和分离距离三种反馈类型，量子方法所需查询次数分别为O(k log k)、O(log k)和O(log M)，且量子复杂度与秘密长度n无关，显著优于经典线性复杂度。

　　

摘要

本研究探讨了在名为“Mastermind”的流行游戏中利用量子计算实现加速的可能性。该游戏共有两名参与者：一名是密码制定者（codemaker），负责选择一条秘密字符串；另一名是密码破解者（codebreaker），负责提交查询字符串并接收密码制定者的回答。密码破解者的目标是以尽可能少的查询次数猜出秘密字符串。本文重点研究了在量子计算机上使用不同类型的密码制定者回答（如“黑数计数”（black count）、?_p距离（?_{p distance）和“可分离距离”（separable distance）来玩“Mastermind”游戏。我们证明了通过使用量子算法，密码破解者可以确定地猜出秘密字符串，而且这些算法相比经典算法大幅减少了查询次数。具体来说，我们的量子算法分别需要\({\cal O}(k \log k)\)次“黑数计数”查询、\({\cal O}(\log k)\)次?p距离查询以及\({\cal O}(\log M)\)次“可分离距离”查询来猜出长度为[k]ⁿ的秘密字符串s，其中M完全由k决定。因此，量子算法的查询复杂度与秘密字符串s的长度n无关，而经典算法的查询复杂度则与n成线性关系。}