∣GroverMind⟩

(we LovGroverMind) by Angelini Filippo, Campesan Giulia, Faorlin Tommaso, Marcomini Alessandro and Piccinelli Samuele.

Introduction: a Quantum challenge

As a creative project for the Microsoft challenge for qcHack 2021 we developed a quantum version of Mastermind which makes use of the Grover’s search algorithm. The goal here is to make Grover’s algorithm understandable and fun by applying its principles to a well-known game.

In the board game of Mastermind, one player becomes the codemaker and the other the codebreaker. The codemaker chooses a sequence of N code pegs and the codebreaker tries to guess the pattern, in both order and color, within eight to twelve turns. Each guess is followed by the codemaker’s feedback who provides hints on the correct placed pegs.

In our implementation, the Grover’s algorithm plays the role of the codebreaker and tries to guess an ordered sequence of 5 values, labelled by a selection of 4 possible colours. It’s the same old game but with a quantum twist: if we had your interest before, we are sure to have your attention now.

How does it work: Grover’s algorithm

Grover’s algorithm is a great example of a solution to a problem which can be efficiently solved by a quantum computer. Although the purpose of Grover’s algorithm is usually described as searching a database, it may be more accurate to think of it in terms of a search problem. Given any search task and N samples, a classical algorithm is able to find the solution by proceeding sequentially, scanning through each single element. The algorithm allows a quadratic gain, going from O(N) to O(√N). The algorithm runs as follows:

1. We start with a register of N qubits initialized to the ground state;
2. The register is put into a uniform superposition by applying an Hadamard gate to each qubit in the register;
3. We implement a function, typically called an oracle in the form of a unitary operator which returns 1 only when fed with the correct input;
4. The phase oracle applies a conditional phase shift of -1 for the wanted items: an Hadamard gate is applied to each qubit in the register before and after a conditional phase shift of -1 to every computational basis state except the ground one (CNOT gate).

The 4ᵗʰ point is repeated an optimal number of times. This is a pivotal step: after each iteration the squared amplitude of the queried element is increased. Like many quantum algorithms, Grover’s algorithm is probabilistic: luckily, it can be shown that the probability of failing scales as 1/N and is therefore generally negligible.

Our game

The whole game breaks down to the following steps:

1. Sequences initialization. The master starts by generating a sequence of 5 random numbers; the player draws his first random guess in the same fashion.
2. Sequences comparison. The player’s guess is then compared to the unknown master’s sequence, identifying in which positions the same colours are found. This makes up the master’s feedback which is exploited in the next step.
3. Oracle control. After receiving the master’s feedback, the player needs to formulate a new proposal. Since sequence of 5 numbers between 0 and 3 can be encoded in a 10 qubits register, starting from the basis states we apply to each qubit an Hadamard gate to create a superposition of all possible states. In this superposition, the oracle will consequently mark all the states for which the master hints are respected. We exploited the marking oracle trick, translating it into a phase oracle by means of the phase kick-back technique.
4. Grover’s search. We now iterate Grover’s algorithm in order to amplify the marked states. The optimal number of iterations has been estimated as follows:

where N and M are the number of possible and valid sequences respectively. This leads, in the case of N = 2¹⁰ possible combinations, to

where it is worth to observe that in the case where no numbers are being guessed, the number of iterations is π/4. After this process has come to an end, we proceed to measure our register and set the collapsed state as the new player’s proposal.

This implementation does not exploit the speed-up potential of the Grover algorithm, but it just proceeds through a traditional trial-and-error approach. We could have implemented a version in which the oracle knows the correct sequence and, within a certain probability, it is able to find it in a single trial. In this way, we would have exploited at its fullest the Grover speed up. But…. where’s the fun without a little effort? 😉

Our team

Given the state of the ongoing pandemic we couldn’t meet and work in presence; in spite of all the difficulties we had a great time working together and learned a lot in the process. This challenge gave us the opportunity to think outside the usual academic setting: we worked our way through 24 hours of coding to see the developement of a creative project, built upon our own ideas by applying our knowledge in a concrete way. Plus, Q# was a great deal of fun.

We hope to have got you excited about the quantum world as we are; just in case we’ve sparked your curiosity enough, you might want to look at the whole projet on GitHub.

Thanks Microsoft, Stanford University and Yale University for the opportunity!

Contacts

• Alessandro Marcomini (alessandro.marcomini.1@studenti.unipd.it)
• Tommaso Faorlin (tommaso.faorlin@studenti.unipd.it)
• Giulia Campesan (giulia.campesan.1@studenti.unipd.it)
• Samuele Piccinelli (samuele.piccinelli@studenti.unipd.it)
• Filippo Angelini (filippo.angelini@studenti.unipd.it)