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:2406.16142 · Leibniz international proceedings in informatics

Nearly Optimal Circuit Size for Sparse Quantum State Preparation

Lvzhou Li, Jingquan Luo

Published Jun 23, 2024• 2 citations
arXivHTMLPDF

Abstract

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)$.

DOI
10.4230/lipics.icalp.2025.113

Related papers

Towards Optimal Circuit Size for Sparse Quantum State Preparation

Mao, Rui, Guojing Tian, Xiaoming Sun

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$ non-zero amplitudes and propose two algorithms. The first algorithm uses $O(ns/\log n + n)$ gates, improving upon previous methods by $O(\log n)$. We further establish a matching lower bound for any algorithm which is not amplitude-aware and employs at most $\operatorname{poly}(n)$ ancillary qubits. The second algorithm is tailored for binary strings that exhibit a short Hamiltonian path. An application is the preparation of $U(1)$-invariant state with $k$ down-spins in a chain of length $n$, including Bethe states, for which our algorithm constructs a circuit of size $O\left(\binom{n}{k}\log n\right)$. This surpasses previous results by $O(n/\log n)$ and is close to the lower bound $O\left(\binom{n}{k}\right)$. Both the two algorithms shrink the existing gap theoretically and provide increasing advantages numerically.

arXiv:2404.05147•Apr 8, 2024•0 citations

Toward optimal circuit size for sparse quantum state preparation

Rui Mao, Guojing Tian, Xiaoming Sun

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/{log}_{2}n+n)$ gates, improving upon previous methods by $O({log}_{2}n)$. 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(\left(\genfrac{}{}{0pt}{}{n}{k}\right){log}_{2}n)$. This surpasses previous results by $O(k/{log}_{2}n)$ and is close to the lower bound $O(\left(\genfrac{}{}{0pt}{}{n}{k}\right))$. The classical runtime is also nearly optimal. Both algorithms shrink the existing gap theoretically and provide increasing advantages numerically.

Physical Review A•Sep 30, 2024•11 citations

Sparse Quantum State Preparation with Sublinear T-Count

Jingquan Luo, Lvzhou Li

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.

quant-pharXiv:2608.00414•Aug 4, 2026•0 citations

Space-time tradeoff for sparse quantum state preparation

Luo, Jingquan, Li, Guanzhong, Li, Lvzhou

In this work, we investigate the trade-off between the circuit depth and the number of ancillary qubits for preparing sparse quantum states. We prove that any $n$-qubit $d$-spare quantum state (i.e., it has only $d$ non-zero amplitudes) can be prepared by a quantum circuit with depth $O\left(\frac{nd \log m}{m \log m/n} + \log nd\right)$ using $m\geq 6n$ ancillary qubits, which achieves the current best trade-off between depth and ancilla number. In particular, when $m = Θ({\frac{nd}{\log d}})$, our result recovers the optimal circuit depth $Θ(\log nd)$ given in \hyperlink{cite.zhang2022quantum}{[Phys. Rev. Lett., 129, 230504(2022)]}, but using significantly fewer gates and ancillary qubits.

arXiv:2506.16964•Jun 20, 2025•0 citations

Algebraic Reduction to Improve an Optimally Bounded Quantum State Preparation Algorithm

Giacomo Belli, Michele Amoretti

The preparation of $n$-qubit quantum states is a cross-cutting subroutine for many quantum algorithms, and the effort to reduce its circuit complexity is a significant challenge. In the literature, the quantum state preparation algorithm by Sun et al. is known to be optimally bounded, defining the asymptotically optimal width-depth trade-off bounds with and without ancillary qubits. In this work, a simpler algebraic decomposition is proposed to separate the preparation of the real part of the desired state from the complex one, resulting in a reduction in terms of circuit depth, total gates, and CNOT count when $m$ ancillary qubits are available. The reduction in complexity is due to the use of a single operator $Λ$ for each uniformly controlled gate, instead of the three in the original decomposition. Using the PennyLane library, this new algorithm for state preparation has been implemented and tested in a simulated environment for both dense and sparse quantum states, including those that are random and of physical interest. Furthermore, its performance has been compared with that of Möttönen et al.'s algorithm, which is a de facto standard for preparing quantum states in cases where no ancillary qubits are used, highlighting interesting lines of development.

quant-pharXiv:2602.06535•Feb 9, 2026•0 citations

Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications

Xiao‐Ming Zhang, Tongyang Li, Xiao Yuan

Quantum state preparation is an important subroutine for quantum computing. We show that any n-qubit quantum state can be prepared with a Θ(n)-depth circuit using only single- and two-qubit gates, although with a cost of an exponential amount of ancillary qubits. On the other hand, for sparse quantum states with d⩾2 nonzero entries, we can reduce the circuit depth to Θ(log(nd)) with O(ndlogd) ancillary qubits. The algorithm for sparse states is exponentially faster than best-known results and the number of ancillary qubits is nearly optimal and only increases polynomially with the system size. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories, and find cases with exponential reductions of the circuit depth for all these three tasks. In particular, using our algorithm, we find a family of linear system solving problems enjoying exponential speedups, even compared to the best-known quantum and classical dequantization algorithms.

arXiv:2201.11495•Physical Review Letters•Nov 30, 2022•176 citations
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).
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 nnn-qubit sparse quantum states with sss non-zero amplitudes and propose two algorithms. The first algorithm uses O(ns/log⁡n+n)O(ns/\log n + n)O(ns/logn+n) gates, improving upon previous methods by O(log⁡n)O(\log n)O(logn). We further establish a matching lower bound for any algorithm which is not amplitude-aware and employs at most poly⁡(n)\operatorname{poly}(n)poly(n) ancillary qubits. The second algorithm is tailored for binary strings that exhibit a short Hamiltonian path. An application is the preparation of U(1)U(1)U(1)-invariant state with kkk down-spins in a chain of length nnn, including Bethe states, for which our algorithm constructs a circuit of size O((nk)log⁡n)O\left(\binom{n}{k}\log n\right)O((kn​)logn). This surpasses previous results by O(n/log⁡n)O(n/\log n)O(n/logn) and is close to the lower bound O((nk))O\left(\binom{n}{k}\right)O((kn​)). Both the two algorithms shrink the existing gap theoretically and provide increasing advantages numerically.
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 nnn-qubit sparse quantum states with sss nonzero amplitudes and propose two algorithms. The first algorithm uses O(ns/log2n+n)O(ns/{log}_{2}n+n)O(ns/log2​n+n) gates, improving upon previous methods by O(log2n)O({log}_{2}n)O(log2​n). 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)poly(n)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 kkk in quantum machine learning, for which our algorithm constructs a circuit of size O((nk)log2n)O(\left(\genfrac{}{}{0pt}{}{n}{k}\right){log}_{2}n)O((kn​)log2​n). This surpasses previous results by O(k/log2n)O(k/{log}_{2}n)O(k/log2​n) and is close to the lower bound O((nk))O(\left(\genfrac{}{}{0pt}{}{n}{k}\right))O((kn​)). The classical runtime is also nearly optimal. Both algorithms shrink the existing gap theoretically and provide increasing advantages numerically.
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.
In this work, we investigate the trade-off between the circuit depth and the number of ancillary qubits for preparing sparse quantum states. We prove that any nnn-qubit ddd-spare quantum state (i.e., it has only ddd non-zero amplitudes) can be prepared by a quantum circuit with depth O(ndlog⁡mmlog⁡m/n+log⁡nd)O\left(\frac{nd \log m}{m \log m/n} + \log nd\right)O(mlogm/nndlogm​+lognd) using m≥6nm\geq 6nm≥6n ancillary qubits, which achieves the current best trade-off between depth and ancilla number. In particular, when m=Θ(ndlog⁡d)m = Θ({\frac{nd}{\log d}})m=Θ(logdnd​), our result recovers the optimal circuit depth Θ(log⁡nd)Θ(\log nd)Θ(lognd) given in \hyperlink{cite.zhang2022quantum}{[Phys. Rev. Lett., 129, 230504(2022)]}, but using significantly fewer gates and ancillary qubits.
The preparation of nnn-qubit quantum states is a cross-cutting subroutine for many quantum algorithms, and the effort to reduce its circuit complexity is a significant challenge. In the literature, the quantum state preparation algorithm by Sun et al. is known to be optimally bounded, defining the asymptotically optimal width-depth trade-off bounds with and without ancillary qubits. In this work, a simpler algebraic decomposition is proposed to separate the preparation of the real part of the desired state from the complex one, resulting in a reduction in terms of circuit depth, total gates, and CNOT count when mmm ancillary qubits are available. The reduction in complexity is due to the use of a single operator ΛΛΛ for each uniformly controlled gate, instead of the three in the original decomposition. Using the PennyLane library, this new algorithm for state preparation has been implemented and tested in a simulated environment for both dense and sparse quantum states, including those that are random and of physical interest. Furthermore, its performance has been compared with that of Möttönen et al.'s algorithm, which is a de facto standard for preparing quantum states in cases where no ancillary qubits are used, highlighting interesting lines of development.
Quantum state preparation is an important subroutine for quantum computing. We show that any n-qubit quantum state can be prepared with a Θ(n)-depth circuit using only single- and two-qubit gates, although with a cost of an exponential amount of ancillary qubits. On the other hand, for sparse quantum states with d⩾2 nonzero entries, we can reduce the circuit depth to Θ(log(nd)) with O(ndlogd) ancillary qubits. The algorithm for sparse states is exponentially faster than best-known results and the number of ancillary qubits is nearly optimal and only increases polynomially with the system size. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories, and find cases with exponential reductions of the circuit depth for all these three tasks. In particular, using our algorithm, we find a family of linear system solving problems enjoying exponential speedups, even compared to the best-known quantum and classical dequantization algorithms.