Many quantum algorithms require coherent access to classical data, often modeled by quantum read-only memory (QROM). We initiate the study of the $\mathrm{T}$ count of sparse QROM, in which only $s$ of the $2^n$ addresses store nonzero data. We prove that the optimal $\mathrm{T}$ count is $Θ\left(n+\min\left\{s,\sqrt{s\left(m+\log(2^{n+1}/s)\right)}\right\}\right)$. Our upper bounds use a multilevel hashing scheme, while our lower bounds reduce sparse QROM to state preparation and use counting arguments for adaptive Clifford+$\mathrm{T}$ circuits. The lower bounds thus hold even when mid-circuit measurements and classically controlled operations are allowed. As applications, we obtain matching $\mathrm{T}$-count bounds $Θ\left(\min\left\{s,\sqrt{s\log(2^{n+1}/s)}\right\} +\sqrt{s\log(1/\varepsilon)}+\log(1/\varepsilon)\right)$ for $s$-sparse state preparation and $Θ\left(\sqrt{2^n s\left(n+\log(1/\varepsilon_{\rm BE})\right)} +\log(1/\varepsilon_{\rm BE})\right)$ for block encoding of $s$-sparse matrices, where $\varepsilon$ and $\varepsilon_{\rm BE}$ are the precision of state preparation and block encoding, respectively.
Many quantum algorithms require coherent access to classical data, often modeled by quantum read-only memory (QROM). We initiate the study of the T count of sparse QROM, in which only s of the 2n addresses store nonzero data. We prove that the optimal T count is Θ(n+min{s,s(m+log(2n+1/s))}). Our upper bounds use a multilevel hashing scheme, while our lower bounds reduce sparse QROM to state preparation and use counting arguments for adaptive Clifford+T circuits. The lower bounds thus hold even when mid-circuit measurements and classically controlled operations are allowed. As applications, we obtain matching T-count bounds Θ(min{s,slog(2n+1/s)}+slog(1/ε)+log(1/ε)) for s-sparse state preparation and Θ(2ns(n+log(1/εBE))+log(1/εBE)) for block encoding of s-sparse matrices, where ε and εBE are the precision of state preparation and block encoding, respectively.
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 Θ(2nlog(1/ε)+log(1/ε)), 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 ε using O(min{s,n3/4s}+slog(1/ε)+log(1/ε))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<ε≤1/6 and 2≤s≤2n/2, sparse-state preparation requires Ω(min{s,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.
We determine the non-Clifford T-gate cost of constructing block encodings of structured fermionic and spin Hamiltonians in a unitary Clifford+T model, when arbitrarily many clean ancillas and unrestricted block-encoding subnormalization are allowed, but without mid-circuit measurements or classical feed-forward. Our main technical tool is an ancilla-compression theorem: any block encoding of an n-qubit operator with a clean ancillas and at most sT gates can be compressed to use at most min{a,n+2s} ancillas, without increasing the absolute error or T-count. For general second-quantized Hamiltonians with bounded one- and two-body coefficients, at operator-norm block-encoding error ε, a volume-covering argument combined with circuit counting gives the worst-case lower bound Ω(n2log(n4/ε)), matching the existing upper bound at fixed precision. For the bond-dependent Kitaev honeycomb family on n spins, we obtain independent lower bounds Ω(n) from stabilizer nullity and Ω(log(1/ε)) from one-qubit state preparation, established using different Hamiltonian instances. Together with an explicit LCU construction, they give the tight worst-case scaling Θ(n+log(1/ε)). As an application, we evaluate the T-count of a Hamiltonian simulation circuit based on quantum singular value transformation, with each block-encoding query compiled separately. When phase synthesis and controlled queries add at most constant-factor overhead, the simulation T-count scales as the query count times the optimal T-count per query.
Compared to general quantum states, the sparse states arise more frequently in the field of quantum computation. In this work we consider the preparation for n-qubit sparse quantum states with s nonzero amplitudes and propose two algorithms. The first algorithm uses O(ns/log2n+n) gates, improving upon previous methods by O(log2n). Moreover, the classical runtime of this algorithm is optimal. We further establish a matching lower bound for any algorithm that is not amplitude aware and employs at most poly(n) ancillary qubits. The second algorithm is tailored for binary strings that exhibit a short Hamiltonian path. An application is encoding the input data into a state with specified Hamming weight k in quantum machine learning, for which our algorithm constructs a circuit of size O((kn)log2n). This surpasses previous results by O(k/log2n) and is close to the lower bound O((kn)). The classical runtime is also nearly optimal. Both algorithms shrink the existing gap theoretically and provide increasing advantages numerically.
Quantum state preparation and block encoding are versatile and practical input models for quantum algorithms in scientific computing. The circuit complexity of state preparation and block encoding frequently dominates the end-to-end gate complexity of quantum algorithms. We give algorithms with lower C-NOT counts for both the state preparation and block encoding. For a general n-qubit state, we improve the C-NOT count of the Plesch-Brukner algorithm (2011) from (23/24)×2n to (11/12)×2n. For block encoding, our single-ancilla protocol for 2n−1×2n−1 matrices uses the spectral norm as subnormalization and achieves a C-NOT count leading term (11/48)×4n. Further optimization is performed for low-rank matrices, which frequently arise in practical applications. Specifically, we achieve the C-NOT count leading term (2⌈log2K⌉+(11/12))×2n for a rank-K matrix. This is the first quantum algorithm that encodes matrices using the optimal normalization factor while also allowing the C-NOT count to be adjusted according to the matrix rank. Our approach builds upon the recursive Block-ZXZ decomposition from Krol et al. (2024) and introduces a diagonal matrix migration technique based on the commutativity of the diagonal matrix and the uniformly controlled rotation about the z-axis to minimize the use of C-NOT gates.
Abstract How to efficiently encode classical data is a fundamental task in quantum computing. While many existing works treat classical data encoding as a black box in oracle-based quantum algorithms, their explicit constructions are crucial for the efficiency of practical algorithm implementations. Here, we unveil the mystery of the classical data encoding black box and study the Clifford + T complexity in constructing several typical quantum access models. For general matrices (even including sparse ones), we prove that sparse-access input models and block-encoding both require nearly linear circuit complexities relative to the matrix dimension. We also give construction protocols achieving near-optimal gate complexities. On the other hand, the construction becomes efficient with respect to the data qubit when the matrix is a linear combination of polynomial terms of efficiently implementable unitaries. As a typical example, we propose improved block-encoding when these unitaries are Pauli strings. Our protocols are built upon improved quantum state preparation and a select oracle for Pauli strings, which hold independent values. Our access model constructions provide considerable flexibility, allowing for tunable ancillary qubit numbers and offering corresponding space-time trade-offs.
Quantum read only memory (QROM) is a substantial source of non-Clifford cost in fault-tolerant quantum algorithms. Borrowing dirty qubits can reduce this cost, provided their unknown initial states are restored. We consider the practically relevant qubit-constrained regime, where limited workspace restricts the table-block size and table loading dominates the cost. For N entries of b bits and approximately bλ dirty qubits, SelectSwap has leading Toffoli count 2N/λ. Recent work using sequential bit packets reduces this to (1+1/b)N/λ. In this work we introduce a dense encoding construction of QROM, where two bits of classical information are stored in each dirty qubit instead of one by utilizing both the Z and X bases. On its own, dense encoding provides a 2× improvement over SelectSwap by reducing the leading Toffoli count to N/λ. Combining it with sequential bit packets gives 21(1+1/b)N/λ, a further halving of the sequential construction's leading cost, and an approximately 4× improvement over SelectSwap in the large-N limit for practical values of b.