Efficient method to find square root of a Hamiltonian

Question

I'm working with a Hamiltonian $H$ represented as a linear combination of Pauli strings:

$$H = \sum_j \alpha_j P_j,$$

where $P_j \in \{I, X, Y, Z\}^{\otimes n}$ are tensor products of Pauli matrices and $n$ is the number of qubits.

I'm looking for an efficient method to find another Hamiltonian $\tilde{H} = \sum_j \tilde{\alpha_j} \tilde{P_j}$, such that:

$$ \tilde{H}^2 = H. $$

I am also assuming that $H$ has only positive eigenvalues. So, $\sqrt{H}$ will also be a Hermitian operator. As one can always shift the system by a finite amount to make all the eigenvalues positive.

I cannot diagonalize the Hamiltonian or use methods that require the matrix representation of $H$, as the dimension increases exponentially with the system size. Are there any known techniques or approximations that could be useful for this problem? Any insights or references would be greatly appreciated! To be more precise I want to find methods to time-evolve $\sqrt{H}$ without using extra qubits.

Answer 1

There cannot be an efficient such algorithm -- where by efficient, I mean that

1. it works for a small ($\mathrm{poly(n)}$) number of non-zero $\alpha_j$,
2. the number of $\tilde\alpha_j$ is also $\mathrm{poly(n)}$ (my feeling is that this is what is the real restriction -- the cases where this happens are probably very special)
3. the algorithm scales as $\mathrm{poly(n)}$.

The reason is that such an algorithm could be used to find the smallest eigenvalue of $H$, $E_0(H)$. To this end, simply change $H\to H-c\,I$, compute $\tilde H$, and test whether $\tilde H^2=H$ (the latter can be done efficiently). The test will fail as soon as $c\ge E_0(H)$, thus allowing to determine the ground state energy up to an exponential accuracy (!) in poly(n) time by binary search. (If instead the algorithm to compute $\tilde H$ declares failure for non-positive $H$, we can use the failure flag instead of the test.)

Since finding the ground state energy even to $1/\mathrm{poly}(n)$ accuracy is a QMA-hard problem, such an algorithm cannot exist (under the usual complexity theoretic assumptions). (In fact, it is even sufficient to consider classical spin glasses.)

---

Notes:

My suspicion is that what fails is condition 2. -- I think the cases where $\tilde H$ has a small number of non-zero $\tilde\alpha_j$ is very small. Whether an algorithm to solve a promise version of the problem could work is an interesting question.

Another question is whether one can find a variant which can be used to compute individual $\tilde \alpha_j$ in time $\mathrm{poly}(n)$, given that there are only $\mathrm{poly}(n)$ non-zero $\alpha_j$.