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

Physical Review A

Toward optimal circuit size for sparse quantum state preparation

Rui Mao, Guojing Tian, Xiaoming Sun

Published Sep 30, 2024• 11 citations
Publisher

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

DOI
10.1103/physreva.110.032439

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

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

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

Exact quantum Hamming-weight computation at optimal depth and minimum width

Wei Zi, Pei Yuan, Junhong Nie

Hamming-weight computation and symmetric Boolean functions are basic primitives for quantum arithmetic and state preparation, where circuit depth and qubit overhead matter. We construct an exact circuit computing the Hamming weight of an $n$-qubit register with depth $O(\log n)$ and size $O(n\log n)$, using only the $n$ input qubits and $m=\lceil\log_2(n+1)\rceil$ binary output qubits. The circuit uses arbitrary one-qubit gates and CNOTs with all-to-all connectivity. Both depth and total width are optimal. Our constructions combine tree structures and pipelining, temporarily using input qubits as workspace. We also give exact circuits for every symmetric Boolean function with the same depth and size bounds, using only $m$ ancillary qubits returned to zero. Finally, we apply the counter to exact preparation of balanced Dicke states for even $n$. With only $O(\log n)$ ancillary qubits, we obtain expected depth $O(\log^2 n)$ using measurements and classical feedforward, and depth $O(n^{1/4}\log n)$ using unitary gates alone.

quant-pharXiv:2610.25315•Oct 20, 2026•0 citations

Low-depth quantum state preparation

Xiao‐Ming Zhang, Man‐Hong Yung, Xiao Yuan

A crucial subroutine in quantum computing is to load the classical data of $N$ complex numbers into the amplitude of a superposed $n=\ensuremath{\lceil}{log}_{2}N\ensuremath{\rceil}$-qubit state. It has been proven that any algorithm universally implementing this subroutine would need at least $O(N)$ constant weight operations. However, the proof assumes that only $n$ qubits are used, whereas the circuit depth could be reduced by extending the space and allowing ancillary qubits. Here we investigate this space-time tradeoff in quantum state preparation with classical data. We propose quantum algorithms with $O({n}^{2})$ circuit depth to encode any $N$ complex numbers using only single- and two-qubit gates, and local measurements with ancillary qubits. Different variances of the algorithm are proposed with different space and runtime. In particular, we present a scheme with $O({N}^{2})$ ancillary qubits, $O({n}^{2})$ circuit depth, and $O({n}^{2})$ average runtime, which exponentially improves the conventional bound. While the algorithm requires more ancillary qubits, it consists of quantum circuit blocks that only simultaneously act on a constant number of qubits, and at most $O(n)$ qubits are entangled. We also prove a fundamental lower bound $\mathrm{\ensuremath{\Omega}}(n)$ for the minimum circuit depth and runtime with an arbitrary number of ancillary qubits, aligning with our scheme with $O({n}^{2})$. The algorithms are expected to have wide applications in both near-term and universal quantum computing.

Physical Review Research•Dec 21, 2021•73 citations

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
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.
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.
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).
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.
Hamming-weight computation and symmetric Boolean functions are basic primitives for quantum arithmetic and state preparation, where circuit depth and qubit overhead matter. We construct an exact circuit computing the Hamming weight of an nnn-qubit register with depth O(log⁡n)O(\log n)O(logn) and size O(nlog⁡n)O(n\log n)O(nlogn), using only the nnn input qubits and m=⌈log⁡2(n+1)⌉m=\lceil\log_2(n+1)\rceilm=⌈log2​(n+1)⌉ binary output qubits. The circuit uses arbitrary one-qubit gates and CNOTs with all-to-all connectivity. Both depth and total width are optimal. Our constructions combine tree structures and pipelining, temporarily using input qubits as workspace. We also give exact circuits for every symmetric Boolean function with the same depth and size bounds, using only mmm ancillary qubits returned to zero. Finally, we apply the counter to exact preparation of balanced Dicke states for even nnn. With only O(log⁡n)O(\log n)O(logn) ancillary qubits, we obtain expected depth O(log⁡2n)O(\log^2 n)O(log2n) using measurements and classical feedforward, and depth O(n1/4log⁡n)O(n^{1/4}\log n)O(n1/4logn) using unitary gates alone.
A crucial subroutine in quantum computing is to load the classical data of NNN complex numbers into the amplitude of a superposed $n=\ensuremath{\lceil}{log}_{2}N\ensuremath{\rceil}$-qubit state. It has been proven that any algorithm universally implementing this subroutine would need at least O(N)O(N)O(N) constant weight operations. However, the proof assumes that only nnn qubits are used, whereas the circuit depth could be reduced by extending the space and allowing ancillary qubits. Here we investigate this space-time tradeoff in quantum state preparation with classical data. We propose quantum algorithms with O(n2)O({n}^{2})O(n2) circuit depth to encode any NNN complex numbers using only single- and two-qubit gates, and local measurements with ancillary qubits. Different variances of the algorithm are proposed with different space and runtime. In particular, we present a scheme with O(N2)O({N}^{2})O(N2) ancillary qubits, O(n2)O({n}^{2})O(n2) circuit depth, and O(n2)O({n}^{2})O(n2) average runtime, which exponentially improves the conventional bound. While the algorithm requires more ancillary qubits, it consists of quantum circuit blocks that only simultaneously act on a constant number of qubits, and at most O(n)O(n)O(n) qubits are entangled. We also prove a fundamental lower bound $\mathrm{\ensuremath{\Omega}}(n)$ for the minimum circuit depth and runtime with an arbitrary number of ancillary qubits, aligning with our scheme with O(n2)O({n}^{2})O(n2). The algorithms are expected to have wide applications in both near-term and universal quantum computing.
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.