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

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$$

?

• No. See the definition of matrix exponential. Commented Jun 18, 2023 at 17:58
• @AdamZalcman thank you.Should the correct operation be like $e^{iA}|b\rangle=(I + A + \frac{A^2}{2!} + \frac{A^3}{3!} + ...)|b\rangle$ truncated at some high enough power of A? Commented Jun 18, 2023 at 18:05
• Almost, but not exactly. You forgot the imaginary unit and there is no truncation. Commented Jun 18, 2023 at 18:06
• @AdamZalcman ok, thanks! I suppose it's $e^{iA}|b\rangle=(I + iA - \frac{A^2}{2!} - i \frac{A^3}{3!} + ...)|b\rangle$? Commented Jun 18, 2023 at 18:07
• @James yes I think so. The top two qubits are ancillae to store the phase, the third qubit is labeled $|b\rangle$, and the last qubit is the flag register for postselection. Can we help with a particular qubit? Commented Jun 20, 2023 at 12:19

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.

• thank you. I have not understood the HHL completely. Is HHL essentially a quantum mechanical way of finding the eigenvalues (7 and -5 in the above answer) for very large matrices? Does it find the eigenvector matrix $U$ and $U^{-1}$ in a quantum way too? Commented Jun 19, 2023 at 14:59
• @James: within HHL you find all eigenvalues in superposition. Those are then used for finding solution of the linear system. Please have a look at my article where HHL is described, mainly how eigenvalue decomposition is used for finding solution of the system: cnb.cz/export/sites/cnb/en/economic-research/.galleries/…, page 19.. Commented Jun 19, 2023 at 16:19
• thank you very much. I am reading it and starting to understand parts of the algorithm I think. Commented Jun 19, 2023 at 17:09

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.

• Great. Since you have a $2\times 2$ matrix, it would have been just as easy to find the eigenvalues and eigenvectors of $A=\lambda_1|a_1\rangle\langle a_1|+\lambda_2|a_2\rangle\langle a_2|$ and use the definition $f(A)=\sum_i f(\lambda_i)|a_i\rangle\langle a_i|$ for any function of an operator $f(A)$. Commented Jun 19, 2023 at 0:12
• Beware! $A$ should be Hermitian so that $e^{i\pi A}$ is untary. Commented Jun 19, 2023 at 8:35
• @QuantumMechanic thank you. I added a part about eigenvalue decomposition since it is related to the HHL algorithm. Commented Jun 19, 2023 at 14:48
• It is the requirement that states are normalised (and hence probabilities sum to 1). One can prove that the operations that map normalized vectors to normalized vectors are the unitaries. Commented Jun 20, 2023 at 8:42
• I think this is very quickly heading into territory that cannot be covered by comments. Start by understanding classical probabilities better. If I toss a fair coin, who calculates the probability of outcome (as an equivalent to the question you ask. It's not a question I would ever ask)? How is the outcome actually resolved? Commented Jun 20, 2023 at 9:23