Solving Mastermind with Knuth, Grover, and Deutsch

In a previous article I explored how a quantum search algorithm can be used to amplify Euchre’s high value winning hands in a deck of cards. I will admit it was a little contrived: the rules of the game were just used as a model to build an oracle to use in Grover’s algorithm for an unstructured search. The main purpose was simply to illustrate a concept, the usefulness was a little lacking.

This article will go beyond the contrived and conceptual: solve a popular logic puzzle, the game of Mastermind. A classical algorithm and two quantum algorithms will be given which play the game in three different ways: one actually solves it in linear time!

So in this 100th anniversary of quantum mechanics, the International Year of Quantum Science and Technology, let’s look at the game of Mastermind: an excellent topic for both classical and quantum methods.

Mastermind: the Game and the Solvers

After its invention and release in the early 1970s Mastermind caught the attention of mathematicians, puzzle game enthusiasts, and of course, programmers. The common interest is the fundamental object of the game: to crack a hidden code in as few guesses as possible: a classic problem in logic, combinatorics & optimization, and computer science. “Easy to learn. Easy to play. But not so easy to win”

The game was initially very popular but over the years has seen some decline. I noticed that recently in May 2025 the toy company Goliath entered a multi-year agreement with Hasbro to become the worldwide manufacturer and distributor of the Mastermind brand, so maybe there might be a resurgence.

A quick recap for the newcomers: the game is played with $n$ positions for coloured pegs selected among $k $ colors. The original classic game has 4 positions and 6 colours. The game starts with the code-maker choosing a secret colour sequence of $n$ colours $s$ with
$s = (s_1, s_2, ... s_n) \in (1, 2, 3, ..., k^n)$.

The game proceeds with rounds of guesses from the code-breaker and feedback from the code-maker, where each guess is scored with black and white pegs:

Black pegs: for each correct color in a correct position
White pegs: for each correct color in an incorrect position

The goal is to minimize a limited number of rounds to guess the code. Three solver methods will be discussed in this article:

Knuth’s algorithm is a classic implementation which has been proven to solve any code with $(n=4,k=6)$ in 5 moves or less (with a standard first guess). The second method uses Grover’s quantum search to amplify the solution by iterating calls to an oracle which has knowledge of the secret code. The third is another quantum method performing synchronous executions of Deutsch’s algorithm, and then classically processes the results to solve the code.

Knuth and Grover can be implemented with a common model of a Mastermind game. But a major difference with the quantum methods is how they do not utilize feedback with black and white feedback pegs. The Deutsch solver uses the concept of a black peg match on pairs, but in any case, the two quantum methods are non-adaptive, that is, feedback results are not used in subsequent processing. Knuth’s is adaptive: feedback is used to filter for the next guess.

The solvers’ complexities vary: Knuth’s iterations are 5 (or less), but that comes with an extreme time complexity of $O(k^{2n})$. Grover’s optimal iteration complexity is $O(\sqrt{k^n})$, a quadratic improvement on classical Knuth’s time complexity. The Deutsch method improves on Grover and is linear $O(k) $ (!)

Modeling the Game

For Knuth and Grover a common class can be used for a game instance: Knuth and Grover require all the possible outcomes to be initialized. The solvers differ of course: Knuth finds the solution performing classical filtering based on feedback, while Grover’s finds the solution performing quantum amplitude amplification via an oracle. This differs from Deutsch which does not need the entire set: it performs a series of quantum queries where each reveal the presence of specific colors at all positions in parallel, with a final step which constructs the solution from the results.

Here is the class shared by Knuth and Grover. It creates a game instance with some default settings: replacement, four positions, and a random secret code. Since these two methods have complexity exponential on $n $ the value $k$ = 6 will be constant and will use the first 6 colours from “ROYGBIV”.

class MMGame:
    def __init__(self, code_length: int=4, secret_code: str=None, replace: bool=True):
        """ Initialize game with code length, optional secret, and replace mode """
        self.colours: dict[str, str] = {'R': 'Red', 'O':'Orange', 'Y':'Yellow',
                                       'G':'GREEN', 'B':'Blue', 'I':'Indigo'}
        self.code_length: int = code_length
        self.all_codes: list[str] = self._generate_all_codes(replace=replace)
        self.secret_code: str = secret_code if secret_code else random.choice(self.all_codes)

    def _generate_all_codes(self, replace: bool=False) -> list[str]:
        """ Generate all possible codes with or without replacement."""
        from itertools import permutations, product
        if replace:
            return [''.join(p) for p in product(self.colours.keys(), repeat=self.code_length)]
        else:
            return [''.join(p) for p in permutations(self.colours.keys(), self.code_length)]

The Knuth Solver

In 1976 Donald Knuth published his Mastermind solver. The solution involves iterating on guesses and feedback, where after each guess the remaining possible codes are narrowed down based on white/black peg feedback. The codes are pruned until there is only one code left.

The strategy is based on a minimax technique: minimize the maximum number of remaining possibilities. It guarantees finding the solution in at most five guesses for the classic original game with 4 colours and 6 positions. It has been a benchmark for the minimum number of guesses to determine the secret code

Knuth steps:

Start with all possible codes.
Make an initial guess (the best is to start with 2 colours each repeated twice.)
Score the guess against the secret, using the feedback.
Prune possible codes inconsistent with that feedback.
Select the next guess: Consider each remaining possible code as the secret code, and get score feedback against the remaining codes, count every possible feedback response to determine the code with the maximum feedback. The next guess is the code that has the lowest of that maximum.

Implementation Walkthrough

The Knuth solver defines feedback pegs (black, white, and empty), a game, game play history, and methods to score the black/white peg feedback. Note that the feedback for a guess can be with respect to a given reference code, or the actual secret code, a feature which is used in selecting the next guess.

class KnuthSolver:

    class Peg(Enum):
        BLACK = 2
        WHITE = 1
        NONE = 0

    def __init__(self, game: MMGame):
        """ Initialize solver with a MasterMind game with all possible codes."""
        self.game = game
        self.possible_codes = self.game.all_codes.copy()
        self.history = []

    def _get_feedback(self, guess: str, ref_code: str=None) -> list[Peg]:
        """ Compute feedback pegs comparing guess to reference code or secret """
        ref_code = ref_code if ref_code else self.game.secret_code
        black = sum(g == c for g, c in zip(guess, ref_code))
        white = sum(min(guess.count(c), ref_code.count(c))
                    for c in set(self.game.colours.keys())) - black
        feedback = [self.Peg.BLACK] * black + [self.Peg.WHITE] * white
        feedback += [self.Peg.NONE] * (self.game.code_length - len(feedback))
        return feedback

    def score_feedback(self, code: str, guess: str=None) -> tuple[Peg]:
        """ Return a sorted tuple of Peg feedback for a given code and guess """
        return tuple(
            sorted(
                self._get_feedback(code, guess),
                key=lambda x: x.value,
                reverse=True
            )
        )

With this we can create a game instance, pass it into the solver and score feedback based on a guess:

m_game = MMGame(secret_code='RBRY')
solver = KnuthSolver(mm_game)
print(f"Total possible codes = {len(solver.possible_codes)}")
print(f"Secret code = {solver.game.secret_code}")
feedback = [f.name for f in solver.score_feedback('RRBB')]
print(f"Score feedback on guess RRBB: {feedback}")

Total possible codes = 1296
Secret code = RBRY
Score feedback on guess RRBB: ['BLACK', 'WHITE', 'WHITE', 'NONE']

The solver takes an initial guess, scores the feedback, checks if the guess is the solution (all black pegs) and if not then prunes candidates and selects the next guess:

    def solve(self, initial_guess: str):
        guess = initial_guess
        while True:
            feedback = self.score_feedback(guess)
            self.history.append((guess, feedback))
            if feedback.count(Peg.BLACK) == self.game.code_length:
                return guess
            self.prune_candidates(guess, feedback)
            guess = self.next_guess()

Knuth prunes codes that do not produce the current feedback:

    def prune_candidates(self, guess: str, feedback: tuple):
        self.possible_codes = [
            c for c in self.possible_codes
            if self.score_feedback(c, guess) == feedback
        ]

The more complicated step is in selecting the next guess, which uses the minimax technique. For each of the remaining possible codes, consider them as the secret code and score the feedback for each based on guesses from the remaining possible codes! Then count the sets of feedbacks, and creates a map of the highest score for each guess.

e.g. for a remaining code RRRR as the guess, consider each remaining code as the secret code and get the following count of feedbacks, and then set the max feedback count for RRRR = 90.

[((BLACK, BLACK, NONE, NONE), 12), ((BLACK, NONE, NONE, NONE), 90), (NONE, NONE, NONE, NONE), 34)]

Over the entire set of remaining codes for the first pass in this case, we end up with max counts for each remaining code, and choose the code which has the least max count. The next guess is then chosen from the remaining codes that matches the minimum score, or if that isn’t the case, just choose the first guess.

    def next_guess(self) -> str:
        max_scores = {}
        for guess in self.possible_codes:
            # For each feedback response, count them as a set
            score_counts = Counter(
                self.score_feedback(guess, ref_code)
                for ref_code in self.possible_codes
            )
            max_score = max(score_counts.values())
            max_scores[guess] = max_score
        min_score = min(max_scores.values())
        best_guesses = [g for g, score in max_scores.items() if score == min_score]
        # Prefer guesses that are still possible codes
        return next((g for g in best_guesses if g in self.possible_codes), best_guesses[0])

Let’s run an example:

mm_game = MMGame(replace=True)  # random secret is chosen
solver = KnuthSolver(mm_game)
print(f"Secret code: {mm_game.secret_code}")
solution = solver.solve(initial_guess='RGBY')
print(f"Game solved in {len(solver.history)} guesses!")
for guess, feedback in solver.history:
    print(f"Guess: {guess}, Feedback: {[f.name for f in feedback]}")
assert solution == mm_game.secret_code

Secret code: ROYR 
Game solved in 4 guesses! 
Guess: RGBY, Feedback: ['BLACK', 'WHITE', 'NONE', 'NONE'] 
Guess: RRGO, Feedback: ['BLACK', 'WHITE', 'WHITE', 'NONE'] 
Guess: RBOR, Feedback: ['BLACK', 'BLACK', 'WHITE', 'NONE'] 
Guess: ROYR, Feedback: ['BLACK', 'BLACK', 'BLACK', 'BLACK']

Knuth’s approach is remarkably efficient in the number of guesses required, but it has significant computation costs !

Efficiency, Complexity, and the Cost of Knuth’s Five Guesses

Knuth’s algorithm in 1976 was remarkable in combinatorial game strategy. The promise of solving any standard Mastermind puzzle in five or fewer guesses was impressive, some even said it was almost magical. But there is a huge trade-off: while the number of guesses is minimal, the amount of computation to derive its guesses is significant.

As you can see in the code, every time a guess is chosen, every possible remaining code is scored to count every possible feedback, and then selects the next guess that has the smallest worst-case set. For $n$ positions and $k$ colors, the total number of possible codes $N$ grows exponentially: $N = k^n$

The complexity of pruning and scoring feedback on this large solution space after each move makes the algorithm impractical if the code length or number of colors increases. The time complexity is $O(N^2)$ per guess, since every possible code is scored, the feedback is counted: each are considered as a possible guess.

When we scale up the puzzle, the computational cost rises steeply. Lets compare the execution times for $n \in (4,5,6)$: (Apple M1 Pro with 8 Cores). I picked an example with a secret code and an initial guess that was expensive to solve for $n=4$:

### n = 4 ###
mm_game = MMGame(replace=True, code_length=4, secret_code='OOYG')
solver = KnuthSolver(mm_game)
solution = solver.solve(initial_guess='RGBY')

Secret code: OOYG 
Game solved in 5 guesses! 
Guess: RGBY, Feedback: ['WHITE', 'WHITE', 'NONE', 'NONE'] 
Guess: OROB, Feedback: ['BLACK', 'WHITE', 'NONE', 'NONE'] 
Guess: OYRI, Feedback: ['BLACK', 'WHITE', 'NONE', 'NONE'] 
Guess: BRII, Feedback: ['NONE', 'NONE', 'NONE', 'NONE'] 
Guess: OOYG, Feedback: ['BLACK', 'BLACK', 'BLACK', 'BLACK'] 
--> Elapsed time: 0.450990 seconds

### n = 5 ###
mm_game = MMGame(replace=True, code_length=5, secret_code='OOYGI')
solver = KnuthSolver(mm_game)
solution = solver.solve(initial_guess='RGBYY')

Secret code: OOYGI
Game solved in 5 guesses!
Guess: RGBYY, Feedback: ['WHITE', 'WHITE', 'NONE', 'NONE', 'NONE']
Guess: OBGOG, Feedback: ['BLACK', 'WHITE', 'WHITE', 'NONE', 'NONE']
Guess: BOROB, Feedback: ['BLACK', 'WHITE', 'NONE', 'NONE', 'NONE']
Guess: YOGIO, Feedback: ['BLACK', 'WHITE', 'WHITE', 'WHITE', 'WHITE']
Guess: OOYGI, Feedback: ['BLACK', 'BLACK', 'BLACK', 'BLACK', 'BLACK']
--> Elapsed time: 7.955119 seconds

### n = 6 ###
mm_game = MMGame(replace=True, code_length=6, secret_code='OOYGIB') 
solver = KnuthSolver(mm_game)
solution = solver.solve(initial_guess='RGBYYY')

Secret code: OOYGIB
Game solved in 5 guesses!
Guess: RGBYYY, Feedback: ['WHITE', 'WHITE', 'WHITE', 'NONE', 'NONE', 'NONE']
Guess: GBRROO, Feedback: ['WHITE', 'WHITE', 'WHITE', 'WHITE', 'NONE', 'NONE']
Guess: BRGIRI, Feedback: ['WHITE', 'WHITE', 'WHITE', 'NONE', 'NONE', 'NONE']
Guess: OYIOGB, Feedback: ['BLACK', 'BLACK', 'WHITE', 'WHITE', 'WHITE', 'WHITE']
Guess: OOYGIB, Feedback: ['BLACK', 'BLACK', 'BLACK', 'BLACK', 'BLACK', 'BLACK']
--> Elapsed time: 295.727246 seconds

In each case the code is solved in 5 guesses, but the execution time for each of those guesses grows exponentially. I’m not going to try any larger n, life is too short :)

The Exponential Wall and NP-Completeness

Is there a better way to search the code space? Can more information be extracted from each guess? Can it be done faster? There are other algorithms discussed here and here, but the exponential wall is always there, baked into the game: $N=k^n $

In this paper from 2004, De Bondt proves that deciding whether any code fits a series of guesses and feedbacks is NP-complete. This means the problem is as hard as the most difficult problems in NP: the class of problems where a solution can be verified quickly, but there is no known polynomial-time algorithm to actually find that solution. So classical algorithms to solve Mastermind inevitably become infeasible to solve as positions $n$ and colors $k$ increase.

This is where quantum algorithms offer something: By exploiting quantum parallelism, it is possible to crack the secret code without the classical burden of evaluating every possible candidate. Let’s leave Knuth and move onto Grover and Deutsch where we see how two methods solve the secret code using two different quantum algorithms.

Grover’s Mastermind: Use the Quantum Force

The exponential complexity of Knuth’s algorithm is due to brute force filtering: $O(N^2) $ over $|N|= |k^n| $ . With Grover’s algorithm we don’t need feedback: skip all the guessing, checking, filtering: amplify the secret code directly out of an exponentially large space of possibilities. No black pegs, no white pegs, just quantum amplitude amplification.

I discussed Grover’s in a previous article so if you want more details check it out. The code and process here is very similar: create an oracle which marks the solution, add and compose a Grover operator to create a circuit, and then run iterations for amplification. The previous article searched for 3 winning Euchre hands, this one for Mastermind is even simpler: the oracle only marks a single solution. Unlike Knuth’s clever but complex filtering with adaptive guesses, Grover’s quantum method is non-adaptive and just asks: “Call an oracle a few times to find the solution”

Grover Steps:

All possible codes in superposition: For $n$ positions and $k$ possible colours, the search space is $|N| = |k^n|$. Grover’s algorithm places all $N$ codes in equal quantum superposition.
Create oracle which marks the solution: The oracle flips the sign of the quantum amplitude for a single code which matches the secret code.
Perform Grover iterations to amplify the marked state: Each Grover iteration increases the probability of measuring the marked secret code.
Measure to reveal the secret: After a small number of iterations $O(\sqrt{N})$, measure the quantum state. With high probability, the secret code will be selected.

The Oracle in Step 2:

The oracle in Grover’s is a unitary operator which acts as follows:

$$U_{secret}|x\rangle \longmapsto \begin{cases} -|x\rangle & \text{if } x = \text{secret} \\\\ \phantom{-}|x\rangle & \text{otherwise} \end{cases}$$

Implementation Walkthrough

Setup: Define the game and initialize Grover’s solver. This uses the same MMGame class.

mm = MMGame(replace=True, code_length=4)  # for specific code: e.g. secret_code="BGRY"
solver = QuantumMMSolver(mm, backend='Aer')
print(f"Total permutations: {len(mm.all_codes)}")
print(f"Secret: {mm.secret_code}")

Oracle Construction: This circuit marks only the correct secret code.

solver.build_oracle(phase_oracle=True, log=True)

Build backend and run: Construct Grover circuit and execute

solver.build_backend(log=True)
counts = solver.run_grover()

Interpret and process results: Check bitstring for validity within the colour space and plot results.

def is_valid_result(bits):
    # Ensures result encodes a valid colour combination
    ...
valid_counts = {b: c for b, c in counts.items() if is_valid_result(b)}
# Map bitstrings back to codes for display
...
plot_distribution(decoded_top, title="Mastermind Solver Results"

Notes:

No feedback: This approach ignores feedback (black/white pegs). It’s a full search: the quantum circuit knows the secret code only through an oracle.
Quantum advantage: In classical search over $N $ possibilities we have $O(N)$. Knuth’s processing is $O(N^2)$. Grover’s optimal complexity is $O(\sqrt{N})$, still exponential since $N=k^n$, but a quadratic speedup.
Circuit size: This oracle-only model results in a single, potentially deep quantum circuit.

A Qiskit QuantumMMSolver

The MMGame class is the same as above, here is the QuantumMMSolver code using Qiskit. There are also methods for bitstring maniipulation and encode / decode:

from qiskit_aer import AerSimulator
from qiskit.circuit import QuantumCircuit
from qiskit.circuit.library import MCMTGate, ZGate, GroverOperator
from qiskit.circuit.library.phase_oracle import PhaseOracle
from qiskit_ibm_runtime import SamplerV2 as Sampler, Session
from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime.fake_provider import FakeAlmadenV2
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
from qiskit.visualization import plot_distribution

from enum import Enum
from typing import Union
import random
import math

class QuantumMMSolver:
    def __init__(self, mm_game: MMGame, backend: str='AER'):
        """ Initialize solver with game instance and mappings """
        self.mm_game: MMGame = mm_game
        self.num_solutions = 1
        self.char_bits: int = 3
        self.code_bits: int = self.char_bits * self.mm_game.code_length
        self.colour_to_bin = {
            c: format(i, f'0{self.char_bits}b')
            for i, c in enumerate(mm_game.colours)
        }
        self.bin_to_colour = {v: k for k, v in self.colour_to_bin.items()}
        self.solved: bool = False
        self.oracle: Union[PhaseOracle, QuantumCircuit] = None
        self.isa_circuit = None
        if backend.upper() == 'AER':
            self.backend = AerSimulator()
        elif backend.upper() == 'FAKE':
            self.backend = FakeAlmadenV2()
        elif backend.upper() == 'IBM':
            self.backend = QiskitRuntimeService().least_busy(operational=True, simulator=False)            

    def _iterations(self, number: int=None, imax: int=10, imin: int=3) -> int:
        """ Compute clamped number of Grover iterations based on remaining solutions """
        if number:
            return number
        i = math.floor(
            math.pi / 
            (4 * math.asin(math.sqrt(self.num_solutions / 2**self.code_bits)))
        )
        return max(imin, min(i, imax))

    def encode(self, code: str) -> str:
        """ Convert colour code string into binary bitstring """
        return ''.join(self.colour_to_bin[c] for c in code)

    def decode(self, bitstring: Union[int, str]) -> str:
        """ Convert binary bitstring or integer into colour code string """
        if isinstance(bitstring, int):
            bitstring = format(bitstring, f"0{self.code_bits}b")
        return ''.join(
            self.bin_to_colour[bitstring[i:i+self.char_bits]]
            for i in range(0, len(bitstring), self.char_bits)
        )

    @staticmethod
    def _bitstrings_to_formula(bitstrings: list[str]) -> str:
        """
        Convert bitstring list to logical formula. Use with PhaseOracle.
        e.g ["101...", "010...", ...] => (q0 & ~q1 & q2 & ...) | (...)
        """
        terms = []
        for bstring in bitstrings:
            bits = []
            for idx, bit in enumerate(bstring):
                t = '' if bit == '1' else '~'
                bits.append(f'{t}q{idx}')
            term = '(' + ' & '.join(bits) + ')'
            terms.append(term)
        return ' | '.join(terms)

    def build_oracle(self, log: bool=False, phase_oracle: bool=False):
        """ Build Grover oracle circuit using either PhaseOracle or manual gates """
        solution_bitstring = self.encode(self.mm_game.secret_code)[::-1]
        if phase_oracle:
            logical_formula = self._bitstrings_to_formula([solution_bitstring])
            self.oracle = PhaseOracle(logical_formula)
        else:
            n = self.code_bits
            qc = QuantumCircuit(n)
            zeros = [i for i, bit in enumerate(solution_bitstring) if bit == '0']
            qc.x(zeros)
            qc.compose(MCMTGate(ZGate(), n - 1, 1), inplace=True)
            qc.x(zeros)
            self.oracle = qc
        if log:
            print("Oracle depth:", self.oracle.decompose().depth())
            print("Oracle size (gate count):", self.oracle.size())
            print("Oracle width (qubits used):", self.oracle.width())

    def build_backend(self, iterations: int=None, log: bool=False):
        """ Compose and build Grover circuit for execution on backend """
        if log:
            print(f"Backend selected: {self.backend.name} with {self.backend.num_qubits} qubits")
            print("Compose Grover operator...")
        grover_op = GroverOperator(self.oracle)
        qc = QuantumCircuit(self.code_bits)
        qc.h(range(self.code_bits))
        qc.compose(grover_op.power(self._iterations(iterations)), inplace=True)
        qc.measure_all()
        if log:
            print(f"Circuit composed: iterations={self._iterations(iterations)}")

        pm = generate_preset_pass_manager(backend=self.backend, optimization_level=1)
        self.isa_circuit = pm.run(qc)
        if log:
            print("Grover circuit depth:", self.isa_circuit.depth())
            print("Grover circuit size (gate count):", self.isa_circuit.size())
            print("Grover circuit width (qubits used):", self.isa_circuit.width())

    def run_grover(self, shots: int=10_000) -> dict[str, int]:
        """ Execute Grover circuit using V2 sampler and return measurement counts """
        self.isa_circuit.draw()
        with Session(backend=self.backend) as session:
            sampler = Sampler()
            results = sampler.run([self.isa_circuit]).result()
            return results[0].data.meas.get_counts()

Usage:

# Set up game and solver
mm = MMGame(replace=True, code_length=4)
solver = QuantumMMSolver(mm, backend='Aer')
print(f"Total permutations: {len(mm.all_codes)}")
print(f"Secret: {mm.secret_code}")

# Build oracle using PhaseOracle
solver.build_oracle(phase_oracle=True, log=True)

# Build backend and circuit
solver.build_backend(log=True)

# Run Grover
counts = solver.run_grover() 

def is_valid_result(bits):
    """ Filter results ensuring within range of game colours """
    if isinstance(bits, int):  
        bits = format(bits, f"0{solver.code_bits}b")
    bitstrings = [bits[i:i+solver.char_bits] for i in range(0, len(bits), solver.char_bits)]
    result = all(int(b, 2) < len(solver.mm_game.colours) for b in bitstrings)
    return result

valid_counts = {b: c for b, c in counts.items() if is_valid_result(b)}

top = dict(sorted(valid_counts.items(), key=lambda x: -x[1])[:12])
decoded_top = {}
for k, v in top.items():
    # for simulator: convert from integer
    if isinstance(k, int):
        bitstring = format(k, f"0{solver.code_bits}b")
    else:
        bitstring = k          # for Simulators: same endianness
        # bitstring = k[::-1]  # for mocked backend and IBM Quantum: big-endian bitstring

    code = solver.decode(bitstring)
    decoded_top[code] = v

plot_distribution(decoded_top, title="Mastermind Solver Results")

Sample run, with total iterations = 10. Note the gate counts and circuit size and depths.

Total permutations: 1296
Secret: GGRB
Oracle depth: 3
Oracle size (gate count): 1
Oracle width (qubits used): 12
Backend selected: aer_simulator with 30 qubits
Compose Grover operator...
Circuit composed: iterations=10
Grover circuit depth: 42
Grover circuit size (gate count): 283
Grover circuit width (qubits used): 24

Improving on Grover’s: a Deutsch Approach

While Grover’s algorithm gives Mastermind a quadratic boost over classical methods it is still a quantum brute force search: the time complexity is $O(\sqrt{N})$ where $N = k^n$, so it is still behind the exponential wall.

But quantum computation is more than just faster search: sometimes, it can transform the problem altogether. What if, instead of searching for a single solution among all possibilities, we could “learn” global information about the secret in a few highly-structured quantum queries?

That’s the approach taken by an algorithm inspired by the Deutsch-Jozsa framework as described in Li, Luo, Xu (2023). This quantum method leverages pairwise colour oracles and non-adaptive queries, trading the brute force of Grover’s for smaller parallel calls that extract the entire secret with only $(k-1)$ queries.

The Math: Oracle Construction and Algorithm

Following algorithm 1 and 2 in Li, Luo, Xu (2023) given a secret string $s \in [k]^n$ (with $n$ positions and $k$ colours), construct a sequence of oracles $B_s^{(c_1, c_i)}$ for each pair $(c_1, c_i) (i = 2, \ldots, k)$:

$$B_s^{(c_1, c_i)}(x) = \sum_{j=1}^n \left(\delta_{x_j, 0} \delta_{s_j, c_1} + \delta_{x_j, 1} \delta_{s_j, c_i}\right)$$

This function tells us, for any bitstring $x$, how many positions correspond to $c_1$ or $c_i$ in the secret.
The quantum oracle is this transformation:

$$|x\rangle |b\rangle \mapsto |x\rangle |b \oplus B_s^{(c_1, c_i)}(x)\rangle$$

That does look a little scary, but the actual implementation is simple: for each oracle, mark the quantum state (flip the phase) if the position matches either colour:

def mastermind_deutsch_oracle(secret, c1, c2, n):
    qc = QuantumCircuit(n)
    for j in range(n):
        if secret[j] == c1:
            qc.x(j)
            qc.z(j)
            qc.x(j)
        if secret[j] == c2:
            qc.z(j)
    return qc

The overall circuit for each query follows a Deutsch-Jozsa pattern:

Prepare a uniform superposition over all bitstrings with Hadamards.
Apply the oracle for $(c_1, c_i)$.
Apply Hadamards again.
Measure.

From the paper we have the FindTwoColourPosition method:

def find_two_colour_position(n, color_oracle):
    qc = QuantumCircuit(n, n)
    qc.h(range(n))
    qc.compose(color_oracle, inplace=True)
    qc.h(range(n))
    qc.measure(range(n), range(n))
    # ...simulate and return the most frequent bitstring...

By repeating this for each $(c_1, c_i)$, the algorithm learns the colour at each position directly, and the solution can be derived from $k-1$ queries. Note that the work is spread out across sequential oracle calls implemented with smaller circuits. This is a much more scalable algorithm than Grover’s where circuit dimensions increase dramatically as $k $ increases.

From the paper, for each fixed reference color $c_1$ and each other color $c_i$ $(i = 2, \dots, k)$, we define a membership string $M$:

$$M^{(c_1, c_i)}_j = \begin{cases} 1 & \text{if } s_j = c_1 \text{ or } s_j = c_i \\ 0 & \text{otherwise} \end{cases}$$

In the code, creating the membership and combined measurements is a simple loop, where each iteration gathers a bit more information until all information is gathered.

for ci in range(2, k + 1): 
    oracle = mastermind_deutsch_oracle(secret, c1, ci, n) 
    membership = find_two_colour_position(n, oracle)
    measurements[(c1, ci)] = membership[::-1]  # ...combine results to reconstruct the code...

Once all membership strings are collected, the solution code $s $ can be decoded, which is implemented in decode_solution():

$$\begin{alignat}{2} \text{If for a given position } j: \, M^{(c_1, c_i)}_j = 1 \text{ for all } i, \text{ then } s_j = c_1 \\ \text{Otherwise } s_j \text{ is the smallest } c_i \text{ where } \, M^{(c_1, c_i)}_j = 1 \end{alignat}$$

Notes:

$O(k)$ complexity: Only $k-1$ queries are needed regardless of number of positions $n$.
Non-adaptive: All queries are fixed in advance: no need for back-and-forth with the game.
Exact: The algorithm reconstructs the secret with certainty.

Full code: Qiskit Deutsch-inspired Solver

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
from qiskit_ibm_runtime import SamplerV2 as Sampler, Session
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
from enum import Enum
import random

class Colour(Enum):
    RED = 1
    ORANGE = 2
    YELLOW = 3
    GREEN = 4
    BLUE = 5
    INDIGO = 6
    VIOLET = 7
    WHITE = 8

def encode_colour_sequence(colours):
    """ convert a list of Colour enums to 1-based integer indices """
    return [c.value for c in colours]

def decode_colour_sequence(indices):
    """ convert a list of 1-based indices to Colour enums """
    return [Colour(i) for i in indices]

# Choose n random colours from the first c Colours (with possible repeats)
def random_secret_colours(n_positions, n_colours):
    """ generate random list of Colour enums of length n """
    return random.choices(list(Colour)[:n_colours], k=n_positions)

def decode_solution(memberships, k, n):
    """ decode secret code from measured membership bitstrings """
    solution = []
    for pos in range(n):
        bits = [int(memberships[(1, ci)][pos]) for ci in range(2, k+1)]
        if all(bits):
            solution.append(1)
        else:
            for i, bit in enumerate(bits, start=2):
                if bit:
                    solution.append(i)
                    break                            
    return decode_colour_sequence(solution)

def mastermind_deutsch_oracle(secret, c1, c2, n, log=False):    
    """ create oracle marking states where positions match c1 or c2 in the secret """
    qc = QuantumCircuit(n)
    for j in range(n):
        if secret[j] == c1:
            qc.x(j)
            qc.z(j)
            qc.x(j)
        if secret[j] == c2:
            qc.z(j)
    if log:
        print("Oracle depth:", qc.decompose().depth())
        print("Oracle size (gate count):", qc.size())
        print("Oracle width (qubits used):", qc.width())
    return qc

def find_two_colour_position(n, color_oracle, log=False):
    """ create and run Deutsch-Jozsa circuit to return probable bitstrings """
    qc = QuantumCircuit(n, n)
    qc.h(range(n))
    qc.compose(color_oracle, inplace=True)
    qc.h(range(n))
    qc.measure(range(n), range(n))

    backend = AerSimulator()
    if log:
        print(f"Backend selected: {backend.name} with {backend.num_qubits} qubits")

    pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
    isa_circuit = pm.run(qc)

    if log:
        print("ISA circuit depth:", isa_circuit.decompose().depth())
        print("ISA circuit size (gate count):", isa_circuit.size())
        print("ISA circuit width (qubits used):", isa_circuit.width())

    with Session(backend=backend) as session:
        sampler = Sampler(mode=session)
        results = sampler.run([isa_circuit]).result()
        counts = results[0].data.c.get_counts()
    return max(counts, key=counts.get)

def mastermind_non_adaptive(k, n, secret_code, log=False):
    """ a non-adaptive algorithm iterating on the Deutsch-Jozsa-ish oracle """
    secret = encode_colour_sequence(secret_code)
    measurements = {}
    c1 = 1  # 1-based index for colours
    for ci in range(2, k + 1):
        oracle = mastermind_deutsch_oracle(secret, c1, ci, n, log=log)
        membership = find_two_colour_position(n, oracle, log=log)
        measurements[(c1, ci)] = membership[::-1]

    if log: 
        print("Quantum measured membership bitstrings for (c1, ci) pairs:")
        for ci in range(2, k + 1):
            print(f"(c1={c1}, ci={ci}): {measurements[(c1, ci)]}")

        print(f"\nClassical membership matrix (rows: positions, cols: colours 1-{k}):")
        for pos in range(n):
            print([int(secret[pos] == c) for c in range(1, k+1)])

    return decode_solution(measurements, k, n)


k = 6  # number of colours in game
n = 4  # number of positions in solution

# secret_colours = [Colour.BLUE, Colour.ORANGE, Colour.YELLOW, Colour.ORANGE]  # List of Colour enums
secret_code = random_secret_colours(n, k)

solution_colours = mastermind_non_adaptive(k, n, secret_code, log=True)

print("\nSecret code:", [c.name for c in secret_code])
print("Solution   :", [c.name for c in solution_colours])

Running the code above: $n=4$, $k=6$:

Quantum measured membership bitstrings for (c1, ci) pairs:
(c1=1, ci=2): 1011
(c1=1, ci=3): 1001
(c1=1, ci=4): 1001
(c1=1, ci=5): 1001
(c1=1, ci=6): 1101

Classical membership matrix (rows: positions, cols: colours 1-6):
[1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]

Secret code: ['RED', 'INDIGO', 'ORANGE', 'RED']
Solution   : ['RED', 'INDIGO', 'ORANGE', 'RED']

Here are the details for one of the $k-1 $ oracles and its circuit diagram. Note the small size compared to Grover’s:

Oracle depth: 3
Oracle size (gate count): 7
Oracle width (qubits used): 4
Backend selected: aer_simulator with 30 qubits
ISA circuit depth: 2
ISA circuit size (gate count): 7
ISA circuit width (qubits used): 8
------
global phase: π
     ┌────────────┐   ┌─┐      
q_0: ┤ U3(π,0,-π) ├───┤M├──────
     ├────────────┤   └╥┘┌─┐   
q_1: ┤ U3(π,-π,0) ├────╫─┤M├───
     └────────────┘┌─┐ ║ └╥┘   
q_2: ──────────────┤M├─╫──╫────
     ┌────────────┐└╥┘ ║  ║ ┌─┐
q_3: ┤ U3(π,0,-π) ├─╫──╫──╫─┤M├
     └────────────┘ ║  ║  ║ └╥┘
c: 4/═══════════════╩══╩══╩══╩═
                    2  0  1  3

Complexity:

This was shown above and in the referenced paper to be $O(\sqrt{k}) $ . But In the tradition of one of my former professors, the late great Dr. Ralph G Stanton, the exercise and coding will be left for the student.👨‍🎓👩🏽‍🎓🧑🏻‍🎓

Conclusion

In summary, while Grover’s quantum brute force is still fundamentally limited by the size of the problem, the Deutsch-style approach is a great example of how a quantum algorithm can leverage problem structure to collapse complexity from exponential to linear. This leap in efficiency is possible only by reimagining how quantum circuits can extract global patterns invisible to classical search.

This Casual Chronicle dove a bit deeper into quantum algorithms with Mastermind solvers. It took a look at three fundamentally different approaches: Knuth’s classical algorithm, Grover’s quantum search, and a Deutsch quantum-iterative algorithm.

Once the rules of Mastermind were modeled Knuth’s efficient guess count but exponential filtering method over $N = k^n$ was explored. Grover’s algorithm offered a quantum boost, amplifying the probability of finding the solution in $O(\sqrt{N})$, though still fundamentally a global search.

The real leap in performance is with utilizing Deutsch, which doesn’t actually do a search, rather, it uses quantum parallelism to learn global properties of the secret in just $O(k)$queries. This algorithm dramatically reduces complexity by approaching the problem in smaller increments with a classical derivation of the solution in a post-quantum process.

Each code-cracking method has its own strengths and weaknesses: Knuth’s guarantees minimal guesses, but with expensive computation cost for each guess. Grover’s searches via quantum amplitude amplification, but with large circuits as a penalty. The Deutsch approach reveals how quantum structure and a simple set of oracles can sidestep the exponential wall: its complexity is linear. It also can be improved: in Li, Luo, Xu there is an adaptive version which has complexity $O(\sqrt{k})$!

A big high five if you made it this far in this rather lengthy Casual Chronicle ! Thanks for reading ! —carl—

https://github.com/carlek/qiskit-fun

https://learning.quantum.ibm.com/tutorial/grovers-algorithm

https://learning.quantum.ibm.com/course/fundamentals-of-quantum-algorithms/quantum-query-algorithms#deutschs-algorithm

https://theses.liacs.nl/pdf/2018-2019-GraafSde.pdf

https://arxiv.org/pdf/2207.09356

https://www.researchgate.net/publication/254888546_NP-completeness_of_Master_Mind_and_Minesweeper