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, Renata Wong, Ju-Chin Chen, Mang Feng, Athanasios V. Vasilakos · IEEE Transactions on NanoBioscience · 2021
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.