论文标题
在量子计算机上演奏策划者
Playing Mastermind on quantum computers
论文作者
论文摘要
从1970年代到现在，经典的两人游戏Mastermind引起了广泛的关注，不仅是公众作为一种受欢迎的游戏，而且还引起了学术界的科学问题。具有n位和k颜色的策划者正式描述为：CodeMaker私下选择了[K]^n $中的秘密$ s \，而CoderBreaker希望确定$ s $，因为很少的查询$ f_s（x）$，例如$ f_s（x）$，例如向Codemaker，$ f_s（x）$指示x x近x的位置。策略的复杂性通过使用的查询数量来衡量。在这项工作中，我们研究了在非自适应和适应性设置中量策划者在量子计算机上弹奏策划者，获得了有效的量子算法，这些算法都是精确的（即用确定性返回正确的结果）并显示巨大的量子加速。从技术上讲，我们开发了一个三步框架，用于为一般字符串学习问题设计量子算法，该算法不仅允许在演奏策划者上进行巨大的量子加速，而且还可以阐明探索其他字符串学习问题的量子加速。
From the 1970s up to now, Mastermind, a classic two-player game, has attracted plenty of attention, not only from the public as a popular game, but also from the academic community as a scientific issue. Mastermind with n positions and k colors is formally described as: the codemaker privately chooses a secret $s\in [k]^n$, and the coderbreaker want to determine $s$ in as few queries like $f_s(x)$ as possible to the codemaker, where $f_s(x)$ indicates how x is close to s. The complexity of a strategy is measured by the number of queries used. In this work we study playing Mastermind on quantum computers in both non-adaptive and adaptive settings, obtaining efficient quantum algorithms which are all exact (i.e., return the correct result with certainty) and show huge quantum speedups. Technically, we develop a three-step framework for designing quantum algorithms for the general string learning problem, which not only allows huge quantum speedups on playing Mastermind, but also may shed light on exploring quantum speedups for other string learning problems.
