⚛️ quantum physics

Sparse Quantum State Preparation with Sublinear T-Count

This paper presents a fault-tolerant quantum algorithm that prepares $s$ -sparse $n$ -qubit states with a sublinear $T$ -count of $\widetilde{O}(\min\{s,\ n^{3/4}\sqrt{s}\}+\sqrt{s\log(1/\epsilon)}+\log(1/\epsilon))$ , while simultaneously establishing a matching lower bound of $\Omega(\min\{s,\sqrt{ns}\})$ that proves linear dependence on $s$ is unavoidable for small support sizes.

Original authors: Jingquan Luo, Lvzhou Li

Published 2026-08-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jingquan Luo, Lvzhou Li

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to build a massive, intricate castle out of LEGO bricks. In the world of quantum computing, this castle is a "quantum state"—a specific, complex arrangement of information that a quantum computer needs to hold to solve a problem. But there's a catch: the tools we have to build these castles are incredibly finicky. Some tools, called "Clifford gates," are cheap, fast, and easy to use without breaking anything. Others, called "T gates," are like rare, glowing, super-expensive gems. They are the only way to build the truly magical parts of the castle, but using too many of them makes the whole project too slow and expensive to be practical.

Now, imagine you don't need to build a castle with every single brick in the box. Maybe you only need to build a castle that uses a tiny, specific selection of bricks, leaving the rest of the box empty. In the language of the paper, this is called a "sparse" state. For a long time, scientists thought that even if you only needed a few bricks, the cost of the rare gems (the T gates) would still grow in a straight line with the number of bricks you used. If you doubled the number of bricks, you'd double the cost. But what if you could find a shortcut? What if, once your castle got big enough, you could stop paying for every single brick and start paying for just a fraction of them? That is the big question this paper tackles: Can we build these sparse quantum castles using fewer of those expensive gems than we thought was possible?

The authors of this paper, Jingquan Luo and Lvzhou Li, say "Yes, but with a twist." They discovered that for small castles, the old rule still holds: you have to pay for every brick. But once the castle gets large enough (specifically, when the number of bricks is bigger than a certain mathematical threshold involving the size of the computer), the cost stops growing in a straight line. Instead, it grows much slower, following a formula that combines the size of the computer and the square root of the number of bricks (roughly proportional to $n^{3/4}\sqrt{s}$ ). This means that for very large, sparse quantum states, we can save a massive amount of those expensive T gates, though the savings follow a specific, slightly more complex curve than a simple square root.

To understand how they did this, think of the problem as a game of "Hide and Seek" with a twist. The quantum state is a list of secret locations (the "support") where the information lives. The old way of preparing this state was like checking every single possible hiding spot one by one, which is slow and expensive. The authors came up with a new strategy based on a clever "synthesis theorem" for Boolean functions (which are just fancy math rules for turning inputs into outputs).

Their method works in two main phases. First, they create a "label" for the secret locations. Instead of dealing with the huge, messy list of all possible locations, they compress the secret spots into a smaller, manageable list of labels. Then, they use a special, efficient circuit to "load" the actual locations based on those labels. The real magic happens in the final step: erasing the labels so the computer doesn't get confused. This is the hardest part, and it's where they found their shortcut.

They realized that if the list of secret spots is huge, they don't need to check every single one individually. Instead, they can look at the "prefixes" (the beginning parts) of the locations. If many locations share the same beginning, they can group them together and handle them all at once. If only a few locations share a beginning, they can compress those beginnings into a shorter code. By constantly switching between grouping and compressing, they can peel away layers of the problem much faster than before. This allows them to build the state with a number of T gates that is "sublinear"—meaning the cost grows much slower than the size of the state.

However, the paper is very careful not to claim this is a magic wand that solves everything. The authors proved that for small states, the old linear cost is unavoidable; you simply cannot bypass the system when the list of secrets is short. They also showed that while their new method is a huge improvement, there is still a tiny gap between the best possible cost they found and the absolute theoretical limit. It's like finding a path that is 90% shorter than the old road, but not quite the absolute shortest path possible. They aren't sure yet if that last bit of distance is because their map is imperfect, or if the terrain itself just won't allow a shorter path.

In short, this paper proves that for large, sparse quantum states, we can build them much more efficiently than previously thought, saving valuable resources. But it also draws a hard line in the sand: for small states, the expensive cost is here to stay. The authors have opened a door to a more efficient future for quantum computing, but they've also shown us exactly where the walls still stand, inviting future explorers to see if they can find a way through.

Technical Summary: Sparse Quantum State Preparation with Sublinear T-Count

Problem Statement
The paper addresses the fault-tolerant cost of preparing sparse quantum states within the Clifford+T model. An $n$ -qubit state is defined as $s$ -sparse if its support in the computational basis contains at most $s$ non-zero amplitudes. While general $n$ -qubit state preparation has a known optimal T-count of $\Theta(\sqrt{2^n} \log(1/\epsilon) + \log(1/\epsilon))$ , previous results for sparse states were limited by linear dependence on the sparsity $s$ . Specifically, recent works established upper bounds of $O(s)$ T gates for $s$ -sparse states. The central question investigated is whether the T-count for preparing $s$ -sparse states can be made sublinear in $s$ , particularly when the support size $s$ is large relative to the number of qubits $n$ .

Methodology
The authors approach the problem by decomposing state preparation into three main stages:

Label State Preparation: Preparing a dense superposition on a $\lceil \log s \rceil$ -qubit index register.
Coherent Loading: Using a Boolean function to map the index $i$ to the corresponding basis string $x^{(i)}$ in an $n$ -qubit data register.
Label Erasure: Applying the inverse of the labeling map to uncompute the index register, leaving the data register in the target state.

The core technical innovation lies in the synthesis of the label-erasure step, which involves implementing a sparse Boolean function $L: \{0, 1\}^n \to \{0, 1\}^{\lceil \log s \rceil}$ that maps supported inputs $x^{(i)}$ back to their indices $i$ and maps all other inputs to zero. The authors develop a support-aware synthesis theorem for sparse Boolean functions that adapts its strategy based on the support size $s$ :

Small-Support Regime ( $s \leq n^{3/2} \log n$ ): The method compresses the $s$ supported inputs into a logarithmic-size label register using an injection. The problem is reduced to synthesizing a Boolean function on $O(\log s)$ bits, which can be done with $O(s+n)$ Toffoli gates.
Large-Support Regime ( $s > n^{3/2} \log n$ ): The authors employ a recursive algorithm that fixes a prefix length $r$ $r$ . At each step, the algorithm analyzes the active $r$ $r$ -bit prefixes of the current support:
- If few prefixes are active, it performs prefix compression, injectively relabeling active prefixes to shorten the input length without changing the support size.
- If many prefixes are active, it performs support peeling, removing one supported input from each active prefix. This "peeled" slice is implemented cheaply, while the remaining recursive instance loses a substantial fraction of its support points.
  By balancing these two operations, the algorithm achieves a Toffoli count that scales sublinearly with $s$ .

For the lower bounds, the paper utilizes two distinct techniques:

Small $s$ ( $s = O(n)$ ): An extension of the stabilizer nullity argument. The authors prove that for states close to the W-state $|W_s\rangle \otimes |0^{n-s}\rangle$ , the stabilizer subgroup rank is bounded, implying a linear lower bound of $\Omega(s)$ .
Large $s$ ( $s = \Omega(n)$ ): A packing argument combined with a counting lemma from [GKW26]. By constructing a large family of pairwise well-separated $s$ -sparse states and bounding the number of states preparable with $t$ T gates, they derive a lower bound of $\Omega(\sqrt{ns})$ .

Key Contributions and Results

Sublinear Upper Bound: The paper establishes that any $n$ -qubit $s$ -sparse state can be prepared up to error $\epsilon$ using:
$\tilde{O}\left(\min\left\{s, n^{3/4}\sqrt{s}\right\} + \sqrt{s}\log(1/\epsilon) + \log(1/\epsilon)\right)$
T gates. This is the first result showing sublinear dependence on $s$ for sufficiently large support (specifically when $s \gtrsim n^{3/2}$ ). The ancilla requirement is $\tilde{O}(\sqrt{ns})$ .
Tight Lower Bounds: The authors prove that for $0 < \epsilon \leq 1/6$ and $2 \leq s \leq 2^{n/2}$ , the T-count is lower bounded by:
$\Omega(\min\{s, \sqrt{ns}\})$
This result demonstrates that the linear dependence on $s$ is unavoidable in the small-support regime ( $s = O(n)$ ) and that the dependence on $n$ cannot be completely removed in the large-support regime.
Support-Aware Synthesis Theorem: A general theorem for synthesizing sparse Boolean functions $F: \{0, 1\}^n \to \{0, 1\}^b$ with support size $s$ . The Toffoli complexity is $O(s+n)$ for small $s$ and $\tilde{O}(n^{3/4}\sqrt{s} + n^{1/4}\sqrt{bs})$ for large $s$ . The authors note this result may be of independent interest beyond state preparation.

Significance and Claims
The paper claims to resolve the question of whether sparse state preparation can be sublinear in $s$ . The results show that the previously known linear $O(s)$ bound is not inherent for large supports; the cost can be reduced to $\tilde{O}(n^{3/4}\sqrt{s})$ . However, the authors are modest regarding the optimality of their upper bound. They highlight a remaining gap between the upper bound $\tilde{O}(n^{3/4}\sqrt{s})$ and the lower bound $\Omega(\sqrt{ns})$ in the large-support regime.

The paper explicitly states it is unclear whether the crossover point at $s \approx n^{3/2}$ and the $n^{3/4}$ factor are artifacts of their specific algorithm or reflect inherent limitations of fault-tolerant sparse quantum state preparation. Furthermore, while the construction utilizes the partial nature of Boolean functions in the small-support regime, the authors note that incorporating this relaxation into the large-support construction does not currently improve the asymptotic bound, leaving the potential for further exploitation of partial-function structure as an open problem.

Technical Summary: Sparse Quantum State Preparation with Sublinear T-Count

More like this