Grover's algorithm

“Why does this website matter?”
I hear you say. The algorithm implementation I wrote is in Python. Usually you would need to install it on you computer to run it. But not in this case!

Thanks to WebAssembly and PyScript, you can run my code directly on your browser. How cool is that? No need for a server 🫡.

What is Grover's algorithm?

Grover's algorithm is a popular introductory algorithm in quantum computing that "finds" one or more elements in an unsorted list with an algorithmic complexity of \( O (\sqrt{N})\), which is even better than mergesort's \( O (n \log n) \) or radix sort's \( O (nk) \). Grover's algorithm offers a quadratic speedup.

It is said to be an "unstructured search" algorithm "because we are given no guarantees as to how the database is ordered." (Wright, 2015). Professor Umesh V. Vazirani at the University of California, Berkeley describes it as using a magnet to find the needle in a haystack (Vazirani, n.d.).

Okay, but what's the input and output? Let's look at an example:

• Say you input the numbers 2, 4, 7, 19.
• If everything goes well (crossed fingers), your output is… 2, 4, 7, 19.

Yes. You read that right: the algorithm searches for the numbers that you already… know? It's very, very pointless 😐.

Its entire shtick revolves around the proof of the quadratic speedup I mentioned above. So, yeah: this website only matters because of the Python on your browser deal.

References

1. Wright, John (2015, Sep 4). "Lecture 4: Grover’s Algorithm". CMU 15-859BB, Fall 2015).
2. Vazirani, Umesh V. (n.d.). "Lecture 11: Quantum Search (Needle in a haystack)". Quantum Mechanics & Quantum Computation, at University of California, Berkeley.