Quantum Complexity Annealing: Protocols for Disentangling and Stabilizing

Entanglement is arguably the most distinctive feature of quantum mechanics. Since the quantum theory was formulated, the emergence of correlations between sub-parts of a physical system has led, on one hand, to the derivation of numerous interesting paradoxes and, on the other, to the development of information protocols that cannot be implemented in a classical framework. In particular, one of the most thriving areas of research is devoted to the development of quantum algorithms that are intended to outperform their classical analogues. Entanglement therefore represents an important resource for the creation of quantum computers, but its quantification in terms of entropies of entanglement is found to be insufficient to determine whether a quantum advantage over classical computation can be achieved. In this thesis we will review the concept of complexity of entanglement, that characterizes quantum states that can not be efficiently simulated on classical computers and can therefore lead to a speed-up when employed for computational tasks. We will show that the complexity of entanglement is related to the emergence of quantum chaos, the ability to simulate random states and the distance from a class of classically simulable states called stabilizers. Moreover, complex states are shown to be characterized by robustness against certain annealing schedules (disentanglers) aiming at reducing the amount of entanglement within the system. We show how the efficiency of a disentangler relates to multiple probes of complexity on a 1-parameter family of quantum many-body states, and how tuning the parameter can drive a transition between the different complexity phases. We also adopt the same annealing procedure to learn the retrieval of scrambled information from a black hole and we conclude that the learning process is hindered by the conjunction of entanglement and non-stabilizerness within the system. Lastly, we propose an enhanced algorithm to anneal both entanglement and non-stabilizerness, in an attempt to efficiently reduce the overall entanglement complexity of random circuits. We present encouraging results for small systems that show how the new protocol outperforms the original disentangler with the same number of circuit updates. We stress the necessity for an efficient way to compute non-stabilizerness, in order to scale the results to higher system sizes