检索结果-内蒙古大学图书馆

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

学校读者我要写书评

暂无评论

IEEE TRANSACTIONS ON NANOBIOSCIENCE 2022年第2期21卷 286-293页

作者： Chang, Weng-Long Chung, Wen-Yu Hsiao, Chun-Yuan Wong, Renata Chen, Ju-Chin Feng, Mang Vasilakos, Athanasios V. Natl Kaohsiung Univ Sci & Technol Dept Comp Sci & Informat Engn Kaohsiung 80778 Taiwan Natl Ctr Theoret Sci Div Phys Taipei 10617 Taiwan Chinese Acad Sci Wuhan Inst Phys & Math Wuhan 430071 Peoples R China Guangzhou Inst Ind Technol Res Ctr Quantum Precis Measurement Guangzhou 511458 Peoples R China Fuzhou Univ Coll Math & Comp Sci Fuzhou 350116 Peoples R China

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(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-molecularsolution space with 2(n-1 )DNA strands. Next, we demonstratethat 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) 1 (mod 15) and 1 < b < (15/2) using IBM Quantum's backend.

关键词： Data structures and algorithms molecular algorithms quantum algorithms NP-complete problems

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

学校读者我要写书评

暂无评论

IEEE TRANSACTIONS ON NANOBIOSCIENCE 2015年第1期14卷 121-128页

作者： Chang, Weng-Long Ren, Ting-Ting Feng, Mang Natl Kaohsiung Univ Appl Sci Dept Comp Sci & Informat Engn Kaohsiung 807 Taiwan Chinese Acad Sci Wuhan Inst Phys & Math Wuhan 430071 Peoples R China

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.

关键词： Data structure and algorithm quantum algorithms molecular algorithms nuclear magnetic resonance

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

学校读者我要写书评

暂无评论

IEEE TRANSACTIONS ON NANOBIOSCIENCE 2021年第3期20卷 354-376页

作者： Chang, Weng-Long Chen, Ju-Chin Chung, Wen-Yu Hsiao, Chun-Yuan Wong, Renata Vasilakos, Athanasios V. Natl Kaohsiung Univ Sci & Technol Dept Comp Sci & Informat Engn Kaohsiung 80778 Taiwan Nanjing Univ Dept Comp Sci & Technol Nanjing 210023 Peoples R China Univ Technol Sydney Sch Elect & Data Engn Ultimo NSW 2007 Australia Fuzhou Univ Coll Math & Comp Sci Fuzhou 350116 Peoples R China Lulea Univ Technol Dept Comp Sci Elect & Space Engn S-97187 Lulea Sweden

In this paper, we propose a bio-molecular algorithm with O(n(2) + m) biological operations, O(2(n)) 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 x(n + 1)) AND gates and ((n x (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 Omega(2(n/2)) queries and the upper bound O(2(n/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 2(n) real numbers are distinct or not. The quantum lower bound of solving the element distinctness problem is Omega(2(nx(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 Omega((2(n/2))/(2(1/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.

关键词： Electron tubes DNA Computer science Quantum computing Computers Roads Urban areas Data structures and algorithms independent-set problem molecular algorithms molecular computing quantum algorithms quantum computing

Fast quantum algorithm for protein structure prediction in hydrophobic-hydrophilic model

学校读者我要写书评

暂无评论

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2022年第0期164卷 178-190页

作者： Wong, Renata Chang, Weng-Long Nanjing Univ Dept Comp Sci & Technol Nanjing Peoples R China Natl Ctr Theoret Sci Phys Div Taipei Taiwan Natl Kaohsiung Univ Sci & Technol Dept Comp Sci & Informat Engn Kaohsiung Taiwan

In its unfolded form, a protein is a linear sequence of amino acids. Protein structure prediction attempts to find the native conformation for a given protein, which has potential applications in drug and vaccine development. Classically, protein structure prediction is an NP-complete, unsolved computational problem. Quantum computing however promises to improve upon the performance of classical algorithms. Here we develop a quantum algorithm in hydrophobic-hydrophilic model on two-dimensional square lattice to solve the problem for any sequence of length N amino acids with a quadratic speedup over its classical counterpart. This speedup is achieved using Grover's quantum search algorithm. The algorithm can be used for amino acid sequences of arbitrary length. It consists of three stages: (1) preparation of a superposition state that encodes all possible 2(2(N-1)) conformations, (2) calculation of coordinates and energy for each possible conformation in parallel, and (3) finding the conformation with the minimal energy. The asymptotic complexity with regard to space is O(N-3), while the obtained speedup is quadratic compared to the classical counterpart. We have successfully simulated the algorithm on the IBM Quantum's qasm simulator using Qiskit SDK. Also, we have further confirmed the correctness of the results by calculating theoretical probability of finding the right conformation. (C) 2022 Elsevier Inc. All rights reserved.

关键词： molecular algorithms NP-complete problems Protein structure prediction Quantum algorithms

Quantum Speedup for Protein Structure Prediction

学校读者我要写书评

暂无评论

IEEE TRANSACTIONS ON NANOBIOSCIENCE 2021年第3期20卷 323-330页

作者： Wong, Renata Chang, Weng-Long Nanjing Univ Dept Comp Sci & Technol Nanjing 210023 Peoples R China Natl Kaohsiung Univ Sci & Technol Dept Comp Sci & Informat Engn Kaohsiung 80778 Taiwan

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. It is possible however to speed it up with quantum computational methods, as we show in this paper. Here we develop a fast quantum algorithm for PSP in three-dimensional hydrophobic-hydrophilic model on body-centered cubic lattice with quadratic speedup over its classical counterparts. Given a protein sequence of n amino acids, our algorithm reduces the temporal and spatial complexities to, respectively, O(2(n/2)) and O(n(2) log n). 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 algorithm we successfully solve the problem on IBM quantum simulator involving 21 and 25 qubits. We confirm the experimentally obtained high probability of success in finding the desired conformation by calculating the theoretical probability estimations.

关键词： Amino acids Lattices Qubit Quantum computing Quantum algorithm Prediction algorithms Computational modeling molecular algorithms NP-complete problems protein structure prediction quantum algorithms quantum simulation quantum speedup quantum biology

molecular learning with DNA kernel machines

学校读者我要写书评

暂无评论

BIOSYSTEMS 2015年 137卷 73-83页

作者： Noh, Yung-Kyun Lee, Daniel D. Yang, Kyung-Ae Kim, Cheongtag Zhang, Byoung-Tak Seoul Natl Univ Dept Mech & Aerosp Engn Seoul 151 South Korea Univ Penn Dept Elect & Syst Engn Philadelphia PA 19104 USA Columbia Univ Dept Med New York NY 10027 USA Seoul Natl Univ Dept Psychol Seoul 151 South Korea Seoul Natl Univ Sch Comp Sci & Engn Seoul 151 South Korea

We present a computational learning method for bio-molecular classification. This method shows how to design biochemical operations both for learning and pattern classification. As opposed to prior work, our molecular algorithm learns generic classes considering the realization in vitro via a sequence of molecular biological operations on sets of DNA examples. Specifically, hybridization between DNA molecules is interpreted as computing the inner product between embedded vectors in a corresponding vector space, and our algorithm performs learning of a binary classifier in this vector space. We analyze the thermodynamic behavior of these learning algorithms, and show simulations on artificial and real datasets as well as demonstrate preliminary wet experimental results using gel electrophoresis. (C) 2015 Published by Elsevier Ireland Ltd.

关键词： DNA computing Machine learning Learning in vitro Kernel methods molecular algorithms

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

学校读者我要写书评

暂无评论

IEEE TRANSACTIONS ON NANOBIOSCIENCE 2008年第3期7卷 215-222页

作者： Chang, Weng-Long Ren, Ting-Ting Luo, Jun Feng, Mang Guo, Minyi Lin, Kawuu Weicheng Natl Kaohsiung Univ Appl Sci Dept Comp Sci & Informat Engn Kaohsiung 80778 Taiwan Chinese Acad Sci Wuhan Inst Phys & Math State Key Lab Magnet Resonance & Atom & Mol Phys Wuhan 430071 Peoples R China Univ Aizu Sch Comp Sci & Engn Fukushima 9658580 Japan

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.

关键词： molecular algorithms quantum algorithms the NP-complete problems the satisfiability problem