This question builds off of this question.

In the HHL algorithm, how do you efficiently do the $\tilde{\lambda}_k$-controlled rotations on the ancilla qubit? It seems to me that since you don't know the eigenvalues a priori, you would have to control on every single $\lambda$ within your eigenvalue bounds $[\lambda_{\text{min}},\lambda_{\text{max}}]$ (since every $\lambda$ requires a different rotation angle), requiring a potentially exponential number of controlled rotations.

I kind of get how you can avoid an exponential number of controls in Shor's algorithm, because we can split up the modular exponentiation $a^x\pmod N$ so that we can deal with each bit of $x$ separately, $a^{2^{k-1}x_{k-1}}a^{2^{k-2}x_{k-2}}...a^{2^0 x_0} \pmod N$, so you only need as many controls as the number of bits of $x$. But I'm not sure how you can do something similar in the case of HHL, because $\tilde{\lambda}_k$ is not only in the denominator, but nested inside an arcsin, e.g. \begin{align} \mathrm{Controlled\ Rotation}=\sum_{m \in [\lambda_{\text{min}},\lambda_{\text{max}}]}\underbrace{|m\rangle\langle m|}_{\text{control reg.}} \otimes \underbrace{R_y\left(\sin^{-1}(2C/m) \right)}_{\text{anc reg.}} \end{align} where the number of terms in the sum is exponential in the number of bits of precision in $\lambda$. Is there a way to do this more efficiently, and if not, wouldn't this severely eat into the exponential speedup of the algorithm?


1 Answer 1


The setting is that you've got some state $$\sum_{x\in\{0,1\}^n}\alpha_x|x\rangle$$ on a register, you introduce an ancilla in state $|0\rangle$, and you want to create some state $$ \sum_{x\in\{0,1\}^n}\alpha_x|x\rangle\otimes R_X(f(x))|0\rangle $$ where $f(x)$ is some angle that you can compute. So, certainly, if you had to build that gate out of the $2^n$ different gates "if register=$x$, then apply $R_X(f(x))$ on the ancilla" for each $x$, that would be a very bad way to go. So, here's another way to think about it.

  • Firstly, let's not apply $R_X(f(x))$, but $HR_Z(f(x))H$. The two Hadamards don't have to be controlled off anything because every gate requires them.
  • Secondly, let's assume that we know an efficient classical computation of $f(x)$. That means we can build a reversible quantum computation that runs in the same time. This involves introducing a second register. So, what you'd have is $$ \sum_x\alpha_x|x\rangle|f(x)\rangle $$ where $|f(x)\rangle$ is some $k$-bit representation of the value $2^kf(x)/\pi$.
  • Now, recognise that if you've got some state $|z\rangle$ for $z\in\{0,1\}^k$, it's easy to turn it into $e^{i\pi z 2^k}$ - you apply $Z$ on the most significant bit, $\sqrt{Z}$ on the second-most, $Z^{1/4}$ on the third, $Z^{1/8}$ on the fourth, and so on (think about how you convert from a binary to a decimal representation). Thus, if you apply these gates but controlled off the ancilla, this achieves exactly what you need.
  • Finally, you have to uncompute the second register.

Thus, overall, the scaling is limited primarily by the time it takes to compute $f(x)$. The point is this happens simultaneously for all values of $x$ due to linearity.

  • 1
    $\begingroup$ Is the controlled rotation in the HHL algorithm computing $arcsin (C \lambda_k)$ classically or is there some resource to understand how this is being computed before any of the rotations even occur? $\endgroup$ Commented Jul 11, 2019 at 20:56
  • 1
    $\begingroup$ @IntegrateThis It's computed classically (nominally, you could use your quantum computer to perform the classical computation if you want to get the advantages of parallelism). The point is that all the values of $\lambda_k$ are known in advance because they're the discrete set of values that can come out of phase estimation. In practice, you might choose to approximate the values, e.g. if $C\lambda_k$ is small, performing a Taylor expansion. $\endgroup$
    – DaftWullie
    Commented Jul 15, 2019 at 7:26

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.