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

Optimizing sparse quantum state preparation with measurement and feedforward

Yuan Lü, Han-Hsuan Lin

Published Aug 29, 2025• 0 citations
arXivHTMLPDF

Abstract

Quantum state preparation (QSP) is a key component in many quantum algorithms. In particular, the problem of sparse QSP (SQSP) $\unicode{x2013}$ the task of preparing the states with only a small number of non-zero amplitudes $\unicode{x2013}$ has garnered significant attention in recent years. In this work, we focus on reducing the circuit depth of SQSP with limited number of ancilla qubits. We present two SQSP algorithms: one with depth $O(n\log d)$, and another that reduces depth to $O(n)$. The latter leverages mid-circuit measurement and feedforward, where intermediate measurement outcomes are used to control subsequent quantum operations. Both constructions have size $O(dn)$ and use $O(d)$ ancilla qubits. Compared to the state-of-the-art SQSP algorithm in arXiv:2108.06150, which allows an arbitrary number of ancilla qubits $m>0$, both of our algorithms achieve lower circuit depth when $m=d$.

DOI
10.48550/arxiv.2508.21346

Related papers

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

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

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

Reducing circuit depth in quantum state preparation for quantum simulation using measurements and feedforward

Hyeonjun Yeo, Ha Eum Kim, IlKwon Sohn +1 more

Reducing circuit depth and identifying an optimal trade-off between circuit depth and width is crucial for successful quantum computation. In this context, midcircuit measurement and feedforward have been shown to significantly reduce the depth of quantum circuits, particularly in implementing logical gates. By leveraging these techniques, we propose several parallelization strategies that reduce quantum circuit depth at the expense of increasing width in preparing various quantum states relevant to quantum simulation. With measurements and feedforward, we demonstrate that utilizing unary encoding as a bridge between two quantum states substantially reduces the circuit depth required for preparing quantum states, such as sparse quantum states and sums of Slater determinants within the first quantization framework, while maintaining an efficient circuit width. Additionally, we show that a Bethe wave function, characterized by its high degree of freedom in its phase, can be probabilistically prepared in a constant-depth quantum circuit using measurements and feedforward. We anticipate that our study will contribute to the reduction of circuit depth in initial state preparation, particularly for quantum simulation, which is a critical step toward achieving quantum advantage.

arXiv:2501.02929•Physical Review Applied•May 27, 2025•5 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

Hybrid Quantum State Preparation via Data Compression

Emad Rezaei Fard Boosari, Maryam Afsary

Quantum state preparation (QSP) for a general $n$-qubit state requires $O(2^n)$ CNOT gates and circuit depth, making exact amplitude encoding (EAE) impractical for near-term quantum hardware. We introduce an ancilla-free hybrid classical-quantum strategy that reduces this cost to $O(poly(n))$ for a broad class of compressible data. The method first applies a classical compression step to obtain a $d$-sparse representation of the input, loads this sparse vector using a sparse-state preparation routine, and then reconstructs the target state through a polynomial-depth quantum inverse transform. We evaluate the framework on synthetic benchmark signals and real biomedical time series using Fourier and Haar transforms, demonstrating substantial reductions in CNOT counts and circuit depth compared to EAE, together with competitive performance relative to the Fourier Series Loader (FSL). The quantum simulation results show that combining classical data compression with quantum decompression provides a scalable framework for efficient QSP, reducing quantum overhead without requiring variational training or ancillary registers.

quant-pharXiv:2512.01798•Dec 2, 2025•0 citations
Quantum state preparation (QSP) is a key component in many quantum algorithms. In particular, the problem of sparse QSP (SQSP) \unicodex2013\unicode{x2013}\unicodex2013 the task of preparing the states with only a small number of non-zero amplitudes \unicodex2013\unicode{x2013}\unicodex2013 has garnered significant attention in recent years. In this work, we focus on reducing the circuit depth of SQSP with limited number of ancilla qubits. We present two SQSP algorithms: one with depth O(nlog⁡d)O(n\log d)O(nlogd), and another that reduces depth to O(n)O(n)O(n). The latter leverages mid-circuit measurement and feedforward, where intermediate measurement outcomes are used to control subsequent quantum operations. Both constructions have size O(dn)O(dn)O(dn) and use O(d)O(d)O(d) ancilla qubits. Compared to the state-of-the-art SQSP algorithm in arXiv:2108.06150, which allows an arbitrary number of ancilla qubits m>0m>0m>0, both of our algorithms achieve lower circuit depth when m=dm=dm=d.
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).
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.
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.
Reducing circuit depth and identifying an optimal trade-off between circuit depth and width is crucial for successful quantum computation. In this context, midcircuit measurement and feedforward have been shown to significantly reduce the depth of quantum circuits, particularly in implementing logical gates. By leveraging these techniques, we propose several parallelization strategies that reduce quantum circuit depth at the expense of increasing width in preparing various quantum states relevant to quantum simulation. With measurements and feedforward, we demonstrate that utilizing unary encoding as a bridge between two quantum states substantially reduces the circuit depth required for preparing quantum states, such as sparse quantum states and sums of Slater determinants within the first quantization framework, while maintaining an efficient circuit width. Additionally, we show that a Bethe wave function, characterized by its high degree of freedom in its phase, can be probabilistically prepared in a constant-depth quantum circuit using measurements and feedforward. We anticipate that our study will contribute to the reduction of circuit depth in initial state preparation, particularly for quantum simulation, which is a critical step toward achieving quantum advantage.
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 (QSP) for a general nnn-qubit state requires O(2n)O(2^n)O(2n) CNOT gates and circuit depth, making exact amplitude encoding (EAE) impractical for near-term quantum hardware. We introduce an ancilla-free hybrid classical-quantum strategy that reduces this cost to O(poly(n))O(poly(n))O(poly(n)) for a broad class of compressible data. The method first applies a classical compression step to obtain a ddd-sparse representation of the input, loads this sparse vector using a sparse-state preparation routine, and then reconstructs the target state through a polynomial-depth quantum inverse transform. We evaluate the framework on synthetic benchmark signals and real biomedical time series using Fourier and Haar transforms, demonstrating substantial reductions in CNOT counts and circuit depth compared to EAE, together with competitive performance relative to the Fourier Series Loader (FSL). The quantum simulation results show that combining classical data compression with quantum decompression provides a scalable framework for efficient QSP, reducing quantum overhead without requiring variational training or ancillary registers.