Name
Abstract | ||
|---|---|---|
The permanent of a square matrix is defined in a way similar to the determinant, but without using signs. The exact computation of the permanent is hard, but there are Monte Carlo algorithms that can estimate general permanents. Given a planar diagram of a link L with n crossings, we define a 7nx7n matrix whose permanent equals the Jones polynomial of L. This result, accompanied with recent work of Freedman, Kitaev, Larsen and Wang (2003) [8], provides a Monte Carlo algorithm for any decision problem belonging to the class BQP, i.e. such that it can be computed with bounded error in polynomial time using quantum resources. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.aam.2011.03.003 | Advances in Applied Mathematics |
Keywords | Field | DocType |
jones polynomial,decision problem,monte carlo algorithm,exact computation,class bqp,general permanent,link l,permanent,approximation,permanent formula,polynomial time,square matrix,quantum computing . 1,state sums,bounded error,quantum computer,quantum algebra,quantum physics,quantum computing | Discrete mathematics,Characteristic polynomial,Combinatorics,Polynomial matrix,Polynomial,Jones polynomial,Mathematical analysis,Square matrix,Bracket polynomial,Matrix polynomial,Mathematics,BQP | Journal |
Volume | Issue | ISSN |
47 | 4 | Adv. in Appl. Math., 47 (2011) 659-667 |
Citations | PageRank | References |
0 | 0.34 | 14 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Martin Loebl | 1 | 152 | 28.66 |
| Iain Moffatt | 2 | 44 | 9.63 |