Konstantinos Meichanetzidis

Evaluating the Jones Polynomial on Quantum Computers

The Jones polynomial is a knot invariant and constitutes a quantum-native computational problem. It can be evaluated efficiently on quantum computers while classically the resource cost scales exponentially. We optimise the compilation of the quantum algorithm to Quantinuum's trapped-ion high-fidelity quantum processors and introduce problem-tailored error-mitigation protocols. In parallel, we improve on the state-of-the-art classical algorithms for the same problem. Further, we introduce a benchmark which leverages the structure and symmetry of inherent in the problem. This allows us to locate the instance sizes for which quantum computational advantage is expected, defined in terms of time-to-solution. Finally, we comment on the evaluation points at which the problem becomes classically easy, providing a re-interpretation in terms of quantum computation as well as tensor networks and graphical calculi.