{
  "annotation_id": "bcbdb57e-2109-4382-b418-22fb0cf6fcd7",
  "date_created": "2026-03-02T18:02:27.177000Z",
  "date_modified": "2026-03-02T18:02:27.177000Z",
  "file_hash": "22039b91779981911d782e833f21111fc2783badb5e28347829058f1773a7d1a",
  "private": false,
  "record": {
    "abstract": "Many quantum algorithms can be analyzed in a query model to compute Boolean\nfunctions where input is given by a black box. As in the classical version of\ndecision trees, different kinds of quantum query algorithms are possible:\nexact, zero-error, bounded-error and even nondeterministic. In this paper, we\nstudy the latter class of algorithms. We introduce a fresh notion in addition\nto already studied nondeterministic algorithms and introduce dual\nnondeterministic quantum query algorithms. We examine properties of such\nalgorithms and prove relations with exact and nondeterministic quantum query\nalgorithm complexity. As a result and as an example of the application of\ndiscovered properties, we demonstrate a gap of n vs. 2 between classical\ndeterministic and dual nondeterministic quantum query complexity for a specific\nBoolean function.",
    "arxiv_id": "quant-ph/0606248",
    "authors": [
      "Alina Dubrovska Vasilieva"
    ],
    "categories": [
      "quant-ph"
    ],
    "doi": "10.1117/12.720641",
    "title": "Properties and Application of Nondeterministic Quantum Query Algorithms",
    "url": "https://arxiv.org/abs/quant-ph/0606248"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "16d2e8bc-5714-47a7-b053-4fe75c13ce14",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}