Akvelon | Guest Seating using Quantum Computing and Grover’s Algorithm
Akvelon’s team decided to explore quantum computing and experiment with what tasks could be solved using Grover’s search, aiming their focus on solving the guest seating problem.
Quantum Computing, Akvelon, Grover's Algorithm, Quantum engineering, Quantum
32173
post-template-default,single,single-post,postid-32173,single-format-standard,ajax_fade,page_not_loaded,,qode-theme-ver-8.0,wpb-js-composer js-comp-ver-4.9.2,vc_responsive
 

23 Jun Guest Seating using Quantum Computing and Grover’s Algorithm

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

Dive into Quantum Computing with Q#

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.

The problem

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.

 

Q#

Input representation

Or more visually:

Grover’s algorithm

Oracle

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

Output

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

Number of iterations

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.

Running the algorithm

Answer: 2 4 1 3

Analysis

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


 

More Insights

Slack Power BI Integration

 

Wanting to help Power BI reach an even broader audience, Akvelon sought to integrate Power BI with Slack so that the 10 million daily active users on Slack would have better access to Power BI’s data visualization tools. Read more here

How to Implement SMS Verification Codes Auto-Fill in React Native Android Apps

 

Akvelon’s Eldar Abdullazyanov discusses best ways to implement SMS verification codes auto-fill in for React Native Android apps. Read more here.

Make Pixel Art in Seconds With Machine Learning

Akvelon’s Irina Nikolaeva discusses how users can easily pixelate any image with Akvelon’s new PixelArt filter here 



Akvelon

Akvelon

We Make BIG Software Happen. Contact Us