dorsal/arxiv
View SchemaFast Quantum Search Algorithms in Protein Sequence Comparison - Quantum Biocomputing
| Authors | Lloyd C. L. Hollenberg |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0002076 |
| URL | https://arxiv.org/abs/quant-ph/0002076 |
| DOI | 10.1103/PhysRevE.62.7532 |
Abstract
Quantum search algorithms are considered in the context of protein sequence comparison in biocomputing. Given a sample protein sequence of length m (i.e m 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 database 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(sqrt{N}) speedup on the classical O(N) requirements. An algorithm is then presented for the (more realistic) case where the database may contain repeat sequences, and may not necessarily contain an exact match to the sample sequence. In terms of minimizing the Hamming distance between the sample sequence and the database subsequences the algorithm finds an optimal alignment, in O(sqrt{N}) steps, by employing an extension of Grover's algorithm, due to Boyer, Brassard, Hoyer and Tapp for the case when the number of matches is not a priori known.
{
"annotation_id": "ffe88391-5cce-4314-b2fb-bc44c8b09f8b",
"date_created": "2026-03-02T18:01:37.944000Z",
"date_modified": "2026-03-02T18:01:37.944000Z",
"file_hash": "d65b270d85bcb8bbe2420b832d3ab63f9d7c9a6860755b0523f156a306ba4509",
"private": false,
"record": {
"abstract": "Quantum search algorithms are considered in the context of protein sequence\ncomparison in biocomputing. Given a sample protein sequence of length m (i.e m\nresidues), the problem considered is to find an optimal match in a large\ndatabase containing N residues. Initially, Grover\u0027s quantum search algorithm is\napplied to a simple illustrative case - namely where the database forms a\ncomplete set of states over the 2^m basis states of a m qubit register, and\nthus is known to contain the exact sequence of interest. This example\ndemonstrates explicitly the typical O(sqrt{N}) speedup on the classical O(N)\nrequirements. An algorithm is then presented for the (more realistic) case\nwhere the database may contain repeat sequences, and may not necessarily\ncontain an exact match to the sample sequence. In terms of minimizing the\nHamming distance between the sample sequence and the database subsequences the\nalgorithm finds an optimal alignment, in O(sqrt{N}) steps, by employing an\nextension of Grover\u0027s algorithm, due to Boyer, Brassard, Hoyer and Tapp for the\ncase when the number of matches is not a priori known.",
"arxiv_id": "quant-ph/0002076",
"authors": [
"Lloyd C. L. Hollenberg"
],
"categories": [
"quant-ph",
"physics.bio-ph",
"q-bio"
],
"doi": "10.1103/PhysRevE.62.7532",
"title": "Fast Quantum Search Algorithms in Protein Sequence Comparison - Quantum Biocomputing",
"url": "https://arxiv.org/abs/quant-ph/0002076"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "088dc915-e1e1-4669-9a80-4e80d0b11a1a",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}