Halving the cost of QROM
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916030107877376 |
|---|---|
| author | Motlagh, Danial Pocrnic, Matthew |
| author_facet | Motlagh, Danial Pocrnic, Matthew |
| contents | Table lookup, often referred to as quantum read only memory (QROM), is one of the most widely used subroutines in quantum algorithms, and constitutes the majority share of algorithmic overheads in most practical applications of quantum computers. It involves the coherent loading of $N$ bitstrings of length $b$ in superposition, and naively has a non-Clifford cost of $N$ Toffolis. It is known that given access to $b\, λ$ dirty qubits, one can reduce the Toffoli cost of QROM to $2\frac{N}λ + 4b(λ- 1)$. In this work, we first present an optimization to reduce this cost to $2\frac{N}λ + 2b(λ- 1) + 2λ-6$ by replacing the ``SelectSwap" architecture with ``SelectCopy". We then provide a further optimization for the qubit-constrained regime where the Toffoli cost is typically $\sim 2\frac{N}λ$, and reduce it to $\sim (1+\frac{1}{b})\frac{N}λ$, cutting the cost by approximately $50\%$ and effectively matching the performance of clean-qubit QROM using dirty qubits for practical values of $b$. Lastly, we provide a parametric family of methods that allow the interpolation of the prefactor of the $\frac{N}λ $ term from $2$ to ($\, 1+\frac{1}{b}\,$) to obtain the best cost for different qubit availability regimes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_20334 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Halving the cost of QROM Motlagh, Danial Pocrnic, Matthew Quantum Physics Table lookup, often referred to as quantum read only memory (QROM), is one of the most widely used subroutines in quantum algorithms, and constitutes the majority share of algorithmic overheads in most practical applications of quantum computers. It involves the coherent loading of $N$ bitstrings of length $b$ in superposition, and naively has a non-Clifford cost of $N$ Toffolis. It is known that given access to $b\, λ$ dirty qubits, one can reduce the Toffoli cost of QROM to $2\frac{N}λ + 4b(λ- 1)$. In this work, we first present an optimization to reduce this cost to $2\frac{N}λ + 2b(λ- 1) + 2λ-6$ by replacing the ``SelectSwap" architecture with ``SelectCopy". We then provide a further optimization for the qubit-constrained regime where the Toffoli cost is typically $\sim 2\frac{N}λ$, and reduce it to $\sim (1+\frac{1}{b})\frac{N}λ$, cutting the cost by approximately $50\%$ and effectively matching the performance of clean-qubit QROM using dirty qubits for practical values of $b$. Lastly, we provide a parametric family of methods that allow the interpolation of the prefactor of the $\frac{N}λ $ term from $2$ to ($\, 1+\frac{1}{b}\,$) to obtain the best cost for different qubit availability regimes. |
| title | Halving the cost of QROM |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2605.20334 |