End-to-End Quantum Algorithms for the Jones Polynomial

Abstract

We present an end-to-end algorithmic pipeline where a noisy digital quantum computer is used to approximate the value of the Jones polynomial at the fifth root of unity for any input link, i.e. a closed braid. This problem is DQC1-complete for Markov-closed braids and BQP-complete for Plat-closed braids, and we accommodate both versions of the problem. Even though it is widely believed that DQC1 is strictly contained in BQP, and so is 'less quantum', the resource requirements of classical algorithms for the DQC1 version are at least as high as for the BQP version, and so we potentially gain 'more advantage' by focusing on Markov-closed braids in our exposition. We demonstrate our quantum algorithm on Quantinuum's H2-2 quantum computer and show the effect of problem-tailored error-mitigation techniques. Further, leveraging that the Jones polynomial is a link invariant, we construct an efficiently verifiable benchmark to characterise the effect of noise present in a given quantum processor. In parallel, we develop and benchmark the state-of-the-art tensor-network-based classical algorithms for computing the Jones polynomial. The reconfigurable tools provided in this work allow for precise resource estimation to identify minimum link sizes for near-term quantum advantage in practice for a meaningful quantum-native problem in knot theory, if a candidate set of links are provided.

References in corpus (23)

• Improved Simulation of Stabilizer Circuits
• Robust randomized benchmarking of quantum processes
• Validating quantum computers using randomized model circuits
• Quantum Error Mitigation
• A generative modeling approach for benchmarking and training shallow quantum circuits
• A Race Track Trapped-Ion Quantum Processor
• Matchgates and classical simulation of quantum circuits
• Hyper-optimized tensor network contraction
• Measuring the Capabilities of Quantum Computers
• Application-Oriented Performance Benchmarks for Quantum Computing
• Methodology for replacing indirect measurements with direct measurements
• A volumetric framework for quantum computer benchmarks
• Application-Motivated, Holistic Benchmarking of a Full Quantum Computing Stack
• Fast counting with tensor networks
• Experimental approximation of the Jones polynomial with DQC1
• The computational power of random quantum circuits in arbitrary geometries
• Protecting Expressive Circuits with a Quantum Error Detection Code
• Demonstrating scalable randomized benchmarking of universal gate sets
• Optimizing the information extracted by a single qubit measurement
• Power of one non-clean qubit
• The Fibonacci Model and the Temperley-Lieb Algebra
• Quantum Algorithms for the Jones Polynomial
• Braid representatives minimizing the number of simple walks