Bioinspired Quantum Oracle Circuits for Biomolecular Solutions of the Maximum Cut Problem.

Given an undirected, unweighted graph with n vertices and m edges, the maximum cut problem is to find a partition of the n vertices into disjoint subsets V and V such that the number of edges between them is as large as possible. Classically, it is an NP-complete problem, which has potential applications ranging from circuit layout design, statistical physics, computer vision, machine learning and network science to clustering. In this paper, we propose a biomolecular and a quantum algorithm to solve the maximum cut problem for any graph G.

Biomolecular and quantum algorithms for the dominating set problem in arbitrary networks.

A dominating set of a graph [Formula: see text] is a subset U of its vertices V, such that any vertex of G is either in U, or has a neighbor in U. The dominating-set problem is to find a minimum dominating set in G. Dominating sets are of critical importance for various types of networks/graphs, and find therefore potential applications in many fields.

Quantum Speedup for Inferring the Value of Each Bit of a Solution State in Unsorted Databases Using a Bio-Molecular Algorithm on IBM Quantum's Computers.

In this paper, we propose a bio-molecular algorithm with O( n ) biological operations, O( 2 ) DNA strands, O( n ) tubes and the longest DNA strand, O( n ), for inferring the value of a bit from the only output satisfying any given condition in an unsorted database with 2 items of n bits. We show that the value of each bit of the outcome is determined by executing our bio-molecular algorithm n times. Then, we show how to view a bio-molecular solution space with 2 DNA strands as an eigenvector and how to find the corresponding unitary operator and eigenvalues for inferring the value of a bit in the output.

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

In this paper, we propose a bio-molecular algorithm with O( n + m ) biological operations, O( 2 ) 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 Ω ( 2 ) queries and the upper bound O( 2 ) queries.

Quantum Speedup for Protein Structure Prediction.

Protein structure prediction (PSP) predicts the native conformation for a given protein sequence. Classically, the problem has been shown to belong to the NP-complete complexity class. Its applications range from physics, through bioinformatics to medicine and quantum biology.

The DNA-Based Algorithms of Implementing Arithmetical Operations of Complex Vectors on a Biological Computer.

Here we show that arithmetical operations of complex vectors can be implemented by means of the proposed DNA-based algorithms.

Quantum algorithms and mathematical formulations of biomolecular solutions of the vertex cover problem in the finite-dimensional hilbert space.

In this paper, it is shown that the proposed quantum algorithm for implementing Boolean circuits generated from the DNA-based algorithm solving the vertex-cover problem of any graph G with m edges and n vertices is the optimal quantum algorithm. Next, it is also demonstrated that mathematical solutions of the same biomolecular solutions are represented in terms of a unit vector in the finite-dimensional Hilbert space. Furthermore, for testing our theory, a nuclear magnetic resonance (NMR) experiment of three quantum bits to solve the simplest vertex-cover problem is completed.

DNA algorithms of implementing biomolecular databases on a biological computer.

In this paper, DNA algorithms are proposed to perform eight operations of relational algebra (calculus), which include Cartesian product, union, set difference, selection, projection, intersection, join, and division, on biomolecular relational databases.

Fast parallel DNA-based algorithms for molecular computation: quadratic congruence and factoring integers.

Assume that n is a positive integer. If there is an integer such that M (2) ≡ C (mod n), i.e.

Quantum algorithms for biomolecular solutions of the satisfiability problem on a quantum machine.

In this paper, we demonstrate that the logic computation performed by the DNA-based algorithm for solving general cases of the satisfiability problem can be implemented more efficiently by our proposed quantum algorithm on the quantum machine proposed by Deutsch. To test our theory, we carry out a three-quantum bit nuclear magnetic resonance experiment for solving the simplest satisfiability problem.

Fast parallel DNA-based algorithms for molecular computation: the set-partition problem.

This paper demonstrates that basic biological operations can be used to solve the set-partition problem. In order to achieve this, we propose three DNA-based algorithms, a signed parallel adder, a signed parallel subtractor and a signed parallel comparator, that formally verify our designed molecular solutions for solving the set-partition problem.

Fast parallel molecular algorithms for DNA-based computation: factoring integers.

The RSA public-key cryptosystem is an algorithm that converts input data to an unrecognizable encryption and converts the unrecognizable data back into its original decryption form. The security of the RSA public-key cryptosystem is based on the difficulty of factoring the product of two large prime numbers. This paper demonstrates to factor the product of two large prime numbers, and is a breakthrough in basic biological operations using a molecular computer.

Is optimal solution of every NP-complete or NP-hard problem determined from its characteristic for DNA-based computing.

Cook's Theorem [Cormen, T.H., Leiserson, C.

Molecular solutions for the subset-sum problem on DNA-based supercomputing.

In this paper our main purpose is to give molecular solutions for the subset-sum problem. In order to achieve this, we propose a DNA-based algorithm of an n-bit parallel adder and a DNA-based algorithm of an n-bit parallel comparator to formally verify our designed molecular solutions for the subset-sum problem.

Solving the set cover problem and the problem of exact cover by 3-sets in the Adleman-Lipton model.

Adleman wrote the first paper in which it is shown that deoxyribonucleic acid (DNA) strands could be employed towards calculating solutions to an instance of the NP-complete Hamiltonian path problem (HPP). Lipton also demonstrated that Adleman's techniques could be used to solve the NP-complete satisfiability (SAT) problem (the first NP-complete problem). In this paper, it is proved how the DNA operations presented by Adleman and Lipton can be used for developing DNA algorithms to resolving the set cover problem and the problem of exact cover by 3-sets.