Quantum Computing 1 - Quantum computer and qubit

In 1994, Peter Shor showed that quantum computing enabled us to factorize a big integer into prime numbers. It is quite important discovery because the current cryptographic system is based on prime factorization. When a classical computer calculates it, it finds the answer by checking each number step by step. It takes a lot of time, and it is a virtually impossible if the number is large.

Traveling salesman problem is also known as a weak point of classical computers. It is the following question; “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?” If the number of cities is $N$, all routes are $(N-1)!$. A classical computer has to calculate a huge amount of routes when $N$ is large. A quantum computer is one of major candidates to solve these kinds of issue.

A unit of calculation by quantum computation is a qubit stands for a quantum bit. It is very different from a classical bit.

A qubit represents a state.

We express states as $\lvert 0 \rangle$ and $\vert 1 \rangle$ like classical bits, $(0)$ and $(1)$. If you observe a state as $\vert 0 \rangle$, it is impossible to be $\vert 1 \rangle$. In this case, each state is independent. 2 qubits are represented by

$$\begin{equation} \vert 0 \rangle \otimes \vert 1 \rangle = \vert 01 \rangle \end{equation}$$

A qubit can be a superposition.

A superposition $\vert \psi \rangle$ is written by

$$\begin{equation} \vert \psi \rangle = c_0 \vert 0 \rangle + c_1 \vert 1 \rangle \end{equation}$$

Here, $c_0$ and $c_1$ are complex numbers. They satisfy the following equation.

$$\begin{equation} |c_0|^2 + |c_1|^2 = 1 \end{equation}$$

In other words, a qubit can have infinite states.

Calculation is transition of states.

If you change $\vert \psi_1 \rangle$ into $\vert \psi_2 \rangle$, it is called transition from the initial state ($\vert \psi_1 \rangle$) to the final state ($\vert \psi_2 \rangle$). It is equivalent to the following operation.

$$\begin{equation} \vert \psi_1 \rangle = c_0 \vert 0 \rangle + c_1 \vert 1 \rangle \rightarrow \vert \psi_2 \rangle = c'_0 \vert 0 \rangle + c'_1 \vert 1 \rangle \\ |c_0|^2 + |c_1|^2 = |c'_0|^2 + |c'_1|^2 = 1 \end{equation}$$

Reference