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• 1 citation
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•1 citation

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 A. 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•Apr 24, 2000•3 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

Realization of Bernstein-Vazirani quantum algorithm in an interactive educational game

David Gosal, Timothy Rudolf Tan, Yozef Tjandra +1 more

Quantum algorithms are celebrated for their computational superiority over classical counterparts, yet they pose significant learning challenges for non-physics audiences. Among these, the Bernstein-Vazirani (BV) algorithm stands out for its quantum speedup by efficiently identifying a secret binary string. However, the accessibility of such algorithms remains constrained by their inherent technical complexity. To address this educational gap, this paper introduces a gamified, web-based tool that innovatively reinterprets the BV algorithm’s complex mathematical settings through an into engaging scenario of identifying broken lamps. Players assume the role of an investigator, utilizing both classical and quantum solvers to identify faulty lamps with minimal queries. By transforming the BV algorithm into an intuitive gameplay experience, the tool helps reducing technical barriers, making quantum concepts much more comprehensible for educators and students than traditional methods that demand rigorous mathematical understanding. Developed using Qiskit, IBM’s Python package for quantum computation, and deployed via Flask, a popular Python microframework for building web applications, the game effectively simplifies complex quantum algorithms while demonstrating the practical applications of quantum speedup. This contribution advances quantum education by merging technical depth with interactive design, fostering a broader understanding of quantum principles and inspiring new innovations in gamified learning.

TELKOMNIKA (Telecommunication Computing Electronics and Control)•Oct 1, 2025•0 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.
Quantum algorithms are celebrated for their computational superiority over classical counterparts, yet they pose significant learning challenges for non-physics audiences. Among these, the Bernstein-Vazirani (BV) algorithm stands out for its quantum speedup by efficiently identifying a secret binary string. However, the accessibility of such algorithms remains constrained by their inherent technical complexity. To address this educational gap, this paper introduces a gamified, web-based tool that innovatively reinterprets the BV algorithm’s complex mathematical settings through an into engaging scenario of identifying broken lamps. Players assume the role of an investigator, utilizing both classical and quantum solvers to identify faulty lamps with minimal queries. By transforming the BV algorithm into an intuitive gameplay experience, the tool helps reducing technical barriers, making quantum concepts much more comprehensible for educators and students than traditional methods that demand rigorous mathematical understanding. Developed using Qiskit, IBM’s Python package for quantum computation, and deployed via Flask, a popular Python microframework for building web applications, the game effectively simplifies complex quantum algorithms while demonstrating the practical applications of quantum speedup. This contribution advances quantum education by merging technical depth with interactive design, fostering a broader understanding of quantum principles and inspiring new innovations in gamified learning.