2026/08/01 by Jingquan Luo, Lvzhou Li
Physics and Astronomy · #quant-ph
arxiv created 2026/08/01 · arxiv updated 2026/08/04
We study the fault-tolerant cost of preparing sparse quantum states, measured by T-count in the Clifford+T model. Here an n-qubit state is called s-sparse if it is supported on at most s computational-basis states. For arbitrary n-qubit states, the optimal T-count is Θ(√(2nlog(1/ε))+log(1/ε)), but for s-sparse states the best previous upper bounds remained linear in s. We show that any n-qubit s-sparse state can be prepared up to error ε using \widetildeO(min\s, n3/4√(s)\+√(slog(1/ε))+log(1/ε)) T gates, giving the first sublinear dependence on s once the support is sufficiently large. Our approach is based on a support-aware synthesis theorem for sparse Boolean functions, which may be of independent interest. We also prove that, for every 0<ε≤ 1/6 and 2≤ s≤ 2n/2, sparse-state preparation requires Ω(min\s,√(ns)\) T gates, showing that linear dependence on s is unavoidable in the small-support regime and substantially narrowing the gap between the known upper and lower bounds within this parameter range.