Optimal Quantum Approximate Optimization Algirithm: Success Probability and Runtime Dependence on Circuit Depth

Due to its simplicity, universality and optimality, quantum approximate optimization algorithm~(QAOA) has been considered a useful near-term algorithm for conducting classical optimization and quantum simulation. We answer an open question of how the success probability and runtime of QAOA depend on the quantum circuit depth by focusing on a specific problem: state transfer in one-dimensional spin chain. We provide an analytic proof on the success probability scaling by leveraging the spectral property of the XY Hamiltonian. We show both analytically and numerically a Grover like quadratic dependence on the circuit depth in the short circuit depth limit and an exponential scaling in the large circuit depth limit. We prove the perfect state transfer needs O(N) time using Lieb-Robinson bound for a spin chain of length N and confirm this numerically.