Towards Classical Descriptions of the Quantum Approximate Optimization Algorithm

We summarize and extend the concept of homogeneity in the Quantum Approximate Optimization Algorithm. Informally, homogeneity refers to an empirically-observed phenomenon that for QAOA on certain constraint satisfaction problems (CSPs) and parameter schedules, bitstrings (representing variable configurations) with identical cost retain similar amplitudes throughout the algorithm. Previous works assumed a more strong version of this phenomenon, where bitstrings with identical cost retain identical amplitudes, and leveraged this, along with problem class properties, to create polynomial-sized proxy for QAOA, and empirically studied how faithfully the proxy represents QAOA. Here, we aim to extend the model, incorporating deviations from homogeneity, with the goal of creating a "second-order" homogeneous proxy for QAOA, with the goal of capturing more qualities of QAOA, while retaining polynomial memory and time requirements.