RECORD
Sparse quantum state preparation with improved Toffoli cost
Quantum Physics · Submitted 14 Jan 2026 · Published version
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | The preparation of quantum states is one of the most fundamental tasks in quantum computing, and a key primitive in many quantum algorithms. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s1 | 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. | background 1.00 | 0.05 | 0.02 | asserted 0.96 |
| s2 | 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. | contribution 1.00 | 0.95 | 0.78 | asserted 1.00 |
| s3 | 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. | method 0.97 | 0.43 | 0.07 | asserted 1.00 |
| s4 | The speed-up is achieved by designing an efficient algorithm for finding and implementing the isometry. | method 0.85 | 0.89 | 0.14 | asserted 1.00 |
| s5 | 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. | result 0.99 | 0.92 | 0.64 | asserted 0.63 |
| s6 | In numerical benchmarks on randomly chosen states, the cost is closer to $s$. | result 1.00 | 0.93 | 0.06 | asserted 0.99 |
| s7 | 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. | contribution 0.84 | 0.94 | 0.09 | asserted 0.96 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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.
Human review
References
How the literature uses it
7 arXiv papers cite this in 24 sentences
Papers citing it · 9 sentences without a confident label
Uses its method or tool 3 papers
-
If $s ≤n^3/2logn$, then the claim follows from the sparse-state preparation construction of [ref] , together with the observation that the dense-state preparation step can be implemented using $O(s)$ $T$ gates and $O(log(1/ϵ))$ ancillas [ref] .
Sparse Quantum State Preparation with Sublinear T-Count · Sparse Quantum State Preparation · 0.86
-
For $s≥2$, non-diagonal encoding partitions the columns into batches of size $m$ and applies the batched isometry subroutine of Rupprecht and Wölk [ref] , where the estimated $$-gate count is [equation]
Clifford-efficient sparse state preparation for molecular wavefunctions · Binary encoding for diagonal and non-diagonal columns · 1.00
-
This can easily be taken into account by adapting the state preparation $U_1$, for which we use the Grover–-Rudolph variant described in [ref] .
Faster matrix product state preparation by exploiting symmetry-induced block-sparsity · Preparation of blocksparse MPS · 0.99
Compares with it 3 papers
-
We benchmark our method in two variants, without binary encoding and with binary encoding, against two recent sparse state preparation methods with publicly available implementations: the batched-pivoting algorithm of Rupprecht–Wölk [ref] and the permuted Grover–Rudolph method of Ramacciotti et al. [ref] , both implemented in Qualtran [ref] .
Clifford-efficient sparse state preparation for molecular wavefunctions · Results · 0.83
-
Overall, this improves the near-linear dependence on the sparsity \(s\) in prior sparse state-preparation constructions [ref] to a square-root dependence, matching the lower bound in <Ref>.
Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding · Main results · 0.99
-
In this context, it is an interesting question how the direct preparation of MPS compares to computing a sparse sum of Slater determinants (SOS) representation from the MPS and preparing this SOS state directly [ref] .
Faster matrix product state preparation by exploiting symmetry-induced block-sparsity · Conclusion and Outlook · 0.84
Cites it as background 3 papers
-
Methods tailored to the sparsity of the target state instead compress the $d$ nonzero-amplitude basis states onto a smaller dense register, most often using permutations [ref] .
Clifford-efficient sparse state preparation for molecular wavefunctions · Introduction · 0.82
-
Many QSP algorithms tailored to sparse states have been proposed in recent years [ref] .
Approximate Sparse State Preparation with the Grover-Rudolph Algorithm · Introduction · 0.97
-
On the other hand, they open the door to entirely new applications across the quantum computing stack, in settings where other classical simulation paradigms have traditionally played an enabling role [ref] .
Enabling Lie-Algebraic Classical Simulation beyond Free Fermions · Conclusions · 0.80
What it cites · 9 sentences without a confident label
Uses the method or tool of 2 papers
-
Quantum circuits for the sparse state preparation and the necessary sub-circuits are implemented within the framework [ref] , with the computationally more expensive classical algorithms for finding the isometry outsourced to SIMD-accelerated Rust code.
Expressing and Analyzing Quantum Algorithms with Qualtran · Introduction · 1.00
-
The circuit diagrams in the paper were created with the package [ref] .
Yquant: Typesetting quantum circuits in a human-readable language · Acknowledgements · 1.00
Compares with 2 papers
-
In [ref] , this incurs a Toffoli cost for the isometry of $s(2⌈log(s)⌉-2 ) + s̃$, which, although not explicitly considered in the other papers, seems to be the best Toffoli gate count within the group [ref] .
Postponing the orthogonality catastrophe: efficient state preparation for electronic structure simulations on quantum devices · Introduction · 0.90
-
We note that there are other approaches to sparse state preparation, potentially with a smaller number of required gates [ref] ; however, the proposals require a substantial amount of additional qubits.
Resource-Efficient Synthesis of Sparse Quantum States · Introduction · 0.86
Cites as background 2 papers
-
Approaches for efficiently preparing such sparse states have been studied in multiple works [ref] and can, for the most part, be categorized into two groups.
Postponing the orthogonality catastrophe: efficient state preparation for electronic structure simulations on quantum devices · Introduction · 0.96
-
A class of quantum states of particular interest [ref] is the class of sparse quantum states.
Quantum Linear System Solvers: A Survey of Algorithms and Applications · Introduction · 0.94
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.