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^{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.