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

Question

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

Answer 1

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.