The Quantum Alternating Operator Ansatz on Max-k Vertex Cover

We study the performance of the Quantum Alternating Operator Ansatz (a generalization of the QAOA for problems with hard constraints) on the problem of Max-k Vertex Cover due to its modest complexity, while still being more complex than the well studied problems of Max-Cut and Max-E3LIN2. Our approach includes (i) a performance comparison between easy-to-prepare classical states and Dicke states, (ii) a performance comparison between two XY-Hamiltonian mixing operators: the ring mixer and the complete graph mixer, (iii) an analysis of the distribution of solutions via Monte Carlo sampling, and (iv) the exploration of efficient angle selection strategies. Our results are: (i) Dicke states improve performance compared to easy-to-prepare classical states, (ii) an upper bound on the simulation of the complete graph mixer, (iii) the complete graph mixer improves performance relative to the ring mixer, (iv) the standard deviation on the distribution of solutions decreases exponentially in p (the number of rounds in the algorithm), requiring an exponential number of random samples find a better solution in the next round, and (iv) a correlation of angle parameters which exhibit high quality solutions that behave similarly to a discretized version of the Quantum Adiabatic Algorithm.