Quantum algorithm for secret learning in Mastermind game

This work investigates quantum speedups for the popular game named Mastermind, in which there are two participants: the codemaker who selects a secret string, and the codebreaker who submits query strings and receives answers from the codemaker. The codebreaker's objective is to learn the secret string in as few queries as possible. This work focuses on playing the Mastermind game on quantum computers using different types of codemaker's answers such as black count, $\ell_p$ distance, and separable distance. We show that the codebreaker can learn the secret with certainty by using quantum algorithms which exhibit a sharp reduction in query numbers compared with their classical counterparts. Specifically, our quantum algorithms require $\mathcal{O}(k~\log~k)$ black-count queries, $\mathcal{O}(\log~k)$ $\ell_p$-distance queries, and $\mathcal{O}(\log~M)$ separable-distance queries to learn the secret $s\in[k]^n$, respectively, where $M$ is completely determined by $k$. Thus, the quantum query complexity is independent of the length $n$ of the secret $s$, as opposed to the query complexity linear in $n$ of classical algorithms.