Tunneling and Speedup in Permutation-Invariant Quantum Optimization Problem

Tunneling is often claimed to be the key mechanism underlying possible speedups in quantum optimization via the quantum adiabatic algorithm. Restricting ourselves to qubit-permutation invariant problems, we show that tunneling in these problems can be understood using the semi-classical potential derived from the spin-coherent path integral formalism. Using this, we show that the class of problems that fall under Reichardt's bound (1), i.e., have a constant gap and hence can be efficiently solved using the quantum adiabatic algorithm, do not exhibit tunneling in the large system-size limit. We proceed to construct problems that do not fall under Reichardt's bound but numerically have a constant gap and do exhibit tunneling. However, perhaps counter-intuitively, tunneling does not provide the most efficient mechanism for finding the solution to these problems. Instead, an evolution involving a sequence of diabatic transitions through many avoided level-crossings, involving no tunneling, is optimal and outperforms tunneling in the adiabatic regime. In yet another twist, we show that in this case, classical spin-vector dynamics is as efficient as the diabatic quantum evolution (2).\\ (1) B. W. Reichardt, in Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, STOC ’04 (ACM, New York, NY, USA, 2004) pp. 502–510.\\ (2) S. Muthukrishnan, T. Albash, D.A. Lidar, arXiv:1505.01249.