Quantum Secret Santa

It’s that beautiful time of the year again! It is snowing, reindeer are flying around, and families are coming together (with safe distancing) to celebrate the holidays.
During Christmas I normally play a game of Secret Santa with a group of people. The rules are quite simple: you write the names of everyone in the group on small pieces of paper. You throw all the pieces of paper in a big bowl and shuffle them. Lastly, everyone picks a name from the bowl; if someone picks their own name, the whole process starts again.
When everyone has a name picked, the fun part begins: you write a little poem and buy a small gift for the person that you have picked. On Christmas Eve you exchange the gifts and the poems.

You might think, what does this have to do with quantum computing and Q#?

When doing the Secret Santa this year, I asked myself: how would I use Q# to perform this Secret Santa raffle?

There are multiple ways to solve this; I settled on using Grover’s search to pick a valid solution.

Before we dive into the Q# code, let’s visualize the problem that needs to be solved. Below you see a matrix representing the raffle when playing with 3 people. You can see that the diagonal cells of the table do not have variables assigned to them, since in a valid solution you can’t pick yourself.

All the other cells have a variable x which can be either True or False. For example, if $x_0$ is True in the final solution, Tess has to buy Vincent a gift and write him a poem.

What are all the valid solutions to this problem? The solution is only valid if in each horizontal row and each vertical column there is exactly one True value.

This problem can be nicely mapped into a Boolean satisfiability problem (or SAT problem for short): we can construct a formula that has to evaluate to True for any valid solution to our problem. For the matrix above this formula looks as follows:

$$(x_o \oplus x_1) \wedge (x_2 \oplus x_3) \wedge (x_4 \oplus x_5) \wedge (x_2 \oplus x_4) \wedge (x_o \oplus x_5) \wedge (x_1 \oplus x_3) $$

Let’s look at this formula piece by piece, starting with $(x_0 \wedge x_1)$ . $\oplus$ is a XOR operator (also known as addition modulo 2), which means this term will only be True if one of the variables is True and the other is False. This corresponds to the requirement that the first row has exactly one True value. The second and third terms correspond to the requirements on the other two rows, and the last three terms – the requirements on the columns.

Next, $\wedge$ is an AND operator, so the whole formula will only evaluate as True if each of the individual terms is True. This means that in each of the smaller terms exactly one variable has to be True and the other False.

When the problem grows larger than 3 people, each row and each column has more than two variables. This means we cannot use the XOR operator to construct our terms any more, because we still only want a single True value in each row and each column. We need to introduce a special operator - the “exactly-1” operator which evaluates as True only if exactly one argument is True and all others are False regardless of the number of its arguments. Using this operator instead of XOR will generalize the problem for any number of Secret Santa participants.

Now we have the SAT problem that we want to solve; how can we solve this using Q#? The Quantum Katas – the collection of tutorials and programming exercises on quantum computing - have a whole chapter on how to solve SAT problems using Grover’s search algorithm.

However, if you going through this kata, you will find that the SAT formula we constructed is not a standard SAT problem, but rather an “exactly-1 SAT” problem, a mix of the standard SAT problems discussed in the first part of the kata and the “exactly-1 3-SAT” problem discussed in the second part. Below I will go through the changes I made to the kata code to make it work for this problem; you can find the end result here on GitHub.

In the SolveSATWithGrover code all terms of the formula are evaluated with a fixed gate - OR gate in the first part of the kata or “exactly-1 one” gate in the second part of the kata. Instead, we want to be able to use arbitrary types of gates depending on the problem we’re solving. To do this, I added an extra array to the 2D array of tuples that described the clauses of a SAT problem with fixed operators used in each clause (see the kata for the format description). This array lists the gates that should be applied when evaluating each clause of the formula. For example, the SAT formula  $(x_0 \oplus x_1) \wedge (x_2 \oplus x_3)$ would be described by these two arrays:

let problem = [[(0, true), (1, true)], [(2, true), (3, true)]];
let clauseTypes = [“XOR”, ”XOR”];

The rest of the code is fairly similar to the kata, except for the last part where I generate the SAT instance to solve depending on the number of players and print the results. Here is an example of program output for 3 players:

  |A    |B    |C    |
A |  X  |false|true |
B |true |  X  |false|
C |false|true |  X  |

I hope this little game will bring a nice sparkle of quantum to your holiday cheer. Take a look at the Quantum Katas and who knows – maybe you’ll find yourself inspired to experiment with Q# and applying it to some unusual problem!

Have great (and safe) holidays!

Vincent