{
  "abstract": "Linear combination of unitaries (LCU) is a fundamental primitive in quantum algorithms, whose cost is typically governed by the most expensive unitary appearing in the combination. We develop a transducer-based LCU framework that reduces this worst-case dependence to a weighted average query complexity, when the constituent unitaries share access to a common set of primitive oracles. Consider $A=\\sum_j c_j U_j$, where $c_j>0$ and each unitary $U_j$ can be implemented using $C_j$ primitive queries. Given an upper bound $a\\geq \\|A\\|$, our algorithm implements a block-encoding of $A/α$ with rescaling factor $α=\\mathcal{O}(a)$, using $\\widetilde{\\mathcal{O}} (C_{\\max}+\\overline{C} λ/{a} )$ primitive queries, where $λ=\\sum_j c_j$, $C_{\\max}=\\max_j C_j$, and $\\overline{C}= {\\sum_j c_j C_j}/λ$. By comparison, the standard LCU construction requires $\\widetilde{\\mathcal{O}} (C_{\\max} λ/{a} )$ primitive queries. The improvement can therefore be substantial when costly unitaries have small weights and $λ/a$ is large. As applications, we obtain improved block-encodings of sparse matrices, leading to quantum algorithms for sparse Hamiltonian simulation and quantum linear systems with near-optimal query complexity up to polylogarithmic factors in all relevant parameters. Our main technique is the transducer framework developed by Belovs, Jeffery, and Yolcu [Quantum, 8:1444 (2024)]. Here we develop a complementary operator-level theory tailored to block-encodings. We identify the resolvent norm $K$ as a key complexity measure for transducer implementation besides the existing catalyst complexity. We show that the transducer action can be converted into an $ε$-approximate block-encoding using only $\\mathcal{O}\\left(K \\log(1/ε)\\right)$ queries to the transducer, improving the precision dependence from polynomial to logarithmic.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.40073",
  "author_total": 5,
  "authors": [
    {
      "name": "Dong An"
    },
    {
      "name": "Dekuan Dong"
    },
    {
      "name": "Changpeng Shao"
    },
    {
      "name": "Yuxin Zhang"
    },
    {
      "name": "Chenhao Zhao"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/6yd6dvmt47gth.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.40073",
  "fulltext_url": null,
  "id": "6yd6dvmt47gth",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.40073",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "quant-ph"
    ],
    [
      "openalex",
      "1702|Quantum Computing Algorithms and Architecture"
    ]
  ],
  "openalex": "W7215074752",
  "pdf_url": "https://arxiv.org/pdf/2609.40073",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-30",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/6yd6dvmt47gth.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:25:49Z",
      "native_id": "2609.40073",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.40073"
    }
  ],
  "subjects": [
    {
      "field": "physics",
      "origin": "arxiv:quant-ph",
      "subfield": "quantum"
    }
  ],
  "title": "Transducer-based linear combination of unitaries: theory and applications",
  "title_text": "Transducer-based linear combination of unitaries: theory and applications",
  "type": "preprint",
  "updated_at": "2026-10-30T12:25:49Z",
  "url": "https://research.draconitic.com/paper/6yd6dvmt47gth",
  "venue": "arXiv",
  "versions": []
}