27 March 2008 Possible quantum algorithms for the Bollobas-Riordan-Tutte polynomial of a ribbon graph
Author Affiliations +
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.
© (2008) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Mario Vélez, Mario Vélez, Juan Ospina, 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); doi: 10.1117/12.777401; https://doi.org/10.1117/12.777401
PROCEEDINGS
12 PAGES


SHARE
RELATED CONTENT

Topological quantum computing and the Jones polynomial
Proceedings of SPIE (May 11 2006)
Hawk-Dove-Bully-Retaliator quantum game CAS aided
Proceedings of SPIE (April 16 2010)
Is quantum parallelism real?
Proceedings of SPIE (April 02 2008)
Quantum advantage without entanglement
Proceedings of SPIE (September 14 2005)
Quantum algorithms for the Jones polynomial
Proceedings of SPIE (April 16 2010)

Back to Top