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λ 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× improvement over SelectSwap by reducing the leading Toffoli count to N/λ. Combining it with sequential bit packets gives 1/2(1+1/b)N/λ, a further halving of the sequential construction's leading cost, and an approximately 4× improvement over SelectSwap in the large-N limit for practical values of b.
Related
- Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding
- Towards the Impossibility of Imperfectly Complete Key Agreement in the QROM
- Thermodynamic approach to momentum transport in dense fluids
- Qudit encoding in Rydberg-blockaded arrays of atoms
- Persistence-driven void formation in dense active-passive mixtures
BibTeX
@misc{motlagh2026halving,
title = {{Halving the cost of QROM again via dense encoding}},
author = {Danial Motlagh},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02321},
eprint = {2610.02321},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02321},
}
RIS
TY - UNPB
TI - Halving the cost of QROM again via dense encoding
AU - Danial Motlagh
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02321
UR - https://arxiv.org/abs/2610.02321
AB - 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× improvement over SelectSwap by reducing the leading Toffoli count to N/λ. Combining it with sequential bit packets gives 1/2(1+1/b)N/λ, a further halving of the sequential construction's leading cost, and an approximately 4× improvement over SelectSwap in the large-N limit for practical values of b.
ER -