Gain insights into quantum computing, starting with qubits and quantum mechanics. Discover quantum gates, circuits, and algorithms like Grover’s search and Shor’s factoring. Explore potential applications.

Intro to Quantum Computing_Getting started with Burp Suite extension.png

tarball.tar.gz

Quantum Computing

Jupyter Notebook

Firms like IBM, Honeywell, Zapata, Rigetti, Amazon, Google, IonQ, and others are all adopting and investing heavily in quantum computing. This is a great opportunity to get involved.

In this course, you will learn the fundamentals of quantum computing, starting with quantum bits or qubits. These are the centerpiece and most basic computational unit. 

You will then move on to quantum mechanics and the role of quantum gates, circuits, and simulating computers. From there, you will get acquainted with the many different quantum algorithms that are asymptotically faster than their classical counterparts. These include: Deutsch Jozsa, Grover’s search, and Shor’s factoring.

By the end of this course, you will have the foundations in place to start exploring more applications of quantum computing. This is just the beginning!

The Fundamentals of Quantum Computing

**Grover's Algorithm** was proposed by Lov Grover in 1996. Like the **Deutsch-Jozsa Algorithm**, a quantum algorithm is empirically faster than our fastest classical solution to the same problem. How much faster? **Grover's Algorithm** provides a **quadratic speedup** over its classical counterpart. While at first sight, it is not as remarkable as the **exponential** speedup of the **DJ Algorithm**, one can argue that Grover's solution is immediately useful and provides a great blueprint for solving similar problems.

The problem that Lov Grover solved using his algorithm is related to searching an unordered collection of items. Imagine an **unordered list** of elements from which we want to **search** for a particular item. For example, in the following array, we want to find **-6**, the second-to-last element.



Take a moment and think about how you would approach this problem classically. Take the general case and ask yourself:

* What's the fastest way to find an element in an unordered collection?

# Classical solution

Since there is no internal structure or metadata that we can use to speed up our search, the best we can do classically is a **linear search**. In a linear search, we start from the beginning of the list and iterate over all elements. In each iteration, we inspect the current element and see if that is the one that we were looking for initially. If we have encountered that item, great, we stop our search. Otherwise, we move ahead and check the rest of the list until the last element. What's the time complexity of such a solution? If we're lucky, the first item we inspect is the one we sought. In that case, the complexity is $O(1)$. In the worst case, we iterate through the list, and either the element is right at the end, or it does not exist at all. In that case, the time complexity is $O(N)$. So, in the average case, we'll have to inspect $50\%$ or $\frac{N}{2}$ elements of the list.

It genuinely seems like this is the best we can do no matter how we approach the problem. But that would be myopic on our part. We can solve this problem much faster on a quantum computer using **Grover's Algorithm**, which has an asymptotic time complexity of $O(\sqrt{N})$.

At this point, some people might argue that **binary search** with $O(log\space N)$ complexity after sorting the data would be much faster than the proposed $O(\sqrt{N})$. But there are two things we need to remind ourselves of here. Sorting this array would most probably require a comparison-based sort, giving an overhead of $O(N\space log\space N)$. Also, we are talking about a generic, **unstructured search** via an algorithm that does not depend on the structure of the data itself. So, sorting 
would defeat that purpose.

With that short clarification out of the way, let's dissect **Grover's Algorithm**, which not only provides us the required generic algorithm but also extracts a **quadratic** speedup over its classical counterpart.

# Quantum solution

**Grover's Algorithm** uses three foundational techniques from quantum computing. We've already used two techniques in the previous chapter on the DJ Algorithm, **superposition** and a quantum **oracle**. The third technique is dubbed **amplitude amplification**, and we will study it in detail in this chapter.

First, let's revisit the array above in which we had to find **-6**. Since we work directly with qubits, it's helpful to reformulate the array where every element is a bit string. That way, we can input and encode all this information in our quantum computer before searching for the required element. Writing the binary representation of all those elements would lead to messy working. Let's instead restructure the problem as follows:

* From all possible computational basis states that $n$ qubits can be in, find a particular state, say $x$.

This way it's helpful to think of the search-space for $x$ being all bit-strings of length $n$, which corresponds to $2^{n}$ possible items in the collection list. For three qubits, our search space would be the states $|000\rangle, \space |001\rangle\space ,...,\space |111\rangle$ or $|0\rangle, \space |1\rangle\space ,...,\space |7\rangle$. And let's say our $x$, which is what we have to find, is $|101\rangle$ or $|5\rangle$.

Let's learn about quantum search and how it is faster than its classical counterpart.

Baby Steps

The Essence of Quantum Mechanics

Quantum Gates and Circuits

Simulating Quantum Computers

Getting Started with Quantum Algorithms

The Deutsch-Jozsa Algorithm

Grover's Search Algorithm

Shor's Factoring Algorithm

The Future

Quantum Search