  Parameterized quantum circuits are widely studied approaches for tackling
optimization problems. A prominent example is the Quantum Alternating Operator
Ansatz (QAOA), an approach that builds off the structure of the Quantum
Approximate Optimization Algorithm. Finding high-quality parameters efficiently
for QAOA remains a major challenge in practice. In this work, we introduce a
classical strategy for parameter setting, suitable for common cases in which
the number of distinct cost values grows only polynomially with the problem
size. The crux of our strategy is that we replace the cost function expectation
value step of QAOA with a parameterized model that can be efficiently evaluated
classically. This model is based on empirical observations that QAOA states
have large overlaps with states where variable configurations with the same
cost have the same amplitude, which we define as Perfect Homogeneity. We thus
define a Classical Homogeneous Proxy for QAOA in which Perfect Homogeneity
holds exactly, and which yields information describing both states and
expectation values. We classically determine high-quality parameters for this
proxy, and use these parameters in QAOA, an approach we label the Homogeneous
Heuristic for Parameter Setting. We numerically examine this heuristic for
MaxCut on random graphs. For up to $3$ QAOA levels we are easily able to find
parameters that match approximation ratios returned by previous globally
optimized approaches. For levels up to $20$ we obtain parameters with
approximation ratios monotonically increasing with depth, while a strategy that
uses parameter transfer instead fails to converge with comparable classical
resources. These results suggest that our heuristic may find good parameters in
regimes that are intractable with noisy intermediate-scale quantum devices.
Finally, we outline how our heuristic may be applied to wider classes of
problems.
