Quantum Computing Prelude
It's time to dive deeper into the fundamentals of quantum computing and explore one of its most well-known problems. Here's the outline for today's lesson, which will lay the foundation for future simulations and applications.
- Quantum Bit and Quantum Gate
- Deutsch's Quantum Algorithm
Quantum Bit and Quantum Gate
In classical computing, information is represented using bits, which can be either 0 or 1. In contrast, quantum computing usesqubits as its basic unit. A qubit can represent both 0 and 1 simultaneously due to the principle of superposition. Its basic form, corresponding to the classical 0 and 1, is defined as follows:
$$\lvert 0 \rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \in ℂ^2 \quad \lvert 1 \rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix} \in ℂ^2$$
We can further define the general form of a qubit as follows:
$$\lvert x \rangle = \alpha \lvert 0 \rangle + \beta \lvert 1 \rangle = \begin{pmatrix} \alpha \\ \beta \end{pmatrix} \in ℂ^2$$
where: $\lvert \alpha \rvert^2 + \lvert \beta \rvert^2 = 1$
The most fundamental operations in quantum computing include:
- Estimation: Extracting information from a quantum state.
- Time Evolution: Describing how a quantum state changes over time.
But where does quantum computing truly differ from classical computing? To explore this, let’s consider a system of two bits in both classical and quantum contexts:
Classical Computing (2-bits)
$$00, 01, 10, 11$$
Quantum Computing (2-bits)
$\lvert x \rangle = \alpha_{00}\lvert 00 \rangle + \alpha_{01}\lvert 01 \rangle + \alpha_{10}\lvert 10 \rangle + \alpha_{11}\lvert 11 \rangle, $ $\sum_{j}|\alpha_j|^2 = 1$
As the quantum bits could be superpositioned, meaning
$$\lvert 00 \rangle = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} \in ℂ^4, \lvert 01 \rangle = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} \in ℂ^4, \lvert 10 \rangle = \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix} \in ℂ^4, \lvert 01 \rangle = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} \in ℂ^4$$
However, to represent and calculate the state of multiple qubits, we use tensor (Kronecker) multiplication, which is defined as follows:
$$\begin{pmatrix} \alpha_1 \\ \alpha_2 \end{pmatrix} \otimes \begin{pmatrix} \beta_1 \\ \beta_2 \end{pmatrix} = \begin{pmatrix} \alpha_1\beta_1 \\ \alpha_1\beta_2 \\ \alpha_2\beta_1 \\ \alpha_2\beta_2 \end{pmatrix} $$
Note that any quantum state that cannot be written as a tensor product of individual qubit states is called an entangled state.
Let's talk deeper about these two operations.
Quantum Estimation
An operation that extracts information from a quantum state is known as estimation, where the goal is to determine an unknown parameter 𝜽 that is encoded in the quantum state 𝑥.
Therefore, for the state above,
$$\lvert x \rangle = \alpha \lvert 0 \rangle + \beta \lvert 1 \rangle = \begin{pmatrix} \alpha \\ \beta \end{pmatrix} \in ℂ^2$$
If we use $\lvert 0 \rangle$ or $\lvert 1 \rangle$ to estimate the quantum state $x$, we will have
- Getting estimation 0 with probability $|\alpha|^2$, and the state becomes $\lvert 0 \rangle$
- Getting estimation 1 with probability $|\beta|^2$, and the state becomes $\lvert 1 \rangle$
Note: quantum state can be estimated with other computing basis except $\lvert 0 \rangle$ and $\lvert 1 \rangle$
Quantum Time Development
The evolution of a quantum state over time is described by the rules of quantum mechanics. This process is deterministicand governed by the Schrödinger Equation, which is defined as follows:
$$i\hslash \dfrac{d}{dt}\lvert \psi(t) \rangle = H\lvert \psi(t) \rangle$$
Where:
- $\hslash$: reduced Planck constant
- $H$: Hamiltonian of the system
- $\lvert \psi(t) \rangle$: the state of the system at time $t$
In the context of Quantum Informatics, we focus on the basic form of time evolution represented by a unitary matrix, such that:
$$\lvert x' \rangle = U\lvert x \rangle$$
Where:
- $U^{\dag}U = UU^{\dag} = I$: $U$ is unitary matrix
- $U^{\dag}$: conjucate matrix of $U$, meaning transpose and conjugate
Below, we list some commonly used quantum gates:
X Gate (NOT-Gate)
$$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$$
Hadamard Gate
$$H = \dfrac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$$
Deutsch's Problem
So far, we have discussed all the pre knowledge we need to understand Deutsch's problem. The Deutsch's problem is describes as follows:
Given a black box (oracle) that computes a function:
$$f: \set{0, 1} \rightarrow \set{0, 1}$$
there are only two types of possible functions:
- Constant function: either $f(0) = f(1) = 0$ or $f(0) = (f1) = 1$
- Balanced function: exactly $f(0)$ or $f(1)$ is $0$, the other is $1$
The task is to determine whether the function is constant or balanced using the fewest possible evaluations of $f$.
Classically, determining whether ff is constant or balanced requires two evaluations—checking both f(0)f(0) and f(1)f(1) separately. However, using Deutsch’s algorithm, we can solve this problem with just one query to the oracle. Here’s how it works:
Input: Initial State
$$|0\rangle \otimes |1\rangle = |0\rangle|1\rangle$$
Step1: Apply Hadamanrd Gate H
- $H|0\rangle$: $\dfrac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$
- $H|1\rangle$: $\dfrac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$
Full state becomes
$$\dfrac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \otimes (|0\rangle - |1\rangle)$$
Step2: Apply oracle (black box function) $U_f$, which is defined:
$$U_f|x\rangle |y\rangle = |x\rangle|y \oplus f(x)\rangle$$
- $x \in \set{0, 1}$: input
- $y \in \set{0, 1}$: target qubit
- $\oplus$: bitwise XOR
$U_f$ flips the second qubit if $f(x) = 1$ and does nothing if $f(x) = 0$
Looking further into $U_f$,
Case1: $f(x) = 0$ for all x, then
$$U_f|x\rangle|y\rangle = |x\rangle|y \oplus 0\rangle = |x\rangle|y\rangle$$
Case2: $f(x) = 1$ for all x, then
$$U_f|x\rangle|y\rangle = |x\rangle|y \oplus 1\rangle = |x\rangle|NOT y\rangle$$
Case3: $f(0) = 0, f(1) = 1$, then
- $U_f \lvert 0 \rangle \lvert y \rangle = |0 \rangle |y \oplus 0 \rangle = 0 \rangle \lvert y \rangle$
- $U_f \lvert 1 \rangle \lvert y \rangle = |1 \rangle |y \oplus 1 \rangle = 1 \rangle \lvert NOT y \rangle$
Case4: $f(0) = 1, f(1) = 0$, then
- $U_f \lvert 0 \rangle \lvert y \rangle = |0 \rangle |y \oplus 1 \rangle = 0 \rangle \lvert NOT y \rangle$
- $U_f \lvert 1 \rangle \lvert y \rangle = |1 \rangle |y \oplus 0 \rangle = 1 \rangle \lvert y \rangle$
Therfore, you can see that it behaves in a clever way that:
$$U_f(|x\rangle(|0\rangle - |1\rangle)) = (-1)^{f(x)}(|0\rangle - |1\rangle)$$
Apply this to what we derived at step1, we got
$$\dfrac{1}{\sqrt{2}}[(-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle] \otimes (|0\rangle - |1\rangle)$$
This tells us that the second qubit could be ignored.
With the unitary property, we apply Hadamard gate again to the first qubit:
$$|\psi\rangle = [(-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle]$$
$$H|\psi\rangle = \dfrac{1}{\sqrt{2}}[\alpha(|0\rangle + |1\rangle) + \beta(|0\rangle - |1\rangle)] = \dfrac{1}{\sqrt{2}}[(\alpha + \beta)|0\rangle + (\alpha - \beta)|1\rangle]$$
- $\alpha = (-1)^{f(0)}$
- $\beta = (-1)^{f(1)}$
For the measurement, simply consider two cases:
Case1: $f(0) = f(1) \rightarrow (-1)^{f(0)} = (-1)^{f(1)}$
$$H|\psi = |0\rangle$$ → Constant
Case2: $f(0) ≠ f(1) \rightarrow (-1)^{f(0)} = -(-1)^{f(1)}$
$$H|\psi = |1\rangle$$ → Balanced
Conclusion
In this post, I discussed the basics of quantum computing—most importantly, its foundational principles. I also compared it with classical computing and highlighted how quantum computing can outperform classical approaches in certain areas. Along the way, I introduced several new concepts, which may take some time to fully grasp. Nevertheless, my curiosity about quantum computing continues to grow!
