Content deleted Content added
No edit summary |
Topological quantum field theories and knot invariants |
||
Line 139:
The problem is to compute the value of a formula given by a balanced binary tree with bits at the leaves, and NAND gates at the inner vertices.<ref>{{cite web |url=http://scottaaronson.com/blog/?p=207 |title=NAND now for something completely different |author=[[Scott Aaronson]] |date=2007-02-03 |work=Shtetl-Optimized |accessdate=2009-12-17}}</ref> This problem requires Θ(''N''<sup>0.753</sup>) queries classically, but can be solved in Θ(''N''<sup>0.5</sup>) queries by a quantum algorithm.<ref>E. Farhi, [[Jeffrey Goldstone|J. Goldstone]], and S. Gutmann, A quantum algorithm for the Hamiltonian NAND tree, Theory of Computing 4 (2008), no. 1, 169–190, quant-ph/0702144</ref>
== Knot invariants ==
Witten had shown that the [[Chern-Simons]] [[topological quantum field theory]] can be solved in terms of [[Jones polynomial]]s. A quantum computer can simulate a TQFT, and thereby approximate the Jones polynomial
<ref>
{{Citation
| last = Aharonov
| first = Dorit
| author-link = [[Aharonov]]
| last2 = Jones
| first2 = Vaughan
| author2-link = [[Vaughan Jones]]
| last3 = Landau
| first3 = Zeph
| title = A polynomial quantum algorithm for approximating the Jones polynomial
| journal = STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing
| volume =
| issue =
| pages = 427--436
| date =
| origyear =
| year = 2006
| month =
| url =
| archiveurl =
| archivedate =
| doi = http://doi.acm.org/10.1145/1132516.1132579
| id = }}
</ref>, which as far as we know, is hard to compute classically in the worst case scenario.
==Quantum Simulation==
| |||