On the Complexity of Random Quantum Computations and the Jones Polynomial

Ryan L. Mann*, Michael J. Bremner

*Corresponding author for this work

Research output: Working paperPreprint

18 Downloads (Pure)


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 of Jones polynomials can be used to bound the classical complexity of approximately simulating random quantum computations. We prove that random quantum computations cannot be classically simulated up to a constant total variation distance, under the assumption that (1) the Polynomial Hierarchy does not collapse and (2) the average-case complexity of relative-error approximations of the Jones polynomial matches the worst-case complexity over a constant fraction of random links. Our results provide a straightforward relationship between the approximation of Jones polynomials and the complexity of random quantum computations.
Original languageEnglish
Number of pages8
Publication statusUnpublished - 2 Nov 2017

Bibliographical note

8 pages, 4 figures


  • quant-ph
  • cs.CC


Dive into the research topics of 'On the Complexity of Random Quantum Computations and the Jones Polynomial'. Together they form a unique fingerprint.

Cite this