Adiabatic quantum computation and quantum phase transitions

We analyze the ground-state entanglement in a quantum adiabatic evolution algorithm designed to solve the $NP$-complete Exact Cover problem. The entropy of entanglement seems to obey linear and universal scaling at the point where the energy gap becomes small, suggesting that the system passes near a quantum phase transition. Such a large scaling of entanglement suggests that the effective connectivity of the system diverges as the number of qubits goes to infinity and that this algorithm cannot be efficiently simulated by classical means. On the other hand, entanglement in Grover’s algorithm is bounded by a constant.

Figure 1

Average over 300 instances of the entanglement entropy between two blocks of size $n∕2$ as a function of the parameter $s$ controlling the adiabatic evolution. A peak appears for $s_c\sim 0.7$. The plot also shows the increase of the peak as the number of qubits grows $n=10,12,14$.

Figure 2

Scaling of the entanglement entropy both for the worst case and for the average over 300 randomly generated instances. Error bars give 95% confidence intervals. The behavior appears to be linear.

Figure 3

Minimum gap versus the inverse size of the system, both for the worst case and for the average over all instances. Error bars give 95% confidence intervals. The behavior appears to be linear.

Figure 4

Mean critical point $s_c$ for the minimum gap and for the maximum entropy. Error bars give 95% confidence intervals. Both sets of points tend to approach as the size of the system is increased.