On the robustness of bucket brigade quantum RAM

Abstract

We study the robustness of the bucket brigade quantum random access memory model introduced by Giovannetti, Lloyd, and Maccone [Phys. Rev. Lett. 100, 160501 (2008)]. Due to a result of Regev and Schiff [ICALP '08 pp. 773], we show that for a class of error models the error rate per gate in the bucket brigade quantum memory has to be of order $o(2^{-n/2})$ (where $N=2^n$ is the size of the memory) whenever the memory is used as an oracle for the quantum searching problem. We conjecture that this is the case for any realistic error model that will be encountered in practice, and that for algorithms with super-polynomially many oracle queries the error rate must be super-polynomially small, which further motivates the need for quantum error correction. By contrast, for algorithms such as matrix inversion [Phys. Rev. Lett. 103, 150502 (2009)] or quantum machine learning [Phys. Rev. Lett. 113, 130503 (2014)] that only require a polynomial number of queries, the error rate only needs to be polynomially small and quantum error correction may not be required. We introduce a circuit model for the quantum bucket brigade architecture and argue that quantum error correction for the circuit causes the quantum bucket brigade architecture to lose its primary advantage of a small number of "active" gates, since all components have to be actively error corrected.

Replaced with the published version. 13 pages, 9 figures

References in corpus (11)

• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum principal component analysis
• Quantum random access memory
• Exponential algorithmic speedup by quantum walk
• Topological Quantum Distillation
• Quantum Data Fitting
• Magic state distillation with low overhead
• Architectures for a quantum random access memory
• Fault-tolerant conversion between the Steane and Reed-Muller quantum codes
• Using concatenated quantum codes for universal fault-tolerant quantum gates

Cited by in corpus (60)

• Quantum Machine Learning
• Quantum machine learning: a classical perspective
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Quantum gradient descent for linear systems and least squares
• Hardware-efficient quantum random access memory with hybrid quantum acoustic systems
• Circuit-Based Quantum Random Access Memory for Classical Data
• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• Biology and medicine in the landscape of quantum advantages
• Fault tolerant resource estimation of quantum random-access memories
• Time-Space Complexity of Quantum Search Algorithms in Symmetric Cryptanalysis
• Resilience of quantum random access memory to generic noise
• The theory of the quantum kernel-based binary classifier
• Quantum algorithm and quantum circuit for A-Optimal Projection: dimensionality reduction
• Linear-depth quantum circuits for multiqubit controlled gates
• An improved quantum-inspired algorithm for linear regression
• Circuit-based quantum random access memory for classical data with continuous amplitudes
• Physical-Layer Supervised Learning Assisted by an Entangled Sensor Network
• Parallelising the Queries in Bucket Brigade Quantum RAM
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• A hybrid classical-quantum workflow for natural language processing
• 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
• Optimizing a Polynomial Function on a Quantum Simulator
• Tower: Data Structures in Quantum Superposition
• Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
• Quantum adiabatic machine learning with zooming
• Optimal Usage of Quantum Random Access Memory in Quantum Machine Learning
• Networked Quantum Services
• Quantum algorithms for scientific computing
• Quantum-accelerated constraint programming
• Parallel quantum trajectories via forking for sampling without redundancy
• Error Suppression for Arbitrary-Size Black Box Quantum Operations
• Experimental demonstration of quantum learning speed-up with classical input data
• Quantum Text Encoding for Classification Tasks
• Ancilla-Error-Transparent Controlled Beam Splitter Gate
• QRAM: A Survey and Critique
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• Two-level Quantum Walkers on Directed Graphs II: An Application to qRAM
• Nondestructive classification of quantum states using an algorithmic quantum computer
• Quantum Power Flows: From Theory to Practice
• Hardware-Efficient Quantum Random Access Memory Design with a Native Gate Set on Superconducting Platforms
• Quantum matching pursuit: A quantum algorithm for sparse representations
• Quantum algorithm for the Vlasov simulation of the large-scale structure formation with massive neutrinos
• Quantum computing for genomics: conceptual challenges and practical perspectives
• A quantum random access memory (QRAM) using a polynomial encoding of binary strings
• Tangible reduction in learning sample complexity with large classical samples and small quantum system
• Quantum-classical reinforcement learning for decoding noisy classical parity information
• Hybrid Quantum-Classical Algorithm For Robust Optimization via Stochastic-Gradient Online Learning
• The Quantum Monadology
• Context aware quantum simulation of a matrix stored in quantum memory
• Error-Mitigated Quantum Routing on Noisy Devices
• Quantum Alphatron: quantum advantage for learning with kernels and noise
• Optimal Qubit Mapping Search for Encoding Classical Data into Matrix Product State Representation with Minimal Loss
• Ensuring superior learning outcomes and data security for authorized learner
• Unified Architecture for Quantum Lookup Tables
• Sample-size-reduction of quantum states for the noisy linear problem
• Robust and optimal loading of general classical data into quantum computers
• Error-Mitigated Multi-Layer Quantum Routing
• Error-Mitigated Quantum Random Access Memory
• Exploring Quantum Bootstrap Sampling for AQP Error Assessment: A Pilot Study