Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2206.11221 · Physica A Statistical Mechanics and its Applications

Quantum algorithm for learning secret strings and its experimental demonstration

Yongzhen Xu, Shihao Zhang, Lvzhou Li

Published Dec 5, 2022• 6 citations
arXivHTMLPDF
DOI
10.1016/j.physa.2022.128372

Related papers

Quantum algorithms for learning hidden strings with applications to matroid problems

Xiaowei Huang, Shihao Zhang, Lvzhou Li

arXiv:2211.10667•Theoretical Computer Science•Oct 13, 2023•8 citations

Quantum algorithm for secret learning in Mastermind game

Wentao Qi, Yongzhen Xu, Shenggen Zheng +1 more

Science China Physics Mechanics and Astronomy•Nov 12, 2025•4 citations

Provable super-exponential quantum advantage for learning secrets in Mastermind

Yongzhen Xu, Jingquan Luo, Lvzhou Li

Quantum computing can speed up the solution of certain computational problems. However, a large proportion of such problems discovered so far are either contrived or do not directly correspond to real-world applications. Here, we prove super-exponential quantum speedups for a learning problem called Mastermind where Alice hopes to learn the secret string from Bob by doing as few interactive question-answering as possible. It first appeared as a popular game and then was abstracted to a combinatorial optimization problem with a wide range of applications. To establish the quantum advantage, we propose non-adaptive and adaptive quantum algorithms for this problem, both demonstrating super-exponential quantum speedups over their classical counterparts. The non-adaptive one has a promising experimental realizability on near-term quantum computers since it is simply to run a shallow quantum circuit. Our work adds a new member to the zoo of super-exponential quantum speedups and demonstrates quantum advantages for problems with potential applications.

npj Quantum Information•Dec 5, 2025•2 citations

Playing Mastermind on quantum computers

Lvzhou Li, Jingquan Luo, Yongzhen Xu

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.

arXiv:2207.09356•Jul 19, 2022•4 citations

Quantum Algorithms for String Processing

Farid Mansurovich Ablayev, Marat Ablayev, Kamil Ravilevich Khadiev +2 more

arXiv:2012.00372•Lecture notes in computational science and engineering•Oct 21, 2021•19 citations

Quantum secret sharing protocol with four state Grover algorithm and its proof-of-principle experimental demonstration

Liang Hao, Chuan Wang, Gui Lu Long

Optics Communications•Apr 15, 2011•48 citations
Quantum computing can speed up the solution of certain computational problems. However, a large proportion of such problems discovered so far are either contrived or do not directly correspond to real-world applications. Here, we prove super-exponential quantum speedups for a learning problem called Mastermind where Alice hopes to learn the secret string from Bob by doing as few interactive question-answering as possible. It first appeared as a popular game and then was abstracted to a combinatorial optimization problem with a wide range of applications. To establish the quantum advantage, we propose non-adaptive and adaptive quantum algorithms for this problem, both demonstrating super-exponential quantum speedups over their classical counterparts. The non-adaptive one has a promising experimental realizability on near-term quantum computers since it is simply to run a shallow quantum circuit. Our work adds a new member to the zoo of super-exponential quantum speedups and demonstrates quantum advantages for problems with potential applications.
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∈[k]ns\in [k]^ns∈[k]n, and the coderbreaker want to determine sss in as few queries like fs(x)f_s(x)fs​(x) as possible to the codemaker, where fs(x)f_s(x)fs​(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.