Citation: Aharonov, Dorit, and Itai Arad. "The BQP-hardness of approximating the Jones polynomial." New Journal of Physics 13.3 (2011): 035019.
Web: https://arxiv.org/abs/quant-ph/0605181v2
Tags: Foundational,
This paper discusses a somewhat subtle point about the BQP-hardness of approximating the Jones polynomial. While the earlier results of
>Freedman, Michael H., Michael Larsen, and Zhenghan Wang. "A modular functor which is universal for quantum computation." Communications in Mathematical Physics 227 (2002): 605-622.
show that approximating the Jones polynomial evaluated at a k-th root of unity for a given k>4 , k !=6,10 is BQP-complete, they do not give uniformity in k. Namely, if k is allowed to grow polynomially in the number of crossings one should still expect a BQP complete problem. It was shown in
> Aharonov, Dorit, Vaughan Jones, and Zeph Landau. "A polynomial quantum algorithm for approximating the Jones polynomial." Proceedings of the thirty-eighth annual ACM symposium on Theory of computing. 2006.
that the growing-k case is still in BQP. It is just not clear that it is BQP complete. The subtelty lies in the fact that the basis of the space is constantly changing as k is increasing, so you cannot immediately apply the density=uniformity result of Solovay-Kitaev. They go through a detailed analaysis showing that, if you pick your bases correctly, you still get uniformity and everything is nice.
This paper is a good cautionary tale. In exotic situations with new phases of matter we must be very careful to check that density=>uniformity, because a-priori there could be a situation where this is not the case.