Sparse Quantum State Preparation with Sublinear T-Count

Abstract: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 $\Theta(\sqrt{2^n\log(1/\epsilon)}+\log(1/\epsilon))$, 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 $\epsilon$ using $\widetilde{O}(\min\{s,\ n^{3/4}\sqrt{s}\}+\sqrt{s\log(1/\epsilon)}+\log(1/\epsilon))$ $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<\epsilon\le 1/6$ and $2\le s\le 2^{n/2}$, sparse-state preparation requires $\Omega(\min\{s,\sqrt{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.

arXiv:2608.00414 [quant-ph]

(or arXiv:2608.00414v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2608.00414 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.