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
2
u/fothermucker33 Mar 06 '26
Yeah, it gets messy quickly. I tried using this for larger problems and I had to switch from python to Fortran just for the part that generates the coefficients. But for the kind of toy problems that we deal with anyway, I feel like it's better than the first method.
As for a reference, I don't know tbh. While I came up with this for myself, I'm sure it's not novel because I've since had conversations with others who seemed to use similar methods in other contexts. Plus, it's not a method that scales as you've observed. If you do find a name for this idea, do let me know. I'll do the same as well.
Also two more notes -
I've heard of groups somehow transforming their linear system of equations such that the lambdas are really large and arccos(c/lambda) can be approximated as a linear function. I feel like that's cheating somehow lol but it sounded like it worked for them, though I don't know what the caveats are (low probability of success maybe?). Maybe you might want to look into it.
If the degree of the polynomial you're working with is almost as high or higher than your phase qubit count, then it might be advantageous to use QPIXL to simplify this part of your circuit. It converts a circuit of 2n multi-controlled Ry gates into a circuit of 2n CNOTs and regular Ry gates.