Introduction to Quantum Computing

Recently I've been diving into quantum computing. It's been interesting to see various connect previous classes to what I'm learning now.

What is Classical Computing?

To understand quantum computing we must first understand classical computing. This is the computation which our computers take, bits being either in a state of 0 or 1. Multiple bits coming together to represent information on a larger scale is the classical system we see when thinking of typical computing.

Classical computing is great for a lot of things such as rendering videos and preforming arithmetic; However, many problems aren't so good for classical computing. These "hard" problems are sometimes the basis for modern cryptographic primitives which rely on the difficulty of computational problems for classical computers.

An example of a problem hard for classical computing would be to figure out possible partner assignments for a class. We want to examine every possibility for partnerships of groups in this class. This gets exponentially big relative to the class size. If there are 2 people, well either the people are together or they aren't. If there are 3 people, then we can form 3 solo groups, 2 different groups, or a single 3-person group. For each person we add to this class, we multiply the group possibilities by 2 (since the new person can either be part of not part of every pre-existing group from the previous class size). This problem results in $2^{n - 1}$ groups for a class size of n, thus having an exponential growth relative to the class size. When we have 5 students, this is $2^{5 - 1} = 2^{4} = 16$, when we have 10 students, there are $2^{10-1} = 2^9 = 512$, and when we have 20 students we have $2^{20-1} = 2^{19} = 524288$. The number of partnerships quickly gets big, passing a trillion with just 41 students in the class (as $2^{41-1} = 2^{40} = 1.09 \cdot 10^{12}$).

Quantum computers are better at handling this type of case load. This is because quantum computing leverages a concept called superposition, where atoms are in two positions or states at the same time. This could be accomplished by utilizing the spin of electrons but I won't get into the hardware side of how this is implemented in quantum computers. Quantum computing allows for us to utilize quantum bits, otherwise known as qubits. This becomes an advantage because by running programs multiple times we get to see the probabilitistic distribution associated with algorithms, and utilize those distributions to seemingly exponential questions with relative certainty in a more efficient fashion.

Qubits

Rather than being 0 or 1, qubits are possibly in state of superposition, where they have a probability of being measured as 0 or 1. Often a qubit, say $\psi$ is represented as

in matrix form or

in Dirac (otherwise known as bra-ket) notation where $\alpha, \beta \in \mathbb{C}$ such that the magnitude squared represents the probability for the qubit to be measured as 0 or 1 respectively.

Bloch Sphere

To better visually represent qubits, a block sphere is used. This contains three axis of interest, where $(0, 0, 1)$ represents $|0\rangle$ and $(0, 0, -1)$ represents $|1\rangle$. Note that $(x, y, z)$ in the unit 3 sphere is in the complex space. That is that $x, y, z \in \mathbb{C}$

That is when evaluated those qubits would result in 0 and 1 respectively 100% of the time.

Points on the sphere corespond to a qubit $\psi$ as

Note that a qubit $\psi$ described on the block sphere with point $(x, y, z)$ must have $||x||^2 + ||y||^2 + ||z||^2 = 1$. This is because the total probability of $\psi$, $||\psi||^2 = 1$.