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, ℓ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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">${\cal O}(k \log k)$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mi mathvariant="script">O</mi> </mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mi>log</mi> <mo /> <mi>k</mi> <mo stretchy="false">)</mo> </math></EquationSource> </InlineEquation> black-count queries, <InlineEquation ID="IEq2"> <EquationSource Format="TEX">${\cal O}(\log k)$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mi mathvariant="script">O</mi> </mrow> <mo stretchy="false">(</mo> <mi>log</mi> <mo /> <mi>k</mi> <mo stretchy="false">)</mo> </math></EquationSource> </InlineEquation> ℓp-distance queries, and <InlineEquation ID="IEq3"> <EquationSource Format="TEX">${\cal O}(\log M)$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mi mathvariant="script">O</mi> </mrow> <mo stretchy="false">(</mo> <mi>log</mi> <mo /> <mi>M</mi> <mo stretchy="false">)</mo> </math></EquationSource> </InlineEquation> separable-distance queries to learn the secret s ∈ [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.

Quantum algorithm for secret learning in Mastermind game

期刊论文
发表日期：

2025年11月12日

查看全文

Wentao Qi,
Yongzhen Xu,
Shenggen Zheng,
Lvzhou Li

摘要

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, ℓ_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 ${\cal O}(k \log k)$ $O (k \log k)$ black-count queries, ${\cal O}(\log k)$ $O (\log k)$ ℓ_p-distance queries, and ${\cal O}(\log M)$ $O (\log M)$ separable-distance queries to learn the secret s ∈ [k]ⁿ, 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.