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

CREATORJingquan Luo, Lvzhou Li
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE54 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Read the complete text