Curve-to-word conversion complexity: expressing Dehn twists about geometrically given curves as bounded-length words in mapping-class-group generators

Determine the computational complexity of the curve-to-word conversion problem left open by Freedman–Kitaev–Wang's 'Simulation of topological field theories by quantum computers' (Communications in Mathematical Physics 227:587–603, 2002): the complexity of expressing the Dehn twist about a geometrically given simple closed curve as a word of polynomially bounded length in a fixed generating set of the mapping class group, with an effective algorithm and tight bounds. Two problems raised by that paper were later resolved: measurement-phase extraction of topological data (Aharonov–Jones–Landau's explicit polynomial quantum algorithm giving additive approximations of Jones polynomial evaluations, with BQP-completeness by Aharonov–Arad), and the conjecture that every topological modular functor extends to a TQFT (subsumed by Turaev's construction once the functor carries fusion-category data). The detailed relation between 3-manifold invariants and quantum computation was substantially delivered by the 2009–2026 complexity literature, which however uniformly takes its inputs as braids, Heegaard splittings, triangulations, or ready-made generator words. The source records Lickorish's super-exponential procedure and a non-effective linear bound from Mosher's automaticity (closed and once-punctured surfaces, constants uncontrolled); the conversion problem itself remains open.

Background

A topological quantum field theory (TQFT), in the standard axiomatic formulation, assigns a finite-dimensional complex vector space $V(\Sigma)$ to each closed oriented surface $\Sigma$ and a linear map to each bordism between surfaces, compatibly with gluing. The purely two-dimensional part of such a theory — the vector spaces attached to surfaces together with the action of the diffeomorphism classes of those surfaces — is a topological modular functor (TMF), and it is unitary (a UTMF) when the spaces carry inner products preserved by that action. The standard examples arise from modular tensor categories — braided ribbon fusion categories with a non-degenerate braiding, the algebraic data of two-dimensional anyon systems (anyons being quasiparticles whose exchange statistics is a unitary matrix rather than a phase) — through the Reshetikhin–Turaev construction, the general machine producing 3-manifold invariants and TQFTs from such a category.

Freedman, Kitaev and Wang (2002) proved that quantum computers can efficiently simulate such theories: if $h$ is an element of the mapping class group of a surface — the group of isotopy classes of orientation-preserving diffeomorphisms — written as a word of length $L$ in standard Dehn twists (a Dehn twist $D_\gamma$ cuts the surface along a simple closed curve $\gamma$, rotates one side by a full turn and reglues; finitely many such twists about standard curves generate the group, in Lickorish's generators), then the action of $V(h)$ is realized exactly by a quantum circuit of length $O(L)$. BQP, the class such circuits define, is the set of decision problems solvable with bounded error by polynomial-size quantum circuits. Their construction works with elementary moves on a pants decomposition — a cutting of the surface into pairs of pants (three-holed spheres) along cuff curves, with auxiliary seam arcs cutting each pair of pants into two hexagons — so for them the natural complexity measure for a curve $\alpha$ is its combinatorial length $\ell(\alpha)$: the minimum number of intersections with the fixed cuffs and seams over the isotopy class of $\alpha$.

The bottleneck. To simulate the action of a Dehn twist $D_\alpha$ about a curve $\alpha$ that is given geometrically — say by normal coordinates on a fixed triangulation (the standard encoding that records how many times the curve crosses each edge) or by its intersection pattern with a fixed pants decomposition — one must first express $D_\alpha$ as a word in the fixed generators. Lickorish's classical procedure produces such a word, but of super-exponential length in the curve's complexity, and the 2002 paper records that the best upper bound known to its authors on the word length $L(D_\alpha)$ was a super-exponential function of $\ell(\alpha)$. A footnote adds Lee Mosher's remark that a linear bound in $\ell(\alpha)$ follows, without control of the constants, at least for closed and once-punctured surfaces, from his proof that mapping class groups are automatic — a group being automatic when its elements admit a regular language of normal forms supporting efficient algebraic algorithms, a property that decides given words but does not by itself convert geometric curve data into short words. To evade the issue the paper introduced the combinatorial-length input measure and costed its simulations in terms of it; the complexity of the conversion itself was thereby left open.

Three of the issues this problem builds on were later resolved or substantially developed: an explicit quantum algorithm whose measurement phase yields additive approximations of Jones polynomial evaluations, together with BQP-completeness; the extension of modular functors to three-dimensional TQFTs in the modern fusion-category formulation; and the detailed theory of 3-manifold invariants in quantum computation. Here the Jones polynomial is the standard 1984 knot and link invariant whose exact evaluation is classically intractable, an additive approximation is one whose error is bounded by a quantity depending only on the input size, and DQC1 denotes the one-clean-qubit model, in which a single pure qubit controls a computation on an otherwise maximally mixed register. The conversion problem above is the surviving open core. Its resolution determines whether the simulation theorem — and the later BQP-completeness and DQC1-completeness results for approximating 3-manifold invariants — applies with only polynomial overhead when the input is presented in the natural geometric form rather than as a ready-made generator word.

Problem Statement

Settle the computational complexity of the curve-to-word conversion for Dehn twists, as left open by Freedman, Kitaev and Wang when they costed their quantum simulation of modular functors.

Let $S$ be a compact, connected, oriented surface of finite type (possibly with boundary components and marked points); let $\Gamma$ be a fixed finite generating set of its mapping class group — Dehn twists about standard curves in the spirit of Lickorish's generators, with braid half-twists (local exchanges of two adjacent marked points, whose squares are boundary-parallel Dehn twists) adjoined when marked points are present; and let a simple closed curve $\alpha$ on $S$ be presented in a standard geometric or combinatorial encoding — for example as a normal curve with respect to a fixed triangulation, or by its intersections with the cuffs and seams of a fixed pants decomposition — with input complexity measured accordingly, e.g. by the combinatorial length $\ell(\alpha)$, the minimum number of intersections with the fixed cuff curves and seam arcs over the isotopy class of $\alpha$.

The problem is to determine the complexity of producing, from such data — for a single curve, for a family of curves, or for a mapping class $h$ specified as a composition of Dehn twists and braid moves along such curves — a word $w$ in $\Gamma^{\pm 1}$ representing $D_\alpha$ (respectively $h$). Concretely:

(1) Effective bounded-length conversion. Does there exist an algorithm, running in time polynomial in the input size, that outputs a word for $D_\alpha$ whose length is bounded by a polynomial in $\ell(\alpha)$ with explicitly controlled constants, for all finite-type surfaces including those with boundary and marked points? Lickorish's constructive procedure is super-exponential; Mosher's automaticity gives a linear bound without controlled constants only for closed and once-punctured surfaces.

(2) Tight bounds. Establish matching upper and lower bounds for the minimal word length $L_\Gamma(D_\alpha)$ as a function of $\ell(\alpha)$, of the chosen encoding, and of the surface type: either construct an effective polynomial-length conversion, or exhibit an explicit family of curves $\alpha_n$ with polynomially growing $\ell(\alpha_n)$ and prove that every word representing $D_{\alpha_n}$ has super-polynomial length (or the corresponding tight bound for the chosen encoding).

References

1. Michael H. Freedman, Alexei Kitaev, Zhenghan Wang, 'Simulation of topological field theories by quantum computers', Communications in Mathematical Physics 227(3):587–603 (2002). DOI: 10.1007/s002200200635; arXiv:quant-ph/0001071. https://doi.org/10.1007/s002200200635
2. W. B. R. Lickorish, 'A Representation of Orientable Combinatorial 3-Manifolds', Annals of Mathematics 76(3):531–540 (1962). DOI: 10.2307/1970373. https://doi.org/10.2307/1970373
3. Lee Mosher, 'Mapping Class Groups are Automatic', Annals of Mathematics 142(2):303–384 (1995). DOI: 10.2307/2118637. https://doi.org/10.2307/2118637
4. Michael H. Freedman, 'P/NP, and the quantum field computer', Proceedings of the National Academy of Sciences USA 95(1):98–101 (1998). DOI: 10.1073/pnas.95.1.98. https://doi.org/10.1073/pnas.95.1.98
5. Michael H. Freedman, Michael Larsen, Zhenghan Wang, 'A Modular Functor Which is Universal for Quantum Computation', Communications in Mathematical Physics 227:605–622 (2002). DOI: 10.1007/S002200200645; arXiv:quant-ph/0001108. https://doi.org/10.1007/S002200200645
6. Dorit Aharonov, Vaughan Jones, Zeph Landau, 'A Polynomial Quantum Algorithm for Approximating the Jones Polynomial', Algorithmica 55:395–421 (2009). DOI: 10.1007/s00453-008-9168-0; arXiv:quant-ph/0511096. https://doi.org/10.1007/s00453-008-9168-0
7. Dorit Aharonov, Itai Arad, 'The BQP-hardness of approximating the Jones polynomial', New Journal of Physics 13:035019 (2011). DOI: 10.1088/1367-2630/13/3/035019; arXiv:quant-ph/0605181. https://doi.org/10.1088/1367-2630/13/3/035019
8. Peter W. Shor, Stephen P. Jordan, 'Estimating Jones polynomials is a complete problem for one clean qubit', arXiv:0707.2831 (2007). https://arxiv.org/abs/0707.2831
9. Vladimir G. Turaev, 'Quantum Invariants of Knots and 3-Manifolds', 2nd edition, De Gruyter Studies in Mathematics 18, Walter de Gruyter, Berlin (2016). DOI: 10.1515/9783110435221. https://doi.org/10.1515/9783110435221
10. Eric Rowell, Zhenghan Wang, 'Mathematics of topological quantum computing', Bulletin of the American Mathematical Society 55(2):183–238 (2018). DOI: 10.1090/bull/1605; arXiv:1705.06206. https://doi.org/10.1090/bull/1605
11. S. Garnerone, A. Marzuoli, M. Rasetti, 'Efficient quantum processing of three-manifold topological invariants', Advances in Theoretical and Mathematical Physics 13(6):1601–1652 (2009). DOI: 10.4310/ATMP.2009.V13.N6.A1. https://doi.org/10.4310/ATMP.2009.V13.N6.A1
12. Gorjan Alagic, Stephen P. Jordan, Robert König, Ben W. Reichardt, 'Estimating Turaev-Viro three-manifold invariants is universal for quantum computation', Physical Review A 82:040302(R) (2010). DOI: 10.1103/PhysRevA.82.040302. https://doi.org/10.1103/PhysRevA.82.040302
13. Gorjan Alagic, Edgar A. Bering, 'Quantum Algorithms for Invariants of Triangulated Manifolds', published in Quantum Information & Computation 12(9–10):843–863 (2012); preprint arXiv:1108.5424 (2011). https://arxiv.org/abs/1108.5424
14. Stephen P. Jordan, Gorjan Alagic, 'Approximating the Turaev-Viro Invariant of Mapping Tori is Complete for One Clean Qubit', in Theory of Quantum Computation, Communication and Cryptography (TQC 2011), Lecture Notes in Computer Science, pp. 53–72 (2014). DOI: 10.1007/978-3-642-54429-3_5; preprint arXiv:1105.5100 (2011). https://arxiv.org/abs/1105.5100
15. Henrique Ennes, Clément Maria, 'Hardness of computation of quantum invariants on 3-manifolds with restricted topology', arXiv:2503.02814 (2025). https://arxiv.org/abs/2503.02814
16. César Galindo, 'A Complexity Dichotomy for Quantum Invariants of 3-Manifolds', arXiv:2605.06984 (2026). https://arxiv.org/abs/2605.06984
17. Mark C. Bell, Richard C. H. Webb, 'Polynomial-time algorithms for the curve graph', arXiv:1609.09392 (2016). https://arxiv.org/abs/1609.09392
18. Mark C. Bell, Saul Schleimer, 'The word problem for the mapping class group in quasi-linear time', arXiv:2511.02459 (2025). https://arxiv.org/abs/2511.02459
19. Nariya Kawazumi, Yusuke Kuno, 'Intersections of curves on surfaces and their applications to mapping class groups', arXiv:1112.3841 (2011). https://arxiv.org/abs/1112.3841