Fault tolerant resource estimation of quantum random-access memories

Abstract

Quantum random-access look-up of a string of classical bits is a necessary ingredient in several important quantum algorithms. In some cases, the cost of such quantum random-access memory (qRAM) is the limiting factor in the implementation of the algorithm. In this paper we study the cost of fault-tolerantly implementing a qRAM. We construct and analyze generic families of circuits that function as a qRAM, discuss opportunities for qubit-time tradeoffs, and estimate their resource costs when embedded in a surface code.

14 pages, 14 figures. Code repository available in references. To appear in IEEE Transactions on Quantum Engineering

References in corpus (9)

• Quantum algorithm for solving linear systems of equations
• Surface codes: Towards practical large-scale quantum computation
• Quantum random access memory
• Toward the first quantum simulation with quantum speedup
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Architectures for a quantum random access memory
• Quantum circuits of T-depth one
• Quantum algorithms for training Gaussian Processes

Cited by in corpus (43)

• Challenges and Opportunities in Quantum Optimization
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Trading T gates for dirty qubits in state preparation and unitary synthesis
• Resilience of quantum random access memory to generic noise
• Circuit-based quantum random access memory for classical data with continuous amplitudes
• T-count and T-depth of any multi-qubit unitary
• Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• Quantum state preparation protocol for encoding classical data into the amplitudes of a quantum information processing register's wave function
• Data centers with quantum random access memory and quantum networks
• Tower: Data Structures in Quantum Superposition
• Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
• Systems Architecture for Quantum Random Access Memory
• Quantum random access memory via quantum walk
• Evaluating the Potential of Quantum Machine Learning in Cybersecurity: A Case-Study on PCA-based Intrusion Detection Systems
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits
• Quantum algorithms for scientific computing
• Quantum-accelerated constraint programming
• Quantum diffusion map for nonlinear dimensionality reduction
• Error Suppression for Arbitrary-Size Black Box Quantum Operations
• Efficient MPS representations and quantum circuits from the Fourier modes of classical image data
• Quantum Next Generation Reservoir Computing: An Efficient Quantum Algorithm for Forecasting Quantum Dynamics
• Ancilla-Error-Transparent Controlled Beam Splitter Gate
• Quantum Control Machine: The Limits of Control Flow in Quantum Programming
• Two-level Quantum Walkers on Directed Graphs II: An Application to qRAM
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• QRAM: A Survey and Critique
• Hardware-Efficient Quantum Random Access Memory Design with a Native Gate Set on Superconducting Platforms
• Fundamental causal bounds of quantum random access memories
• Quantum random access memory with transmon-controlled phonon routing
• Quantum density peak clustering
• Quantum algorithm for the Vlasov simulation of the large-scale structure formation with massive neutrinos
• 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
• Variational quantum algorithm based on Lagrange polynomial encoding to solve differential equations
• Error-Mitigated Quantum Routing on Noisy Devices
• Unified Architecture for Quantum Lookup Tables
• Sublinear Classical-to-Quantum Data Encoding using $n$-Toffoli Gates
• Refined Criteria for QRAM Error Suppression via Efficient Large-Scale QRAM Simulator
• Hybrid Data Management Architecture for Present Quantum Computing
• Error-Mitigated Quantum Random Access Memory
• Error-Mitigated Multi-Layer Quantum Routing