Quantum Algorithms and Mathematical Formulations of Biomolecular Solutions of the Vertex Cover Problem in the Finite-Dimensional Hilbert Space

Author

Weng-Long Chang ; Ting-Ting Ren ; Mang Feng

Author_Institution

Dept. of Comput. Sci. & Inf. Eng., Nat. Kaohsiung Univ. of Appl. Sci., Kaohsiung, Taiwan

Volume

14

Issue

1

fYear

2015

fDate

Jan. 2015

Firstpage

121

Lastpage

128

Abstract

In this paper, it is shown that the proposed quantum algorithm for implementing Boolean circuits generated from the DNA-based algorithm solving the vertex-cover problem of any graph G with m edges and n vertices is the optimal quantum algorithm. Next, it is also demonstrated that mathematical solutions of the same biomolecular solutions are represented in terms of a unit vector in the finite-dimensional Hilbert space. Furthermore, for testing our theory, a nuclear magnetic resonance (NMR) experiment of three quantum bits to solve the simplest vertex-cover problem is completed.

Keywords

Boolean functions; DNA; Hilbert spaces; biocomputing; molecular biophysics; multidimensional systems; nuclear magnetic resonance; quantum computing; vertex functions; Boolean circuit implementation; DNA-based algorithm-generated Boolean circuits; Hilbert space unit vector; NMR experiment; biomolecular solution mathematical formulation; biomolecular solution quantum algorithm; deoxyribonucleic acid; finite-dimensional Hilbert space; graph G m edges; graph G n vertices; graph G vertex-cover problem; optimal quantum algorithm; quantum bit nuclear magnetic resonance; vertex cover problem; vertex-cover problem biomolecular solution; DNA; Electron tubes; Law; Logic gates; Registers; Vectors; Data structure and algorithm; molecular algorithms; nuclear magnetic resonance; quantum algorithms;

fLanguage

English

Journal_Title

NanoBioscience, IEEE Transactions on

Publisher

ieee

ISSN

1536-1241

Type

jour

DOI

10.1109/TNB.2014.2375356

Filename

6977919