  Variational quantum algorithms (VQAs) have demonstrated considerable
potential in solving NP-hard combinatorial problems in the contemporary near
intermediate-scale quantum (NISQ) era. The quantum approximate optimisation
algorithm (QAOA) is one such algorithm, used in solving the maximum cut
(Max-Cut) problem for a given graph by successive implementation of $L$ quantum
circuit layers within a corresponding Trotterised ansatz. The challenge of
exploring the cost function of VQAs arising from an exponential proliferation
of local minima with increasing circuit depth has been well-documented.
However, fewer studies have investigated the impact of circuit depth on QAOA
performance in finding the correct Max-Cut solution. Here, we employ
basin-hopping global optimisation methods to navigate the energy landscapes for
QAOA ans\"atze for various graphs, and analyse QAOA performance in finding the
correct Max-Cut solution. The structure of the solution space is also
investigated using discrete path sampling to build databases of local minima
and the transition states that connect them, providing insightful
visualisations using disconnectivity graphs. We find that the corresponding
landscapes generally have a single funnel organisation, which makes it
relatively straightforward to locate low-lying minima with good Max-Cut
solution probabilities. In some cases below the adiabatic limit the second
lowest local minimum may even yield a higher solution probability than the
global minimum. This important observation has motivated us to develop broader
metrics in evaluating QAOA performance, based on collections of minima obtained
from basin-hopping global optimisation. Hence we establish expectation
thresholds in elucidating useful solution probabilities from local minima, an
approach that may provide significant gains in elucidating reasonable solution
probabilities from local minima.
