On the Complexity of Random Quantum Computations and the Jones Polynomial

Ryan L. Mann, Michael J. Bremner

There is a natural relationship between Jones polynomials and quantum computation. We use this relationship to show that the complexity of evaluating relative-error approximations…