Clarification of the "Calculations" section of the (HHL09) paper

Question

I am reading this paper entitled "Quantum algorithm for linear systems of equations" and am trying to understand a portion of the algorithm described on page 2 and in more detail in the appendix starting at the bottom of page 10 (section 3. Phase Estimation calculations).

Suppose we have a hermitian matrix $A$ of dimension $n$ and a vector $b$ of size $n$ and denote by $|u_j \rangle$ the eigenvectors of $A$, which are also eigenvectors of $e^{iAt}$, and $\lambda_j$ the corresponding eigenvalues. Ultimately this algorithm aims to find $x$ such that $Ax = b$.

Assuming we have access to the state $\left|\Psi_{0} \right\rangle = \sqrt{\frac {2} {T} } \sum_{\tau = 0} ^{T - 1} \sin \left(\frac {\pi(\tau + 1/2)} {T}\right) |\tau \rangle$, the algorithm instructs to apply $\sum_{\tau = 0} ^{T - 1} |\tau \rangle \langle \tau |\otimes e^{iA \tau to/T}$ to $|\Psi_{0} \rangle |b \rangle$, the former being referred to as a conditional Hamiltonian evolution. The register $C$ initially contains $|\Psi_0 \rangle $, while the register $I$ contains $|b \rangle$.

The author/s then writes "assume the target state is $|u_j \rangle$, so this becomes simply the condition phase $|\Psi_{\lambda_j t_o} \rangle = \sqrt{\frac {2} {T} } \sum_{\tau = 0} ^{T - 1} e^{\frac {i \lambda_j \tau t_{0}} {T}} \sin \left(\frac {\pi(\tau + 1/2)} {T}\right) |\tau \rangle |u_j\rangle$", where now we have a superposition of $|\Psi_0 \rangle$ and the result of applying $e^{iA\tau t_{0}/T}$ to the eigenvector $|u_j \rangle$. My questions are:

1. Are we not applying the conditional Hamiltonian evolution to $|\Psi_0 \rangle |b \rangle$? I know that $b$ can be decomposed mathematically as $b= c_1u_1 + \cdots + c_nu_n$ since these eigenvectors form an orthonormal basis. Why only consider the effect on $|u_j \rangle$?

2. What is going on with the $\sum_{\tau = 0} ^{T - 1} |\tau \rangle \langle \tau|$ portion of the sum in the conditional Hamiltonian evolution? In this answer here, it is described "[...] a control part. It means that the operation will be controlled by the state of the first quantum register (the register C as the exponent tells us)". I understand the "gist" of this statement but any reference to understand it more fully would be much appreciated.

   Edit: Is $\sum_{\tau = 0} ^{T - 1} |\tau \rangle \langle \tau|$, not simply the identity matrix of dimension $T$? In which case the result after tensoring is a block matrix with $e^{iA\tau t_{0}/T}$ on the main diagonal, and $0_n$ elsewhere. Do I have this right?

3. After this step, a Fourier transform is applied to the register $C$, but at this point what is contained in register $ C$? The state $|\Psi_{\lambda_j t_o} \rangle $ seems to describe the superposition of registers $C,I$.

I would be happy to edit/add any information that can help decipher this. Thanks

Answer 1

I know that $b$ can be decomposed mathematically as $b= c_1u_1 + > \cdots + c_nu_n$ since these eigenvectors form an orthonormal basis. Why only consider the effect on $|u_j \rangle$?

As you say, you know you can decompose $b$ in terms of the $|u_j \rangle$, so by linearity, if we know the effect on one basis state (which is pedagogically easier to describe), then we know the overall effect.

Is $\sum_{\tau = 0} ^{T - 1} |\tau \rangle \langle \tau|$, not simply the identity matrix of dimension $T$? In which case the result after tensoring is a block matrix with $e^{iA\tau t_{0}/T}$ on the main diagonal, and $0_n$ elsewhere. Do I have this right?

This is sort of right - if the term $e^{iA\tau t_{0}/T}$ didn't contain $\tau$, you'd be fine. However, it does, so you have to include that in the sum over $\tau$, so you're not just doing $\sum_{\tau = 0} ^{T - 1} |\tau \rangle \langle \tau|$ in isolation. As a simple example of this, imagine you were doing $$ \sum_{\tau}|\tau\rangle\langle\tau|\otimes |\tau\rangle\langle\tau|, $$ this is certainly not the same thing as $1\otimes|\tau\rangle\langle\tau|$ (after all, what is $\tau$ at this point?). That is why the operator describes a controlled evolution. It say "if the first register is in the state $\tau$, apply the evolution $e^{iA\tau t_{0}/T}$ on the second register". To reiterate, the key point is that both terms in the tensor product depend on $\tau$.

what is contained in register $C$ ? The state $|\Psi_{\lambda_j t_o} > \rangle $ seems to describe the superposition of registers $C,I$.

Indeed it does. It is crucial that the two registers are entangled, and you cannot consider just $C$ in isolation. However, this is where it continues to help by just considering $|u_j \rangle$ instead of $b$. In that case, the register $C$ is separable from register $I$. What that state is looks horribly messy and hard to decipher. When I think about this calculation, as a first step, I find it easier to think about setting $|\Psi_0\rangle$ as a uniform superposition, just like you would in a 'normal' phase estimation procedure. Then your register $C$ is in the state that is output from a normal phase estimation procedure, and it is clear that application of the (inverse) Fourier transform gives you the phase, in other words the eigenvalue of $|u_j\rangle$ with high probability.

If my alteration of $|\Psi_0\rangle$ is so obvious and simple, why don't they do that? The answer is it's an optimisation. The normal phase estimation protocol aims to maximise the probability of getting the right phase, whatever that phase may be. However, that's not the right figure of merit for the HHL algorithm (basically, because you're inverting eigenvalues, you need your small eigenvalues to be estimated more accurately than the larger ones), and the slightly different choice of $|\Psi_0\rangle$ aims to optimise the phase estimation procedure for that particular application.

Answer 2

1) Are we not applying the conditional Hamiltonian evolution to $|\Psi_0 \rangle |b \rangle$?

The operation $$\sum_{\tau = 0} ^{T - 1} |\tau \rangle \langle \tau| \otimes e^{iA\tau t_0 / T}$$ is a controlled operation. You can read it as:

$\forall \tau \in [0, T-1]$, if the first register is in the state $\vert \tau \rangle$, apply $e^{iA\tau t_0 / T}$.

This can be verified with the following property: $$\left( A \otimes B \right) \times \left( \vert a \rangle \otimes \vert b \rangle\right) = \left(A \times \vert a \rangle \right) \otimes \left( B \times \vert b \rangle\right)$$ where:

• $A$ (resp. $B$) is a unitary operator on the space of $\vert a \rangle$ (resp. $\vert b \rangle$)
• $\times$ is the matrix-vector multiplication
• $\otimes$ is the kronecker product.

Coming back to the "controlled Hamiltonian operation", if you apply the operator on a state $\vert \Psi_0 \rangle \otimes \vert b \rangle$ you end up with:

$$ \begin{split} \left( \sum_{\tau = 0} ^{T - 1} |\tau \rangle \langle \tau| \otimes e^{iA\tau t_0 / T} \right) \times \left(\vert \Psi_0 \rangle \otimes \vert b \rangle\right) &= \sum_{\tau = 0} ^{T - 1} \left(|\tau \rangle \langle \tau| \otimes e^{iA\tau t_0 / T}\right) \times \left(\vert \Psi_0 \rangle \otimes \vert b \rangle\right) \\ &= \sum_{\tau = 0} ^{T - 1} \left(|\tau \rangle \langle \tau| \times \vert \Psi_0 \rangle \right) \otimes \left(e^{iA\tau t_0 / T} \times\vert b \rangle\right) \\ \end{split} $$ The first part of the sum $\left(|\tau \rangle \langle \tau| \times \vert \Psi_0 \rangle \right)$ is $\vert \Psi_0 \rangle$ when $\vert \Psi_0 \rangle = \vert \tau \rangle$, else it simplifies to the zero vector, which "removes" the effect of $e^{iA\tau t_0 / T}$ on $\vert b \rangle$ when $\vert \Psi_0 \rangle \neq \vert \tau \rangle$.

I know that $b$ can be decomposed mathematically as $b= c_1u_1 + \cdots + c_nu_n$ since these eigenvectors form an orthonormal basis. Why only consider the effect on $|u_j \rangle$?

We could consider the effect on any other basis instead of the eigenbasis. But for the HHL algorithm, the controlled Hamiltonian simulation part is used in the Quantum Phase Estimation algorithm to estimate the eigenvalues of the simulated matrix ($A$ in your example). Considering another basis, even if it is possible, is not what will lead us to the solution which is the extraction of the eigenvalues of $A$ to invert them afterwards.

2)What is going on with the $\sum_{\tau = 0} ^{T - 1} |\tau \rangle \langle \tau|$ portion of the sum in the conditional Hamiltionian evolution? In this answer here , it is described "[...] a control part. It means that the operation will be controlled by the state of the first quantum register (the register C as the exponent tells us)". I understand the "gist" of this statement but any reference to understand it more fully would be much appreciated. Edit: Is $\sum_{\tau = 0} ^{T - 1} |\tau \rangle \langle \tau|$, not simply the identity matrix of dimension $T$? In which case the result after tensoring is a block matrix with $e^{iA\tau t_{0}/T}$ on the main diagonal, and $0_n$ elsewhere. Do I have this right?

See above. The error you made in your reasoning here is that you studied one part of the sum independently of the other, which is not possible.

Quick note: $\sum_{\tau = 0} ^{T - 1} |\tau \rangle \langle \tau|$ alone is the identity matrix of size $T$; you are right.

3) After this step, a Fourier transform is applied to the register $C$, but at this point what is contained in register $C$ ? The state $|\Psi_{\lambda_j t_o} \rangle $ seems to describe the superposition of registers $C,I$.

The Fourier transform is part of the Quantum Phase Estimation algorithm. I personally find easier to understand first all the details of the QPE algorithm and then viewing the first part of the HHL algorithm as the QPE algorithm with a specific unitary matrix. Doing this allows you to first untangle the mathematical complexity of the QPE algorithm, and then "forget" about this and focus on the mathematical complexity added by the state $\vert \Psi_0\rangle$ and the application of the controlled Hamiltonian simulations.

Note: @DaftWullie explains why $\vert \Psi_0 \rangle$ has such a complicated expression both in its answer to this question and a more detailed answer.