量子计算机上玩Mastermind游戏：高效精确量子算法的突破性研究

作者及发表信息

本文由Lvzhou Li、Jingquan Luo和Yongzhen Xu（均来自中国中山大学量子计算与计算机理论研究所）合作完成，发表于Leibniz International Proceedings in Informatics (LIPIcs)，遵循Creative Commons CC-BY 4.0许可协议。

学术背景

研究领域：本文属于量子计算复杂性理论与算法博弈论的交叉领域，聚焦于经典游戏Mastermind（猜颜色密码的游戏）在量子计算模型下的算法设计与复杂性分析。

研究动机：自20世纪70年代以来，Mastermind作为经典的双人游戏，不仅广受欢迎，更成为理论计算机科学的研究对象。经典算法在非自适应（non-adaptive）和自适应（adaptive）设置下的查询复杂度已得到深入研究，但量子计算能否带来显著加速尚未充分探索。本文旨在填补这一空白，设计高效的精确量子算法（exact quantum algorithms，即结果必然正确的算法），并揭示量子计算在字符串学习问题中的新结构。

核心问题：给定一个由n个位置和k种颜色组成的秘密字符串s，玩家通过黑钉查询（black-peg query，仅反馈匹配位置数）或黑白钉查询（black-white-peg query，额外反馈颜色正确但位置错误的数目）逐步猜测s，目标是以最少查询次数确定s。

研究方法与流程

1. 非自适应量子算法设计

核心思想：通过发现秘密字符串s的特征矩阵（characteristic matrix）M的新结构，将问题转化为学习矩阵行的组合。
- 特征矩阵定义：M是一个k×n的二元矩阵，M(c_i, j)=1当且仅当s_j = c_i。
- 关键观察：
- 仅需学习k-1对颜色组合的行和（如M^(c2,c1), ..., M^(ck,c1)）即可重构s（Lemma 2）。
- 更高效的方法是利用⌈k/3⌉组三元颜色组合（如(c_g, c_l, c_h)）的行和（Lemma 4）。
- 量子子程序：
- 设计量子算法FindTwoColorPosition（Algorithm 1），通过一次查询b_s^(cl,ch)（由黑钉查询b_s构造）学习M^(cl,ch)。
- 通过量子傅里叶变换（QFT）和相位反冲（phase kickback）实现精确计算。

算法成果：
- Algorithm 2：使用k-1次黑钉查询的非自适应算法。
- Algorithm 3：使用不超过2⌈k/3⌉次查询的优化版本。

2. 自适应量子算法设计

核心思想：结合Grover搜索的精确变体，在n个位置上同步搜索颜色。
- 算法流程（Algorithm 5）：
- 初始化均匀叠加态，通过迭代旋转操作逐步放大目标状态的振幅。
- 使用精确Grover搜索（exact Grover search）确保零误差，查询复杂度为O(√k)。
- 下界证明：任何量子算法至少需要Ω(√k)次黑钉查询（Theorem 12），证明通过将问题归约至非结构化搜索（unstructured search）。

3. 黑白钉查询的加速算法

核心思想：利用黑白钉查询的额外信息分两阶段学习：
1. 通过Bernstein-Vazirani算法确定秘密字符串s使用的颜色集合C_s（复杂度O(⌈k/n⌉)）。
2. 在|C_s|种颜色上运行自适应算法，总复杂度为O(⌈k/n⌉ + √|C_s|)（Theorem 15）。
突破性：当n ≤ k ≤ n²时，该算法突破Ω(√k)的下界。

主要结果与贡献

1. 量子加速优势：

   • 非自适应设置下，量子算法复杂度O(k)远优于经典算法的Θ(n log k / max{log(n/k),1})（当k ≤ n）或O(k log k)（当k > n）。
     
   • 自适应设置下，量子算法仅需O(√k)次查询，而经典算法需Θ(n log k / log n + k/n)次。
     

2. 技术框架创新：提出三阶段通用字符串学习框架：

   • (a) 发现支持量子加速的新结构（如特征矩阵的行和关系）；
     
   • (b) 设计学习该结构的量子子程序；
     
   • © 将原问题查询（如黑钉查询）转化为子程序所需的量子预言机。
     

3. 理论意义：

   • 首次系统建立了Mastermind问题的量子复杂性界限。
     
   • 为其他字符串学习问题（如群测试、梯度估计）的量子算法设计提供了方法论参考。
     

研究亮点与价值

1. 算法精确性：所有量子算法均为零误差（exact），优于多数依赖概率的经典算法。
   
2. 结构创新：特征矩阵的行和关系揭示了Mastermind问题中未被经典研究利用的数学结构。
   
3. 应用潜力：框架可推广至密码学（如破解银行密码）和生物信息学（如基因组数据分析）。
   

总结

本文通过量子计算的新视角，彻底改进了Mastermind游戏的算法效率，不仅填补了量子复杂性理论的空白，更提出了适用于广义字符串学习问题的通用框架。其技术核心——将经典查询转化为量子可处理的结构化信息——为未来量子算法设计提供了重要范例。