Parallelising the Queries in Bucket Brigade Quantum RAM

Abstract

Quantum algorithms often use quantum RAMs (QRAM) for accessing information stored in a database-like manner. QRAMs have 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: 1) address translation time, and 2) effective query time. The bucket brigade QRAMs were proposed to achieve faster addressing at the cost of exponentially many ancillae. We illustrate a systematic method to significantly reduce the effective query time by using Clifford+T gate parallelism. The method does not introduce any ancillae qubits. Our parallelisation method is compatible with the surface code quantum error correction. We show that parallelisation is a result of advantageous Toffoli gate decomposition in terms of Clifford+T gates, and after addresses have been translated, we achieve theoretical $\mathcal{O}(1)$ parallelism for the effective queries. We conclude that, in theory: 1) fault-tolerant bucket brigade quantum RAM queries can be performed approximately with the speed of classical RAM; 2) the exponentially many ancillae from the bucket brigade addressing scheme are a trade-off cost for achieving exponential query speedup compared to quantum read-only memories whose queries are sequential by design. The methods to compile, parallelise and analyse the presented QRAM circuits were implemented in software which is available online.

accepted in Physical Review A, changed title and abstract, included a discussion about overheads

References in corpus (9)

• Elementary gates for quantum computation
• Measurement-based quantum computation with cluster states
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Halving the cost of quantum addition
• Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
• On the robustness of bucket brigade quantum RAM
• Synthesis of Arbitrary Quantum Circuits to Topological Assembly
• Optimal Usage of Quantum Random Access Memory in Quantum Machine Learning
• Synthesis of Arbitrary Quantum Circuits to Topological Assembly: Systematic, Online and Compact

Cited by in corpus (18)

• Resilience of quantum random access memory to generic noise
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• Data centers with quantum random access memory and quantum networks
• Tower: Data Structures in Quantum Superposition
• Quantum random access memory via quantum walk
• Quantum Control Machine: The Limits of Control Flow in Quantum Programming
• Ancilla-Error-Transparent Controlled Beam Splitter Gate
• QRAM: A Survey and Critique
• Two-level Quantum Walkers on Directed Graphs II: An Application to qRAM
• Quantum solvability of noisy linear problems by divide-and-conquer strategy
• Quantum random access memory with transmon-controlled phonon routing
• Quantum algorithm for the Vlasov simulation of the large-scale structure formation with massive neutrinos
• Quantum matching pursuit: A quantum algorithm for sparse representations
• A quantum random access memory (QRAM) using a polynomial encoding of binary strings
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation
• Fat-Tree QRAM: A High-Bandwidth Shared Quantum Random Access Memory for Parallel Queries
• A T-depth two Toffoli gate for 2D square lattice architectures
• Error-Mitigated Quantum Random Access Memory