On Assessing the Quantum Advantage for MaxCut Provided by Quantum Neural Network Ans\"atze

Abstract

In this work we design a class of Ansätze to solve MaxCut on a parameterized quantum circuit (PQC). Gaining inspiration from properties of quantum optimal control landscapes, we consider the presence of optimization traps as a measure of complexity for hybrid variational quantum algorithms. In particular, we analytically show that no simple Ansatz, satisfying certain criteria, can provide a superpolynomial quantum advantage in solving MaxCut while nevertheless creating entanglement. Furthermore, in order to characterize properties of Ansätze that could provide a quantum advantage, we study the role of noncommutativity in PQCs through a series of numerical experiments. Finally, we compare this notion to similar properties in classical neural networks such as nonlinearity, based on the perspective of the recent moniker for PQCs as quantum neural networks. (displayed version) In this thesis we expand upon the results that led to the paper [1] of Lee et al., arXiv:2105.01114 (2021). In particular, we give more details on the oracular formulation of variational quantum algorithms, and the relationship between properties of Ansätze and the strength of their corresponding oracles. Furthermore, having identified the importance of noncommutativity in parameterized quantum circuits (PQCs) as likely being crucial to achieving a quantum advantage, we compare this notion to similar properties in classical neural networks such as nonlinearity, based on the perspective of the recent moniker for PQCs as quantum neural networks. While this thesis includes much of the figures and content from the aforementioned paper, it should be considered mainly as a self-contained collection of supplementary materials.