home | literature reviews
Citation: Freedman, Michael H., Alexei Kitaev, and Zhenghan Wang. "Simulation of topological field theories¶ by quantum computers." Communications in Mathematical Physics 227 (2002): 587-603.
Tags: To-read, Foundational
This paper seriously explores the question of the power of quantum computation using a topological quantum field theory (TQFT) based model. The main conclusion is, despite Freedman's optimism in
> Freedman, Michael H. "P/NP, and the quantum field computer." Proceedings of the National Academy of Sciences 95.1 (1998): 98-101,
You cannot get a "marvelously powerful" quantum computer using TQFTs. In fact, everything you get will can be effectively simulated on a quantum circuit in polynomial time. They spin this as a positive thing, though: the "exotic" nature of TQFTs might suggest a (quote from article) "new quantum algorithm". This was later shown to be true, in the now-codified Aharonov-Jones-Landau algorithm:
> 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.
Which gives an approximation for the Jones polynomial at roots of unity in quantum polynomial (BQP) time. In fact, this problem is BQP complete. The existence of this algorithm thus also answers a second question of this paper, which is whether or not TQFTs can simulate all of BQP. This Jones polynomial algorithm was found in TQFT language in the paper
> 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.
While evaluating the Jones polynomial is #P-complete, such approximations are not. A good discussion of how hard it is to approximate the Jones polynomial is found here:
> Kuperberg, Greg. "How hard is it to approximate the Jones polynomial?." arXiv preprint arXiv:0908.0512 (2009).
The bulk of this paper is a large technical computation. There are lots of manifolds, braids, modular functors, and quantum gates. It gives a very nice constructive method for simulating TQFTs with quantum computers. Topological quantum computing is not more powerful than standard quantum computing.