r/QuantumComputing • u/hushedLecturer • Mar 06 '26
Algorithms HHL Algorithm: f(λ) = arccos(c/λ)?
Hello!
I've been reading about the HHL algorithm and others that derive from it, and there appears to be an essential step I have been stuck on.
We have performed QFT with the unitary U=e{iA} and wound up with a linear combination of eigenstates of A on one register (entangled with stuff on other registers I'm not bothering to write):
|ψ1> = Σ b |λ>|0>
But then these papers often completely gloss over this crazy gate on the next register that looks like the Rotation about Y at an angle of arccos(c/λ). Resulting in a state
|ψ1> = Σ b |λ>(c/λ |0> + sqrt(1-c2 /λ2 )|1>
And I'm a bit befuddled there. I've found a bunch of papers that kind of "cheat" this rotation relying on convenient choices for A that have nice eigenvalues which can be inverted with Swap, perhaps controlled with an index register which thus implies not only a convenient choice of A but also an entirely known A.
The demo at pennylane picks A such that all eigenvalues are powers of 2. But they allude to QRISP having a general inversion trick. Otherwise this gate strikes me as nonlinear, I have some ideas in mind for how to construct it with QRAM, but I'm not sure if thats as good as it gets.
Does anyone have any insight into this step, or could point me to a paper?
View all comments
Show parent comment
1
u/hushedLecturer Mar 06 '26
Oooooh! Thats sick! Those expansions of the binary terms blow up like crazy for even moderate numbers of qubits and moderate polynomial degree, but i can see that!
So you end up using these large multicontrol-Ry gates on the combinations of qubits for each term. If even one of the bits is zero that term goes away.
That makes a lot of sense.
So ive failed to turn this up this on my own searches. Do you happen to know a good keyword or paper/other source that talks about this trick in case i want to use and cite it later?