Halving the cost of QROM again via dense encoding

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\lambda$ dirty qubits, SelectSwap has leading Toffoli count $2N\mathrm{/}\lambda$. Recent work using sequential bit packets reduces this to $(1+1\mathrm{/}b)N\mathrm{/}\lambda$. 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\mathrm{/}\lambda$. Combining it with sequential bit packets gives $\frac{1}{2}(1+1\mathrm{/}b)N\mathrm{/}\lambda$, 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$.