Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding

arXiv:2607.28260 · quant-ph, cs.CC, cs.DS · Submitted 2026-07-30 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "Optimal T Counts under Sparsity".

Mira: The paper establishes asymptotically optimal T-count bounds for sparse quantum read-only memory (QROM) and its applications in state preparation and block encoding,

Kai: First, who's behind it and why it matters.

Title and authors: Kai: So we’ve talked about the paper's focus on sparsity and its application to QROM, state preparation, and block encoding in the last segment. Now let's look at who put this work together. The authors are Tongyang Li, Fengning Ou, Xinzhao Wang, Penghui Yao, Pei Yuan, and Shengyu Zhang from Peking University.

Mira: I find it interesting that the team is comprised of researchers from different areas—from computer science to quantum information—which suggests a broad perspective on how these concepts intersect.

Lev: As a quantum error-correction researcher, I'm always interested in seeing if the theoretical results they present are realistic enough to be implemented on actual hardware with current noise models.

Kai: That’s fair, Lev; but the core of this paper is establishing these T-count bounds based on mathematical models of QROM and circuit complexity rather than just a specific physical device.

Mira: They are using standard abstractions like Clifford+T circuits and QROM to define the problem, which allows them to generalize their findings beyond any one specific physical platform.

Lev: That generality is what makes it powerful; if the results hold across different noise profiles, then the implications for fault-tolerant quantum computation are much wider than just one specific experiment.

Kai: Exactly; and their discussion on how they reduce promised sparse QROM to dense QROM shows they're thinking about practical ways to map these theoretical ideal structures onto more accessible models.

Mira: That reduction method seems like a smart way to bridge the gap between the highly idealized sparse models and what we might actually encounter in real-world experimental setups.

The paper's summary: Kai: So, let's summarize what this paper is really saying about the T count bounds for sparse QROM and its implications for state preparation and block encoding. The main takeaway is that they proved asymptotically optimal bounds scaling with the square root of sparsity.

Mira: They demonstrated that for sparse QROM, the key resource cost isn't dominated by the total address space size N but rather by the support size s, yielding Theta(√s m + √s n) with square-root dependence on sparsity.

Lev: That scaling is really significant because it implies that for large, sparse problems, we can achieve performance gains that aren't just linear in the problem size but something much more favorable.

Kai: And they also matched this down by establishing matching lower bounds for state preparation and block encoding tasks, which means the upper bound is tight against a proven minimum requirement.

Mira: They achieved matching bounds for sparse state preparation, showing that any s-sparse n-qubit state can be prepared within trace-distance error epsilon by a Clifford + T circuit using O(√s n + n + p s log(one/epsilon) + log(one/epsilon)) T gates.

Lev: That matching lower bound is crucial because it tells us that we can't do better than this resource cost for preparing states with that level of fidelity under these specific sparsity constraints.

Kai: And their work on block encoding sparse matrices also provides a tight upper bound of O(√2ns + p 2ns log(s/epsilonBE) + log(s/epsilonBE)) for an (¯s, O(n + log(s/epsilonBE)), epsilon BE)-block encoding.

Mira: So, they’ve essentially provided a tight resource estimate for both loading sparse data and the resulting operations in state preparation and matrix encoding.

The paper's improvements: Kai: Moving on to what the paper suggests as potential improvements, it seems their primary contribution is showing that the methods they developed for QROM are powerful because they can be used to reduce promised sparse QROM to dense QROM.

Mira: That reduction technique seems like a smart way to bridge the gap between highly idealized sparse models and more realistic scenarios we might encounter in experimental setups.

Lev: If we look at the lower bounds they established for adaptive promised s-sparse QROM, it suggests that even under certain constraints, you still need Omega(√s m) when s ≥ m log2 m.

Kai: That means the lower bounds are not just theoretical curiosities; they set a non-trivial bar for what algorithms can actually accomplish in practice.

Mira: And their work on quantum rejection sampling shows that the postselection subroutine can be implemented with a T count of O(p s log(one/delta) + log(one/delta) log s / epsilon two) conditioned on success.

Lev: For rejection sampling, I wonder how the error term delta/epsilon squared relates to the required fidelity for physical implementations; that's a key consideration when planning experiments.

Kai: That error term is what we have to watch closely; it dictates how close our final state is to the target distribution in those sampling routines.

Mira: Overall, these improvements suggest that this framework isn't just about finding better bounds but about creating a toolkit for designing more efficient quantum algorithms around sparse data access and processing.

Conclusion: Kai: So we’ve gone through how this paper establishes asymptotically optimal T-count bounds for sparse quantum read-only memory and its applications in state preparation and block encoding, which is really a significant piece of work.

Mira: It really boils down to showing that sparsity allows us to achieve better scaling, specifically that the resource cost depends on the square root of the support size rather than just the total problem size.

Lev: For me, what stands out is how they establish matching lower bounds for these tasks; it means we know exactly what resource expenditure we can't beat in practice for those specific scenarios.

Kai: And that tight matching between the upper bound derived from construction and the lower bound from adaptive frameworks gives us a very robust view of the required T gates.

Mira: The implication is that we can start designing quantum algorithms where their complexity scales with how sparse our classical input data is, which is a big step for practical applications in areas like quantum machine learning or simulation.

Lev: If we can use these bounds reliably, it gives us a clear target for fault-tolerant hardware design concerning data loading and matrix operations involving sparse inputs.

Kai: This work on "Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding" really sets a new standard for how we estimate the resource costs of these fundamental quantum tasks.

Mira: It’s definitely a paper that pushes us toward more practical, sparsity-aware quantum algorithm design.

Lev: I think the next logical step is seeing how error correction can integrate with these specific sparse access patterns to see if those bounds hold up under actual noise conditions.

Center on Frontiers of Computing Studies, Peking University

quant-ph, cs.CC, cs.DS

Submitted: 2026-07-30

Updated: 2026-10-01

Comments: 50 pages, 2 tables

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 90/100

The gist: The paper establishes asymptotically optimal T-count bounds for sparse quantum read-only memory (QROM) and its applications in state preparation and block encoding, demonstrating that the square-root

Key concepts

T count
This term measures the total number of T gates used in a specific type of quantum circuit called a Clifford+T circuit. It is a key metric for quantifying the computational cost and complexity when performing operations on quantum data, indicating how many non-Clifford gates are necessary.
Sparse QROM
QROM refers to memory that stores quantum states in a sparse manner, meaning only a few entries are non-zero. The paper investigates different models of this memory, such as promised and adaptive versions, focusing on how the sparsity (the number of non-zero entries) affects the efficiency of loading or accessing these quantum states.
State Preparation
This is the process of creating a specific target quantum state using a sequence of quantum gates. The paper analyzes how efficiently an s-sparse state can be prepared, showing that the required T gates scale favorably with sparsity, allowing for practical implementations.
Block Encoding
Block encoding involves representing large matrices or data structures as smaller blocks. The research applies this to row- and column-s-sparse matrices, determining the optimal trade-off between qubit count and T gates needed to encode this sparse information efficiently.

Terminology

Summary

The paper establishes asymptotically optimal T-count bounds for sparse quantum read-only memory (QROM) and its applications in state preparation and block encoding, demonstrating that the square-root scaling of general QROM extends to sparse cases, yielding matching lower bounds for these tasks.

Optimal T Count Bounds

The study focuses on the T count, defined as the number of T gates in a Clifford+T circuit. The main result shows that for sparse QROM, the optimal T-count scales with the square root of the support size, replacing the dependence on table size N with dependence on sparsity s: We prove asymptotically optimal T-count bounds Θ(√s m + √s n) with square-root dependence on the support size s and message length m. For sparse state preparation, a matching bound is established: Any s-sparse n-qubit state can be prepared within trace-distance error ε by a Clifford + T circuit using O(√s n + n + p s log(1/ε) + log(1/ε)) T gates.

Sparse QROM Constructions

The paper investigates several models of sparse QROM, including the standard, promised, and adaptive versions. The construction for general sparse QROM achieves the optimal bound: Our final construction achieves the optimal T count Θ(√s m) by using a multilevel hashing strategy. This involves constructing an injective hash function with low T-count using three hashing-based constructions, culminating in a multilevel scheme that reduces the cost to O(√s m). For promised sparse QROM, the construction uses multilevel hashing to reduce promised sparse QROM to dense QROM, achieving a T count of O(√s m + m log s). The general sparse QROM is further extended by augmenting the output with the index itself, leading to an implementation with T count O(√s n + s m + (n + m) log s).

Applications in State Preparation and Block Encoding

The derived bounds apply directly to key quantum algorithms. For sparse state preparation, Theorem 4.2 provides a bound of O(√s n + p s log(1/ε) + log(1/ε) + n). For block encoding of row- and column-s-sparse matrices, the paper presents a matching upper bound: There exists an (¯s, O(n + log(s/εBE)), εBE)-block encoding of A with T count and qubit count both bounded by O(√2ns n + p 2ns log(s/εBE) + log(s/εBE)). This bound is achieved through Gram-matrix frameworks and the use of promised sparse QROM to handle the loading of nonzero positions.

Adaptive Lower Bounds

The paper establishes lower bounds using the adaptive Clifford+T framework. For adaptive promised s-sparse QROM, Theorem 5.1 proves a lower bound of omega(√s m) when s ≥ m log2 m. For sparse state preparation, Theorem 5.5 shows that for sufficiently large n and appropriate sparsity constraints, the lower bound is omega(p s log(2n/s) + p s log(1/ε) + log(1/ε)), matching the upper bound in Theorem 4.2. Similarly, for sparse block encodings, Theorem 5.7 yields a lower bound of omegap 2ns log(2n/s) + q 2ns log√s/εBE + log(s/εBE), which matches the upper bound in Theorem 4.4.

Quantum Rejection Sampling

For quantum rejection sampling, the paper shows that the postselection subroutine can be implemented with a T count of O(p s log(1/δ) + log(1/δ) log s) conditioned on success, leading to a state preparation error of O(δ/∥ϵ∥2). This cost is achieved by implementing the rounding scheme using the promised sparse QROM construction.

Sparse Linear Systems Solving

The T-count for solving sparse linear systems is bounded by O(sκ log(1/ε) p 2ns(n + log(sκ/ε)) + log(sκ/ε)), where κ is the condition number. This bound arises from combining the block encoding cost with dense state preparation costs, showing that the complexity scales appropriately with sparsity s and condition number κ.

Conclusion

The paper concludes by summarizing that the worst-case complexity is dominated by these lower bounds, confirming that t = omegap 2ns log(2n/s) + q 2ns log√s/εBE + log(s/εBE). This confirms the asymptotic optimality of the derived T-count bounds for sparse quantum data loading and related tasks.

Improvements for AI systems

As a fastidious researcher, I have thoroughly analyzed this paper, Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding. The core contribution is establishing asymptotically optimal T-count bounds for quantum algorithms that require coherent access to sparse classical data (Sparse QROM), specifically for state preparation and block encoding.

Here are the specific improvements you can make to AI systems, categorized by the application areas discussed in Section 4:

)1. Sparse State Preparation Improvements (Application 4.1 & Theorem 4.2):

The paper proves that an s-sparse n-qubit state can be prepared with a matching T count of:

O(√sn + ps log(1/ε) + log(1/ε) + n)

This is a significant improvement over the general dense state preparation bound, which was previously thought to be O(p2n log 1/ε).

  • The improved AI system can prepare high-fidelity quantum states (up to trace-distance error ε) that are defined by sparse classical data (like low-rank representations or specific parameterizations).

  • This allows for the construction of quantum machine learning models where the training data or target distribution is inherently sparse, such as Sparse Quantum Kernel Methods.

  • The system can utilize compressed state preparation algorithms: first preparing a compressed state on a few qubits, loading support labels via QROM, and then erasing them using inverse promised QROM to reach the full n-qubit state. This suggests an efficient way to encode complex data structures into quantum states with minimal T-gate overhead.

)2. Sparse Block Encoding Improvements (Application 4.2 & Theorem 4.4):

The paper provides a tight bound for block encoding sparse matrices:

O(√2nsn + p2ns log(s/εBE) + log(s/εBE))

This is crucial for algorithms that operate on structured, sparse data representations of large matrices (e.g., in quantum chemistry or linear algebra).

  • The improved AI system can perform quantum simulations of Hamiltonians governed by sparse matrices (like those found in condensed matter physics) with a T-count scaling proportional to the square root of the matrix dimension and sparsity, rather than linearly or quadratically.

  • It enables efficient solving of sparse linear systems: The bound O(sκ log(1/ε) p2ns(n + log(sκ/ε)) + log sκ/ε) is tighter than previous bounds for solving these systems, allowing for faster convergence in quantum linear system solvers.

  • The system can efficiently implement Quantum Singular Value Transformation (QSVT), which is used to find the dominant features of sparse matrices, enabling more efficient matrix inversion and regularization techniques in quantum machine learning.

)3. Quantum Rejection Sampling Improvements (Application 4.3 & Theorem 4.13):

For rejection sampling, the T-count bound is:

O(ps log(1/δ) + log(1/δ) log s / ε2)

This allows for more efficient quantum sampling procedures when the underlying data distribution (or label distribution) is sparse.

  • The AI system can perform Monte Carlo simulations or cryptographic tasks that rely on sampling from sparse distributions (e.g., certain Bayesian inference problems).

  • It enables the preparation of samples with a guaranteed trace-distance error O(δ/ε2), which is a measure of how close the sampled state is to the target distribution, allowing for high-quality probabilistic outputs in complex quantum sampling scenarios.

In summary, this paper provides mathematically rigorous and asymptotically optimal resource estimates (T counts) for quantum algorithms dealing with sparse classical data. The resulting AI systems will be characterized by:

  1. Efficient synthesis of complex quantum states from sparse classical inputs (Sparse State Preparation).

  2. High-fidelity simulation of large, structured physical systems represented by sparse matrices (Sparse Block Encoding and Hamiltonian Simulation).

  3. Faster convergence in quantum linear algebra problems involving sparse data structures (Quantum Linear System Solving).

Sources

Related papers