Transactions on
NanoBioscience

Highlights
Dan has degrees in Chemical Engineering (PhD, MEng) and in Statistics, Cybernetics & Information Technology (MSc). His research covers biocomputation and biosimulation, nanodevices powered by protein molecular motors, surface science and engineering, micro- and nano-fabrication for semiconductor and biomedical devices, process modelling and control, and protein adsorption. Dan is a Professor of Bioengineering with McGill University, the Maria Zelenka-Roy Chair in Bioengineering, and the founding Chair of McGill’s Department of Bioengineering in the Faculty of Engineering. Dan authored more than 200 peer-reviewed publications, co-edited a book, and chaired more than 30 international conferences. He has been the Editor-in-Chief of the IEEE Transactions on NanoBioscience since January 1, 2020.
Email: dan.nicolau@mcgill.ca
Dan has degrees in Chemical Engineering (PhD, MEng) and in Statistics, Cybernetics & Information Technology (MSc). His research covers biocomputation and biosimulation, nanodevices powered by protein molecular motors, surface science and engineering, micro- and nano-fabrication for semiconductor and biomedical devices, process modelling and control, and protein adsorption. Dan is a Professor of Bioengineering with McGill University, the Maria Zelenka-Roy Chair in Bioengineering, and the founding Chair of McGill’s Department of Bioengineering in the Faculty of Engineering. Dan authored more than 200 peer-reviewed publications, co-edited a book, and chaired more than 30 international conferences. He has been the Editor-in-Chief of the IEEE Transactions on NanoBioscience since January 1, 2020.
Email: dan.nicolau@mcgill.ca
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 O(2n/2) queries and the upper bound Ω(2n/2) queries. This work offers an obvious evidence that to solve the independent-set problem in... Read 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 O(2n/2) queries and the upper bound Ω(2n/2) queries. This work offers an obvious evidence 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. Furthermore, to justify the feasibility of the proposed quantum-molecular algorithm, we successfully solve a typical independent set problem for a graph G with three vertices and two edges 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.
Read lessUpdates
NanoBioscience
VOLUME 20
NUMBER 2
ITMCEL

