# Role of entanglement in a VQE ansatz for combinatorial problems

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.

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?

• Hi Kaj226! Thank you very much. You gave a great illustrative example. However, I would like to clarify one thing. In CO the Hamiltonian is a linear combination of Pauli Z tensor products so all eigenvectors are standard basis states which can be obtained without entanglement. In that case it is still not obvious to me why entanglement is important or usefull. May 21, 2021 at 1:24
• I am thinking that originally, QAOA was based from from the discretization of adiabatic quantum annealing process. Which leads to quantum circuits that involved CNOT gates to represent the exponential of Pauli terms. Then my guess is that people found that this is too expensive on current quantum hardware... people create some parametrized quantum circuits that is less expensive but can do a similar job then perform VQE on it. Since the original circuit involved entanglement gates, a modified version of it should have it as well... May 21, 2021 at 15:23
• @MonteNero Often in your CO type problems, how many Pauli terms ($Z_i\cdots Z_j \cdots$) do you have in your $H_C$ ? Is it polynomial? May 22, 2021 at 0:24
• thanks for further refining your post. The number of Pauli tensor products terms is 2*(n+1) where n is a number of qubits. If I get clever with measurements then it is possible that I would end up with n terms. The factor of 2 comes from a constraint that needs to be satisfied. May 25, 2021 at 22:43
• @MonteNero By the way, your question and other factors lead me to simulate the minimum vertex cover problems on different graphs, some up to 20 qubits and a single layer of rotation works.... there are cases where I would get stuck in local min, but I have built the optimizer to try to get out of it.. Also just because you randomly add 2 qubit gate to the circuit doesn't mean it does any help in term of avoiding local min... QAOA circuit was designed with a specific idea in mind... to approx the annealing process. But even with QAOA circuit/ansatz, you still get stuck in local min too... May 25, 2021 at 23:31

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.

• Hi Alexey, thanks for the paper, really useful one! Do you think entanglement in the ansatz can help with quantum tunneling effect? Intuitively, I feel like entanglement might help to tunnel through high picks of an energy landscape. May 25, 2021 at 22:45
• I'm not sure it actually tunnels through the peaks of the energy landscape, it's more like the ansatz and the problem instance shape the landscape together. That is, if you think of the landscape as the function of ansatz parameters. May 27, 2021 at 10:09