# We take the reciprocal $\lambda^{-1}$ of eigenvalues in HHL - but what's stopping us from raising them to a positive exponent $\lambda^m$?

The HHL algorithm generally can be thought of as diagonalizing our matrix $$A$$ with the quantum phase estimation algorithm, and applying a specific function $$f(\lambda)=\lambda^{-1}$$ to the eigenvalues so obtained by rotating an ancilla qubit and post-selecting on the ancilla qubit being $$|1\rangle$$. The post-selection probability is given by the condition number $$\kappa$$, or the difference between the largest and smallest eigenvalues of $$A$$. We then kick these reciprocal eigenvalues back to our wavefunction by uncomputing the quantum phase estimation.

But after we diagonalize $$A$$, I don't think anything precludes us from applying any (Lipschitz continuous?) one-to-one function $$f$$ to our eigenvalues. Indeed I can imagine that we could apply $$f(\lambda)=\lambda^m$$ for some positive integer $$m$$, and then kick these back to our state.

This feels as if we can prepare a properly normalized version of $$A^m|\psi\rangle$$ using a variant of the HHL algorithm (which would normally evaluate $$A^{-1}|\psi\rangle$$) if we were successful in post-selecting our ancilla. But, if $$A$$ were the adjacency matrix of a connected undirected graph, and if $$m$$ were large enough, then by the Perron-Frobenius theorem I think we can also say that $$A^m|\psi\rangle$$ is indeed the stationary distribution, or the ground state, of $$A$$. Clearly we can't easily prepare the ground state for any arbitrary hermitian matrix, as this is QMA-hard.

So, under what conditions could we prepare $$A^m|\psi\rangle$$ using a version of HHL where the reciprocal $$\lambda^{-1}$$ rotation is replaced with positive exponentiation $$\lambda^m$$? Would then the post-selection probability given by the spectral gap (the largest vs. second-largest eigenvalue) in lieu of the condition number (the largest vs. smallest eigenvalue)?

• I certainly agree that, in principle, this lets you calculate (almost) any $f(A)|\psi\rangle$. One has to be very careful with making the mapping to QMA-hard problems: there are limits on the structure of $A$ for the algorithm to work, which at least rule out "arbitrary hermitian matrix", and one also has to check what happens to the accuracy of the approximation. I haven't checked any of the relevant details with particular care, hence the comment rather than answer. Commented Jul 18, 2023 at 9:15
• Thanks for the comment! I also think that one would need to properly scale by $\Vert A\Vert$, otherwise $f(\lambda)$ might just wrap around the circle (?). It might be helpful to consider even $f(\lambda)=\lambda^3$ or something simple, which I think is akin to "take three steps on this graph $A$, starting from the home vertex $|\psi\rangle$" (if $|\psi\rangle$ is a basis state). Commented Jul 18, 2023 at 20:47
• Yes, an important part of HHL is being able to bound the range of eigenvalues of $A$ so that you don't get any eigenvalue ambiguity from the phase estimation.. Commented Jul 19, 2023 at 6:48

In that paper they do much of exactly what I propose - namely, they calculate, in superposition, the function $$f(A)$$ on a hermitian matrix $$A$$, for various Lipschitz-continuous functions such as $$f(x)=x^p$$ or $$\vert x\vert ^p$$. They use HHL's trick of storing the eigenphases $$\lambda$$ in a top register by using quantum phase estimation with a local Hamiltonian simulation of $$A$$, rotating an ancilla based on the $$\arccos f(\lambda)$$, and uncomputing the phase estimation. (They use $$p$$ for the Schatten $$p$$-norm, where I use $$m$$ for the number of $$m$$-length walks).
But, they are interested in the trace of $$\vert A\vert^p$$ for various values of $$p$$, which they sometimes can achieve with even a DQC-1 algorithm, while I was interested in preparing the ground state of $$A$$ by post-selecting on the ancilla being properly rotated. Their phase estimation acts on a maximally-mixed state, and not on any particular basis state. Cade and Montanaro don't bother with post-selection, as far as I can tell.