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:2601.09388 · Quantum

Sparse quantum state preparation with improved Toffoli cost

Felix Rupprecht, Sabine Wölk

quant-phSubmitted Jan 14, 2026• Announced Jan 15, 2026• 0 citations
v1 · Jan 14, 2026v2 · Sep 4, 2026
arXivHTMLPDF

Abstract

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.

Journal reference
Quantum 10, 2208 (2026)
DOI
10.22331/q-2026-09-10-2208
Comments
20 (16 + 4) pages, 10 Figures, code available, feedback and comments welcome

Related papers

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

Faster matrix product state preparation by exploiting symmetry-induced block-sparsity

Felix Rupprecht, Sabine Wölk

Matrix product states (MPS) serve as a key tool for studying quantum systems from chemistry and condensed-matter physics, making their preparation on quantum computers an important task in interfacing classical and quantum simulation. Many systems of interest have $U(1)$-symmetries induced by particle number and spin projection conservation, allowing to restrict the MPS tensors to be of block-sparse form, a property widely used in the implementation of classical algorithms such as the density matrix renormalization group. We reduce the cost of fault-tolerantly preparing block-sparse MPS within the standard ancilla-assisted linear-depth approach by implementing row and column permutations that transform the block-sparse matrices into block-diagonal form. These block-diagonal unitaries are then implemented via unitary synthesis, with the cost being determined by the size of the largest block. In this context, we modify the unitary synthesis approach of Berry et al. in order to reduce the Toffoli cost for real-valued unitaries by a factor of $\sqrt{2}$. In numerical benchmarks, we achieve Toffoli cost improvement factors of $10 - 30$ compared to the state-of-the-art for MPS of various molecular systems.

quant-pharXiv:2605.28489•May 28, 2026•0 citations

Comparative Study of Quantum State Preparation Methods in Sparse Isometry Decomposition

Ana Sofia Moreira de LIRA

Initializing an isometry in a quantum circuit is a fundamental yet challenging task, espe- cially when aiming for efficient state preparation and resource optimization. In this work, we present a comparative analysis of the Householder Decomposition for isometry implementation, leveraging three distinct state preparation methods starting from the original Pivot method and extending the study to two additional strategies: Merge and Low Rank. The study investigates how each method impacts the performance of the isometry decomposition, focusing on key metrics such as CNOT gate count and circuit depth. To provide a comprehensive evaluation, we examine variations in matrix size and sparsity levels, capturing the effects of structural complexity on resource requirements. Our results reveal that the Merge state preparation method generally outperforms the other two approaches, particularly in terms of scalability and gate efficiency. Building upon these findings, we further compare the best-performing method, Merge, with the state-of- the-art isometry decomposition implementation available in Qiskit, a widely used quantum computing framework. The analysis demonstrates that, for isometries involving up to 6 qubits, Qiskit’s implementation exhibits superior performance. However, beyond this threshold, our proposed decomposition method proves more effective, especially for highly sparse isometries or those characterized by a smaller number of columns. This work highlights the potential for optimizing isometry decompositions in scenarios where sparsity and structural constraints are critical factors. These findings contribute to advancing state preparation techniques and offer insights into improving the efficiency of quantum circuits for applications in quantum information processing.

•Feb 6, 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

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

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
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.
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.
Matrix product states (MPS) serve as a key tool for studying quantum systems from chemistry and condensed-matter physics, making their preparation on quantum computers an important task in interfacing classical and quantum simulation. Many systems of interest have U(1)U(1)U(1)-symmetries induced by particle number and spin projection conservation, allowing to restrict the MPS tensors to be of block-sparse form, a property widely used in the implementation of classical algorithms such as the density matrix renormalization group. We reduce the cost of fault-tolerantly preparing block-sparse MPS within the standard ancilla-assisted linear-depth approach by implementing row and column permutations that transform the block-sparse matrices into block-diagonal form. These block-diagonal unitaries are then implemented via unitary synthesis, with the cost being determined by the size of the largest block. In this context, we modify the unitary synthesis approach of Berry et al. in order to reduce the Toffoli cost for real-valued unitaries by a factor of 2\sqrt{2}2​. In numerical benchmarks, we achieve Toffoli cost improvement factors of 10−3010 - 3010−30 compared to the state-of-the-art for MPS of various molecular systems.
Initializing an isometry in a quantum circuit is a fundamental yet challenging task, espe- cially when aiming for efficient state preparation and resource optimization. In this work, we present a comparative analysis of the Householder Decomposition for isometry implementation, leveraging three distinct state preparation methods starting from the original Pivot method and extending the study to two additional strategies: Merge and Low Rank. The study investigates how each method impacts the performance of the isometry decomposition, focusing on key metrics such as CNOT gate count and circuit depth. To provide a comprehensive evaluation, we examine variations in matrix size and sparsity levels, capturing the effects of structural complexity on resource requirements. Our results reveal that the Merge state preparation method generally outperforms the other two approaches, particularly in terms of scalability and gate efficiency. Building upon these findings, we further compare the best-performing method, Merge, with the state-of- the-art isometry decomposition implementation available in Qiskit, a widely used quantum computing framework. The analysis demonstrates that, for isometries involving up to 6 qubits, Qiskit’s implementation exhibits superior performance. However, beyond this threshold, our proposed decomposition method proves more effective, especially for highly sparse isometries or those characterized by a smaller number of columns. This work highlights the potential for optimizing isometry decompositions in scenarios where sparsity and structural constraints are critical factors. These findings contribute to advancing state preparation techniques and offer insights into improving the efficiency of quantum circuits for applications in quantum information processing.
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.
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.
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.