Paper Info
Title
Quantum Algorithms of Bio-molecular Solutions for the Clique Problem on a Quantum Computer
Abstract
In this paper, it is demonstrated that the DNA-based algorithm [Ho et al. 2005] for solving an instance of the clique problem to any a graph G = (V, E) with n vertices and p edges and its complementary graph G1 = (V, E1) with n vertices and m = (((n*(n-1))/2)-p) edges can be implemented by Hadamard gates, NOT gates, CNOT gates, CCNOT gates, Grover's operators, and quantum measurements on a quantum computer. It is also demonstrated that if Grovers algorithm is employed to accomplish the readout step in the DNA-based algorithm, the quantum implementation of the DNA-based algorithm is equivalent to the oracle work (in the language of Grover's algorithm), that is, the target state labeling preceding Grover,s searching steps. It is shown that one oracle work can be completed with O((2 * n) * (n + 1) * (n + 2) / 3) NOT gates, one CNOT gate and O((4 * m) + (((2 * n) * (n + 1) * (n + 14)) / 6)) CCNOT gates. This is to say that for the quantum implementation of the DNA-based algorithm [Ho et al. 2005] a faster labeling of the target state is attained, which also implies a speedy solution to an instance of the clique problem.
Year
Venue
Keywords
2009
Clinical Orthopaedics and Related Research
quantum algorithm,grover s algorithm,quantum computer,data structure
Field
DocType
Volume
Quantum circuit,Discrete mathematics,Combinatorics,Amplitude amplification,Controlled NOT gate,Quantum computer,Quantum Fourier transform,Quantum algorithm,Grover's algorithm,Mathematics,Clique problem
Journal
abs/0905.2
Citations 
PageRank 
References 
0
0.34
0
Authors
7
Name
Order
Citations
PageRank
Weng-long Chang113618.80
Ting-ting Ren231.75
Mang Feng322.76
Jun Luo401.01
Kawuu Weicheng Lin5344.36
Minyi Guo63969332.25
Lai Chin Lu781.54