Variational quantum algorithms and the complexity of many-body systems

Recently, variational quantum algorithms have received much attention, having the potential to be successfully run on near-term quantum computers. In this thesis, we study these algorithms from a quantum many-body systems perspective. The Lie theoretical framework for variational quantum algorithms is expanded upon, and we show that the states that a variational algorithm can prepare are the ground states of the Hamiltonians in the Lie algebra of the corresponding parameterised circuit. Leveraging this, we prove that the 1D QAOA can prepare all states mappable to a fermionic Gaussian state through the Jordan-Wigner transformation. We exploit this to conduct a numerical study, where we find that the use of symmetries can overly constrain the optimisation when the target Hamiltonian is non-local. Further, we characterise the overparameterised regime of optimisation, where we find that, as the circuit becomes more overparameterised, the number of iterations to reach the solution sharply decreases before saturating, and that this number goes from a polynomial to a linear scaling in the size of the lattice. By modifying the variational protocol to increase its expressibility, we study non-integrable systems, where we find that the success of state preparation can be quantified by the interaction distance, an entanglement-based measure of fermionic Gaussianity. We employ this measure in an analysis of the XYZ model, where we quantify the emerging freedom of the ground state of the model in the thermodynamic limit. Our work furthers the understanding of how variational algorithms are influenced by the physical properties of the model, the choice of parameterised circuit, and the classical optimisation of the associated parameters.