Parallelizing the queries in a bucket-brigade quantum random access memory

Abstract

Quantum algorithms often use quantum random access memory (QRAM) for accessing information stored in a databaselike manner. QRAM has to be fast, resource efficient, and fault tolerant. The latter is often influenced by access speeds, because shorter times introduce less exposure of the stored information to noise. The total execution time of an algorithm depends on the QRAM access time which includes (i) address translation time and (ii) effective query time. The bucket-brigade QRAM was proposed to achieve faster addressing at the cost of exponentially many ancillas. We illustrate a systematic method to significantly reduce the effective query time by using $\mathrm{Clifford}+T$ gate parallelism. The method does not introduce any ancilla qubits. Our parallelization method is compatible with the surface code quantum error correction. We show that parallelization is a result of advantageous Toffoli gate decomposition in terms of $\mathrm{Clifford}+T$ gates, and after addresses have been translated, we achieve theoretical $O(1)$ parallelism for the effective queries. We conclude that, in theory, (i) fault-tolerant bucket-brigade quantum RAM queries can be performed approximately with the speed of classical RAM, and (ii) the exponentially many ancillas from the bucket-brigade addressing scheme are a tradeoff cost for achieving exponential query speedup compared to quantum read-only memories whose queries are sequential by design. The methods used to compile, parallelize, and analyze the presented QRAM circuits have been implemented in software which is available online.