  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 that consists of a problem and mixer Hamiltonian, with the parameters
being classically optimised. While QAOA can be implemented on near-term quantum
hardware, physical limitations such as gate noise, restricted qubit
connectivity, and state-preparation-and-measurement (SPAM) errors can limit
circuit depth and decrease performance. To address these limitations, this work
introduces the eXpressive QAOA (XQAOA), a modified version of QAOA that assigns
more classical parameters to the ansatz to improve the performance of low-depth
quantum circuits. XQAOA includes an additional Pauli-Y component in the mixer
Hamiltonian, thereby allowing the mixer to implement arbitrary unitary
transformations on each qubit. To benchmark the performance of the XQAOA ansatz
at low depth, we derive its closed-form expression for the MaxCut problem and
compare it to QAOA, Multi-Angle QAOA (MA-QAOA), a Classical-Relaxed (CR)
algorithm, and the state-of-the-art Goemans-Williamson (GW) algorithm on a set
of unweighted regular graphs with 128 and 256 nodes and degrees ranging from 3
to 10. Our results show that XQAOA performs better than QAOA, MA-QAOA, and the
CR algorithm on all graphs and outperforms the GW algorithm on graphs with
degrees greater than 4. Additionally, we find an infinite family of graphs for
which XQAOA solves MaxCut exactly and show analytically that for some graphs in
this family, special cases of XQAOA can achieve a larger approximation ratio
than QAOA. Overall, XQAOA is a more viable choice for implementing quantum
combinatorial optimisation on near-term quantum devices, as it can achieve
better results with a single iteration, despite requiring additional classical
resources.
