Note: Quantum Computing (3)

Encoding in Quantum Computer

1. Basis Encoding

Basis Encoding is a method that associates the basis states of an N-qubit system with classical bit sequence like below.

000011 \rarr \bra{000011}

Therefore, the purpose of the algorithm is to increase the probabilities that the elements of the amplitude vector, which represents the solution, become high values.

2. Amplitude Encoding

Amplitude Encoding is going to associate vectors which takes real valus, with quantum ampitude vector. We can describe classical vector x using amplitude vector.

x = \begin{pmatrix} x_1 \\ \vdots \\ x_{2^n} \\ \end{pmatrix} \leftrightarrow \ket{\psi_x}=\displaystyle\sum_{j=1}^{2^{n}}x_j\ket{j} \\ x \in \mathcal{C}^{2^n}, \displaystyle\sum_{k} \begin{Vmatrix} x_k \end{Vmatrix}^2 = 1

And also, classical matrix representation can be introduced by expanding the above formulation to Hilbert space.

\ket{\psi_A}=\displaystyle\sum_{i=1}^{2^{n}}\displaystyle\sum_{j=1}^{2^{n}}a_{ij}\ket{i}\ket{j}

But amplitude vector in quantum world is quite different from real value vectors, So it is not used frequently. For example, the operation like non-linear transformation cannot be applied for amplitude vector. Another restriction is that normalized vector can be associated with amplitude vector obviously.

3. Qsample Encoding

It utilizes the amplitude vector to represent classical probability distributions. Sampling the quantum state of an n-qubit system is equivalent to sampling an n-bit string from a discrete probability distribution.

\ket{\psi}=\displaystyle\sum_{i=1}^{2^{n}} \sqrt{p_i}\ket{i}

4. Dynamic Encoding

Dynami Encoding is a way to embed data into quantum gate.

In some applications, interpreting matrix as hamiltonian, and encoding it to unitary operation is useful. This is no doubt that the unitary operation defenitely restrict the expression of matrix classes, but it is good idea to associate hamiltonian H into square matrix.

When matrix representation which you are going to use for computation is not Hermite matrix, below matrix should be introduced(The Hamiltonian should have Hermitian symmetry.).

\tilde{A}=\begin{pmatrix} 0 & A \\ A^\dagger & 0 \\ \end{pmatrix}

And then, use a part of result after you computed. By multiplying with amplitude encoded vectors, the eigenvalues of matrix A one can be computed. This encoding is used for inverse Fourier transformation, inverse matrix calculations, and so on.

Example

Quantum Fourier Transform

Fourier Transform is described below formulation in general.

y_k= \frac{1}{\sqrt{N}} \displaystyle\sum_{j=0}^{N-1} x_j{w_N^{jk}} \\ where \ {w_N^{jk}}=e^{2{\pi}\frac{jk}{\sqrt{N}}}

to represent state using ampitude encoding, use below definition. This is from the 2. ampitude encoding section above.

\ket{x}:=\displaystyle\sum_{j=0}^{N-1}x_j\ket{j}

and then, consider encoding fourier transorm as same.

\ket{y}:=\displaystyle\sum_{k=0}^{N-1}y_k\ket{k}

Substituting the encodings into the Fourier transform formula

\ket{y}:=\displaystyle\sum_{k=0}^{N-1}\displaystyle\sum_{j=0}^{N-1} x_j{w_N^{jk}}\ket{k}= \displaystyle\sum_{j=0}^{N-1} x_j (\displaystyle\sum_{k=0}^{N-1} {w_N^{jk}}\ket{k})

it means that to map basis j to the values inside bracket () above.

\ket{j} \rarr \displaystyle\sum_{k=0}^{N-1} {w_N^{jk}}\ket{k} \\ U_n = \frac{1}{\sqrt{N}} \displaystyle\sum_{k=0}^{N-1}\displaystyle\sum_{j=0}^{N-1} {w_N^{jk}} \ket{k} \bra{j}

These formulation looks quite complicated, but by using matrix representation, it gets more understantable.

If the amplitude vector is described in matrix form instead of basis,

\ket{y} = U_N \ket{x}

apply below unitary transform for state vector means that do Fourier Transform.

U_N = \frac{1}{\sqrt{N}} \begin{bmatrix} e^{-2\pi i 0 \cdot 0 / N} & e^{-2\pi i 0 \cdot 1 / N} & \cdots & e^{-2\pi i 0 \cdot (N-1) / N} \\ e^{-2\pi i 1 \cdot 0 / N} & e^{-2\pi i 1 \cdot 1 / N} & \cdots & e^{-2\pi i 1 \cdot (N-1) / N} \\ \vdots & \vdots & \ddots & \vdots \\ e^{-2\pi i (N-1) \cdot 0 / N} & e^{-2\pi i (N-1) \cdot 1 / N} & \cdots & e^{-2\pi i (N-1) \cdot (N-1) / N} \ \end{bmatrix}

Now we got transformed vector y, but how can we compose the unitary matrix as quantum circuit?

Let’s consider binary number of quantum circuit.

|y\rangle = \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} \sum_{j=0}^{2^n-1} x_j e^{i\frac{2\pi kj}{2^n}} |k\rangle = \sum_{j=0}^{2^n-1} x_j \left( \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{i\frac{2\pi kj}{2^n}} |k\rangle \right)

It means that finding out a circuit that unitary transform j to k like below equals to Qautum Fourier Transform.

|j\rangle \rightarrow \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{i\frac{2\pi kj}{2^n}} |k\rangle

We can deform the transformation like this.

\sum_{k=0}^{2^n-1} e^{i\frac{2\pi kj}{2^n}} \ket{k} = \sum_{k_1=0}^{1} \cdots \sum_{k_n=0}^{1} e^{i2\pi (k_1 2^{n-1} + \cdots + k_n 2^0) \frac{j}{2^n}} \ket{k_1 \cdots k_n} \\ =\left( \sum_{k_1=0}^{1} e^{i\frac{2\pi j k_1}{2^{1}}} \ket{k_1} \right) \otimes \cdots \otimes \left( \sum_{k_n=0}^{1} e^{i\frac{2\pi j k_n}{2^{n}}} \ket{k_n} \right) \\ \\ =\left( \ket{0} + e^{i2\pi 0.j_n} \ket{1} \right) \otimes \left( \ket{0} + e^{i2\pi 0.j_{n-1}j_n} \ket{1} \right) \otimes \cdots \otimes \left( \ket{0} + e^{i2\pi 0.j_1j_2\cdots j_n} \ket{1} \right)

What important here is how to represent terms over exponentials as binary decimals. The deformation uses below relation.

0.j_l \cdots j_n = \frac{j_l}{2} + \frac{j_{l-1}}{2^2} + \cdots + \frac{j_n}{2^{n-l+1}} \\ e^{i2\pi j/2^{-l}} = e^{i2\pi (j_1 \cdots j_l . j_{l-1} \cdots j_n)} = e^{i2\pi 0.j_{l-1} \cdots j_n}

Quantum Phase Estimation

Concept

A method to extract eigenvalues by decoding the phase information obtained using controlled unitary gates through inverse quantum Fourier transform.”

Computatinoal Flow

Initialize quantum bits
apply hadamal gates on the bits
Apply Ctr-Unitary gates
Apply inverse fourier transform on ancilla bits to estimate phase on the unitary vector