Efficient quantum circuits for approximating the Jones polynomial

Yumi Nakajima, Yasuhito Kawano, Hiroshi Sekigawa

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

Freedman, Kitaev, and Wang proved the equivalence between quantum field theory and quantum computation, and consequently showed that the problem of approximating the Jones polynomial (a knot invariant) at the fifth root of unity is BQP-complete. Recently, Aharonov, Jones, and Landau proposed a concrete quantum algorithm, called the AJL algorithm, that approximates the Jones polynomial at the kth root of unity in polynomial time. In this paper, we propose a new method for implementing the AJL algorithm, which improves the performance from O(mnlog2 k) to O(mn). Here, n is the number of strands, m is the number of the crossings in a braid. Since, in the AJL algorithm, m and k are assumed to be given as polynomials in n, the difference in the performance between the original implementation and our design is significant if k is a large-degree polynomial.

Original languageEnglish
Pages (from-to)489-500
Number of pages12
JournalQuantum Information and Computation
Volume8
Issue number5
Publication statusPublished - 1 May 2008

Keywords

  • Jones polynomial approximation
  • Quantum circuit
  • The Aharonov-Jones- Landau (AJL) algorithm

Fingerprint Dive into the research topics of 'Efficient quantum circuits for approximating the Jones polynomial'. Together they form a unique fingerprint.

  • Cite this