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

@misc{li2026optimal,
  title = {{Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding}},
  author = {Tongyang Li and Fengning Ou and Xinzhao Wang and Penghui Yao and Pei Yuan and Shengyu Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2607.28260},
  eprint = {2607.28260},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2607.28260},
}

TY  - UNPB
TI  - Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding
AU  - Tongyang Li
AU  - Fengning Ou
AU  - Xinzhao Wang
AU  - Penghui Yao
AU  - Pei Yuan
AU  - Shengyu Zhang
PY  - 2026
DA  - 2026/10/01
PB  - arXiv
DO  - 10.48550/arxiv.2607.28260
UR  - https://arxiv.org/abs/2607.28260
AB  - Many quantum algorithms require coherent access to classical data, often modeled by quantum read-only memory (QROM). We initiate the study of the T count of sparse QROM, in which only s of the 2^n addresses store nonzero data. We prove that the optimal T count is Θ(n+min{s,√(s(m+log(2^n+1/s)))}). 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+T circuits. The lower bounds thus hold even when mid-circuit measurements and classically controlled operations are allowed. As applications, we obtain matching T-count bounds Θ(min{s,√(slog(2^n+1/s))} +√(slog(1/ε))+log(1/ε)) for s-sparse state preparation and Θ(√(2^n s(n+log(1/ε_BE))) +log(1/ε_BE)) for block encoding of s-sparse matrices, where ε and ε_BE are the precision of state preparation and block encoding, respectively.
ER  -