arXiv:2610.02321
Halving the cost of QROM again via dense encoding
Danial Motlagh
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$.
AI Summary
The paper addresses the non-Clifford cost of coherent classical-table lookup in the qubit-constrained regime, where table loading dominates QROM cost. For $N$ entries of $b$ bits and approximately $b\lambda$ borrowed dirty qubits, it introduces dense encoding: each dirty qubit receives $X^aZ^z$, encoding bits from two adjacent entries in its two Pauli components. An address-selected, output-controlled Pauli read extracts the requested bit through a commutator, while restoring the dirty register, including its entanglement with other systems. Dense encoding doubles the entries covered per table-loading pass without increasing dirty workspace. The resulting Toffoli bound is $N/\lambda+(4b+2)\lambda-6$, versus SelectSwap’s leading cost $2N/\lambda$. Combining dense encoding with sequential bit packets shares packet unload/load passes. With one-bit packets, the count becomes $\tfrac12(1+1/b)N/\lambda+3b(b+1)\lambda-3(b+1)$: half the previous sequential construction’s leading term and a leading-term improvement over SelectSwap of $4b/(b+1)$. The paper also gives integer bounds accommodating incomplete packets and table blocks. Correctness follows from Pauli conjugation identities, extended coherently across address sectors; resource bounds count high-address loading passes, unary row-selection passes, and controlled reads. The reported factors concern the loading-dominated regime, not uniform reductions across all parameters. Power-of-two row counts and finite-workspace constraints enter the bounds. Clifford scheduling, measurement latency, and physical layout are left for future analysis, so the paper does not establish corresponding physical implementation savings.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.