arXiv:2610.02321

Halving the cost of QROM again via dense encoding

Danial Motlagh

quant-phSubmitted Oct 1, 2026• Announced Oct 5, 2026• 0 citations

Abstract

Quantum read only memory (QROM) is a substantial source of non-Clifford cost in fault-tolerant quantum algorithms. Borrowing dirty qubits can reduce this cost, provided their unknown initial states are restored. We consider the practically relevant qubit-constrained regime, where limited workspace restricts the table-block size and table loading dominates the cost. For $N$ entries of $b$ bits and approximately $bλ$ dirty qubits, SelectSwap has leading Toffoli count $2N/λ$. Recent work using sequential bit packets reduces this to $(1+1/b)N/λ$. In this work we introduce a dense encoding construction of QROM, where two bits of classical information are stored in each dirty qubit instead of one by utilizing both the $Z$ and $X$ bases. On its own, dense encoding provides a $2\times$ improvement over SelectSwap by reducing the leading Toffoli count to $N/λ$. Combining it with sequential bit packets gives $\tfrac12(1+1/b)N/λ$, a further halving of the sequential construction's leading cost, and an approximately $4\times$ improvement over SelectSwap in the large-$N$ limit for practical values of $b$.

Related papers

Halving the cost of QROM

Danial Motlagh, Matthew Pocrnic

quant-pharXiv:2605.20334May 21, 20260 citations

Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding

Tongyang Li, Fengning Ou, Xinzhao Wang +3 more

quant-pharXiv:2607.28260Jul 31, 20260 citations

Productionizing Quantum Mass Production

William J. Huggins, Tanuj Khattar, Nathan Wiebe

arXiv:2506.00132May 30, 20250 citations

Optimization of Quantum Read-Only Memory Circuits

Koustubh Phalak, Mahabubul Alam, Abdullah Ash Saki +2 more

arXiv:2204.03097IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD)Oct 1, 20224 citations

Fast Cliffords When Your Quantum Memory Is Full

Marten Folkertsma, Ian Mertz, Sergii Strelchuk +1 more

quant-pharXiv:2609.40144Oct 1, 20260 citations

Sparse quantum state preparation with improved Toffoli cost

Felix Rupprecht, Sabine Wölk

quant-pharXiv:2601.09388QuantumJan 15, 20260 citations

arXiv:2610.02321

Halving the cost of QROM again via dense encoding

Danial Motlagh

quant-phSubmitted Oct 1, 2026• Announced Oct 5, 2026• 0 citations

arXiv HTML PDF

Abstract

N

entries of

b

bits and approximately

bλ

dirty qubits, SelectSwap has leading Toffoli count

2N/λ

. Recent work using sequential bit packets reduces this to

(1+1/b)N/λ

. In this work we introduce a dense encoding construction of QROM, where two bits of classical information are stored in each dirty qubit instead of one by utilizing both the

Z

and

X

bases. On its own, dense encoding provides a

2\times

improvement over SelectSwap by reducing the leading Toffoli count to

N/λ

. Combining it with sequential bit packets gives

\tfrac12(1+1/b)N/λ

, a further halving of the sequential construction's leading cost, and an approximately

4\times

improvement over SelectSwap in the large-

N

limit for practical values of

b

Related papers

Halving the cost of QROM

Danial Motlagh, Matthew Pocrnic

Table lookup, often referred to as quantum read only memory (QROM), is one of the most widely used subroutines in quantum algorithms, and constitutes the majority share of algorithmic overheads in most practical applications of quantum computers. It involves the coherent loading of $N$ bitstrings of length $b$ in superposition, and naively has a non-Clifford cost of $N$ Toffolis. It is known that given access to $b\, λ$ dirty qubits, one can reduce the Toffoli cost of QROM to $2\frac{N}λ + 4b(λ- 1)$ . In this work, we first present an optimization to reduce this cost to $2\frac{N}λ + 2b(λ- 1) + 2λ-6$ by replacing the ``SelectSwap" architecture with ``SelectCopy". We then provide a further optimization for the qubit-constrained regime where the Toffoli cost is typically $\sim 2\frac{N}λ$ , and reduce it to $\sim (1+\frac{1}{b})\frac{N}λ$ , cutting the cost by approximately $50\%$ and effectively matching the performance of clean-qubit QROM using dirty qubits for practical values of $b$ . Lastly, we provide a parametric family of methods that allow the interpolation of the prefactor of the $\frac{N}λ $ term from $2$ to ( $\, 1+\frac{1}{b}\,$ ) to obtain the best cost for different qubit availability regimes.Table lookup, often referred to as quantum read only memory (QROM), is one of the most widely used subroutines in quantum algorithms, and constitutes the majority share of algorithmic overheads in most practical applications of quantum computers. It involves the coherent loading of $N$ bitstrings of length $b$ in superposition, and naively has a non-Clifford cost of $N$ Toffolis. It is known that given access to $b\, λ$ dirty qubits, one can reduce the Toffoli cost of QROM to $2\frac{N}λ + 4b(λ- 1)$. In this work, we first present an optimization to reduce this cost to $2\frac{N}λ + 2b(λ- 1) + 2λ-6$ by replacing the ``SelectSwap" architecture with ``SelectCopy". We then provide a further optimization for the qubit-constrained regime where the Toffoli cost is typically $\sim 2\frac{N}λ$, and reduce it to $\sim (1+\frac{1}{b})\frac{N}λ$, cutting the cost by approximately $50\%$ and effectively matching the performance of clean-qubit QROM using dirty qubits for practical values of $b$. Lastly, we provide a parametric family of methods that allow the interpolation of the prefactor of the $\frac{N}λ $ term from $2$ to ($\, 1+\frac{1}{b}\,$) to obtain the best cost for different qubit availability regimes.

quant-pharXiv:2605.20334May 21, 20260 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.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.28260Jul 31, 20260 citations

Productionizing Quantum Mass Production

William J. Huggins, Tanuj Khattar, Nathan Wiebe

For many practical applications of quantum computing, the most costly steps involve coherently accessing classical data. We help address this challenge by applying mass production techniques, which can reduce the cost of applying an operation multiple times in parallel. We combine these techniques with modern approaches for classical data loading based on "quantum read-only memory" (QROM). We find that we can polynomially reduce the total number of gates required for data loading, but we find no advantage in cost models that only count the number of non-Clifford gates. Furthermore, for realistic cost models and problem sizes, we find that it is possible to reduce the cost of parallel data loading by an order of magnitude or more. We present several applications of quantum mass production, including a scheme that uses parallel phase estimation to asymptotically reduce the gate complexity of state-of-the-art algorithms for estimating eigenvalues of the quantum chemical Hamiltonian, including both Clifford and non-Clifford gates, from $\widetilde{\mathcal{O}}\left(N_{orb}^2\right)$ to $\widetilde{\mathcal{O}}\left(N_{orb}^{\log_2 3}\right)$ , where $N_{orb}$ denotes the number of orbitals. We also show that mass production can be used to reduce the cost of serial calls to the same data loading oracle by precomputing several copies of a novel QROM resource state.For many practical applications of quantum computing, the most costly steps involve coherently accessing classical data. We help address this challenge by applying mass production techniques, which can reduce the cost of applying an operation multiple times in parallel. We combine these techniques with modern approaches for classical data loading based on "quantum read-only memory" (QROM). We find that we can polynomially reduce the total number of gates required for data loading, but we find no advantage in cost models that only count the number of non-Clifford gates. Furthermore, for realistic cost models and problem sizes, we find that it is possible to reduce the cost of parallel data loading by an order of magnitude or more. We present several applications of quantum mass production, including a scheme that uses parallel phase estimation to asymptotically reduce the gate complexity of state-of-the-art algorithms for estimating eigenvalues of the quantum chemical Hamiltonian, including both Clifford and non-Clifford gates, from $\widetilde{\mathcal{O}}\left(N_{orb}^2\right)$ to $\widetilde{\mathcal{O}}\left(N_{orb}^{\log_2 3}\right)$, where $N_{orb}$ denotes the number of orbitals. We also show that mass production can be used to reduce the cost of serial calls to the same data loading oracle by precomputing several copies of a novel QROM resource state.

arXiv:2506.00132May 30, 20250 citations

Optimization of Quantum Read-Only Memory Circuits

Koustubh Phalak, Mahabubul Alam, Abdullah Ash Saki +2 more

Quantum computing is a rapidly expanding field with applications ranging from optimization all the way to complex machine learning tasks. Quantum memories, while lacking in practical quantum computers, have the potential to bring quantum advantage. In quantum machine learning applications for example, a quantum memory can simplify the data loading process and potentially accelerate the learning task. Quantum memory can also store intermediate quantum state of qubits that can be reused for computation. However, the depth, gate count and compilation time of quantum memories such as, Quantum Read Only Memory (QROM) scale exponentially with the number of address lines making them impractical in state-of-the-art Noisy Intermediate-Scale Quantum (NISQ) computers beyond 4-bit addresses. In this paper, we propose techniques such as, pre-decoding logic and qubit reset to reduce the depth and gate count of QROM circuits to target wider address ranges such as, 8-bits. The proposed approach reduces the number of gates and depth count by at least 2X compared to the naive implementation at only 36% qubit overhead. A reduction in circuit depth and gate count as high as 75X and compilation time by 85X at the cost of a maximum of 2.28X qubit overhead is observed. Experimentally, the fidelity with the proposed pre-decoding circuit compared to existing optimization approach is also higher (as much as 73% compared to 40.8%) under reduced error rates.Quantum computing is a rapidly expanding field with applications ranging from optimization all the way to complex machine learning tasks. Quantum memories, while lacking in practical quantum computers, have the potential to bring quantum advantage. In quantum machine learning applications for example, a quantum memory can simplify the data loading process and potentially accelerate the learning task. Quantum memory can also store intermediate quantum state of qubits that can be reused for computation. However, the depth, gate count and compilation time of quantum memories such as, Quantum Read Only Memory (QROM) scale exponentially with the number of address lines making them impractical in state-of-the-art Noisy Intermediate-Scale Quantum (NISQ) computers beyond 4-bit addresses. In this paper, we propose techniques such as, pre-decoding logic and qubit reset to reduce the depth and gate count of QROM circuits to target wider address ranges such as, 8-bits. The proposed approach reduces the number of gates and depth count by at least 2X compared to the naive implementation at only 36% qubit overhead. A reduction in circuit depth and gate count as high as 75X and compilation time by 85X at the cost of a maximum of 2.28X qubit overhead is observed. Experimentally, the fidelity with the proposed pre-decoding circuit compared to existing optimization approach is also higher (as much as 73% compared to 40.8%) under reduced error rates.

arXiv:2204.03097IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD)Oct 1, 20224 citations

Fast Cliffords When Your Quantum Memory Is Full

Marten Folkertsma, Ian Mertz, Sergii Strelchuk +1 more

Additional qubits can reduce the depth of a quantum circuit by providing workspace for parallel computation, but standard constructions assume that this workspace is initialized in a known state. In this work we study catalytic implementations, i.e. asking whether dirty qubits can instead be used provided that their joint state including any entanglement with other registers is restored exactly at the end of the computation. We show that every $n$ -qubit Clifford circuit has a catalytic implementation of depth $O(\log n)$ using $O(n^2/\log^2 n)$ catalytic qubits and no clean qubits, matching the asymptotic depth achievable when clean workspace is available. We extend this approach to diagonal elements of any fixed level $C_k$ of the Clifford hierarchy, which admit catalytic implementations of depth $O(\log(n+1))$ with $O(n^k/\log(n))$ gates and $O(n^k/\log^2(n))$ catalytic qubits, as well as to semi-Clifford Gates.Additional qubits can reduce the depth of a quantum circuit by providing workspace for parallel computation, but standard constructions assume that this workspace is initialized in a known state. In this work we study catalytic implementations, i.e. asking whether dirty qubits can instead be used provided that their joint state including any entanglement with other registers is restored exactly at the end of the computation. We show that every $n$-qubit Clifford circuit has a catalytic implementation of depth $O(\log n)$ using $O(n^2/\log^2 n)$ catalytic qubits and no clean qubits, matching the asymptotic depth achievable when clean workspace is available. We extend this approach to diagonal elements of any fixed level $C_k$ of the Clifford hierarchy, which admit catalytic implementations of depth $O(\log(n+1))$ with $O(n^k/\log(n))$ gates and $O(n^k/\log^2(n))$ catalytic qubits, as well as to semi-Clifford Gates.

quant-pharXiv:2609.40144Oct 1, 20260 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.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.09388QuantumJan 15, 20260 citations

N

entries of

b

bits and approximately

bλ

dirty qubits, SelectSwap has leading Toffoli count

2N/λ

. Recent work using sequential bit packets reduces this to

(1+1/b)N/λ

. In this work we introduce a dense encoding construction of QROM, where two bits of classical information are stored in each dirty qubit instead of one by utilizing both the

Z

and

X

bases. On its own, dense encoding provides a

2\times

improvement over SelectSwap by reducing the leading Toffoli count to

N/λ

. Combining it with sequential bit packets gives

\tfrac12(1+1/b)N/λ

, a further halving of the sequential construction's leading cost, and an approximately

4\times

improvement over SelectSwap in the large-

N

limit for practical values of

b

N

bitstrings of length

b

in superposition, and naively has a non-Clifford cost of

N

Toffolis. It is known that given access to

b\, λ

dirty qubits, one can reduce the Toffoli cost of QROM to

2\frac{N}λ + 4b(λ- 1)

. In this work, we first present an optimization to reduce this cost to

2\frac{N}λ + 2b(λ- 1) + 2λ-6

by replacing the ``SelectSwap" architecture with ``SelectCopy". We then provide a further optimization for the qubit-constrained regime where the Toffoli cost is typically

\sim 2\frac{N}λ

, and reduce it to

\sim (1+\frac{1}{b})\frac{N}λ

, cutting the cost by approximately

50\%

and effectively matching the performance of clean-qubit QROM using dirty qubits for practical values of

b

. Lastly, we provide a parametric family of methods that allow the interpolation of the prefactor of the $\frac{N}λ $ term from

2

to (

\, 1+\frac{1}{b}\,

) to obtain the best cost for different qubit availability regimes.

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.

\widetilde{\mathcal{O}}\left(N_{orb}^2\right)

\widetilde{\mathcal{O}}\left(N_{orb}^{\log_2 3}\right)

, where

N_{orb}

denotes the number of orbitals. We also show that mass production can be used to reduce the cost of serial calls to the same data loading oracle by precomputing several copies of a novel QROM resource state.

n

-qubit Clifford circuit has a catalytic implementation of depth

O(\log n)

using

O(n^2/\log^2 n)

catalytic qubits and no clean qubits, matching the asymptotic depth achievable when clean workspace is available. We extend this approach to diagonal elements of any fixed level

C_k

of the Clifford hierarchy, which admit catalytic implementations of depth

O(\log(n+1))

with

O(n^k/\log(n))

gates and

O(n^k/\log^2(n))

catalytic qubits, as well as to semi-Clifford Gates.

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.