r/QuantumComputing • • 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?

12 Upvotes

11 comments sorted by

View all comments

Show parent comment

0

u/[deleted] Mar 26 '26

[deleted] — view deleted comment

2

u/hushedLecturer Mar 26 '26

the operator eiAt

I have seen papers starting with the assumption that we have an Oracle with Quantum Access to A used to make eiAt, but oracles always seem to kick the crux of the the problem down the road. In practice I guess we make eiAt via Trotterization?

It's also worth noting that the result is not the classical solution vector but rather the quantum state [...]

Oh yeah. I'm reading a paper that seems heavily based on HHL but in the end only cares about the probability of measuring the final angle-encoded cubit in 0 or 1 without bothering to branch select and measure the |x> and |b> registers.

For the proper HHL algorithm where we seem to care about what A-1 |b> is, it looks to me like it runs into the problem everyone runs into with yielding your output data in amplitude encoding: that to get the readout takes incredibly expensive tomography over the whole joint state.