2026-07-22T02:03:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24505 2025-12-16T14:00:06Z ddc:004 open_access

Hardness of Computation of Quantum Invariants on 3-Manifolds with Restricted Topology Ennes, Henrique Maria, Clément 3-manifold Heegaard splitting Hempel distance Quantum invariant polynomial time reduction Quantum invariants in low-dimensional topology offer a wide variety of valuable invariants about knots and 3-manifolds, presented by explicit formulas that are readily computable. Their computational complexity has been actively studied and is tightly connected to topological quantum computing. In this article, we prove that for any 3-manifold quantum invariant in the Reshetikhin-Turaev model, there is a deterministic polynomial time algorithm that, given as input an arbitrary closed 3-manifold M, outputs a closed 3-manifold M' with the same quantum invariant, such that M' is hyperbolic, contains no low genus embedded incompressible surface, and is presented by a strongly irreducible Heegaard diagram. Our construction relies on properties of Heegaard splittings and the Hempel distance. At the level of computational complexity, this proves that the hardness of computing a given quantum invariant of 3-manifolds is preserved even when severely restricting the topology and the combinatorics of the input. This positively answers a question raised by Samperton [Samperton, 2023]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Henrique Ennes and Clément Maria 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.37 urn:nbn:de:0030-drops-245057 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.37 eng https://creativecommons.org/licenses/by/4.0/legalcode