{
  "annotation_id": "1a5c9233-fe5f-465b-888f-8708dd6a6313",
  "date_created": "2026-03-02T18:02:20.580000Z",
  "date_modified": "2026-03-02T18:02:20.580000Z",
  "file_hash": "2c2ffb396b51bb36cbdf40d446c0da67b79c0d485c344cfbb6fecca18194816e",
  "private": false,
  "record": {
    "abstract": "We propose a quantum algorithm for closest pattern matching which allows us\nto search for as many distinct patterns as we wish in a given string\n(database), requiring a query function per symbol of the pattern alphabet. This\nrepresents a significant practical advantage when compared to Grover\u0027s search\nalgorithm as well as to other quantum pattern matching methods, which rely on\nbuilding specific queries for particular patterns. Our method makes arbitrary\nsearches on long static databases much more realistic and implementable. Our\nalgorithm, inspired by Grover\u0027s, returns the position of the closest substring\nto a given pattern of size $M$ with non-negligible probability in $O(\\sqrt{N})$\nqueries, where $N$ is the size of the string. Furthermore, we give the full\nrecipe to implement our algorithm (together with its total circuit complexity),\nthus offering an oracle-based quantum algorithm ready to be implemented.",
    "arxiv_id": "quant-ph/0508237",
    "authors": [
      "P. Mateus",
      "Y. Omar"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Quantum Pattern Matching",
    "url": "https://arxiv.org/abs/quant-ph/0508237"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "e6d5a09b-86c4-4595-8b52-2c11d89a2c93",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}