Abstract
There has been considerable success in using combinatorial techniques to rigorously identify computational complexity transitions in statistical mechanical models. Recently developed techniques have provided the ability to study the complexity of these models with complex parameters, which are closely related to probability amplitudes in quantum physical models. In this talk, we present some results on how these techniques can be applied to identify computational complexity transitions in quantum physics. Our first result is an efficient deterministic algorithm for approximating certain output probability amplitudes of a class of commuting quantum circuits when the interaction graph has bounded maximum degree d and the interactions are absolutely bounded from above by Omega(1/d) (see arXiv:1806.11282). Key to our algorithm is an approach due to Barvinok for approximating evaluations of a polynomial based on the location of the complex zeros and a technique due to Patel and Regts for efficiently computing coefficients of graph polynomials on bounded degree graphs. Our second result is a hardness proof for these amplitudes when the interactions are bounded from above by O(1/d). Specifically, we show that additive-error approximations are BQP-hard and relative-error approximations are #P-hard. These results demonstrate quantum computational complexity transitions at Theta(1/d), where additive-error approximations transition from P to BQP-hard and relative-error approximations transition from P to #P-hard. This is joint work with Michael Bremner.