# Quantum phase estimation and HHL algorithm - knowledge of eigenvalues required?

The quantum phase estimation algorithm (QPE) computes an approximation of the eigenvalue associated to a given eigenvector of a quantum gate $U$.

Formally, let $\left|\psi\right>$ be an eigenvector of $U$, QPE allows us to find $\vert\tilde\theta\rangle$, the best $m$ bit approximation of $\lfloor2^m\theta\rfloor$ such that $\theta \in [0,1)$ and $$U\vert\psi\rangle = e^{2\pi i \theta} \vert\psi\rangle.$$

The HHL algorithm (original paper) takes as input a matrix $A$ that satisfy $$e^{iAt} \text{ is unitary }$$ and a quantum state $\vert b \rangle$ and computes $\vert x \rangle$ that encodes the solution of the linear system $Ax = b$.

Remark: Every hermitian matrix statisfy the condition on $A$.

To do so, HHL algorithm uses the QPE on the quantum gate represented by $U = e^{iAt}$. Thanks to linear algebra results, we know that if $\left\{\lambda_j\right\}_j$ are the eigenvalues of $A$ then $\left\{e^{i\lambda_j t}\right\}_j$ are the eigenvalues of $U$. This result is also stated in Quantum linear systems algorithms: a primer (Dervovic, Herbster, Mountney, Severini, Usher & Wossnig, 2018) (page 29, between equations 68 and 69).

With the help of QPE, the first step of HLL algorithm will try to estimate $\theta \in [0,1)$ such that $e^{i2\pi \theta} = e^{i\lambda_j t}$. This lead us to the equation $$2\pi \theta = \lambda_j t + 2k\pi, \qquad k\in \mathbb{Z}, \ \theta \in [0,1)$$ i.e. $$\theta = \frac{\lambda_j t}{2\pi} + k, \qquad k\in \mathbb{Z}, \ \theta \in [0,1)$$ By analysing a little the implications of the conditions $k\in \mathbb{Z}$ and $\theta \in [0,1)$, I ended up with the conclusion that if $\frac{\lambda_j t}{2\pi} \notin [0,1)$ (i.e. $k \neq 0$), the phase estimation algorithm fails to predict the right eigenvalue.

But as $A$ can be any hermitian matrix, we can choose freely its eigenvalues and particularly we could choose arbitrarily large eigenvalues for $A$ such that the QPE will fail ($\frac{\lambda_j t}{2\pi} \notin [0,1)$).

In Quantum Circuit Design for Solving Linear Systems of Equations (Cao, Daskin, Frankel & Kais, 2012) they solve this problem by simulating $e^{\frac{iAt}{16}}$, knowing that the eigenvalues of $A$ are $\left\{ 1, 2, 4, 8 \right\}$. They normalised the matrix (and its eigenvalues) to avoid the case where $\frac{\lambda_j t}{2\pi} \notin [0,1)$.

On the other side, it seems like parameter $t$ could be used to do this normalisation.

Question: Do we need to know a upper-bound of the eigenvalues of $A$ to normalise the matrix and be sure that the QPE part of the HHL algorithm will succeed? If not, how can we ensure that the QPE will succeed (i.e. $\frac{\lambda_j t}{2\pi} \in [0,1)$)?

• Let's say $t=1$. Are you saying lambda cannot ever be negative? What's wrong with having a negative eigenvalue? Let's say $k=2$ and $t=1$. Then: $0 < (\lambda / 2\pi) + 2 < 1$, and $-4\pi < \lambda < -2\pi$. A completely valid value for $\lambda = -3\pi$. What is wrong with that? Why does $\lambda/2\pi$ have to be positive or $0$ ? Eigenvalues can be negative. – user1271772 Oct 27 '18 at 4:35
• @user1271772 In this case no, $\lambda$ cannot ever be negative because the QPE impose that $\theta \in [0, 1)$. If $\lambda < 0$ (because you plugged a matrix with a negative eigenvalue, this is possible of course), then the output of the QPE will not represent $\lambda$ but rather $\lambda - 2k\pi$ with $k = \lfloor \frac{\lambda}{2\pi} \rfloor$, i.e. "$\lambda$ modulo $2\pi$", and this will make the HHL algorithm fail. – Adrien Suau Oct 29 '18 at 7:33

You should know a bound on the eigenvalues (both upper and lower). As you say, you can then normalise $A$ by rescaling $t$. Indeed, you should do this to get the most accurate estimate possible, spreading the values $\lambda t$ over the full $2\pi$ range. Bounding the eigenvalues is not typically a problem. For example, you're probably requiring your matrix $A$ to be sparse, so that there aren't too many non-zero matrix elements on each row. Indeed, the problem specification probably gives you a bound on the number $N$ of non-zero entries per row, and the maximum value of any entry $Q$.
Then you could apply something like Gershgorin's circle theorem. This states that the maximum eigenvalue is upper bounded by $$\max_i a_{ii}+\sum_{j\neq i}|a_{ij}|\leq NQ,$$ and the minimum is lower bounded by $$\min_ia_{ii}-\sum_{j\neq i}|a_{ij}|\geq -NQ.$$ The $a_{ij}$ are the matrix elements of $A$.
Within the values of $N$, $Q$, if you're worrying that for a large matrix (say $n$ qubits), while the row sum might be easy to calculate (because there's not many entries), the max over all rows might take a long time (because there's $2^n$ rows), there will be a variety of ways to get good approximations to it (e.g. sampling, or using knowledge of the problem structure). Worst case, you can probably use Grover's search to speed it up a bit.
• Grover is not an improvement: even if we can use the algorithm, we will still need $\mathcal{O}(\sqrt{N})$ queries, which destroy the exponential improvement of HHL over classical methods and replace it with a quadratic speedup. So the only hope left is sampling (introduce an other source of errors) or pray and hope that the problem allows us to estimate the upper/lower bounds. Seems like a major flaw of the algorithm to me. – Adrien Suau Jul 4 '18 at 13:38