Provable super-exponential quantum advantage for learning secrets in Mastermind

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.