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:2404.05147

Towards Optimal Circuit Size for Sparse Quantum State Preparation

Mao, Rui, Guojing Tian, Xiaoming Sun

Published Apr 8, 2024• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2404.05147

Related papers

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

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

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

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

Circuit-based quantum random access memory for sparse quantum state preparation

Tiago M. L. Veras

In order to use a quantum device to assess a classical dataset D, we need to representthe set D in a quantum state. Applying a quantum algorithm, that is a quantum state preparation algorithm, to convert classical data into quantum data would be the common method. Loading classical data into a quantum device is required in many current applications. Efficiently preparing a quantum state to be used as the initial state of a quantum algorithm is an essential step in developing efficient quantum algorithms, since many algorithms need to reload the initial state several times during their execution. The cost to initialize a quantum state can compromise the algorithm efficiency if the process of quantum states preparation is not efficient. The topic of quantum states preparation in quantum computing has been the focus of much attention. In this scope, preparing sparse quantum states is a more specific problem that remains open since many quantum algorithms also require sparse initialization. This dissertation presents the results of an investigation on sparse quantum states preparation with the development of three algorithms, with highlight to the preparation of sparse quantum states, the main contributionof this dissertation. From a classical input dataset with M patterns formed by pairs composed of a complex number and a binary pattern with n bits, this algorithm can prepare a quantum state with n qubits and continuous amplitudes. The cost of its steps is O(nM), classical cost of o(MlogM+nM)and requires a lower CNOT number than the main quantum state preparation algorithms currently known. The preparation of a quantumstate with 2 non-zero amplitudes reveals the need of fewer CNOT gates in n>>1 relation to the main known state preparation algorithms, with even more favorable results with s higher and less 1S in the binary string.

•Sep 13, 2021•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
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.
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).
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.
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.
In order to use a quantum device to assess a classical dataset D, we need to representthe set D in a quantum state. Applying a quantum algorithm, that is a quantum state preparation algorithm, to convert classical data into quantum data would be the common method. Loading classical data into a quantum device is required in many current applications. Efficiently preparing a quantum state to be used as the initial state of a quantum algorithm is an essential step in developing efficient quantum algorithms, since many algorithms need to reload the initial state several times during their execution. The cost to initialize a quantum state can compromise the algorithm efficiency if the process of quantum states preparation is not efficient. The topic of quantum states preparation in quantum computing has been the focus of much attention. In this scope, preparing sparse quantum states is a more specific problem that remains open since many quantum algorithms also require sparse initialization. This dissertation presents the results of an investigation on sparse quantum states preparation with the development of three algorithms, with highlight to the preparation of sparse quantum states, the main contributionof this dissertation. From a classical input dataset with M patterns formed by pairs composed of a complex number and a binary pattern with n bits, this algorithm can prepare a quantum state with n qubits and continuous amplitudes. The cost of its steps is O(nM), classical cost of o(MlogM+nM)and requires a lower CNOT number than the main quantum state preparation algorithms currently known. The preparation of a quantumstate with 2 non-zero amplitudes reveals the need of fewer CNOT gates in n>>1 relation to the main known state preparation algorithms, with even more favorable results with s higher and less 1S in the binary string.
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.