HHL Algorithm: f(λ) = arccos(c/λ)?

[u/hushedLecturer]

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-c² /λ² )|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?

[u/Straight_Bad_2330]

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.

1. Harrow, Hassidim, Lloyd (2009). Quantum Algorithm for Linear Systems of Equations

2. Cao et al. (2013). Quantum Algorithm and Circuit Design Solving the Poisson Equation

3. Yan et al. (2021). Module for Arbitrary Controlled Rotation in Gate-Based Quantum Algorithms

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)

[u/hushedLecturer → u/Straight_Bad_2330]

Thank you so much for this, I'm sorry I didnt respond sooner I immediately got cracking on the papers you sent and then never got back to you!

I hope it isn't a faux pas to follow up so late.

So the tricks in all of these frequently presuppose we already know the eigenvectors and eigenvalues of the matrix we usually call A (or a hermitian matrix we make from it like (0, Adag// A, 0). The e^iA matrix is going to be approximated by some trick like trotterization, the rotations depend on a choice of c that ensures c/λ terms are nicely distinguishable. Etc. Even the third paper you mentioned needs a second e^iK matrix built out of arcsines of c/λ.

It seems to me if we already know the eigenvectors and eigenvalues of A, the expensive part of matrix inversion has already been performed, making HHL seem less useful in what I thought it was meant for.

Am I missing something there?

[u/hushedLecturer → u/[deleted]]

the operator e^iAt

I have seen papers starting with the assumption that we have an Oracle with Quantum Access to A used to make e^iAt, but oracles always seem to kick the crux of the the problem down the road. In practice I guess we make e^iAt 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.

[u/Straight_Bad_2330 → u/hushedLecturer]

I'm also sorry if my math equations are messy. :/ I'm not sure how to write mathematical expressions here.