Quantum computing

As part of my undergrad I did a seminar on quantum computing. Here I outline the basics of Quantum Computing I have learnt so far. Note that I am only explaining quantum computing from a Computer Science (mathematical) perspective.

Before I further proceed, lets take a dive into some of the related terminology. The fundamental unit of information in modern computers is a bit. In the context of quantum computing, the modern computers will be referred to as the classical computer, and the bit on which the classical computing model is built will be referred to as a classical bit. The classical computers perform computations by manipulating these bits, using logic gate, which we will be calling classical gates in this case. Similarly in a quantum computer, the quantum bit more commonly known as a qubit is the analogous entity of a classical bit. computation is performed by manipulating these qubits using, what is referred to as, quantum gates.

Qubit

A classical bit can take one of two states, $1$ and $0$. Now, a qubit, is a two state quantum system. The two states are similar to that of the classical bit's, but a qubit does not have to be in just one of those states. Before diving further into that, let’s take a look at how the state of a qubit can be represented. It is represented using ket notation ( $|\psi ⟩$), from the bra-ket notation ( $⟨\varphi |\psi ⟩$ ), as any other quantum state. That is, the state of the qubit can be represented using a two-dimensional complex state vector,

$|\psi ⟩=\left(\begin{array}{c}\alpha \\ \beta \end{array}\right)$

where $\alpha$ and $\beta$ are complex coordinates (think of it as a vactor of size 2). The basis states (basis vectors) of a qubit are $|0⟩$ and $|1⟩$, which can be represented as follows.

$|0⟩=\left(\begin{array}{c}1\\ 0\end{array}\right)$ $|1⟩=\left(\begin{array}{c}0\\ 1\end{array}\right)$

These two basis states are analogous to the binary states of the classical bit. As said before a qubit can be in either of these states, or be in a state between these two. This can be written as a linear combination of these two states. This is what is known as a superposition. In quantum mechanics, two quantum states added together, i.e. “superposed”, is also a valid quantum state. Hence, we can represent the state of a qubit with the following linear equation.

$|\psi ⟩=\alpha |0⟩+\beta |1⟩$

Where $\alpha$ and $\beta$ are complex numbers, which are the probability amplitudes of the $|0⟩$ state and $|1⟩$ state, in the state represented by $|\psi ⟩$. Or in other words, the probability of the qubit, represented by the state $|\psi ⟩$, being in the basis state $|0⟩$ would be $|\alpha {|}^2$ and the probability of it being in the basis state $|1⟩$ would be $|\beta {|}^2$. As we are dealing with probabilities, naturally, the following must always hold.

$|\alpha {|}^2+|\beta {|}^2=1$

In a classical system with $n$ bits, the state of thee system can be represented using $n$ bits(digits). But, as seen above, in order to describe a qubit, we need two complex numbers, or in other terms, since a single qubit system has two basis states we need a complex number to represent the probability it could be in each of those basis states. Similarly, a two qubit system has four basis states, and a three qubit system has eight basis states, requiring four complex numbers and eight complex numbers respectively to represent the state they can be in. That is to say, to describe a quantum system with $n$ qubits, we need $2^n$ complex numbers. To further elaborate, lets see how a two qubit system can be represented.

$|\psi ⟩=\alpha |00⟩+\beta |01⟩+\delta |10⟩+\gamma |11⟩$

Where,

$|\alpha {|}^2+|\beta {|}^2+|\delta {|}^2+|\gamma {|}^2=1$

The basis state vectors of the above two qubit system would be $|00⟩$, $|01⟩$, $|10⟩$, and $|11⟩$.

Even though much higher number of digits are needed to represent the state of a qubit, it does not mean that we can store more information using a qubit. The reason for that is the effect of measurement in a quantum system. When we measure a quantum system which could be in a superposition of states, it will collapse to one of the states. Consider a qubit in the state $\alpha |0⟩+\beta |1⟩$. When this qubits state is measured, it will collapse to either of the states $|0⟩$ or $|1⟩$. The probability of it collapsing to either state will be $|\alpha {|}^2$ and $|\beta {|}^2$ respectively. Similarly a two qubit system would collapse to one of the four basis states with the probability of collapsing to a particular state being the squared magnitude of it’s coefficient.

Quantum Gates

Now that we have established how we can represent qubits, let us move to how we can use the qubit(s) to perform computation. In a classical computer, computations are performed by setting bits in the system to an initial state, and applying a sequence of logical gates to manipulate the bits to obtain the final state. Similarly in a qubit system, we need to define how to perform such manipulations to the qubits to perform computations. Since qubits can be represented as vectors, manipulating the states of the qubits can be expressed using transformations, which can be represented using matrices. Simply put, quantum gates can be represented using matrices.

As discussed earlier, the summation of the squared magnitude of the probability amplitudes of a state must equal to one. Hence, we can intuitively say that any transformation applied to a qubit system must preserve this. It can be further elaborated as the transformation applied must preserve the length of the state vector. The matrix that represents such a transformation would be a unitary matrix. For example the Hadamard gate $H$, which can be represented using the following matrix,

$H{=}^1{/}_{\sqrt{2}}\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]$

is a single quibit gate. If it were to be applied to a qubit in the state $|\psi ⟩=\alpha |0⟩+\beta |1⟩$, which can be represented using the vector $\left[\begin{array}{c}\alpha \\ \beta \end{array}\right]$, it can be expressed using simple matrix multiplication as follows,

$H|\psi ⟩{=}^1{/}_{\sqrt{2}}\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]\left[\begin{array}{c}\alpha \\ \beta \end{array}\right]$

Thus,

$H|\psi ⟩{=}^1{/}_{\sqrt{2}}\left[\begin{array}{c}\alpha +\beta \\ \alpha -\beta \end{array}\right]$

Which can be written as,

$H|\psi ⟩=\frac{\alpha +\beta }{\sqrt{2}}|0⟩+\frac{\alpha -\beta }{\sqrt{2}}|1⟩$

$H$ is a unitary matrix, i.e. $H{H}^{\ast }=I$, where $I$ is an identity matrix and $H^{\ast }$ is the conjugate transpose of $H$. As it can be seen, a gate that works on $k$ qubits can be represented using a $2^k\times 2^k$ matrix. Some of the gates can be seen in the following table. Note that I ave not discussed the involvement of $\varphi$ and $i$ in this article.

In classical computers the NAND gate is known as the universal gate, also the AND gate and the NOT gate in classical computing can be shown to be universal, i.e. they can be used to build any logical circuit. Similarly for a quantum system such gate(s) can be shown to be universal. The Hadamard gate, $R_{{}^{\pi }{/}_4}$ gate (phase shift gate with $\varphi {=}^{\pi }{/}_4$ ), which are single qubit gates, together with the control-NOT(cNOT) gate can be known as universal, as any quantum circuit can be built from them.

Entanglement

An important distinguishing feature between a qubit and a classical bit is that multiple qubits can exhibit quantum entanglment. Take, for example, the bell state, ${}^1{/}_{\sqrt{2}}(|00⟩+|11⟩)$, which can be obtained from the inital state $|00⟩$, and apply the Hadamard gate to one qubit and then apply the cNOT gate. The probability of the states $|00⟩$ or $|11⟩$ is ${|}^1{/}_{\sqrt{2}}{|}^2{=}^1{/}_2$. This state cannot be obtained by any combination of classical bits, i.e. we cannot obtain this state by arranging a set of qubits. That is to say, this state can be achieved only by applying a set of quantum gates. And this state exists only when both the qubits are together, and they don’t have a definite state on their own. To further elaborate on that, consider a two qubit placed to gether, hence

$|\psi ⟩=(\alpha |0⟩+\beta |1⟩)(\delta |0⟩+\gamma |1⟩)$

Thus,

$|\psi ⟩=\alpha \delta |00⟩+\alpha \gamma |01⟩+\beta \delta |10⟩+\beta \gamma |11⟩$

for this system, whose state is represented by $|\psi ⟩$, to be in the bell state, the following should hold,

$\alpha \delta {=}^1{/}_{\sqrt{2}}$ , $\alpha \gamma =0$ , $\beta \delta =0$, $\beta \gamma {=}^1{/}_{\sqrt{2}}$

This does not have a solution. Such a state obtained by applying quantum gates are known as entangled states.

As described above, such entangled states are unique to quantum computing. It is entanglement that makes quantum computing stand out from the classical computing models. Such entangled states can be used as shortcuts to perform certain calculations. In fact it can be shown that a quantum computation that does not utilize entangled states can be effectively simulated using classical computing. For certain problems, such as integer factorization, quantum algorithms(algorithms that use quantum phenomena such as entangled states) have been developed which are faster than any classical algorithm.