End-to-End Quantum Algorithms for the Jones Polynomial

Technical Summary: End-to-End Quantum Algorithms for the Jones Polynomial

Problem Definition
The paper addresses the computational challenge of approximating the Jones polynomial, a topological invariant for knots and links, at the fifth root of unity ($t = e^{i 2\pi/5}$). The problem is framed in terms of braids, where any link can be formed by "closing" a braid. Two specific formulations are considered:

1. Markov Closure (DQC1-complete): Estimating the weighted trace of a unitary matrix representing the braid. This corresponds to the "one clean qubit" model of computation.
2. Plat Closure (BQP-complete): Estimating a specific quantum amplitude (an element of the unitary matrix).

While DQC1 is widely believed to be strictly contained within BQP (implying DQC1 is "less quantum"), the authors note that classical resource requirements for the DQC1 version (estimating a trace of an exponentially large matrix) are at least as high as, if not higher than, those for the BQP version (estimating an amplitude). Consequently, the authors focus on the DQC1 formulation (Markov closure) to potentially demonstrate a greater quantum advantage, despite their pipeline supporting both.

Methodology
The authors present an end-to-end algorithmic pipeline designed for noisy, gate-based digital quantum computers (specifically Quantinuum's H2-2). The core methodology involves:

• Unitary Representation: The algorithm utilizes the Fibonacci unitary representation of braid generators ($\sigma_i^{\pm 1}$). This representation acts on a subspace of the $n$-qubit Hilbert space spanned by "Fibonacci strings" (bit strings without consecutive zeros). The dimension of this subspace scales as the $n$-th Fibonacci number ($\phi^n$), where $\phi$ is the golden ratio.
• Algorithmic Primitive (cfev): Instead of the standard Hadamard test, which requires controlled-unitary operations and incurs high gate overhead, the authors employ a control-free echo-verification (cfev) protocol. This protocol:
  • Uses a cat state $|\psi_{cat}\rangle = \frac{1}{\sqrt{2}}(|0\rangle^{\otimes n} + |s\rangle)$, where $|0\rangle^{\otimes n}$ is a known eigenstate of the braid unitary $U_B$.
  • Eliminates the need for controlled-$U$ gates, reducing the 2-qubit gate count significantly.
  • Employs an inverse circuit ($V_{cat}^\dagger$) at the end to verify that the system returned to the initial state, allowing for error detection.
• Error Mitigation:
  • Non-Fibonacci Error Detection: A post-processing function ($g_2$) discards measurement outcomes that fall outside the Fibonacci subspace, effectively filtering out certain hardware errors.
  • Conjugate Trick: To mitigate coherent phase errors (specifically memory errors on trapped-ion qubits), the algorithm is run on both the braid $B$ and its conjugate $B^*$ (where generators are inverted). Combining these results eliminates the global phase error without requiring additional shots.
• Classical Baselines: The authors develop and benchmark state-of-the-art classical algorithms for the same problem, including:
  • tn-proj: Direct tensor network contraction.
  • sv-shor: Statevector simulation exploiting the sparsity of the Fibonacci subspace.
  • mpo-proj: Matrix Product Operator (MPO) contraction with bond dimension compression.
  • bracket: A classical method based on the bracket polynomial (Kauffman).

Key Contributions

1. End-to-End Pipeline: A fully configurable pipeline that generates random braids, compiles them into optimized quantum circuits for specific hardware (Quantinuum H2), executes them, and performs classical pre- and post-processing.
2. Efficiently Verifiable Benchmark: Leveraging the topological invariance of the Jones polynomial, the authors construct a benchmark where a complex braid $B'$ (generated by conjugating a simple braid $B$ with a random braid $A$) is topologically equivalent to $B$. Since $VM(B)$ can be computed classically in negligible time, $VM(B')$ serves as a verifiable ground truth to measure quantum processor noise and error scaling.
3. Optimized Compilation: The authors provide optimized circuit decompositions for the Fibonacci unitary generators, reducing the 2-qubit gate count by approximately 15x compared to previous estimates for similar problems.
4. Resource Estimation Framework: A methodology to estimate the "time-to-solution" and energy consumption crossover points between quantum and classical approaches, accounting for noise models and classical hardware limits (e.g., A100 GPUs and the Frontier supercomputer).

Results

• Experimental Demonstration: The algorithm was executed on Quantinuum's H2-2 quantum computer for a 15-strand braid with 104 crossings (16 qubits, 340 2-qubit gates).
  • Without mitigation, the relative error was 75% with a 9% standard deviation.
  • Applying non-Fibonacci error detection and the conjugate trick reduced the relative error to 43% (though standard deviation increased to 14%).
• Scaling Analysis: Simulations on a dataset of 24,000 braids (10–15 strands, 50–600 crossings) with depolarizing noise models ($\epsilon_{2q} = 10^{-4}$ and $5 \cdot 10^{-4}$) revealed:
  • The relative error scales primarily with the number of crossings (gate count).
  • For $\epsilon_{2q} = 5 \cdot 10^{-4}$, the quantum error becomes so large that classical MPO approximations (mpo-proj) become faster for all tested sizes.
  • For $\epsilon_{2q} = 10^{-4}$, the quantum algorithm (cfev) is predicted to outperform the best classical method (mpo-proj) on the Frontier supercomputer for braid sizes with approximately 2,800 crossings.
• Energy Efficiency: The analysis suggests that for $\epsilon_{2q} = 10^{-4}$, the quantum approach becomes more energy-efficient than the classical mpo-proj method around 2,400 crossings, assuming a 75kW power draw for the quantum processor.

Significance and Claims
The paper claims to provide a practical, quantitative approach to identifying quantum advantage for a meaningful problem in computational topology, rather than relying on abstract complexity classes or unverified random circuit benchmarks.

• Modest Claims on Advantage: The authors explicitly state that their results provide a conservative estimate (a lower bound) for where quantum advantage is possible. They acknowledge that their benchmark braids have a specific structure and may not represent the "average case" or the "hardest" instances. However, they argue that if generic braids are at least as hard as their benchmark set, the identified crossover points represent a valid upper bound for where advantage might be observed for generic instances.
• Shift in Discourse: The work aims to shift the quantum advantage discussion from problem classes to specific problem instances, utilizing a rigorous, multidimensional optimization of error, time, and energy.
• Utility: The pipeline serves as a tool to characterize noise in quantum processors and to determine the minimum hardware specifications (qubit count, gate fidelity, depth) required to solve non-trivial instances of the Jones polynomial problem that are intractable for current classical supercomputers.

The authors conclude that while fault-tolerant regimes and further error correction are necessary for high-precision applications, their current noisy intermediate-scale quantum (NISQ) approach demonstrates a viable path toward identifying practical quantum utility in knot theory.