[AWS Power Up] Beating Wordle Using the Hamming Distance and Variational Algorithms

Team Name:

Entangled_Pirates

Project Description:

The game 'Wordle', first created by Josh Wardle and now owned by the New York Times, is a word-guessing game in which the player must figure a secret word in 6 tries or less. After each try, the game reveals which letters are in the correct position in the secret word (green), which are in the word, but in an incorrect position (yellow), and which are not in the secret word (gray).

We can study the Hamming distance between two words by counting the amount of differing letters. If we find a word whose average distance to all the possible guesses is minimal, then we have a higher chance to get a green match with the secret word of the game. The information given back by the game is then used to shorten the number of possibilities, and the process is repeated. This can be encoded in a Hamiltonian and then minimized by using techniques like VQE or QAOA.

Sources: Khan, Mushahid, and Andriy Miranskyy. "String Comparison on a Quantum Computer Using Hamming Distance." arXiv preprint arXiv:2106.16173 (2021).

Source code:

Github repo to be added

Resource Estimate:

Encoding the entire English alphabet takes at least five qubits. A five-letter word will then take up to 25 qubits to be processed. The Quantum Wordle Solver will be simplified to run in a smaller amount of qubits. The additional credits will allow us to study the problem in a manner closer to the original game, and make a great number of measurements to best estimate an appropriate guess.

XanaduAI / QHack2022