Halving the cost of QROM
Danial Motlagh, Matthew Pocrnic · 2026
Read Halving the cost of QROM by Danial Motlagh, Matthew Pocrnic (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-20334.txt.
Description
Danial Motlagh and Matthew Pocrnic halve the cost of QROM, quantum read-only memory. They first cut its cost to 2N/λ + 2b(λ-1) + 2λ-6 by swapping the SelectSwap architecture for SelectCopy. Next, for the qubit-constrained regime, they cut cost from about 2N/λ to (1+1/b)N/λ, a cut of about 50% that matches clean-qubit QROM with dirty qubits. Last, they give a parametric family that slides the prefactor of the N/λ term from 2 to (1+1/b), giving the best cost for each qubit availability regime.
Catalog record
| CREATOR | Danial Motlagh, Matthew Pocrnic |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 26184 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.20334