A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz

The Quantum Alternating Operator Ansatz, a generalized approach building on the Quantum Approximate Optimization Algorithm, is a widely studied method for tackling optimization problems. Finding high-quality parameters efficiently for QAOA remains a major challenge. In this work we introduce a classical strategy for parameter setting, especially suitable for cases in which the number of distinct cost values grows only polynomially with the problem size. Our approach is based on the observation that if classical variable configurations with the same cost have the same quantum amplitudes at a given step, which we denote as Perfect Homogeneity, then under mild assumptions one may efficiently apply another QAOA step or compute expectation values classically. High overlaps between QAOA states and states with Perfect Homogeneity have been empirically observed in a number of settings. Hence, we define a Classical Homogeneous Proxy for QAOA in which Perfect Homogeneity is asserted to hold exactly. Given a problem instance drawn from a class and QAOA circuit depth, we classically determine good parameters for the the proxy, and then incorporate these parameters into the corresponding QAOA circuit, an approach we call the Homogeneous Heuristic for Parameter Setting. We numerically examine this heuristic for MaxCut on unweighted random graphs. For depth l=3, we demonstrate that the heuristic is easily able to find parameters that match approximation ratios corresponding to previously-found globally optimized approaches. For depth l