  Variational quantum circuits build the foundation for various classes of
quantum algorithms. In a nutshell, the weights of a parametrized quantum
circuit are varied until the empirical sampling distribution of the circuit is
sufficiently close to a desired outcome. Numerical first-order methods are
applied frequently to fit the parameters of the circuit, but most of the time,
the circuit itself, that is, the actual composition of gates, is fixed. Methods
for optimizing the circuit design jointly with the weights have been proposed,
but empirical results are rather scarce. Here, we consider a simple
evolutionary strategy that addresses the trade-off between finding appropriate
circuit architectures and parameter tuning. We evaluate our method both via
simulation and on actual quantum hardware. Our benchmark problems include the
transverse field Ising Hamiltonian and the Sherrington-Kirkpatrick spin model.
Despite the shortcomings of current noisy intermediate-scale quantum hardware,
we find only a minor slowdown on actual quantum machines compared to
simulations. Moreover, we investigate which mutation operations most
significantly contribute to the optimization. The results provide intuition on
how randomized search heuristics behave on actual quantum hardware and lay out
a path for further refinement of evolutionary quantum gate circuits.
