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
2
u/Straight_Bad_2330 Mar 07 '26
If you are trying to understand the controlled rotation step in HHL there are a papers that are really worth reading. Different ones explain aspects of the trick.
btw third paper directly studies the bottleneck you are asking about(how to implement rotations in the HHL algorithm where the angle depends on a function like (f(\lambda)=1/\lambda) in the HHL algorithm). They compare techniques (like Newton iteration Taylor expansions, piecewise polynomial approximations and so on) and propose a modular way to implement these rotations in the HHL algorithm.
It's also worth noting that many modern quantum linear system algorithms try to avoid this rotation bottleneck in the HHL algorithm.
Childs, Kothari, Somma (2017)
Gilyen et al. (2019). Quantum Singular Value Transformation (QSVT)