Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2608.00414

Sparse Quantum State Preparation with Sublinear T-Count

Jingquan Luo, Lvzhou Li

quant-phSubmitted Aug 1, 2026• Announced Aug 4, 2026• 0 citations
arXivHTMLPDF

Abstract

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 $Θ(\sqrt{2^n\log(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 $\widetilde{O}(\min\{s,\ n^{3/4}\sqrt{s}\}+\sqrt{s\log(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<ε\le 1/6$ and $2\le s\le 2^{n/2}$, sparse-state preparation requires $Ω(\min\{s,\sqrt{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.

Related papers

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

Tongyang Li, Fengning Ou, Xinzhao Wang +3 more

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.

quant-pharXiv:2607.28260•Jul 31, 2026•0 citations

Resource-Efficient Synthesis of Sparse Quantum States

Renaud Vilmart, Sunheang Ty, Chetra Mang

Preparing a quantum circuit that implements a given sparse state is an important building block that is necessary for many different quantum algorithms. In the context of fault-tolerant quantum computing, the so-called non-Clifford gates are much more expensive to perform than the Clifford ones. We hence provide an algorithm for synthesizing sparse quantum states with a special care for quantum resources. The circuit depth, ancilla count, and crucially non-Clifford count of the circuit produced by the algorithm are all linear in the sparsity when access to arbitrary-angled rotations is given. When compiled down to the standard Clifford+T gate set, several constructions can be given for increasingly better T-count and depth at the expense of a larger number of ancillae. The most optimised construction for T-count reaches $\mathcal O\left(s+\log_2(1/ε)\right)$ T gates for error $ε$. The constructions are broken into two parts, one that synthesises a generalized W-state, well studied in the literature; and the second which is a classical reversible circuit implementing a permutation that maps the basis states of the W-state to those of the target sparse quantum state. We reduce this problem to the diagonalization of a binary matrix, using a specific set of elementary matrix operations corresponding to the classical reversible gates. We then solve this problem using a new version of Gauss-Jordan elimination, that minimizes the circuit complexities including circuit depth using parallel elimination steps. When the circuit is applied in one direction, we notice that all occurrences of (the expensive) Toffoli gates can all be replaced by adaptive Clifford circuits, leading to a better non-Clifford count.

arXiv:2508.05386•Aug 7, 2025•0 citations

Trading T gates for dirty qubits in state preparation and unitary synthesis

Guang Hao Low, Vadym Kliuchnikov, Luke Schaeffer

Efficient synthesis of arbitrary quantum states and unitaries from a universal fault-tolerant gate-set e.g. Clifford+T is a key subroutine in quantum computation. As large quantum algorithms feature many qubits that encode coherent quantum information but remain idle for parts of the computation, these should be used if it minimizes overall gate counts, especially that of the expensive T-gates. We present a quantum algorithm for preparing any dimension- N pure quantum state specified by a list of N classical numbers, that realizes a trade-off between space and T-gates. Our scheme uses O ( log ⁡ ( N / ϵ ) ) clean qubits and a tunable number of ∼ ( λ log ⁡ ( log ⁡ N ϵ ) ) dirty qubits, to reduce the T-gate cost to O ( N λ + λ log ⁡ N ϵ log ⁡ log ⁡ N ϵ ) . This trade-off is optimal up to logarithmic factors, proven through an unconditional gate counting lower bound, and is, in the best case, a quadratic improvement in T-count over prior ancillary-free approaches. We prove similar statements for unitary synthesis by reduction to state preparation. Underlying our constructions is a T-efficient circuit implementation of a quantum oracle for arbitrary classical data.

arXiv:1812.00954•Quantum•Jun 17, 2024•74 citations

Clifford-efficient sparse state preparation for molecular wavefunctions

Yingrong Chen, Nathan A. Baker, Rushi Gong +7 more

Sparse quantum state preparation concerns an $n$-qubit target state that is a superposition of only $d \ll 2^n$ computational basis states. Existing approaches exploit this sparsity by compressing these $d$ basis states and their amplitudes onto a smaller set of qubits, called the dense register, before expanding the prepared state to the full register. Rather than relying on the permutation-based compression used in prior work, we exploit affine relationships among the binary configurations over the finite field $\operatorname{GF}(2)$ to reduce both the non-Clifford gate count and the ancillary qubit count. Invertible affine transformations over $\operatorname{GF}(2)$, comprising Gaussian elimination and all-ones-row removal, first reduce the dense register from $n$ to the rank $r$ using only Clifford gates and no ancillary qubits. An optional binary encoding stage then trades additional Toffoli gates and ancillary qubits for further compression to the minimum $\lceil\log_2 d\rceil$ dense qubits needed to represent $d$ distinct configurations. For chemically relevant wavefunctions, such as those obtained from selected configuration interaction calculations, shared electronic excitation patterns produce many of these affine relationships, enabling substantial Clifford-only compression before binary encoding. Across the molecular benchmarks, our method requires the fewest ancillary qubits among the evaluated sparse state preparation methods while maintaining comparable non-Clifford gate counts when using binary encoding.

quant-pharXiv:2608.20593•Aug 24, 2026•0 citations

Sparse quantum state preparation with improved Toffoli cost

Felix Rupprecht, Sabine Wölk

The preparation of quantum states is one of the most fundamental tasks in quantum computing, and a key primitive in many quantum algorithms. Of particular interest to areas such as quantum simulation and linear-system solvers are sparse quantum states, which contain only a small number $s$ of non-zero computational basis states compared to a generic state. In this work, we present an approach that prepares $s$-sparse states on $n$ qubits, reducing the number of Toffoli gates required compared to prior art. We work in the established framework of first preparing a dense state on a $\lceil{\log(s)}\rceil$-qubit sub-register, and then mapping this state to the target state via an isometry, with the latter step dominating the cost of the full algorithm. The speed-up is achieved by designing an efficient algorithm for finding and implementing the isometry. The worst-case Toffoli cost of our isometry circuit, which may be viewed as a batched version of an approach by Malvetti et al., is essentially $2s$ for sufficiently large values of $n$, yielding roughly a $\log(s)/2$ improvement factor over the state-of-the-art. In numerical benchmarks on randomly chosen states, the cost is closer to $s$. With the improved isometry circuit, we examine the dense-state preparation step and present ways to optimize the joint cost of both steps, particularly in the case of target states with purely real coefficients, by outsourcing some sub-tasks from the dense-state preparation to the isometry.

quant-pharXiv:2601.09388•Quantum•Jan 15, 2026•0 citations

Nearly Optimal Circuit Size for Sparse Quantum State Preparation

Lvzhou Li, Jingquan Luo

Quantum state preparation is a fundamental and significant subroutine in quantum computing. In this paper, we conduct a systematic investigation on the circuit size (the total count of elementary gates in the circuit) for sparse quantum state preparation. A quantum state is said to be $d$-sparse if it has only $d$ non-zero amplitudes. For the task of preparing an $n$-qubit $d$-sparse quantum state, we obtain the following results: \textbf{Without ancillary qubits:} Any $n$-qubit $d$-sparse quantum state can be prepared by a quantum circuit of size $O(\frac{nd}{\log n} + n)$ without using ancillary qubits, which improves the previous best results. It is asymptotically optimal when $d = \mathrm{poly}(n)$, and this optimality holds for a broader scope under some reasonable assumptions. \textbf{With limited ancillary qubits:} (i) Based on the first result, we prove for the first time a trade-off between the number of ancillary qubits and the circuit size: any $n$-qubit $d$-sparse quantum state can be prepared by a quantum circuit of size $O(\frac{nd}{\log (n + m)} + n)$ using $m$ ancillary qubits for any $m \in O(\frac{nd}{\log nd} + n)$. (ii) We establish a matching lower bound $Ω(\frac{nd}{\log {(n + m)} }+ n)$ under some reasonable assumptions, and obtain a slightly weaker lower bound $Ω(\frac{nd}{\log {(n + m)} + \log d} + n)$ without any assumptions. \textbf{With unlimited ancillary qubits:} Given arbitrary amount of ancillary qubits available, the circuit size for preparing $n$-qubit $d$-sparse quantum states is $Θ(\frac{nd}{\log nd} + n)$.

arXiv:2406.16142•Leibniz international proceedings in informatics•Jun 23, 2024•2 citations
We study the fault-tolerant cost of preparing sparse quantum states, measured by TTT-count in the Clifford+TTT model. Here an nnn-qubit state is called sss-sparse if it is supported on at most sss computational-basis states. For arbitrary nnn-qubit states, the optimal TTT-count is Θ(2nlog⁡(1/ε)+log⁡(1/ε))Θ(\sqrt{2^n\log(1/ε)}+\log(1/ε))Θ(2nlog(1/ε)​+log(1/ε)), but for sss-sparse states the best previous upper bounds remained linear in sss. We show that any nnn-qubit sss-sparse state can be prepared up to error εεε using O~(min⁡{s, n3/4s}+slog⁡(1/ε)+log⁡(1/ε))\widetilde{O}(\min\{s,\ n^{3/4}\sqrt{s}\}+\sqrt{s\log(1/ε)}+\log(1/ε))O(min{s, n3/4s​}+slog(1/ε)​+log(1/ε)) TTT gates, giving the first sublinear dependence on sss 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/60<ε\le 1/60<ε≤1/6 and 2≤s≤2n/22\le s\le 2^{n/2}2≤s≤2n/2, sparse-state preparation requires Ω(min⁡{s,ns})Ω(\min\{s,\sqrt{ns}\})Ω(min{s,ns​}) TTT gates, showing that linear dependence on sss is unavoidable in the small-support regime and substantially narrowing the gap between the known upper and lower bounds within this parameter range.
Many quantum algorithms require coherent access to classical data, often modeled by quantum read-only memory (QROM). We initiate the study of the T\mathrm{T}T count of sparse QROM, in which only sss of the 2n2^n2n addresses store nonzero data. We prove that the optimal T\mathrm{T}T count is Θ(n+min⁡{s,s(m+log⁡(2n+1/s))})Θ\left(n+\min\left\{s,\sqrt{s\left(m+\log(2^{n+1}/s)\right)}\right\}\right)Θ(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\mathrm{T}T circuits. The lower bounds thus hold even when mid-circuit measurements and classically controlled operations are allowed. As applications, we obtain matching T\mathrm{T}T-count bounds Θ(min⁡{s,slog⁡(2n+1/s)}+slog⁡(1/ε)+log⁡(1/ε))Θ\left(\min\left\{s,\sqrt{s\log(2^{n+1}/s)}\right\} +\sqrt{s\log(1/\varepsilon)}+\log(1/\varepsilon)\right)Θ(min{s,slog(2n+1/s)​}+slog(1/ε)​+log(1/ε)) for sss-sparse state preparation and Θ(2ns(n+log⁡(1/εBE))+log⁡(1/εBE))Θ\left(\sqrt{2^n s\left(n+\log(1/\varepsilon_{\rm BE})\right)} +\log(1/\varepsilon_{\rm BE})\right)Θ(2ns(n+log(1/εBE​))​+log(1/εBE​)) for block encoding of sss-sparse matrices, where ε\varepsilonε and εBE\varepsilon_{\rm BE}εBE​ are the precision of state preparation and block encoding, respectively.
Preparing a quantum circuit that implements a given sparse state is an important building block that is necessary for many different quantum algorithms. In the context of fault-tolerant quantum computing, the so-called non-Clifford gates are much more expensive to perform than the Clifford ones. We hence provide an algorithm for synthesizing sparse quantum states with a special care for quantum resources. The circuit depth, ancilla count, and crucially non-Clifford count of the circuit produced by the algorithm are all linear in the sparsity when access to arbitrary-angled rotations is given. When compiled down to the standard Clifford+T gate set, several constructions can be given for increasingly better T-count and depth at the expense of a larger number of ancillae. The most optimised construction for T-count reaches O(s+log⁡2(1/ε))\mathcal O\left(s+\log_2(1/ε)\right)O(s+log2​(1/ε)) T gates for error εεε. The constructions are broken into two parts, one that synthesises a generalized W-state, well studied in the literature; and the second which is a classical reversible circuit implementing a permutation that maps the basis states of the W-state to those of the target sparse quantum state. We reduce this problem to the diagonalization of a binary matrix, using a specific set of elementary matrix operations corresponding to the classical reversible gates. We then solve this problem using a new version of Gauss-Jordan elimination, that minimizes the circuit complexities including circuit depth using parallel elimination steps. When the circuit is applied in one direction, we notice that all occurrences of (the expensive) Toffoli gates can all be replaced by adaptive Clifford circuits, leading to a better non-Clifford count.
Efficient synthesis of arbitrary quantum states and unitaries from a universal fault-tolerant gate-set e.g. Clifford+T is a key subroutine in quantum computation. As large quantum algorithms feature many qubits that encode coherent quantum information but remain idle for parts of the computation, these should be used if it minimizes overall gate counts, especially that of the expensive T-gates. We present a quantum algorithm for preparing any dimension- N pure quantum state specified by a list of N classical numbers, that realizes a trade-off between space and T-gates. Our scheme uses O ( log ⁡ ( N / ϵ ) ) clean qubits and a tunable number of ∼ ( λ log ⁡ ( log ⁡ N ϵ ) ) dirty qubits, to reduce the T-gate cost to O ( N λ + λ log ⁡ N ϵ log ⁡ log ⁡ N ϵ ) . This trade-off is optimal up to logarithmic factors, proven through an unconditional gate counting lower bound, and is, in the best case, a quadratic improvement in T-count over prior ancillary-free approaches. We prove similar statements for unitary synthesis by reduction to state preparation. Underlying our constructions is a T-efficient circuit implementation of a quantum oracle for arbitrary classical data.
Sparse quantum state preparation concerns an nnn-qubit target state that is a superposition of only d≪2nd \ll 2^nd≪2n computational basis states. Existing approaches exploit this sparsity by compressing these ddd basis states and their amplitudes onto a smaller set of qubits, called the dense register, before expanding the prepared state to the full register. Rather than relying on the permutation-based compression used in prior work, we exploit affine relationships among the binary configurations over the finite field GF⁡(2)\operatorname{GF}(2)GF(2) to reduce both the non-Clifford gate count and the ancillary qubit count. Invertible affine transformations over GF⁡(2)\operatorname{GF}(2)GF(2), comprising Gaussian elimination and all-ones-row removal, first reduce the dense register from nnn to the rank rrr using only Clifford gates and no ancillary qubits. An optional binary encoding stage then trades additional Toffoli gates and ancillary qubits for further compression to the minimum ⌈log⁡2d⌉\lceil\log_2 d\rceil⌈log2​d⌉ dense qubits needed to represent ddd distinct configurations. For chemically relevant wavefunctions, such as those obtained from selected configuration interaction calculations, shared electronic excitation patterns produce many of these affine relationships, enabling substantial Clifford-only compression before binary encoding. Across the molecular benchmarks, our method requires the fewest ancillary qubits among the evaluated sparse state preparation methods while maintaining comparable non-Clifford gate counts when using binary encoding.
The preparation of quantum states is one of the most fundamental tasks in quantum computing, and a key primitive in many quantum algorithms. Of particular interest to areas such as quantum simulation and linear-system solvers are sparse quantum states, which contain only a small number sss of non-zero computational basis states compared to a generic state. In this work, we present an approach that prepares sss-sparse states on nnn qubits, reducing the number of Toffoli gates required compared to prior art. We work in the established framework of first preparing a dense state on a ⌈log⁡(s)⌉\lceil{\log(s)}\rceil⌈log(s)⌉-qubit sub-register, and then mapping this state to the target state via an isometry, with the latter step dominating the cost of the full algorithm. The speed-up is achieved by designing an efficient algorithm for finding and implementing the isometry. The worst-case Toffoli cost of our isometry circuit, which may be viewed as a batched version of an approach by Malvetti et al., is essentially 2s2s2s for sufficiently large values of nnn, yielding roughly a log⁡(s)/2\log(s)/2log(s)/2 improvement factor over the state-of-the-art. In numerical benchmarks on randomly chosen states, the cost is closer to sss. With the improved isometry circuit, we examine the dense-state preparation step and present ways to optimize the joint cost of both steps, particularly in the case of target states with purely real coefficients, by outsourcing some sub-tasks from the dense-state preparation to the isometry.
Quantum state preparation is a fundamental and significant subroutine in quantum computing. In this paper, we conduct a systematic investigation on the circuit size (the total count of elementary gates in the circuit) for sparse quantum state preparation. A quantum state is said to be ddd-sparse if it has only ddd non-zero amplitudes. For the task of preparing an nnn-qubit ddd-sparse quantum state, we obtain the following results: \textbf{Without ancillary qubits:} Any nnn-qubit ddd-sparse quantum state can be prepared by a quantum circuit of size O(ndlog⁡n+n)O(\frac{nd}{\log n} + n)O(lognnd​+n) without using ancillary qubits, which improves the previous best results. It is asymptotically optimal when d=poly(n)d = \mathrm{poly}(n)d=poly(n), and this optimality holds for a broader scope under some reasonable assumptions. \textbf{With limited ancillary qubits:} (i) Based on the first result, we prove for the first time a trade-off between the number of ancillary qubits and the circuit size: any nnn-qubit ddd-sparse quantum state can be prepared by a quantum circuit of size O(ndlog⁡(n+m)+n)O(\frac{nd}{\log (n + m)} + n)O(log(n+m)nd​+n) using mmm ancillary qubits for any m∈O(ndlog⁡nd+n)m \in O(\frac{nd}{\log nd} + n)m∈O(logndnd​+n). (ii) We establish a matching lower bound Ω(ndlog⁡(n+m)+n)Ω(\frac{nd}{\log {(n + m)} }+ n)Ω(log(n+m)nd​+n) under some reasonable assumptions, and obtain a slightly weaker lower bound Ω(ndlog⁡(n+m)+log⁡d+n)Ω(\frac{nd}{\log {(n + m)} + \log d} + n)Ω(log(n+m)+logdnd​+n) without any assumptions. \textbf{With unlimited ancillary qubits:} Given arbitrary amount of ancillary qubits available, the circuit size for preparing nnn-qubit ddd-sparse quantum states is Θ(ndlog⁡nd+n)Θ(\frac{nd}{\log nd} + n)Θ(logndnd​+n).