  The Quantum Approximate Optimization Algorithm (QAOA) is a standard method
for combinatorial optimization with a gate-based quantum computer. The QAOA
consists of a particular ansatz for the quantum circuit architecture, together
with a prescription for choosing the variational parameters of the circuit. We
propose modifications to both. First, we define the Gibbs objective function
and show that it is superior to the energy expectation value for use as an
objective function in tuning the variational parameters. Second, we describe an
Ansatz Architecture Search (AAS) algorithm for searching the discrete space of
quantum circuit architectures near the QAOA to find a better ansatz. Applying
these modifications for a complete graph Ising model results in a $244.7\%$
median relative improvement in the probability of finding a low-energy state
while using $33.3\%$ fewer two-qubit gates. For Ising models on a 2d grid we
similarly find $44.4\%$ median improvement in the probability with a $20.8\%$
reduction in the number of two-qubit gates. This opens a new research field of
quantum circuit architecture design for quantum optimization algorithms.
