Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding
The study establishes asymptotically optimal bounds for T-count circuits when dealing with sparse quantum read-only memory (QROM). It shows that for sparse QROM, the optimal T-count scales with the square root of the support size, matching lower bounds for state preparation and block encoding. This demonstrates that sparsity significantly reduces the required gate complexity for these quantum tasks.