{
  "abstract": "We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most $q$ oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision $ε$ requires $Θ(\\frac{1}{q ε^2})$ queries; (ii) (Unbiased) Amplitude estimation up to a precision $ε$ requires $Θ(\\frac{p(1-p)}{q ε^2})$ queries; (iii) Search among $N$ items requires $Θ(\\frac{N}{q})$ queries; (iv) Two level AND-OR tree (AND of $m$ ORs, with $n$ inputs to each OR) requires $Θ(\\frac{nm}{q})$ queries. All of these bounds are optimal up to a constant factor, for all $q$ from 1, corresponding to the classical complexity, to $Q(f)$, the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2610.06803",
  "author_total": 3,
  "authors": [
    {
      "name": "Andris Ambainis"
    },
    {
      "name": "András Gilyén"
    },
    {
      "name": "Martins Kokainis"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/0wee0zxqykzt2.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2610.06803",
  "fulltext_url": null,
  "id": "0wee0zxqykzt2",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2610.06803",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "quant-ph"
    ],
    [
      "openalex",
      "1702|Quantum Computing Algorithms and Architecture"
    ]
  ],
  "openalex": "W7220671324",
  "pdf_url": "https://arxiv.org/pdf/2610.06803",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-05",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/0wee0zxqykzt2.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:27:01Z",
      "native_id": "2610.06803",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2610.06803"
    }
  ],
  "subjects": [
    {
      "field": "physics",
      "origin": "arxiv:quant-ph",
      "subfield": "quantum"
    }
  ],
  "title": "Tight bounds for hybrid quantum-classical query algorithms",
  "title_text": "Tight bounds for hybrid quantum-classical query algorithms",
  "type": "preprint",
  "updated_at": "2026-10-30T12:27:01Z",
  "url": "https://research.draconitic.com/paper/0wee0zxqykzt2",
  "venue": "arXiv",
  "versions": []
}