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

CREATORDanial Motlagh, Matthew Pocrnic
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE26184
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.20334

Browse the full library · About the Tower of Babel