10
$\begingroup$

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

$\endgroup$
  • $\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$ – user1271772 Oct 27 '18 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$ – Nelimee Oct 29 '18 at 7:33
6
$\begingroup$

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.

$\endgroup$
  • 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$ – Nelimee Jul 4 '18 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 Jul 4 '18 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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