Quantum Computing for normal people: Grover’s Algorithm and the quantum search engine
Published: 2023-09-07 07:32:27

Here’s another post in my series on understanding quantum computing as a normal person. We might not be super normal to have an interest in this, but I started down this path as a way to ensure my career in tech is broad and long lasting, and I quickly realised that you don’t need a PhD to work in quantum computing anymore than you need an aeronautical engineering degree to work in cloud computing. Pardon the pun. But the point is, there are fundamentals we can be aware of as enough information to begin to contribute to an industry that needs as many talents and skills as possible. And that includes you too, so let’s jump in.

## Introduction

Imagine going to the library to find that one book you desperately need for your research. If it’s a large library, you could spend hours searching through countless aisles and shelves. Now, what if there was a magical way to find your book faster, reducing your search time dramatically? Welcome to the realm of quantum computing, where something similar is actually possible! Specifically, we’re diving into Grover’s Algorithm — a game-changing way to search through databases quickly.

## What is Grover’s Algorithm?

Grover’s Algorithm is like a turbocharged search engine but for quantum computers. Invented by Lov Grover in 1996, it’s designed to find a specific item in an unsorted list much faster than any classical computer algorithm can. While a classical computer would need to look through each item one by one, Grover’s Algorithm can find the answer with fewer steps, making it exponentially faster.

## How Does It Work?

In a conventional computer, searching through a list is a simple but time-consuming process. Let’s say you have a list of 100 items. In the worst-case scenario, you’d have to check all 100 items to find the one you’re looking for. In the best case, you’d find it on your first try. On average, you’d check about 50 items.

Grover’s Algorithm, on the other hand, takes advantage of the weird and wonderful rules of quantum physics. In the quantum realm, information can exist in multiple states at once — this is called superposition. So instead of checking each item individually, a quantum computer could, theoretically, check multiple items at the same time.

The magic happens when Grover’s Algorithm amplifies the probability of finding the correct item while reducing the probability of the wrong ones. It’s like turning up the volume on your favorite song while muting all the others. After a few of these “amplification cycles,” the algorithm has a high likelihood of finding the item you’re looking for.

## Real-World Applications

You might be wondering, “That’s cool, but why should I care?” Well, Grover’s Algorithm has some promising real-world applications. For instance:

1. Database Searching: Businesses with huge databases could find the information they need more quickly and efficiently. It’s a powerful application but perhaps less funded than…

2. Drug Discovery: Pharmaceutical companies could use it to sift through enormous chemical databases to find potential new drugs. A lot of quantum companies are talking about this now (as they seem to need to prove some kind of revenue potential).

3. Cryptanalysis: While this might not be the most uplifting application, Grover’s Algorithm could break some forms of encryption faster than classical methods. There’s going to be a lot of hype and noise around this. So take note and be sceptical until we see otherwise.

## The Caveats

While Grover’s Algorithm is genuinely revolutionary, it’s essential to know that quantum computers capable of running it efficiently don’t yet exist. The hardware is still in the experimental stage, the funding seems to be drying up a little at the time I am writing this at the end of 2023, and scientists are tackling significant technical challenges despite the hype.

Moreover, the algorithm doesn’t make searching “instant.” It just makes it faster. For a list of 100 items, a classical computer might take 50 steps on average, but Grover’s Algorithm would take around 10. It’s a square root kind of relationship, so the bigger the list, the more time you save.

## Wrapping up

Grover’s Algorithm isn’t just a fanciful concept from the realm of quantum physics — it’s a pathway to solving real-world problems faster than we ever thought possible. While we’re still in the early stages of quantum computing, understanding methods like this helps us peek into a future where we can solve complex problems more efficiently than ever before. So the next time you’re lost in a library, just remember: Grover’s Algorithm could be the magical solution we’ve all been waiting for. Now just to make these machines that can do just that…