Quantum search algorithms are considered in the context of protein sequence
comparison in bioinformatics. Given a sample protein sequence of length In
(i.e., In residues), the problem considered is to find an optimal match in
a large database containing N residues. Initially, Grover's quantum search
algorithm is applied to a simple illustrative case-namely, where the datab
ase forms a complete set of states over the 2(m) basis states of a m qubit
register, and thus is known to contain the exact sequence of interest. This
example demonstrates explicitly the typical O( rootN) speedup on the class
ical O( rootN) requirements. An algorithm is then presented for the (more r
ealistic) case where the database may contain repeat sequences, and may not
necessarily contain an exact match to the sample sequence. In terms of min
imizing the Hamming distance between the sample sequence and the database s
ubsequences the algorithm finds an optimal alignment, in O( rootN) steps, b
y employing an extension of Grover's algorithm, due to Boyer et al. for the
case when the number of matches is not a priori known.