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

Published Dec 6, 2014• 25 citations
Publisher

Abstract

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.

DOI
10.1109/tnb.2014.2375356

Related papers

Quantum Algorithms of the Vertex Cover Problem on a Quantum Computer

Weng-Long Chang, Ting-Ting Ren, Mang Feng +4 more

In this paper, it is demonstrated that solving an instance of the vertex cover problem of any graph G with m edges and n vertices can be implemented by Hadamard gates, NOT gates, CNOT gates, CCNOT gates, Grover's operators, and quantum measurements on a quantum computer. To test our theory, an NMR (nuclear magnetic resonance) experiment for the simplest vertex-cover problem is also performed.

WASE International Conference on Information Engineering•Jul 1, 2009•3 citations

Quantum Algorithms for Biomolecular Solutions of the Satisfiability Problem on a Quantum Machine

Weng-Long Chang, Ting-Ting Ren, J. L. Luo +3 more

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.

IEEE Transactions on NanoBioscience•Sep 1, 2008•21 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

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

Renata Wong, Weng-Long Chang, Wen‐Yu Chung +1 more

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. Particularly, in the area of communication, dominating sets are prominently used in the efficient organization of large-scale wireless ad hoc and sensor networks. However, the dominating set problem is also a hard optimization problem and thus currently is not efficiently solvable on classical computers. Here, we propose a biomolecular and a quantum algorithm for this problem, where the quantum algorithm provides a quadratic speedup over any classical algorithm. We show that the dominating set problem can be solved in [Formula: see text] queries by our proposed quantum algorithm, where n is the number of vertices in G. We also demonstrate that our quantum algorithm is the best known procedure to date for this problem. We confirm the correctness of our algorithm by executing it on IBM Quantum's qasm simulator and the Brooklyn superconducting quantum device. And lastly, we show that molecular solutions obtained from solving the dominating set problem are represented in terms of a unit vector in a finite-dimensional Hilbert space.

Scientific Reports•Mar 14, 2023•9 citations

Quantum Algorithms and Mathematical Representation of Bio-molecular Solutions for the Hitting-set Problem on a Quantum Computer

Weng-Long Chang, Ting-Ting Ren, Mang Feng +6 more

In this paper, it is demonstrated that quantum implementation of bio-molecular solutions to compute the number of elements in each hitting-set in an instance of the hitting-set problem could be considered as the oracle work in Grover's algorithm, i.e., the target state labeling, preceding Grover's searching steps. Finally, for testing our theory, a three-qubit nuclear magnetic resonance (NMR) experiment of solving the simplest hitting-set problem is performed.

International Conference on Computational Aspects of Social Networks (CASoN)•Sep 1, 2010•0 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, 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.
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. Particularly, in the area of communication, dominating sets are prominently used in the efficient organization of large-scale wireless ad hoc and sensor networks. However, the dominating set problem is also a hard optimization problem and thus currently is not efficiently solvable on classical computers. Here, we propose a biomolecular and a quantum algorithm for this problem, where the quantum algorithm provides a quadratic speedup over any classical algorithm. We show that the dominating set problem can be solved in [Formula: see text] queries by our proposed quantum algorithm, where n is the number of vertices in G. We also demonstrate that our quantum algorithm is the best known procedure to date for this problem. We confirm the correctness of our algorithm by executing it on IBM Quantum's qasm simulator and the Brooklyn superconducting quantum device. And lastly, we show that molecular solutions obtained from solving the dominating set problem are represented in terms of a unit vector in a finite-dimensional Hilbert space.
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.