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

The **Deutsch-Jozsa (DJ)** algorithm was proposed by David Deutsch and Richard Jozsa in 1992. It was the first algorithm that showed us the true power of quantum computing because it gave an **exponential speedup** to our fastest classical solution for a certain problem. Let’s see how it did that by first understanding the problem itself.

# Defining the problem

At the heart of the Deutsch-Jozsa algorithm is a mathematical function. That function takes in as an input a bit-string of $n$ bits and returns a single bit as an output, $0$ or $1$ based on the type of the function itself. This function can be one of two types - **balanced** or **constant**. When the function is constant, it will return either a $0$ or a $1$ for all inputs. However, if the function is balanced, it outputs a mixture of $0$ and $1$. That mixture is special. For exactly half of all inputs, that function will return $0$, and for the other half, it will return $1$. Hence the name, **balanced**, signifying a balance in the type of outputs. Mathematically, we can write this function as:

$$f\{0,1\}^{n}\rightarrow\{0,1\}$$

For clarity, let's look at the truth table for this type of function. When the function is **constant**, for a 2-bit input, it will have the following truth table. We assume that we've chosen this function to output $0$s for all inputs. We could've chosen $1$s too.

| Input       | Output      |
| ----------- | ----------- |
| 00          | 0           |
| 01          | 0           |
| 10          | 0           |
| 11          | 0           |

When the function is **balanced**, for a 2-bit input, it will have the following truth table. 

| Input       | Output      |
| ----------- | ----------- |
| 00          | 0           |
| 01          | 1           |
| 10          | 1           |
| 11          | 0           |

The order of $0$s and $1$s do not matter. What matters is that the number of times we get either output should be identical, $50\%$.

So now the question that Deutsch and Jozsa posed with this function is as follows:

* Determine whether the function $f$ is **constant** or **balanced** as efficiently as possible.

For this investigation, we will be provided this function $f$ as a black-box. We won't be able to look into it, but we can give it bit strings in input and read its output bit. 

At this point, try to think about how you would go about solving this problem classically. What would be the time complexity of the solution? Can you do any better than the solution you proposed?


# Classical solution

The best and fastest possible classical solution to the question posed above works as follows. You would prepare all possible inputs for a bit string composed of length $n$. Where $n=1$, this means we prepare two inputs, $0$ and $1$. For $n=2$, we prepare $00,01,10,11$. Generally, for $n=k$ we need $2^k$ inputs. 

You then run these inputs one by one into the function $f$, counting the number of times you get $0$ and $1$ in the output. You would need to do this a total of $2^{k-1}+1$ times for a bit string of length $k$. That is the same as saying that for the case where $k=5$, we have a total of $32$ types of input combinations. We would need to run through $16+1=17$ of them because even if we get a $0$ or $1$ for $16$ inputs, it could still be possible that the $17^{th}$ output can be a $1$. Though this is statistically very improbable, you need $2^{k-1}+1$ inputs to be fully confident that the function is **constant**, not **balanced**.

The computational complexity for this classical algorithm, in terms of the Big-O notation, is exponential at $O(2^{n})$, for a bit string of length $n$ bits.

Let’s dive into the Deutsch-Jozsa algorithm that works in constant time and is exponentially faster than our fastest classical solution.

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

The DJ Circuit