  We embed 1-layer QAOA circuits into the larger class of parameterized
Instantaneous Quantum Polynomial circuits to produce an improved variational
quantum algorithm for solving combinatorial optimization problems. The use of
analytic expressions to find optimal parameters classically makes our protocol
robust against barren plateaus and hardware noise. The average overlap with the
ground state scales as $\mathcal{O}(2^{-0.31 N})$ with the number of qubits $N$
for random Sherrington-Kirkpatrick (SK) Hamiltonians of up to 29 qubits, a
polynomial improvement over 1-layer QAOA. Additionally, we observe that
performing variational imaginary time evolution on the manifold approximates
low-temperature pseudo-Boltzmann states. Our protocol outperforms 1-layer QAOA
on the recently released Quantinuum H2 trapped-ion quantum hardware and
emulator, where we obtain an average approximation ratio of $0.985$ across 312
random SK instances of 7 to 32 qubits, from which almost $44\%$ are solved
optimally using 4 to 1208 shots per instance.
