Guest Seating using Quantum Computing and Grover’s Algorithm
Dive into Quantum Computing with Q# | Akvelon, Inc.
Quantum computing is a relatively 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.
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.
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:
Or more visually:
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.
Grover’s algorithm
Grover’s algorithm allows us to search through state space of N dimensions in only O(sqrt(N)) time. We will use this to find among all possible seating arrangements those that satisfy our constraints.
Discussion of Grover’s algorithm itself is beyond the scope of this article so we assume at least a basic understanding of it. Qiskit provides a great explanation if you want to learn about it.
Our implementation looks like this:
It takes the input: the number of guests and the list of enemies, — and runs the specified number of Grover iterations, each applying an “oracle” and the Grover’s diffusion operator.
Oracles are common elements of quantum algorithms. In this case, its task is to somehow mark, or distinguish, the solution states.
Grover’s algorithm takes an oracle which adds a negative phase to those states that represent a valid solution, also known as a phase oracle. We construct one from a more simple marking oracle, whose task is to simply flip an auxiliary qubit if the solution is valid. This technique is known as phase kickback.
We will concentrate on the implementation of this oracle.
Oracle
Our qubit state register, on measurement, can yield a seating where any of the four guests can take any of the four seats. To get a valid solution, it is sufficient to check two constraints:
- No two neighboring guests are enemies.
- All guests are seated or, equivalently, all seated guests are different.
First, we will prepare two additional qubit registers to perform these checks:
As can be seen, we only flip the ancillary qubit when all checks have passed.
Next, we want to check the constraints and mark our check qubits if the constraints are satisfied.
Lets see how we can check if two guests are enemies.
Similarly, we can verify that two guests aren’t the same.
And now to check all pairs of guests.
Output
Finally, after running the Grover’s search we want to measure our qubits and see if the result is a valid solution. It can be verified using the same marking oracle as for the main algorithm. We simply define another qubit for this verification and check if it was flipped or not.
We also defined a couple of our own auxiliary functions to transform the measurement result into a readable answer:
Number of iterations
One last thing we haven’t addressed yet is the number of Grover iterations that we run. The default formula for the required number of iterations will be
where N is the total number of possible states and k is the number of solution states.
Which we can calculate in Q# like so:
Of course, the number of solutions k is not known beforehand. It can be addressed, however, by trying all k ∈ {1, 2, …, 2ⁱ ≤ N}. This way, we will find the correct solution with high probability eventually.
And the main loop of our algorithm now looks like this:
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.
The final code for the entire program can be found here.
Running the algorithm
Our program should use up to 24 qubits at a time provided this input — a few too many for the publicly available quantum computers at the moment (ones with fully connected topology). A simulator, however, can handle that amount even on a simple laptop.
A simple way to run this code is using Visual Studio paired with a quantum development kit extension. Running the program using the built-in quantum simulator yields the expected output:
Answer: 2 4 1 3A valid seating has been found.
Analysis
But is the performance of the algorithm any good? Let’s look at the time complexity that we’ve managed to achieve.
The Grover’s algorithm itself takes O(sqrt(N/k)) iterations. As you remember, we tried multiple different k from 1 to 2ⁱ = N. It’s easy to see, however, that this only adds a small constant to the overall estimation:
The other component is the oracle. The slowest part of it is verifying that the neighboring guests aren’t enemies. Let the number of guests be g. Remember that the size of the qubit register n = g log₂(g) and the size of the vector space N = 2ⁿ. The number of neighbor pairs is g, each guest takes log₂(g) iterations to process, and the number of enemy pairs is O(g²) giving us the total of O(g³log₂(g)) iterations for the entire check.
The total time complexity of the algorithm will be
or, formulated in terms of the number of guests
which, despite looking complicated, is better than the straightforward, “bruteforce” search at O(g!) for a large enough number of guests:
Conclusion
Thus, we were able to achieve a significant speedup over an exhaustive search, albeit it cannot be observed on such small input. It demonstrates how quantum paradigm can provide fundamentally new approaches to solving existing problems, especially hard ones, resulting in competitive algorithms and potentially breakthrough improvements over classical algorithms.
We are excited about the development and growing availability of quantum hardware and look forward to learning more about quantum computing and how it can be applied to known problems.
This work was conducted at Akvelon, Inc. Akvelon is a custom software development company specializing in the development, testing, consulting and support of web, cloud, desktop and mobile solutions.