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

IEEE Transactions on NanoBioscience

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, Chun-Yuan Hsiao, Renata Wong, Athanasios V. Vasilakos

Published Apr 26, 2021• 24 citations
Publisher

Abstract

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.

DOI
10.1109/tnb.2021.3075733

Related papers

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

Weng-Long Chang, Wen-Yu Chung, Chun-Yuan Hsiao +4 more

In this paper, we propose a bio-molecular algorithm with O(${n}$2) biological operations, O($2^{n-1}$) 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^{n}$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^{{\textit {n-1}}}$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. We also show that using an extension of the quantum phase estimation and quantum counting algorithms computes its unitary operator and eigenvalues from bio-molecular solution space with$2^{{\textit {n-1}}}$DNA strands. Next, we demonstrate that the value of each bit of the output solution can be determined by executing the proposed extended quantum algorithms${n}$times. To verify our theorem, we find the maximum-sized clique to a graph with two vertices and one edge and the solution${b}$that satisfies${b}^{2} \equiv 1$(mod 15) and$1 < {b} < (15/2)$using IBM Quantum’s backend.

IEEE Transactions on NanoBioscience•Nov 25, 2021•14 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

Quantum Algorithms and Mathematical Representation of Bio-molecular Solutions for the Clique Problem in a Finite-dimensional Hilbert Space

Weng-Long Chang, Ting-Ting Ren, Mang Feng +6 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 q edges and its complementary graph = (V, ) with n vertices and m = (((n * (n - 1)) / 2) - q) edges can be implemented by Hadamard gates, NOT gates, CNOT gates, CCNOT gates, Grover's operators, and quantum measurements on a quantum computer.

International Conference on Computational Aspects of Social Networks (CASoN)•Sep 1, 2010•0 citations

Quantum algorithms for bio-molecular solutions to the satisfiability problem on a quantum computer

Weng-Long Chang, Ting-Ting Ren, Jun Luo +2 more

We demonstrate that the logic computation performed by the DNA-based algorithm for solving general cases of the satisfiability problem can be implemented by our proposed quantum algorithm on the quantum machine proposed by Deutsch. Moreover, we also prove that the logic computation by the bio-molecular operations proposed by Adleman can be implemented by quantum gates (for example, the Hadamard gate, NOT, CNOT, and CCNOT) on the quantum machine. Furthermore, those NP-complete problems solved on a bio-molecular computer are also solvable on a quantum computer. To test our theory, we carry out a three-qubit NMR experiment for solving the simplest satisfiability problem.

IEEE Congress on Evolutionary Computation (CEC)•Jun 1, 2008•0 citations

Quantum speedup in solving the maximal-clique problem

Weng-Long Chang, Qi Yu, Zhaokai Li +3 more

The maximal-clique problem, to find the maximally sized clique in a given graph, is classically an NP-complete computational problem, which has potential applications ranging from electrical engineering, computational chemistry, and bioinformatics to social networks. Here we develop a quantum algorithm to solve the maximal-clique problem for any graph $G$ with $n$ vertices with quadratic speedup over its classical counterparts, where the time and spatial complexities are reduced to, respectively, $O(\sqrt{{2}^{n}})$ and $O({n}^{2})$. With respect to oracle-related quantum algorithms for the NP-complete problems, we identify our algorithm as optimal. To justify the feasibility of the proposed quantum algorithm, we successfully solve a typical clique problem for a graph $G$ with two vertices and one edge by carrying out a nuclear magnetic resonance experiment involving four qubits.

arXiv:1803.11356•Physical Review A•Mar 29, 2018•17 citations

Quantum Algorithms and Mathematical Formulations of Biomolecular Solutions of the Vertex Cover Problem in the Finite-Dimensional Hilbert Space

Weng-Long Chang, Ting-Ting Ren, Mang Feng

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.

IEEE Transactions on NanoBioscience•Dec 6, 2014•25 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.
In this paper, we propose a bio-molecular algorithm with O(${n}$2) biological operations, O(2n−12^{n-1}2n−1) DNA strands, O(n{n}n) tubes and the longest DNA strand, O(n{n}n), for inferring the value of a bit from the only output satisfying any given condition in an unsorted database with2n2^{n}2nitems ofn{n}nbits. We show that the value of each bit of the outcome is determined by executing our bio-molecular algorithmn{n}ntimes. Then, we show how to view a bio-molecular solution space with2n-12^{{\textit {n-1}}}2n-1DNA strands as an eigenvector and how to find the corresponding unitary operator and eigenvalues for inferring the value of a bit in the output. We also show that using an extension of the quantum phase estimation and quantum counting algorithms computes its unitary operator and eigenvalues from bio-molecular solution space with2n-12^{{\textit {n-1}}}2n-1DNA strands. Next, we demonstrate that the value of each bit of the output solution can be determined by executing the proposed extended quantum algorithmsn{n}ntimes. To verify our theorem, we find the maximum-sized clique to a graph with two vertices and one edge and the solutionb{b}bthat satisfiesb2≡1{b}^{2} \equiv 1b2≡1(mod 15) and1<b<(15/2)1 < {b} < (15/2)1<b<(15/2)using IBM Quantum’s backend.
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.
We demonstrate that the logic computation performed by the DNA-based algorithm for solving general cases of the satisfiability problem can be implemented by our proposed quantum algorithm on the quantum machine proposed by Deutsch. Moreover, we also prove that the logic computation by the bio-molecular operations proposed by Adleman can be implemented by quantum gates (for example, the Hadamard gate, NOT, CNOT, and CCNOT) on the quantum machine. Furthermore, those NP-complete problems solved on a bio-molecular computer are also solvable on a quantum computer. To test our theory, we carry out a three-qubit NMR experiment for solving the simplest satisfiability problem.
The maximal-clique problem, to find the maximally sized clique in a given graph, is classically an NP-complete computational problem, which has potential applications ranging from electrical engineering, computational chemistry, and bioinformatics to social networks. Here we develop a quantum algorithm to solve the maximal-clique problem for any graph GGG with nnn vertices with quadratic speedup over its classical counterparts, where the time and spatial complexities are reduced to, respectively, O(2n)O(\sqrt{{2}^{n}})O(2n​) and O(n2)O({n}^{2})O(n2). With respect to oracle-related quantum algorithms for the NP-complete problems, we identify our algorithm as optimal. To justify the feasibility of the proposed quantum algorithm, we successfully solve a typical clique problem for a graph GGG with two vertices and one edge by carrying out a nuclear magnetic resonance experiment involving four qubits.
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.