Papers › Novel oracle constructions for quantum random access memory
Novel oracle constructions for quantum random access memory
Ákos Nagy, Cindy Zhang
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We present new designs for quantum random access memory. More precisely, for each function, f : 𝔽₂ⁿ →𝔽₂ᵈ, we construct oracles, 𝒪_f, with the property 𝒪_f | x ⟩ₙ | 0 ⟩_d = | x ⟩ₙ | f(x) ⟩_d. Our methods are based on the Walsh-Hadamard Transform of f, viewed as an integer valued function. In general, the complexity of our method scales with the sparsity of the Walsh-Hadamard Transform and not the sparsity of f, yielding more favorable constructions in cases such as binary optimization problems and function with low-degree Walsh-Hadamard Transforms. Furthermore, our design comes with a tuneable amount of ancillas that can trade depth for size. In the ancilla-free design, these oracles can be ϵ-approximated so that the Clifford + T depth is O ( ( n + log₂ ( dϵ ) ) 𝒲_f ), where 𝒲_f is the number of nonzero components in the Walsh-Hadamard Transform. The depth of the shallowest version is O ( n + log₂ ( dϵ ) ), using n + d 𝒲_f qubit. The connectivity of these circuits is also only logarithmic in 𝒲_f. As an application, we show that for boolean functions with low approximate degrees (as in the case of read-once formulas) the complexities of the corresponding QRAM oracles scale only as 2^(O ( √(n) log₂ ( n ) )).
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections