Halving the cost of QROM again via dense encoding

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

arXiv:2610.02321 [quant-ph]

(or arXiv:2610.02321v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2610.02321 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.