Jul 2026
Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding
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 asymptotically optimal $T$-count bounds $\Theta(\sqrt{sm} + \sqrt{sn})$ with s...
Tongyang Li, Fengning Ou, Xin-Zhao Wang et al.
· arXiv.org · 4 citations