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:2207.09356

Playing Mastermind on quantum computers

Lvzhou Li, Jingquan Luo, Yongzhen Xu

Published Jul 19, 2022• 4 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2207.09356

Related papers

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

Quantum Computation and Pseudotelepathic Games

Jeffrey Bub

A quantum algorithm succeeds not because the superposition principle allows ‘the computation of all values of a function at once’ via ‘quantum parallelism’, but rather because the structure of a quantum state space allows new sorts of correlations associated with entanglement, with new possibilities for information-processing transformations between correlations, that are not possible in a classical state space. I illustrate this with an elementary example of a problem for which a quantum algorithm is more efficient than any classical algorithm. I also introduce the notion of ‘pseudotelepathic’ games and show how the difference between classical and quantum correlations plays a similar role here for games that can be won by quantum players exploiting entanglement, but not by classical players whose only allowed common resource consists of shared strings of random numbers (common causes of the players’ correlated responses in a game).

arXiv:1005.2449•Philosophy of Science•Oct 1, 2008•4 citations

Tutorials

Quantum computers offer the potential to extend our abilities to tackle computational problems in fields such as number theory, encryption, search and scientific computation.Up to a superpolynomial speedup has been reported for quantum algorithms in these areas.Motivated by the promise of faster computations, the development of quantum machines has caught the attention of both academics and industry researchers.Quantum machines are now at sizes where implementations of quantum algorithms or their components are now becoming possible.In order to implement quantum algorithms on quantum machines, resource efficient circuits and functional blocks must be designed.This tutorial will cover the following:

IEEE International Symposium on Smart Electronic Systems (iSES)•Dec 1, 2022•0 citations

Quantum games and quantum algorithms

David Meyer

A quantum algorithm for an oracle problem can be understood as a quantum strategy for a player in a two-player zero-sum game in which the other player is constrained to play classically. I formalize this correspondence and give examples of games (and hence oracle problems) for which the quantum player can do better than would be possible classically. The most remarkable example is the Bernstein-Vazirani quantum search algorithm which I show creates no entanglement at any timestep.

arXiv:quant-ph/0004092•Contemporary mathematics - American Mathematical Society•Jan 1, 2002•58 citations

Practical Guide to Quantum Computing: Fundamental Quantum Algorithms # 1

Mikhail Pavlov

Abstract This guide is based on the IBM Quantum course Fundamentals of Quantum Algorithms and explores the computational advantages enabled by quantum information. The focus is on what can be achieved using a single quantum computer, rather than distributed quantum systems. The primary objective of the course is to analyze how quantum computation can outperform classical computation in specific problem classes. In particular, the material examines quantum query algorithms, which provide a structured framework for understanding quantum speedups. Key themes include: The conceptual foundations of quantum computational advantage. The role of superposition, interference, and entanglement in algorithm design. Query complexity and how quantum algorithms reduce the number of required oracle calls compared to classical approaches. Foundational algorithms that demonstrate provable quantum speedups. The central guiding question is: What advantages can a quantum computer potentially offer over a classical computer? Through hands-on experimentation on IBM Q, the work connects theoretical analysis with practical implementation, enabling deeper insight into how quantum resources translate into measurable computational gains.

•Mar 4, 2026•0 citations

QUANTUM COMPUTATION: AN INTRODUCTION

Adriano Barenco

When applied to computation, quantum mechanics opens completely new perspectives; by exploiting quantum mechanical features such as entanglement or super-position, one can solve some problems much more efficiently than with classical computers. One of the most striking examples is the factoring problem. This task is believed to be out of reach of classical computers as soon as the number of digits in the number to factor exceeds a certain limit. In this contribution, we present the basic notion of quantum computation and review the most common quantum algorithms discovered so far.

WORLD SCIENTIFIC eBooks•Oct 1, 1998•13 citations
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.
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.
A quantum algorithm succeeds not because the superposition principle allows ‘the computation of all values of a function at once’ via ‘quantum parallelism’, but rather because the structure of a quantum state space allows new sorts of correlations associated with entanglement, with new possibilities for information-processing transformations between correlations, that are not possible in a classical state space. I illustrate this with an elementary example of a problem for which a quantum algorithm is more efficient than any classical algorithm. I also introduce the notion of ‘pseudotelepathic’ games and show how the difference between classical and quantum correlations plays a similar role here for games that can be won by quantum players exploiting entanglement, but not by classical players whose only allowed common resource consists of shared strings of random numbers (common causes of the players’ correlated responses in a game).
Quantum computers offer the potential to extend our abilities to tackle computational problems in fields such as number theory, encryption, search and scientific computation.Up to a superpolynomial speedup has been reported for quantum algorithms in these areas.Motivated by the promise of faster computations, the development of quantum machines has caught the attention of both academics and industry researchers.Quantum machines are now at sizes where implementations of quantum algorithms or their components are now becoming possible.In order to implement quantum algorithms on quantum machines, resource efficient circuits and functional blocks must be designed.This tutorial will cover the following:
Abstract This guide is based on the IBM Quantum course Fundamentals of Quantum Algorithms and explores the computational advantages enabled by quantum information. The focus is on what can be achieved using a single quantum computer, rather than distributed quantum systems. The primary objective of the course is to analyze how quantum computation can outperform classical computation in specific problem classes. In particular, the material examines quantum query algorithms, which provide a structured framework for understanding quantum speedups. Key themes include: The conceptual foundations of quantum computational advantage. The role of superposition, interference, and entanglement in algorithm design. Query complexity and how quantum algorithms reduce the number of required oracle calls compared to classical approaches. Foundational algorithms that demonstrate provable quantum speedups. The central guiding question is: What advantages can a quantum computer potentially offer over a classical computer? Through hands-on experimentation on IBM Q, the work connects theoretical analysis with practical implementation, enabling deeper insight into how quantum resources translate into measurable computational gains.
When applied to computation, quantum mechanics opens completely new perspectives; by exploiting quantum mechanical features such as entanglement or super-position, one can solve some problems much more efficiently than with classical computers. One of the most striking examples is the factoring problem. This task is believed to be out of reach of classical computers as soon as the number of digits in the number to factor exceeds a certain limit. In this contribution, we present the basic notion of quantum computation and review the most common quantum algorithms discovered so far.