Sparse Quantum State Preparation with Sublinear T-Count
Jingquan Luo, Lvzhou Li · 2026
Read Sparse Quantum State Preparation with Sublinear T-Count by Jingquan Luo, Lvzhou Li (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2608-00414.txt.
Introduction
Luo and Li cut the fault-tolerant cost of preparing sparse quantum states. Cost is measured by T-count in the Clifford+T model. An s-sparse state rests on at most s basis states. For general states the optimal T-count is known, but sparse bounds stayed linear in s. Their result gives the first sublinear dependence for large support.
Any n-qubit s-sparse state can be prepared within error epsilon at the stated tilde-O cost. A support-aware synthesis theorem for sparse Boolean functions carries the proof. It may hold interest on its own, they note. A lower bound shows linear cost is unavoidable for small support. The gap between upper and lower bounds narrows substantially in that range.
Catalog record
| CREATOR | Jingquan Luo, Lvzhou Li |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 54 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2608.00414
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Sparse Quantum State Preparation with Sublinear T-Count Jingquan Luo, Lvzhou Li Abstract We study the fault-tolerant cost of preparing sparse quantum states, measured by T T -count in the Clifford+ T T model. Here an n n -qubit state is called s s -sparse if it is supported on at most s s computational-basis states. For arbitrary n n -qubit states, the optimal T T -count is Θ ( 2 n log ( 1 / ϵ ) + log ( 1 / ϵ ) ) \Theta(\sqrt{2^{n}\log(1/\epsilon)}+\log(1/\epsilon)) , but for s s -sparse states the best previous upper bounds remained linear in s s . We show that any n n -qubit s s -sparse state can be prepared up to error ϵ \epsilon using O ~ ( min { s , n 3 / 4 s } + s log ( 1 / ϵ ) + log ( 1 / ϵ ) ) \widetilde{O}(\min\{s,\ n^{3/4}\sqrt{s}\}+\sqrt{s\log(1/\epsilon)}+\log(1/\epsilon)) T T gates, giving the first sublinear dependence on s 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 0<\epsilon\leq 1/6 and 2 ≤ s ≤ 2 n / 2 2\leq s\leq 2^{n/2} , sparse-state preparation requires Ω ( min { s , n s } ) \Omega(\min\{s,\sqrt{ns}\}) T T gates, showing that linear dependence on s s is unavoidable in the small-support regime and substantially narrowing the gap between the known upper and lower bounds within this parameter range. 1 Introduction Quantum state preparation is a central primitive in quantum computing. It underlies the initialization of structured superpositions in tasks such as quantum linear systems, Hamiltonian simulation, and amplitude-encoded quantum machine learning [ 9 , 4 , 16 , 12 ] . At the same time, canonical synthesis results for arbitrary states show that the task is expensive in the worst case, because specifying a generic n -qubit pure state requires \Theta(2^{n}) real parameters [ 26 , 23 , 11 ] . This makes state preparation especially interesting when the target state has additional structure that can be translated into a circuit advantage. In the fault-tolerant setting, the relevant resource is usually not the total number of elementary gates but the number of non-Clifford gates, especially T gates. The Clifford+ T gate set is universal, but it is also discrete, so exact synthesis is unavailable for generic target amplitudes. We therefore study approximate state preparation in the unitary Clifford+ T model [ 22 ] . For density operators \rho and \sigma , let D_{\mathrm{tr}}(\rho,\sigma):=\frac{1}{2}\|\rho-\sigma\|_{1} . For pure states \ket{\psi} and \ket{\phi} , let D_{\mathrm{tr}}(\ket{\psi},\ket{\phi}):=D_{\mathrm{tr}}(\ket{\psi}\!\bra{\psi},\ket{\phi}\!\bra{\phi})=\sqrt{1-\left|\braket{\psi|\phi}\right|^{2}} . We say that a unitary Clifford+ T circuit \epsilon -approximately prepares an n -qubit state \ket{\psi} if, for some a\geq 0 , starting from \ket{0^{n+a}} it outputs an (n+a) -qubit pure state \ket{\phi} such that \displaystyle D_{\mathrm{tr}}\!\left(\ket{\phi},\ket{\psi}\otimes\ket{0^{a}}\right)\leq\epsilon. (1) Within this model, Clifford operations are comparatively inexpensive to implement fault tolerantly, whereas T gates are costly because they rely on magic-state injection and distillation [ 15 , 3 ] . Throughout this paper, we therefore use T -count as the primary complexity measure for state preparation. Recent work has clarified the T complexity of general quantum state preparation. Let N=2^{n} . Low et al. established explicit tradeoffs between ancillary workspace and T -count, and Gosset et al. showed that an arbitrary n -qubit state can be \epsilon -approximately prepared using O(\sqrt{N\log(1/\epsilon)}+\log(1/\epsilon)) T gates and ancillas, and that this scaling is asymptotically optimal for general states in the stronger model of adaptive Clifford+ T circuits [ 17 , 8 ] . These results show that ancillary workspace can significantly reduce the cost of unstructured state preparation. However, the worst-case complexity is still exponential in n , because the target state is treated as completely generic. A natural structured family is that of sparse quantum states. We call an n -qubit state s -sparse if its support in the computational basis has size at most s ; equivalently, there exist distinct basis strings x^{(0)},\ldots,x^{(s-1)}\in\{0,1\}^{n} and coefficients \alpha_{0},\ldots,\alpha_{s-1}\in\mathbb{C} such that \displaystyle|\psi\rangle=\sum_{j=0}^{s-1}\alpha_{j}|x^{(j)}\rangle, (2) where \sum_{j=0}^{s-1}|\alpha_{j}|^{2}=1 . We denote its support by \operatorname{supp}(\ket{\psi}):=\{x\in\{0,1\}^{n}:\langle x|\psi\rangle\neq 0\} . When s\ll 2^{n} , the natural question is whether the synthesis cost is governed by the support size rather than by the ambient Hilbert-space dimension. This question is supported by a substantial circuit-complexity literature on sparse state preparation [ 7 , 19 , 24 , 21 , 6 , 5 , 29 , 30 , 28 , 10 ] . Earlier work gave efficient constructions for sparse states with circuit size O(ns) [ 7 , 19 , 24 , 21 , 6 , 5 ] . Subsequent results sharpened this bound and developed refined space-time tradeoffs [ 20 , 14 , 18 ] . However, these works focus primarily on total gate count, depth, or space-time complexity rather than the fault-tolerant non-Clifford cost. Only a small number of recent works speak directly to that metric [ 27 , 25 ] . In particular, Vilmart, Ty, and Mang [ 27 ] gave a sparse-state preparation algorithm with O(s) non-Clifford gates and \max\{s-n,0\} ancillas. Rupprecht and Wölk give a sparse-state preparation method with Toffoli complexity O(s) [ 25 ] ; since each Toffoli admits a constant-size Clifford+ T implementation [ 22 ] , this yields an O(s) contribution to the corresponding T -count. Combined with the optimal dense-state preparation bound on a \lceil\log s\rceil -qubit register [ 8 ] , this gives an O(s+\log(1/\epsilon)) upper bound for \epsilon -approximate preparation of s -sparse states. This leaves a basic question: can the T -count for preparing s -sparse states be made sublinear in s , at least in some parameter regime? 1.1 Contribution Our main result is a new T -count upper bound that becomes sublinear in s once the support reaches \widetilde{\Omega}(n^{3/2}) , together with lower bounds showing that, for 0<\epsilon\leq\frac{1}{6} , linear dependence on s is unavoidable for s=O(n) and that every construction must still pay at least \Omega(\sqrt{ns}) for \Omega(n)\leq s\leq 2^{n/2} . Table 1 and Figure 1 summarize this picture. We first state the constant-error form of the upper bound to highlight the dependence on n and s . Theorem 1 (Informal version of Theorem 9 ) . Any n -qubit s -sparse state can be prepared up to constant error by a Clifford+ T circuit starting with the all-zeros state using \widetilde{O}\left(n^{3/4}\sqrt{s}\right) T gates and \widetilde{O}(\sqrt{ns}) ancillas 1 1 1 The \widetilde{O} notation suppresses polylogarithmic factors, such as \log n and \log s . . Combining Theorem 1 with the previous linear-in- s construction [ 25 , 27 ] yields the following best known upper bound. Corollary 2 . Any n -qubit s -sparse state can be prepared up to constant error by a Clifford+ T circuit starting with the all-zeros state using \widetilde{O}(\min\{s,\ n^{3/4}\sqrt{s}\}) T gates. Thus the previous linear-in- s construction remains the better upper bound for s=\widetilde{O}(n^{3/2}) , while our new construction gives the first sublinear dependence on s beyond that threshold. We complement this upper bound with lower bounds showing