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

  • 2
    $\begingroup$ 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. $\endgroup$
    – DaftWullie
    Jul 18, 2023 at 9:15
  • $\begingroup$ 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). $\endgroup$ Jul 18, 2023 at 20:47
  • $\begingroup$ 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.. $\endgroup$
    – DaftWullie
    Jul 19, 2023 at 6:48


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.