New paper: On the Complexity of Random Quantum Computations
By Ryan Mann and Michael Bremner
Today on the arXiv we released a new paper where we use the natural relationship between Jones polynomials and quantum computation to bound the classical complexity of approximately simulating random quantum computations, under plausible complexity-theoretic assumptions.
Over the last few years there has been a series of results [1,2,3,4,5] that seek to rigorously argue that quantum computers outperform classical computers by studying carefully chosen sets of random quantum circuits. Colloquially, this work seeks to identify quantum computations that demonstrate quantum computational supremacy.
The basic theoretical idea behind these results is to link the complexity of families of quantum circuits to the typical difficulty of evaluating certain mathematical functions. The typical complexity of these functions then determines the complexity of these quantum circuit families. To the best of our knowledge, we believe that such functions are very hard to compute. Unfortunately, definitively proving this turns out to be very difficult (like, literally, it’s been mathematically proven to be difficult [6], we aren’t just being lazy here). Interestingly, it is also the case that most of the families of circuits studied are related to their own distinct family of these hard functions and we still don’t fully understand the relationship between them.
Here we introduce an arguably more natural family of functions that could be useful for linking the aforementioned results. We consider the Jones polynomials, in which random circuits are simply related to random braids in a link (that is, a collection of knots). These functions have the advantage that they are capable of being linked to any family of quantum circuits. In principle, this gives Jones polynomials the capability to describe any of the previous functions that have been studied for quantum computational supremacy. However, in practice, this isn’t necessarily so straightforward. Nonetheless we see this as a first step towards understanding the links between all such problems.
For a brief overview of the technical results, check out Ryan’s blog post.
