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

Question

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)?

Answer 1

^{Self-Answer, making CW}

---

Thanks to @incud for pointing out a 2017 paper of Cade and Montanaro - pdf, arXiv.

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.