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

Journal of Computational and Theoretical Nanoscience

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

Jiawei Li, Zhichao Song, Cheng Zhang, Jing Yang, H. Iñaki Schlaberg, Liu Shi

Published Apr 24, 2015• 1 citation
Publisher
DOI
10.1166/jctn.2015.3885

Related papers

Quantum Circuit Compilation for the Graph Coloring Problem

Angelo Oddi, Riccardo Rasconi, Marco Baioletti +2 more

Lecture notes in computer science•Jan 1, 2023•3 citations

Quantum annealing of the graph coloring problem

Olawale Titiloye, Alan J. Crispin

Discrete Optimization•Jan 8, 2011•114 citations

Exponential-Time Quantum Algorithms for Graph Coloring Problems

Kazuya Shimizu, Ryuhei Mori

Lecture notes in computer science•Jan 1, 2020•10 citations

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

Hierarchical quantum approximation optimization algorithm for solving graph-coloring problems

刘冬梅 Liu Dongmei, Jian Li, XIUBO CHEN +3 more

Physical Review A•Jan 26, 2026•3 citations

Quantum Speedup and Mathematical Solutions of Implementing Bio-Molecular Solutions for the Independent Set Problem on IBM Quantum Computers

Weng-Long Chang, Ju-Chin Chen, Wen‐Yu Chung +3 more

In this paper, we propose a bio-molecular algorithm with O( n2+ m) biological operations, O( 2n) DNA strands, O( n) tubes and the longest DNA strand, O( n), for solving the independent-set problem for any graph G with m edges and n vertices. Next, we show that a new kind of the straightforward Boolean circuit yielded from the bio-molecular solutions with m NAND gates, ( m +n × ( n + 1)) AND gates and (( n × ( n + 1))/2) NOT gates can find the maximal independent-set(s) to the independent-set problem for any graph G with m edges and n vertices. We show that a new kind of the proposed quantum-molecular algorithm can find the maximal independent set(s) with the lower bound Ω( 2n/2) queries and the upper bound O( 2n/2) queries. This work offers an obvious evidence for that to solve the independent-set problem in any graph G with m edges and n vertices, bio-molecular computers are able to generate a new kind of the straightforward Boolean circuit such that by means of implementing it quantum computers can give a quadratic speed-up. This work also offers one obvious evidence that quantum computers can significantly accelerate the speed and enhance the scalability of bio-molecular computers. Next, the element distinctness problem with input of n bits is to determine whether the given 2nreal numbers are distinct or not. The quantum lower bound of solving the element distinctness problem is Ω( 2n×(2/3)) queries in the case of a quantum walk algorithm. We further show that the proposed quantum-molecular algorithm reduces the quantum lower bound to Ω(( 2n/2)/( 21/2)) queries. Furthermore, to justify the feasibility of the proposed quantum-molecular algorithm, we successfully solve a typical independent set problem for a graph G with two vertices and one edge by carrying out experiments on the backend ibmqx4 with five quantum bits and the backend simulator with 32 quantum bits on IBM's quantum computer.

IEEE Transactions on NanoBioscience•Apr 26, 2021•24 citations
In this paper, we propose a bio-molecular algorithm with O( n2+ m) biological operations, O( 2n) DNA strands, O( n) tubes and the longest DNA strand, O( n), for solving the independent-set problem for any graph G with m edges and n vertices. Next, we show that a new kind of the straightforward Boolean circuit yielded from the bio-molecular solutions with m NAND gates, ( m +n × ( n + 1)) AND gates and (( n × ( n + 1))/2) NOT gates can find the maximal independent-set(s) to the independent-set problem for any graph G with m edges and n vertices. We show that a new kind of the proposed quantum-molecular algorithm can find the maximal independent set(s) with the lower bound Ω( 2n/2) queries and the upper bound O( 2n/2) queries. This work offers an obvious evidence for that to solve the independent-set problem in any graph G with m edges and n vertices, bio-molecular computers are able to generate a new kind of the straightforward Boolean circuit such that by means of implementing it quantum computers can give a quadratic speed-up. This work also offers one obvious evidence that quantum computers can significantly accelerate the speed and enhance the scalability of bio-molecular computers. Next, the element distinctness problem with input of n bits is to determine whether the given 2nreal numbers are distinct or not. The quantum lower bound of solving the element distinctness problem is Ω( 2n×(2/3)) queries in the case of a quantum walk algorithm. We further show that the proposed quantum-molecular algorithm reduces the quantum lower bound to Ω(( 2n/2)/( 21/2)) queries. Furthermore, to justify the feasibility of the proposed quantum-molecular algorithm, we successfully solve a typical independent set problem for a graph G with two vertices and one edge by carrying out experiments on the backend ibmqx4 with five quantum bits and the backend simulator with 32 quantum bits on IBM's quantum computer.