Role of entanglement in a VQE ansatz for combinatorial problems

Question

Variational Quantum Eigensolver is used in quantum chemistry and combinatorial optimization (CO). I'm interested in the latter. In the CO setting a Hamiltonian is a diagonal matrix with real entries and it can be expressed as a linear combination of Puali Z matrices.

From what I read a few ansatz' were proposed: hardware efficient ansatz, Hamiltonian variational ansatz and unitary coupled cluster ansatz.

Regardless of the architecture of the ansatz, it seems the entanglement is a very desired property as it somehow improves classical optimization part.

I don't understand why we need entanglement for solving CO problems? I could just use an RY gate on each qubit and that would allow me to span all states with real amplitudes.

However, when I ran a small experiment with an ansatz containing only RY gates, the results were worse than the same ansatz with some extra CNOT gates. So it does seem that entanglement is important. But what does it do?

My intuition (which is incorrect) tells me that entanglement could significantly reduce the space of solutions because some states become too correlated. Think about the following 2 qubit system which produces the EPR state. In this contrived case we only cover half of a solution space which might be really bad for some problems. I expect the same behaviour mildly manifest itself in systems with more qubits.

Thank you.

Answer 1

With just single qubit gate in your circuit, you can only generate a small subset of quantum states. In fact, the states that you can generate are called separable states. These states have no entanglement in them.

Here is an example to see why you need to be able to generate entangle state to have successful VQE calculation, supposed you have the Hamiltonian $H = \begin{pmatrix} 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 \end{pmatrix} $

And you running VQE to find the lowest eigenvalue to this Hamiltonian. This means you need to be able to generate the eigenstate that correspond to the lowest eigenvalue. Now, if you look at all the eigenstates of $H$ and their correspondence eigenvalues:

$$|\psi_1 \rangle = \begin{pmatrix} 1/\sqrt{2} \\ 0 \\ 0 \\ 1/\sqrt{2} \end{pmatrix} \rightarrow 1, |\psi_2 \rangle = \begin{pmatrix} 1/\sqrt{2} \\ 0 \\ 0 \\ -1/\sqrt{2}\end{pmatrix} \rightarrow -1, |\psi_3 \rangle = \begin{pmatrix} 0 \\ 1/\sqrt{2}\\ 1/\sqrt{2} \\ 0\end{pmatrix} \rightarrow 1, |\psi_4 \rangle = \begin{pmatrix} 0 \\ -1/\sqrt{2} \\ 1/\sqrt{2} \\ 0\end{pmatrix} \rightarrow -1$$

Here you should notice that these states are all entangled. So if you want your VQE algorithm to find the lowest eigenvalue (-1) in this case, it must be able to generate an entangled state. That means if you design your Ansatze only made up from $RY$ rotation, for example:

then you can't never generate such entangled state, which means you can never reach the minimum eigenvalue. So the complexity of the Ansatz depends on the complexity of the Hamiltonian that you consider.

---

But you are right about the fact that given a diagonal Hamiltonian, like those that you are interested in then the eigenstate will be one of the computational basis state! Thus, you do not need entanglement gate or any sort... in fact, you only need $X$ gates to generate such states. But then this means you have to iterate through $2^n$ states... which is not ideal.

And since you know the solution you are looking for is in one of these states, it is quite easy to classically go through all the calculations of the expectation values (depending on how many terms in your cost function Hamiltonian). You do have to do $2^n$ check, so it's not ideal either, but these checks are very easy... you just look at the parity of the Pauli string and this can be done very quickly.... So this makes me wonder, giving the sophistication of classical computer systems (like this cluster), how many qubits do we need for quantum computer to beat classical computer? Classical computers can go through this check so fast... but since the number of terms to check do scale as $2^n$... we will reach a bottle neck at some point. But how many qubits is that going to take before quantum computer wins out? 100 or few hundreds?

Answer 2

For diagonal Hamiltonians, you might not need entanglement at all.

The intuition for why a more complicated ansatz might be useful is that the optimization landscape is somehow better, in the sense that the minimum is easier to find. However, in this paper, the author applies VQE to some combinatorial optimization problems and finds that variational forms with entanglement don't bring any advantage.

One more thing: a complicated entagling ansatz may be useful if it is tailored to the problem at hand, like in QAOA.