  Combinatorial optimization is among the main applications envisioned for
near-term and fault-tolerant quantum computers. In this work, we consider a
well-studied quantum algorithm for combinatorial optimization: the Quantum
Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on
3-regular graphs. We explore the idea of improving the solutions returned by
the simplest version of the algorithm (depth-1 QAOA) using a form of
postselection that can be efficiently simulated by state preparation. We derive
theoretical upper and lower bounds showing that a constant (though small)
increase of the fraction of satisfied edges is indeed achievable. Numerical
experiments on large problem instances (beyond classical simulatability)
complement and support our bounds. We also consider a distinct technique: local
updates, which can be applied not only to QAOA but any optimization algorithm.
In the case of QAOA, the resulting improvement can be sharply quantified
theoretically for large problem instances and in absence of postselection.
Combining postselection and local updates, the theory is no longer tractable
but numerical evidence suggests that improvements from both methods can be
combined.
