2020/02/29 by Alexandru Paler, Oumarou Oumarou, Robert Basmadjian · 36 citations
Computer Science · Physics and Astronomy · #Algorithm #Compiler #Computer engineering #Computer science #Distributed computing #Fault tolerance #Parallel computing #Programming language #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum computer #Quantum-Dot Cellular Automata #Qubit #Software #Speedup #Theoretical computer science #cs.ET #quant-ph
paper · pdf · doi:10.1103/physreva.102.032608
published in Physical Review A 102(3) (American Physical Society) · accepted in Physical Review A, changed title and abstract, included a discussion about overheads
arxiv created 2020/07/29 · openalex created_date 2020/08/03 · openalex publication_date 2020/09/08 · arxiv updated 2020/09/16 · openalex updated_date 2026/08/05
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 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 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.