Technology Articles

Guest Seating using Quantum Computing and Grover’s Algorithm

blank

Dive into Quantum Computing with Q#

Quantum computing is a relativel new and developing area of engineering that promises many interesting applications from molecular simulation and encryption to quantum machine learning. What makes quantum computers special is the ability to harness quantum properties of their memory. Quantum effects such as superposition and entanglement make it possible to manage the amount of information exponentially greater than the number of qubits, or quantum memory units.

This opens the door to a number of unique algorithms. One of the most well-known so far is Grover’s algorithm for searching through an unstructured data set, which finds a solution among N items in only O(sqrt(N)) time — a quadratic speedup over the classical approach. It can also be thought of as an algorithm for reversing a function. This makes it an interesting candidate to solve hard problems that don’t have much structure, which could enable a simple and fast algorithm, as a faster alternative to exhaustive search.

Akvelon’s team decided to explore quantum computing and experiment with what tasks could be solved using Grover’s search. One such task is the guest seating problem.

The problem

Suppose that a number of guests are coming to a dinner. Some of the guests are known to be enemies. Given the list of guests as well as all pairs of enemies, find a way to seat all these guests around the table such that no enemies sit next to each other.

blank

This problem can be stated differently. Consider a graph of guests where edges exist between pairs of enemies, and it’s complement graph where edges lie only between not enemies or “compatible”, “seatable” next to each other guests. Our task is effectively to find a Hamiltonian cycle in this latter graph.

blank

It is known to be an NP-complete problem. These two tasks are equivalent.

Q#

We use Q# here because it is a domain-specific language, designed specifically for programming universal quantum computers. Because of that, it demonstrates quantum model quite well and reflects the specifics of working with qubits.

Q# can be used within VSCode or Visual Studio where the solution is run and tested via a built-in quantum simulator. It can then be potentially run on real quantum computers using cloud quantum services.

Input representation

Let’s assume we have a list of four guests. Two pairs of guests are enemies, like so:

blank

Or more visually:

blank

A solution to the problem will be the list of guests in order — a seating. As we plan to explore the state space to find our solution, we want to encode our states using a number of qubits — a register.

Each of n seats will require ⌈log₂(n)⌉ qubits to represent, or 2 in our case.

blank

blank

Grover’s algorithm

blank

Oracle

blank

blank
Similarly, we can verify that two guests aren’t the same.blank
And now to check all pairs of guests.blank

Output

blank

We also defined a couple of our own auxiliary functions to transform the measurement result into a readable answer:

blank

Number of iterations

blank

blank

blank

Finally, Grover’s algorithm is probabilistic, meaning that we find a solution with sufficiently high probability p < 1. Because of this, we will use this repeat-until-success pattern again and wrap everything once more so the program re-tries the algorithm until the answer is found.

blank

Running the algorithm

Answer: 2 4 1 3

Analysis

blank

blank

or, formulated in terms of the number of guests
blank
which, despite looking complicated, is better than the straightforward, “bruteforce” search at O(g!) for a large enough number of guests:
blank

Conclusion

This article was originally published on Medium by Kirill Nikonov from  Akvelon.