Possible quantum algorithms for the Bollobás-Riordan-Tutte polynomial of a ribbon graph

Mario Vélez; Juan Ospina

doi:10.1117/12.777401

27 March 2008 Possible quantum algorithms for the Bollobas-Riordan-Tutte polynomial of a ribbon graph

Mario Vélez, Juan Ospina

Proceedings Volume 6976, Quantum Information and Computation VI; 69760O (2008) https://doi.org/10.1117/12.777401
Event: SPIE Defense and Security Symposium, 2008, Orlando, Florida, United States

Abstract

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.

Citation Download Citation

Mario Vélez and Juan Ospina "Possible quantum algorithms for the Bollobas-Riordan-Tutte polynomial of a ribbon graph", Proc. SPIE 6976, Quantum Information and Computation VI, 69760O (27 March 2008); https://doi.org/10.1117/12.777401

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available