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

**Shor's Algorithm** was proposed by the American mathematician Peter Shor in 1994, and it promises prime factorization of numbers in **polynomial** time. This might seem like an easy problem, at first. After all, we learned the procedure for representing a number as a product of its prime factors in secondary school. Following the same process, we know that we can break down a number, let's say $15$, into its prime factors as $15 = 3\times5$ or another number, let's say $1748$, as $1748=2^{2}\times19^{1}\times23^{1}$. 

It turns out that this problem is not that easy to do with larger numbers. In fact, the time complexity of our fastest and most efficient classical algorithms for prime factorization is **exponential**. Specifically, the **general number field sieve** algorithm, which is the fastest known algorithm for factoring numbers larger than a **googol** ($10^{100}$), takes $O(\exp{1.9(\log N)^{\frac{1}{3}}(\log \log N)^{\frac{2}{3}}})$ to factor an integer $N$.

As Peter Shor discovered in 1994, quantum computers can solve this problem much faster. In fact, **Shor's Algorithm** provides an **exponential** speedup over its classical counterpart. Specifically, it gets rid of the exponential term and has an overall asymptotic time complexity of order $O((\log
{N}^{2}(\log\log N)(\log \log \log N)))$ or $\approx O(N^{3})$, roughly **cubic** time complexity.



Let’s discuss the preliminaries necessary for understanding Shor's Algorithm. We start with describing the factoring problem and its 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

Arduous Factorization