# Applications of an efficient estimation of $\langle \psi | H | \psi \rangle$ for $H$ being the Heisenberg model, and $|\psi\rangle$ an arbitrary state

I consider that $$H$$ is an Hamiltonian acting on $$n$$ qubits. It is a sum containing $$Poly(n)$$ $$n$$-qubit Pauli operators $$P_i^{(k)}$$ for $$i=1,2,3$$, such that $$P_i^{(k)}$$ a tensor product of $$\sigma_0=\mathbb{I}$$ and $$\sigma_i$$ single qubit Pauli operators.

For instance, for $$n=3$$, $$P_1^{(1)}=X \otimes X \otimes \mathbb{I}$$ and $$P_1^{(2)}=X \otimes X \otimes X$$ are allowed but $$X \otimes \color{red}Z\color{black} \otimes X$$ is not (because it mixes $$X$$ and $$Z$$).

In its most general form, we thus have ($$\alpha^{i}_k$$ is some real number to ensure $$H$$ is Hermitian). $$H=\sum_{i=1}^3 \sum_{k=1}^{Poly(n)} \alpha^{i}_k P_i^{(k)}$$

Let's assume that I have a quantum computer that is able to efficiently estimate $$\langle \psi | H | \psi \rangle$$ for any $$n$$-qubit state $$|\psi\rangle$$.

My question: what are problems known to be classically hard that I could efficiently solve with my quantum computer?

Ideally, I would like to know if there is a useful application of estimating $$\langle \psi | H | \psi \rangle$$ for which the best known classical algorithm would require $$exp(n)$$ classical operations. I would also like a reference for this.

The answer might simply be "well, estimating $$\langle \psi | H | \psi \rangle$$ for any $$|\psi\rangle$$ for this class of Hamiltonians is already super usefull in itself". But if so I would also like to see some ref.

Also, I am aware of the Hadamard test which consists in estimating $$\langle \psi | U | \psi \rangle$$ for any unitary $$U$$. But the Hadamard test is more powerfull as it works for any unitary (here my question is a bit more specific).

In the case my example is too general, if it helps I can comment that the Heisenberg models belong in the class I just described. Indeed, they have the following Hamiltonian:

$$H=J_{xx} \sum_{i=1}^N X^{i} X^{i+1} + J_{yy} \sum_{i=1}^N Y^{i} Y^{i+1} + J_{zz} \sum_{i=1}^N Z^{i} Z^{i+1}+h \sum_{i=1}^N Z^{i}$$

I give this example as I know that this is a central Hamiltonian for many problems, but I am a little bit lost in which useful application I could have if I can estimate $$\langle \psi | H | \psi \rangle$$ for any $$n$$-qubit state $$|\psi\rangle$$.

For instance, if my quantum computer can efficiently evaluate $$\langle \psi | H | \psi \rangle$$, it doesn't imply that it can efficiently find the ground state as we would need to try exponentially many ansatz. This is why it is not entirely obvious for me which application we can have.

• Hi! I don't understand, do you assume that $|\psi\rangle$ is prepared in constant time and you want to know the cost of sampling? The complexity could be hidden in preparing $|\psi\rangle$ and not estimating the expectation. Jul 12 at 1:22
• @MonteNero Hi. Thanks for your comment. If I am not wrong we can prepare $|\psi\rangle$ with a good accuracy with a polynomial number of gates thanks to the Solovay–Kitaev theorem. Hence, as we have a polynomial number of Pauli operators here, the net cost of evaluating the expectation value $\langle \psi | H | \psi \rangle$ is only polynomial in $n$. Jul 12 at 9:40