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

  • $\begingroup$ 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. $\endgroup$ Commented Oct 27, 2018 at 4:35
  • $\begingroup$ @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. $\endgroup$ Commented Oct 29, 2018 at 7:33

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.

  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jul 4, 2018 at 13:38
  • 2
    $\begingroup$ Sure, I was only meaning that Grover gives you a square root speedup compared to the naive way of getting the max. Of course that has a bad impact on the overall running time. $\endgroup$
    – DaftWullie
    Commented Jul 4, 2018 at 17:36
  • 1
    $\begingroup$ Just to add, there is a method by Kerenedis and Prakash - arxiv.org/abs/1704.04992 to estimate the spectral norm based on quantum singular value estimation, which can be used to scale the matrix. This method works in the QRAM model, but you can also do it with a sparse-access oracle arxiv.org/pdf/1804.01973.pdf. $\endgroup$
    – dylan7
    Commented Nov 19, 2021 at 3:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.