Delphi.science

Exact Quantum Algorithms for Composed Boolean Functions

Source: arxiv.org/abs/2611.16412

Gagan Chiruvella, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh

arXivarxiv/2611.16412Nov 12, 2026cs.CCscore 0

We study exact quantum algorithms for block compositions of total Boolean functions. For an outer function $f$ of degree $D$ and an inner function $g$ on $m$ bits, we prove $$ Q_E(f\circ g)=O\!\left(mD+Q_E(f)Q_{1/(4D)}(g)\right). $$ The algorithm combines approximate inner evaluations with a finite exact correction. Its two costs are governed by different parameters of the outer function: exact query complexity determines the cost of simulation, whereas polynomial degree determines the number of inner blocks used in the correction. We first establish the construction with an arity-dependent…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.16412
curl -X POST /api/v1/records/arxiv/2611.16412/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.16412/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'