  The quantum approximate optimisation algorithm (QAOA) is a hybrid
quantum-classical algorithm used to approximately solve combinatorial
optimisation problems. It involves multiple iterations of a parameterised
ansatz comprising a problem and mixer Hamiltonian, with the parameters being
classically optimised. While QAOA can be implemented on NISQ devices, physical
limitations can limit circuit depth and decrease performance. To address these
limitations, this work introduces the eXpressive QAOA (XQAOA), an
overparameterised variant of QAOA that assigns more classical parameters to the
ansatz to improve its performance at low depths. XQAOA also introduces an
additional Pauli-Y component in the mixer Hamiltonian, allowing the mixer to
implement arbitrary unitary transformations on each qubit. To benchmark the
performance of XQAOA at unit depth, we derive its closed-form expression for
the MaxCut problem and compare it to QAOA, Multi-Angle QAOA (MA-QAOA), a
classical-relaxed algorithm, and the state-of-the-art Goemans-Williamson
algorithm on a set of unweighted regular graphs with 128 and 256 nodes for
degrees ranging from 3 to 10. Our results indicate that at unit depth, XQAOA
has benign loss landscapes, allowing it to consistently outperform QAOA,
MA-QAOA, and the classical-relaxed algorithm on all graph instances and the
Goemans-Williamson algorithm on graph instances with degrees greater than 4.
Small-scale simulations also reveal that unit-depth XQAOA surpasses both QAOA
and MA-QAOA on all tested depths up to five. Additionally, we find an infinite
family of graphs for which XQAOA solves MaxCut exactly and analytically show
that for some graphs in this family, XQAOA achieves a much larger approximation
ratio than QAOA. Overall, XQAOA is a more viable choice for variational quantum
optimisation on NISQ devices, offering competitive performance at low depths.
