{"id":"arxiv/2607.28260","url":"https://arxiv.org/abs/2607.28260","tags":["quant-ph","cs.CC","cs.DS"],"score":0,"title":"Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding","domain":"quant-ph","source":"arxiv","authors":["Tongyang Li","Fengning Ou","Xinzhao Wang","Penghui Yao","Pei Yuan","Shengyu Zhang"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-07-30","reactions":{}}