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.

  • $\begingroup$ 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. $\endgroup$
    – MonteNero
    Jul 12, 2022 at 1:22
  • $\begingroup$ @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$. $\endgroup$ Jul 12, 2022 at 9:40

1 Answer 1


My answer assumes your question is found in the last paragraph.

Let |𝜓´⟩ be the true ground state of your model, unknown to us. Now, the variational principle allows us to use any trial ansatz |𝜓⟩ to calculate ⟨𝜓|𝐻|𝜓⟩. You are correct to identify that it is not clear what the ansatz should be, given a problem. However, note that this is a problem only because current NISQ quantum computers only allow a very small depth circuit to be run.

If we could run a circuit of any depth, we do not need the variational principle. We could do what is called the dynamics (see https://iopscience.iop.org/article/10.1088/1367-2630/14/10/103017 for an algorithm that can make those circuits for you). If you can run that circuit, no problem, everything is done. But you can't in the foreseeable future.

Coming back to your question. Note, "it doesn't imply that it can efficiently find the ground state as we would need to try exponentially many ansatz" is your problem and not the quantum computer's. Furthermore, many ansatz exist that we know will work rather well, so we do not (hopefully) need to try many, infinitely many.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.