Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Chinese Journal of Computers

Improved Volume Molecular Solutions for the Maximum Clique Problem on DNA-Based Supercomputing

Kenli Li, Xu Zhou, Shuting Zou

Published Oct 16, 2009• 3 citations
Publisher
DOI
10.3724/sp.j.1016.2008.02173

Related papers

Molecular solutions to the binary integer programming problem based on DNA computation

Chung-Wei Yeh, Chih‐Ping Chu, Kee-Rong Wu

Biosystems•Oct 18, 2005•36 citations

Solving Large Maximum Clique Problems on a Quantum Annealer

Elijah Pelofske, Georg Hahn, Hristo N. Djidjev

arXiv:1901.07657•Lecture notes in computer science•Jan 1, 2019•42 citations

A Molecular Computing Model for Graph Coloring Problem Using DNA Quantum Dot

Jiawei Li, Zhichao Song, Cheng Zhang +3 more

Journal of Computational and Theoretical Nanoscience•Apr 24, 2015•1 citation

Improved molecular solutions for the N-QUEEN problem on DNA-based supercomputing

Fan Wu, Kenli Li

In this paper our main point is to give molecular solution to solve N-QUEEN problem. In order to achieve this, we take the divide and conquer strategy into the DNA-based supercomputing and propose DNA-based algorithm of an n-bit Parallel Searcher to formally verify our designed molecular solutions for the N-queen problem. The theoretical and experimental analysis shows that comparing with the exhaustive DNA-based algorithm for knapsack problem the algorithm not only shortened the length of the strands, but also reduced the DNA library strands from O(2q) to O(2q/2).

International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA)•Sep 1, 2010•2 citations

On molecular approximation algorithms for NP optimization problem

Bin Fu, Richard Beigel

DIMACS series in discrete mathematics and theoretical computer science•Apr 6, 1999•0 citations

Quantum Algorithms of Bio-molecular Solutions for the Clique Problem on a Quantum Computer

Weng-Long Chang, Ren, Ting-Ting, Mang Feng +4 more

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.

arXiv:0905.2028•May 13, 2009•0 citations
In this paper our main point is to give molecular solution to solve N-QUEEN problem. In order to achieve this, we take the divide and conquer strategy into the DNA-based supercomputing and propose DNA-based algorithm of an n-bit Parallel Searcher to formally verify our designed molecular solutions for the N-queen problem. The theoretical and experimental analysis shows that comparing with the exhaustive DNA-based algorithm for knapsack problem the algorithm not only shortened the length of the strands, but also reduced the DNA library strands from O(2q) to O(2q/2).
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.