Quantum adiabatic algorithms and large spin tunnelling

We study the quantum adiabatic evolution algorithm with different evolution paths that correspond to different control Hamiltonians H(tau) sampled from a random ensemble. The algorithm is applied to a random binary optimization problem where the cost function is symmetric with respect to the permutation of individual bits. We investigate the method proposed by Farhi when different evolution paths preserve the bit symmetry of the control Hamiltonians H(tau) and are generated by an ensemble of random 8x8 matrices. In this case, the algorithm dynamics is completely described in terms of the motion of a spin-n/2 system. We show that different evolution paths can be parametrized by a small number of independent parameters that are expansion coefficients of H(tau) in a certain universal set of operators. One of these operators is responsible for avoiding the tunnelling for the spin-n/2 system and the corresponding coefficient determines the algorithm complexity for a given problem instance. We show that any problem instance can be solved in polynomial time by applying one of the two universal path modifications (due to the possible reflection symmetry of the problem). We show that a successful evolution path of the algorithm always corresponds to the trajectory of a classical spin n/2 and provide a complete characterization of such paths.