What is the algebraic result of the matrix exponential operation $e^{i A}|b\rangle$?

Question

The circuit for the HHL algorithm looks as follows:

I am uncertain what is the algebraic operation of the matrix exponential $e^{i A}$ on $|b\rangle$?

---

If $$|b\rangle = b_0|0\rangle + b_1|1\rangle$$ and $$A=\begin{bmatrix} a_{00} & a_{01} \\ a_{10} & a_{11} \end{bmatrix}$$ does this imply that

$$e^{i A}|b\rangle$$ $$=\left[\cos{\left( \begin{bmatrix} a_{00} & a_{01} \\ a_{10} & a_{11} \end{bmatrix}\right)} + i \sin{\left( \begin{bmatrix} a_{00} & a_{01} \\ a_{10} & a_{11} \end{bmatrix}\right)}\right] (b_0|0\rangle + b_1|1\rangle)$$ $$=\begin{bmatrix} \cos a_{00} + i\sin a_{00} & \cos a_{01} + i\sin a_{01} \\ \cos a_{10} + i\sin a_{10} & \cos a_{11} + i\sin a_{11} \end{bmatrix} \begin{bmatrix} b_0 \\ b_1 \end{bmatrix}$$

$$=\begin{bmatrix} e^{ia_{00}} & e^{ia_{01}} \\ e^{ia_{10}} & e^{a_{11}} \end{bmatrix} \begin{bmatrix} b_0 \\ b_1 \end{bmatrix}$$

$$ =\begin{bmatrix} b_0e^{ia_{00}} + b_1e^{ia_{01}} \\ b_0e^{ia_{10}} + b_1e^{ia_{11}} \end{bmatrix}$$

$$ = \color{red}{(b_0e^{ia_{00}} + b_1e^{ia_{01}})}|0\rangle + \color{red}{(b_0e^{ia_{10}} + b_1e^{ia_{11}})}|1\rangle$$

?

Answer 1

For any normal matrix you can use spectral decomposition for calculation of matrix exponential.

For normal matrix, it holds $f(A) = \sum f(\lambda_i) |u_i\rangle \langle u_i|$. In your case function $f(x)$ is $e^{ix}$. $\lambda_i$ are eigenvalues and $|u_i\rangle$ respective eigenvectors of matrix $A$.

Since, in HHL we suppose that the matrix is Hermitian, it is also normal and we can use approach described above.

Answer 2

I think I understand the matrix exponential a little bit better now. The scary infinite sum used in the definition

$$e^A = I + A + \frac{A^2}{2!} + \frac{A^3}{3!} + ...$$

actually converges (always?) to a single neat matrix of the same size.

For instance, it can be calculated explicitly by summing the above infinite sum that

$$e^{\begin{bmatrix} 1 & 2 \\ 0 & -1 \end{bmatrix}} = \begin{bmatrix} e & \frac{e^2-1}{e} \\ 0 & \frac{1}{e} \end{bmatrix}$$

so $e^A|b\rangle$ is in fact just

$$e^{\begin{bmatrix} 1 & 2 \\ 0 & -1 \end{bmatrix}}|b\rangle = \begin{bmatrix} e & \frac{e^2-1}{e} \\ 0 & \frac{1}{e} \end{bmatrix} |b\rangle$$

The transition to complex $i$ introduces some possibilities for interference/cancelation of terms, since:

$$e^{iA} = I + iA + \frac{(iA)^2}{2!} + \frac{(iA)^3}{3!} + \frac{(iA)^4}{4!} +...$$ $$e^{iA} = I + iA - \frac{A^2}{2!} - i\frac{A^3}{3!} + \frac{A^4}{4!} + ...$$

Computing explicitly the infinite sum in complex algebra, we get the answer

$$e^{i\begin{bmatrix} 1 & 2 \\ 0 & -1 \end{bmatrix}} = e^{\begin{bmatrix} i & 2i \\ 0 & -i \end{bmatrix}}=$$

from which

$$e^{i\begin{bmatrix} 1 & 2 \\ 0 & -1 \end{bmatrix}}|b\rangle = \begin{bmatrix} 0.54+ 0.84i & 1.68i \\ 0 & 0.54 - 0.84i \end{bmatrix} |b\rangle$$

---

Eigenvalue decomposition (following this):

Let

$$A = \begin{bmatrix} 1 & 4 \\ 9 & 1 \end{bmatrix}$$

We note that

$$ \begin{bmatrix} 1 & 4 \\ 9 & 1 \end{bmatrix} \color{red}{\begin{bmatrix} 2 \\ 3 \end{bmatrix}} = \color{blue}{7} \color{red}{\begin{bmatrix} 2 \\ 3 \end{bmatrix}}$$

$$ \begin{bmatrix} 1 & 4 \\ 9 & 1 \end{bmatrix} \color{red}{\begin{bmatrix} 2 \\ -3 \end{bmatrix}} = \color{blue}{-5} \color{red}{\begin{bmatrix} 2 \\ -3 \end{bmatrix}}$$

Combining both equations:

$$ \begin{bmatrix} 1 & 4 \\ 9 & 1 \end{bmatrix} \color{red}{\begin{bmatrix} 2 & 2\\ 3 & -3\end{bmatrix}} = \color{red}{\begin{bmatrix} \color{blue}{7}\times2 & \color{blue}{-5}\times2\\ \color{blue}{7}\times 3 & \color{blue}{-5}\times -3\end{bmatrix}} = \color{red}{\begin{bmatrix} 2 & 2\\ 3 & -3\end{bmatrix}} \begin{bmatrix} \color{blue}{7} & 0 \\ 0 & \color{blue}{-5}\end{bmatrix}$$

Noting further that

$$\color{red}{\begin{bmatrix} 2 & 2 \\ 3 & -3 \end{bmatrix}}\color{green}{\begin{bmatrix} \frac{3}{12} & \frac{2}{12} \\ \frac{3}{12} & -\frac{2}{12} \end{bmatrix}} = \begin{bmatrix} 1&0 \\ 0&1\end{bmatrix}$$

we obtain

$$\begin{bmatrix} 1 & 4 \\ 9 & 1 \end{bmatrix}=\color{red}{\begin{bmatrix} 2 & 2\\ 3 & -3\end{bmatrix}} \begin{bmatrix} \color{blue}{7} & 0 \\ 0 & \color{blue}{-5}\end{bmatrix}\color{green}{\begin{bmatrix} \frac{3}{12} & \frac{2}{12} \\ \frac{3}{12} & -\frac{2}{12} \end{bmatrix}}$$

$$A = U\Lambda U^{-1}$$

This provides an extremely efficient computation for any $A^n$, since

$$A^n = AAAA...$$ $$=U\Lambda \color{orange}{U^{-1}U}\Lambda \color{orange}{U^{-1}U}\Lambda U^{-1}...$$ $$=U\Lambda^n U^{-1}$$ $$=\color{red}{\begin{bmatrix} 2 & 2\\ 3 & -3\end{bmatrix}} \begin{bmatrix} \color{blue}{7^n} & 0 \\ 0 & \color{blue}{(-5)^n}\end{bmatrix}\color{green}{\begin{bmatrix} \frac{3}{12} & \frac{2}{12} \\ \frac{3}{12} & -\frac{2}{12} \end{bmatrix}}$$

---

Given

$$A|x \rangle = |b \rangle$$

the HHL algorithm finds $|x \rangle$ by constructing $$| x \rangle = A^{-1}|b\rangle$$

Suppose all eigenvalues and eigenvectors of $A$ are known, then we have knowledge of the correct eigenvalue decomposition

$$ A= \begin{bmatrix} 1 & 4 \\ 9 & 1 \end{bmatrix}=\color{red}{\begin{bmatrix} 2 & 2\\ 3 & -3\end{bmatrix}} \begin{bmatrix} \color{blue}{7} & 0 \\ 0 & \color{blue}{-5}\end{bmatrix}\color{green}{\begin{bmatrix} \frac{3}{12} & \frac{2}{12} \\ \frac{3}{12} & -\frac{2}{12} \end{bmatrix}}$$

and immediately its inverse as well:

$$ A^{-1} = \color{red}{\begin{bmatrix} 2 & 2\\ 3 & -3\end{bmatrix}} \begin{bmatrix} \color{blue}{\frac{1}{7}} & 0 \\ 0 & \color{blue}{-\frac{1}{5}}\end{bmatrix}\color{green}{\begin{bmatrix} \frac{3}{12} & \frac{2}{12} \\ \frac{3}{12} & -\frac{2}{12} \end{bmatrix}}$$

since

$$ AA^{-1} =\color{red}{\begin{bmatrix} 2 & 2\\ 3 & -3\end{bmatrix}} \begin{bmatrix} \color{blue}{7} & 0 \\ 0 & \color{blue}{-5}\end{bmatrix}\color{green}{\begin{bmatrix} \frac{3}{12} & \frac{2}{12} \\ \frac{3}{12} & -\frac{2}{12} \end{bmatrix}}\color{red}{\begin{bmatrix} 2 & 2\\ 3 & -3\end{bmatrix}} \begin{bmatrix} \color{blue}{\frac{1}{7}} & 0 \\ 0 & \color{blue}{-\frac{1}{5}}\end{bmatrix}\color{green}{\begin{bmatrix} \frac{3}{12} & \frac{2}{12} \\ \frac{3}{12} & -\frac{2}{12} \end{bmatrix}}$$

$$=\color{red}{\begin{bmatrix} 2 & 2\\ 3 & -3\end{bmatrix}} \begin{bmatrix} \color{blue}{7} & 0 \\ 0 & \color{blue}{-5}\end{bmatrix}\begin{bmatrix} 1& 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} \color{blue}{\frac{1}{7}} & 0 \\ 0 & \color{blue}{-\frac{1}{5}}\end{bmatrix}\color{green}{\begin{bmatrix} \frac{3}{12} & \frac{2}{12} \\ \frac{3}{12} & -\frac{2}{12} \end{bmatrix}}$$

$$=\color{red}{\begin{bmatrix} 2 & 2\\ 3 & -3\end{bmatrix}} \begin{bmatrix} 1& 0 \\ 0 & 1 \end{bmatrix} \color{green}{\begin{bmatrix} \frac{3}{12} & \frac{2}{12} \\ \frac{3}{12} & -\frac{2}{12} \end{bmatrix}}$$

$$= \begin{bmatrix} 1& 0 \\ 0 & 1 \end{bmatrix} $$

---

Suppose that

$$|b\rangle \rightarrow e^{-iA}|b\rangle$$

is the only physically allowable way of interacting with $|b\rangle$.

Then

$$ e^{-ik\begin{bmatrix} 1&4 \\ 9&1 \end{bmatrix}}(\alpha|0\rangle + \beta|1\rangle)$$

$$ = \left(I + ik\begin{bmatrix} 1&4 \\ 9&1 \end{bmatrix} + ...\right)(\alpha|0\rangle + \beta|1\rangle)$$

If $k$ has been sufficiently tuned to be small such that all higher order terms can be neglected,

$$ = \left(\begin{bmatrix} 1&0 \\ 0&1 \end{bmatrix} + ik\begin{bmatrix} 1&4 \\ 9&1 \end{bmatrix}\right)(\alpha|0\rangle + \beta|1\rangle)$$

$$ = \begin{bmatrix} 1+ik&4ik \\ 9ik& 1 + ik \end{bmatrix} \begin{bmatrix} \alpha \\ \beta \end{bmatrix}$$

$$ = \begin{bmatrix} \alpha+ik(\alpha + 4\beta) \\ \beta + ik(9\alpha+\beta) \end{bmatrix} $$

Suppose for instance that $\alpha = 3$ and $\beta = 5$, ie.

$$|b\rangle = \begin{bmatrix} 3 \\ 5 \end{bmatrix}$$

Then

$$ e^{-iA}|b\rangle \approx \begin{bmatrix} 3+23ik \\ 5 + 32ik \end{bmatrix} = (3+23ik)|0\rangle + (5 + 32ik)|1\rangle$$

The phase additions $23ik$ and $32ik$ encode the effect of interacting with matrix A.

Suppose further it is possible to make $|b\rangle$ interact somehow with $e^{iA^{-1}}$. Then

$$ e^{iA^{-1}}|b\rangle \approx \begin{bmatrix} 3+\frac{17}{35}ik \\ 5 + \frac{22}{35}ik \end{bmatrix}$$

now encodes the interaction of $|x \rangle = A^{-1}|b\rangle$ as desired.

---

Starting with a linear system in 3 unknowns:

$$ 3x + y - 2z = 7$$ $$ x - 3y - 4z = 15$$ $$ 2x - 2y + z = 12$$

We might initialize a 2-qubit state to

$$ |b\rangle = \begin{bmatrix} |00\rangle & 0 \\ |01\rangle & 7 \\ |10\rangle & 15 \\ |11\rangle & 12 \end{bmatrix}$$

the eigenvalues of the LHS coefficients are found by quantum phase estimation method to be:

Construct $$A^{-1}|b\rangle$$ by operating on $|b\rangle$ using

$$ |x\rangle = e^{U\Lambda^{-1} U^{-1}}|b\rangle - |b\rangle \approx (I + U\Lambda^{-1} U^{-1})|b\rangle - |b\rangle = A^{-1}|b\rangle$$

---

The HHL algorithm avoids computing $U^{-1}$ (which is $O(n^3)$), by first interacting $|b\rangle$ with the undecomposed $A$:

$$|b\rangle \rightarrow e^{iA} |b\rangle$$

and then changing mid-circuit

$$A=U\Lambda U^{-1} \rightarrow U\Lambda^{-1} U^{-1} = A^{-1}$$

using quantum circuit manipulations.