Three possible quantum algorithms, for the computation of the Bollobás-Riordan-Tutte polynomial of a given ribbon graph, are presented and discussed. The first possible algorithm is based on the spanning quasi-trees expansion for generalized Tutte polynomials of generalized graphs and on a quantum version of the Binary Decision Diagram (BDD) for quasi-trees . The second possible algorithm is based on the relation between the Kauffman bracket and the Tutte polynomial; and with an application of the recently introduced Aharonov-Arad-Eban-Landau quantum algorithm. The third possible algorithm is based on the relation between the HOMFLY polynomial and the Tutte polynomial; and with an application of the Wocjan-Yard quantum algorithm. It is claimed that these possible algorithms may be more efficient that the best known classical algorithms. These three algorithms may have interesting applications in computer science at general or in computational biology and bio-informatics in particular. A line for future research based on the categorification project is mentioned.
Three possible quantum algorithms, for the computation of the Bollobás-Riordan-Tutte polynomial of a given ribbon graph, are presented and discussed. The first possible algorithm is based on the spanning quasi-trees expansion for generalized Tutte polynomials of generalized graphs and on a quantum version of the Binary Decision Diagram (BDD) for quasi-trees . The second possible algorithm is based on the relation between the Kauffman bracket and the Tutte polynomial; and with an application of the recently introduced Aharonov-Arad-Eban-Landau quantum algorithm. The third possible algorithm is based on the relation between the HOMFLY polynomial and the Tutte polynomial; and with an application of the Wocjan-Yard quantum algorithm. It is claimed that these possible algorithms may be more efficient that the best known classical algorithms. These three algorithms may have interesting applications in computer science at general or in computational biology and bio-informatics in particular. A line for future research based on the categorification project is mentioned.
Recently a quantum algorithm for the Jones polynomial of virtual links was proposed by Kauffman and Dye via the implementation of the virtual braid group in anyonic topological quantum computation when the virtual crossings are considered as generalized swap gates. Also recently, a mathematical method for the computation of the Jones polynomial of a given virtual link in terms of the relative Tuttle polynomial of its face (Tait) graph with some suitable variable substitutions was proposed by Diao and Hetyei. The method of Diao and Hetyei is offered as an alternative to the ribbon graph approach according to which the Tutte polynomial of a given virtual link is computed in terms of the Bollobás- Riordan polynomial of the corresponding ribbon graph. The method of Diao and Hetyei can be considered as an extension of the celebrated Thistlethwaite theorem according to which invariant polynomials for knots and links are derived from invariant polynomials for graphs. Starting from these ideas we propose a quantum algorithm for the Jones polynomial of a given virtual link in terms of the generalized Tutte polynomials by exploiting the Thistlethwaite theorem and the Kauffman algorithm . Our method is claimed as the quantum version of the Diao-Hetyei method. Possible supersymmetric implementations of our algortihm are discussed jointly with its formulations using topological quantum lambda calculus.
Possible quantum algorithms for generalized Khovanov homology and the Rasmussen's invariant are proposed. Such algorithms are resulting from adaptations of the recently proposed Kauffman's algorithm for the standard Khovanov homology. The method that was applied consists in to write the relevant quantum invariant as the trace of a certain unitary operator and then to compute the trace using the Hadamard test. We apply such method to the quantum computation of the Jones polynomial, HOMFLY polynomial, Chromatic polynomial, Tutte polynomial and Bollobàs- Riordan polynomial. These polynomials are quantum topological invariants for knots, links, graphs and ribbon graphs respectively. The Jones polynomial is categorified by the standard Khovanov homology and the others polynomials are categorified by generalized Khovanov homologies, such as the Khovanov-Rozansky homology and the graph homologies. The algorithm for the Rasmussen's invariant is obtained using the gauge theory; and the recently introduced program of homotopyfication is linked with the super-symmetric quantum mechanics. It is claimed that a new program of analytification could be development from the homotopyfication using the celebrated Atiyah-Singer theorem and its super-symmetric interpretations. It is hoped that the super-symmetric quantum mechanics provides the hardware for the implementation of the proposed quantum algorithms.
In this dissertation, we investigate three different problems in the field of Quantum computation. First, we discuss the quantum complexity of evaluating the Tutte polynomial of a planar graph. Furthermore, we devise a new quantum algorithm for approximating the phase of a unitary matrix. Finally, we provide quantum tools that can be utilized to extract the structure of black-box modules and algebras. While quantum phase estimation (QPE) is at the core of many quantum algorithms known to date, its physical implementation (algorithms based on quantum Fourier transform (QFT) ) is highly constrained by the requirement of high-precision controlled phase shift operators, which remain difficult to realize. In the second part of this dissertation, we introduce an alternative approach to approximately implement QPE with arbitrary constantprecision controlled phase shift operators. The new quantum algorithm bridges the gap between QPE algorithms based on QFT and Kitaev’s original approach. For approximating the eigenphase precise to the nth bit, Kitaev’s original approach does not require any controlled phase shift operator. In contrast, QPE algorithms based on QFT or approximate QFT require controlled phase shift operators with precision of at least Pi/2n. The new approach fills the gap and requires only arbitrary constant-precision controlled phase shift operators. From a physical implementation viewpoint, the new algorithm outperforms Kitaev’s approach. iii The other problem we investigate relates to approximating the Tutte polynomial. We show that the problem of approximately evaluating the Tutte polynomial of triangular graphs at the points (q, 1/q) of the Tutte plane is BQP-complete for (most) roots of unity q. We also consider circular graphs and show that the problem of approximately evaluating the Tutte polynomial of these graphs at the point (e 2πi/5 ,e−2πi/5 ) is DQC1-complete and at points (q k , 1 + 1−q−k (q 1/2−q−1/2) 2 ) for some integer k is in BQP. To show that these problems can be solved by a quantum computer, we rely on the relation of the Tutte polynomial of a planar G graph with the Jones and HOMFLY polynomial of the alternating link D(G) given by the medial graph of G. In the case of our graphs the corresponding links are equal to the plat and trace closures of braids. It is known how to evaluate the Jones and HOMFLY polynomial for closures of braids. To establish the hardness results, we use the property that the images of the generators of the braid group under the irreducible Jones-Wenzl representations of the Hecke algebra have finite order. We show that for each braid b we can efficiently construct a braid ˜b such that the evaluation of the Jones and HOMFLY polynomials of their closures at a fixed root of unity leads to the same value and that the closures of ˜b are alternating links. The final part of the dissertation focuses on finding the structure of a black-box module or algebra. Suppose we are given black-box access to a finite module M or algebra over a finite ring R, and a list of generators for M and R. We show how to find a linear basis and structure constants for M in quantum poly(log |M|) time. This generalizes a recent quantum algorithm of Arvind et al. which finds a basis representation for rings. We then show that iv our algorithm is a useful primitive allowing quantum computers to determine the structure of a finite associative algebra as a direct sum of simple algebras. Moreover, it solves a wide variety of problems regarding finite modules and rings. Although our quantum algorithm is based on Abelian Fourier transforms, it solves problems regarding the multiplicative structure of modules and algebras, which need not be commutative. Examples include finding the intersection and quotient of two modules, finding the additive and multiplicative identities in a module, computing the order of an module, solving linear equations over modules, deciding whether an ideal is maximal, finding annihilators, and testing the injectivity and surjectivity of ring homomorphisms. These problems appear to be exponentially hard classically.
We show that the problem of approximately evaluating the Tutte polynomial of triangular graphs at the points (q, 1/q) of the Tutte plane is BQP-complete for (most) roots of unity q. We also consider circular graphs and show that the problem of approximately evaluating the Tutte polynomial of these graphs at the point (e2πi/5, e-2πi/5) is DQC1-complete and at points [Formula: see text] for some integer k is in BQP. To show that these problems can be solved by a quantum computer, we rely on the relation of the Tutte polynomial of a planar G graph with the Jones and HOMFLY polynomial of the alternating link D(G) given by the medial graph of G. In the case of our graphs the corresponding links are equal to the plat and trace closures of braids. It is known how to evaluate the Jones and HOMFLY polynomial for closures of braids. To establish the hardness results, we use the property that the images of the generators of the braid group under the irreducible Jones–Wenzl representations of the Hecke algebra have finite order. We show that for each braid b we can efficiently construct a braid [Formula: see text] such that the evaluation of the Jones and HOMFLY polynomials of their closures at a fixed root of unity leads to the same value and that the closures of [Formula: see text] are alternating links.
An emergent trend in quantum computation is the topological quantum computation (TQC). Briefly, TQC results from the application of quantum computation with the aim to solve the problems of quantum topology such as topological invariants for knots and links (Jones polynomials, HOMFLY polynomials, Khovanov polynomials); topological invariants for graphs (Tutte polynomial and Bollobás-Riordan polynomial); topological invariants for 3-manifolds (Reshetiskin-Turaev, Turaev-Viro and Turaer-Viro-Ocneanu invariants) and topological invariants for 4-manifolds( Crane-Yetter invariants). In a few words, TQC is concerned with the formulation of quantum algorithms for the computation of these topological invariants in quantum topology. Given that one of the fundamental achievements of quantum topology was the discovery of strong connections between monoidal categories and 3-dimensional manifolds, in TQC is possible and necessary to exploit such connections with the purpose to formulate universal quantum algorithms for topological invariants of 3-manifolds. In the present work we make an exploration of such possibilities. Specifically we search for universal quantum algorithms for generalized Turaev-Viro invariants of 3-manifolds such as the Turaev-Viro-Ocneanu invariants, the Kashaev-Baseilhac-Benedetti invariants of 3-manifolds with links and the Geer-Kashaev-Turaev invariants of 3-manifolds with a link and a principal bundle. We also look for physical systems (three dimensional topological insulators and three-dimensional gravity) over which implement the resulting universal topological quantum algorithms.
A model of a D-Brane Topological Quantum Computer (DBTQC) is presented and sustained. The model is based on four-dimensional TQFTs of the Donaldson-Witten and Seiber-Witten kinds. It is argued that the DBTQC is able to compute Khovanov homology for knots, links and graphs. The DBTQC physically incorporates the mathematical process of categorification according to which the invariant polynomials for knots, links and graphs such as Jones, HOMFLY, Tutte and Bollobás-Riordan polynomials can be computed as the Euler characteristics corresponding to special homology complexes associated with knots, links and graphs. The DBTQC is conjectured as a powerful universal quantum computer in the sense that the DBTQC computes Khovanov homology which is considered like powerful that the Jones polynomial.