Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0601169 · Quantum Information and Computation

Quantum automata, braid group and link polynomials

Silvano Garnerone, Annalisa Marzuoli, Mario Rasetti

Published Jul 1, 2007• 35 citations
arXivHTMLPDF

Abstract

The spin--network quantum simulator model, which essentially encodes the (quantum deformed) $SU(2)$ Racah--Wigner tensor algebra, is particularly suitable to address problems arising in low dimensional topology and group theory. In this combinatorial framework we implement families of finite--states and discrete--time quantum automata capable of accepting the language generated by the braid group, and whose transition amplitudes are colored Jones polynomials. The automaton calculation of the polynomial of (the plat closure of) a link $L$ on $2N$ strands at any fixed root of unity is shown to be bounded from above by a linear function of the number of crossings of the link, on the one hand, and polynomially bounded in terms of the braid index $2N$, on the other. The growth rate of the time complexity function in terms of the integer $k$ appearing in the root of unity $q$ can be estimated to be (polynomially) bounded by resorting to the field theoretical background given by the Chern--Simons theory.

DOI
10.26421/qic7.5-6-5

Related papers

Quantum Computation of Universal Link Invariants

Silvano Garnerone, Annalisa Marzuoli, Mario Rasetti

In the framework of the spin-network simulator based on the SU q(2) tensor algebra, we implement families of finite state quantum automata capable of accepting the language generated by the braid group, and whose transition amplitudes are coloured Jones polynomials. The automaton calculation of the polynomial of a link L on n strands at any fixed root of unity q is bounded from above by a linear function of the number of crossings of the link, on the one hand, and polynomially bounded in terms of the braid index n, on the other.

Open Systems & Information Dynamics•Nov 13, 2006•10 citations

Spin networks, quantum automata and link invariants

Silvano Garnerone, Annalisa Marzuoli, Mario Rasetti

The spin network simulator model represents a bridge between (generalized) circuit schemes for standard quantum computation and approaches based on notions from Topological Quantum Field Theories (TQFT). More precisely, when working with purely discrete unitary gates, the simulator is naturally modelled as families of quantum automata which in turn represent discrete versions of topological quantum computation models. Such a quantum combinatorial scheme, which essentially encodes SU (2) Racah-Wigner algebra and its braided counterpart, is particularly suitable to address problems in topology and group theory and we discuss here a finite states-quantum automaton able to accept the language of braid group in view of applications to the problem of estimating link polynomials in Chern-Simons field theory.

arXiv:gr-qc/0511161•Journal of Physics Conference Series•Mar 1, 2006•5 citations

Spin networks, quantum automata and link invariants

Garnerone, S., Marzuoli, A., Mario Rasetti +1 more

The spin network simulator model represents a bridge between (generalized) circuit schemes for standard quantum computation and approaches based on notions from Topological Quantum Field Theories (TQFT). More precisely, when working with purely discrete unitary gates, the simulator is naturally modelled as families of quantum automata which in turn represent discrete versions of topological quantum computation models. Such a quantum combinatorial scheme, which essentially encodes SU(2) Racah–Wigner algebra and its braided counterpart, is particularly suitable to address problems in topology and group theory and we discuss here a finite states– quantum automaton able to accept the language of braid group in view of applications to the problem of estimating link polynomials in Chern–Simons field theory. 1 1

•Jan 1, 2005•8 citations

An efficient quantum algorithm for colored Jones polynomials

Silvano Garnerone, Annalisa Marzuoli, Mario Rasetti

We construct a quantum algorithm to approximate efficiently the colored Jones polynomial of the plat presentation of any oriented link L at a fixed root of unity q. Our construction is based on SU(2) Chern-Simons topological quantum field theory (and associated Wess-Zumino-Witten conformal field theory) and exploits the q-deformed spin network as computational background. As proved in (S. Garnerone, A. Marzuoli, M. Rasetti, quant-ph/0601169), the colored Jones polynomial can be evaluated in a number of elementary steps, bounded from above by a linear function of the number of crossings of the link, and polynomially bounded with respect to the number of link strands. Here we show that the Kaul unitary representation of colored oriented braids used there can be efficiently approximated on a standard quantum circuit.

arXiv:quant-ph/0606167•Jun 20, 2006•2 citations

Quantum automata, braid group and link polynomials

GarneroneSilvano, MarzuoliAnnalisa, RasettiMario

The spin-network quantum simulator model, which essentially encodes the (quantum deformed) SU(2) Racah-Wigner tensor algebra, is particularly suitable to address problems arising in low dimensional...

Quantum Information and Computation•Jul 1, 2007•0 citations

The Jones polynomial: quantum algorithms and applications in quantum complexity theory

Paweł Wocjan, Jon Yard

We analyze relationships between quantum computation and a family of generalizations of the Jones polynomial. Extending recent work by Aharonov et al., we give efficient quantum circuits for implementing the unitary Jones-Wenzl representations of the braid group. We use these to provide new quantum algorithms for approximately evaluating a family of specializations of the HOMFLYPT two-variable polynomial of trace closures of braids. We also give algorithms for approximating the Jones polynomial of a general class of closures of braids at roots of unity. Next we provide a self-contained proof of a result of Freedman et al. that any quantum computation can be replaced by an additive approximation of the Jones polynomial, evaluated at almost any primitive root of unity. Our proof encodes two-qubit unitaries into the rectangular representation of the eight-strand braid group. We then give QCMA-complete and PSPACE-complete problems which are based on braids. We conclude with direct proofs that evaluating the Jones polynomial of the plat closure at most primitive roots of unity is a #P-hard problem, while learning its most significant bit is PP-hard, circumventing the usual route through the Tutte polynomial and graph coloring.

arXiv:quant-ph/0603069•Journal of International Crisis and Risk Communication Research•Mar 8, 2006•18 citations
The spin--network quantum simulator model, which essentially encodes the (quantum deformed) SU(2)SU(2)SU(2) Racah--Wigner tensor algebra, is particularly suitable to address problems arising in low dimensional topology and group theory. In this combinatorial framework we implement families of finite--states and discrete--time quantum automata capable of accepting the language generated by the braid group, and whose transition amplitudes are colored Jones polynomials. The automaton calculation of the polynomial of (the plat closure of) a link LLL on 2N2N2N strands at any fixed root of unity is shown to be bounded from above by a linear function of the number of crossings of the link, on the one hand, and polynomially bounded in terms of the braid index 2N2N2N, on the other. The growth rate of the time complexity function in terms of the integer kkk appearing in the root of unity qqq can be estimated to be (polynomially) bounded by resorting to the field theoretical background given by the Chern--Simons theory.
In the framework of the spin-network simulator based on the SU q(2) tensor algebra, we implement families of finite state quantum automata capable of accepting the language generated by the braid group, and whose transition amplitudes are coloured Jones polynomials. The automaton calculation of the polynomial of a link L on n strands at any fixed root of unity q is bounded from above by a linear function of the number of crossings of the link, on the one hand, and polynomially bounded in terms of the braid index n, on the other.
The spin network simulator model represents a bridge between (generalized) circuit schemes for standard quantum computation and approaches based on notions from Topological Quantum Field Theories (TQFT). More precisely, when working with purely discrete unitary gates, the simulator is naturally modelled as families of quantum automata which in turn represent discrete versions of topological quantum computation models. Such a quantum combinatorial scheme, which essentially encodes SU (2) Racah-Wigner algebra and its braided counterpart, is particularly suitable to address problems in topology and group theory and we discuss here a finite states-quantum automaton able to accept the language of braid group in view of applications to the problem of estimating link polynomials in Chern-Simons field theory.
The spin network simulator model represents a bridge between (generalized) circuit schemes for standard quantum computation and approaches based on notions from Topological Quantum Field Theories (TQFT). More precisely, when working with purely discrete unitary gates, the simulator is naturally modelled as families of quantum automata which in turn represent discrete versions of topological quantum computation models. Such a quantum combinatorial scheme, which essentially encodes SU(2) Racah–Wigner algebra and its braided counterpart, is particularly suitable to address problems in topology and group theory and we discuss here a finite states– quantum automaton able to accept the language of braid group in view of applications to the problem of estimating link polynomials in Chern–Simons field theory. 1 1
We construct a quantum algorithm to approximate efficiently the colored Jones polynomial of the plat presentation of any oriented link L at a fixed root of unity q. Our construction is based on SU(2) Chern-Simons topological quantum field theory (and associated Wess-Zumino-Witten conformal field theory) and exploits the q-deformed spin network as computational background. As proved in (S. Garnerone, A. Marzuoli, M. Rasetti, quant-ph/0601169), the colored Jones polynomial can be evaluated in a number of elementary steps, bounded from above by a linear function of the number of crossings of the link, and polynomially bounded with respect to the number of link strands. Here we show that the Kaul unitary representation of colored oriented braids used there can be efficiently approximated on a standard quantum circuit.
We analyze relationships between quantum computation and a family of generalizations of the Jones polynomial. Extending recent work by Aharonov et al., we give efficient quantum circuits for implementing the unitary Jones-Wenzl representations of the braid group. We use these to provide new quantum algorithms for approximately evaluating a family of specializations of the HOMFLYPT two-variable polynomial of trace closures of braids. We also give algorithms for approximating the Jones polynomial of a general class of closures of braids at roots of unity. Next we provide a self-contained proof of a result of Freedman et al. that any quantum computation can be replaced by an additive approximation of the Jones polynomial, evaluated at almost any primitive root of unity. Our proof encodes two-qubit unitaries into the rectangular representation of the eight-strand braid group. We then give QCMA-complete and PSPACE-complete problems which are based on braids. We conclude with direct proofs that evaluating the Jones polynomial of the plat closure at most primitive roots of unity is a #P-hard problem, while learning its most significant bit is PP-hard, circumventing the usual route through the Tutte polynomial and graph coloring.