|
Organizers |
Q 3-Stranded Quantum Algorithm for the Jones Polynomial
by
Samuel J. Lomonaco, Jr.
University of Maryland Baltimore County (UMBC), Baltimore, MD 21250
Coauthors: Louis H. Kauffman and Samuel J. Lomonaco, Jr.
Let K be a 3-stranded knot (or link), and let L denote the number of crossings of K. Let ε₁ and ε₂ be two positive real numbers such that ε₂≤1.
We create two algorithms for computing the value of the Jones polynomial V_{K}(t) at all points t=exp(iϕ) of the unit circle in the complex plane such that |ϕ|≤2π/3.
The first algorithm, called the classical 3-stranded braid (3-SB) algorithm, is a classical deterministic algorithm that has time complexity O(L). The second, called the quantum 3-SB algorithm, is a quantum algorithm that computes an estimate of V_{K}(exp(iϕ)) within a precision of ε₁ with a probability of success bounded below by 1-ε₂. The execution time complexity of this algorithm is O(nL), where n is the ceiling function of (ln(4/ε₂))/2ε₁². The compilation time complexity, i.e., an asymptotic measure of the amount of time to assemble the hardware that executes the algorithm, is O(L).
Date received: April 9, 2007
Copyright © 2007 by the author(s). The author(s) of this work and the organizers of the conference have granted their consent to include this abstract in Topology Atlas. Document # cauq-13.