Transactions on

NanoBioscience

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 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.