Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding

Tongyang Li, Fengning Ou, Xinzhao Wang, Penghui Yao, Pei Yuan, Shengyu Zhang

arXivarxiv/2607.28260Jul 30, 2026quant-phscore 0

Many quantum algorithms require coherent access to classical data, often modeled by quantum read-only memory (QROM). We initiate the study of the $\mathrm{T}$ count of sparse QROM, in which only $s$ of the $2^n$ addresses store nonzero data. We prove that the optimal $\mathrm{T}$ count is $Θ\left(n+\min\left\{s,\sqrt{s\left(m+\log(2^{n+1}/s)\right)}\right\}\right)$. Our upper bounds use a multilevel hashing scheme, while our lower bounds reduce sparse QROM to state preparation and use counting arguments for adaptive Clifford+$\mathrm{T}$ circuits. The lower bounds thus hold even when…

SourceJSON

Comments and reviews

No comments yet.

API

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