A quantum random access memory (QRAM) using a polynomial encoding of binary strings

Abstract

Quantum algorithms claim significant speedup over their classical counterparts for solving many problems. An important aspect of many of these algorithms is the existence of a quantum oracle, which needs to be implemented efficiently in order to realize the claimed advantages. A quantum random access memory (QRAM) is a promising architecture for realizing these oracles. In this paper we develop a new design for QRAM and implement it with Clifford+T circuit. We focus on optimizing the T-count and T-depth since non-Clifford gates are the most expensive to implement fault-tolerantly. Integral to our design is a polynomial encoding of bit strings and so we refer to this design as ${\text{QRAM}}_{poly}$. Compared to the previous state-of-the-art bucket brigade architecture for QRAM, we achieve an exponential improvement in T-depth, while reducing T-count and keeping the qubit count same. Specifically, if $N$ is the number of memory locations, then ${\text{QRAM}}_{poly}$ has T-depth $O(\log \log N)$, T-count $O(N-\log N)$ and qubit count $O(N)$, while the bucket brigade circuit has T-depth $O(\log N)$, T-count $O(N)$ and qubit count $O(N)$. Combining two ${\text{QRAM}}_{poly}$ we design a quantum look-up-table, ${\text{qLUT}}_{poly}$, that has T-depth $O(\log \log N)$, T-count $O(\sqrt{N})$ and qubit count $O(\sqrt{N})$. A qLUT or quantum read-only memory (QROM) has restricted functionality than a QRAM and needs to be compiled each time the contents of the memory change. The previous state-of-the-art CSWAP architecture has T-depth $O(\sqrt{N})$, T-count $O(\sqrt{N})$ and qubit count $O(\sqrt{N})$. Thus we achieve a double exponential improvement in T-depth while keeping the T-count and qubit-count asymptotically same. Additionally, with our polynomial encoding of bit strings, we develop a method to optimize the Toffoli-count of circuits, specially those consisting of multi-controlled-NOT gates.

arXiv commentAccepted in Scientific Reports

References in corpus (42)

• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Surface codes: Towards practical large-scale quantum computation
• Quantum Chemistry in the Age of Quantum Computing
• Quantum random access memory
• Quantum algorithms for quantum chemistry and quantum materials science
• Elucidating Reaction Mechanisms on Quantum Computers
• Quantum machine learning: a classical perspective
• Architectures for a quantum random access memory
• Halving the cost of quantum addition
• Low Depth Quantum Simulation of Electronic Structure
• Quantum computing enhanced computational catalysis
• Provably efficient machine learning for quantum many-body problems
• Quantum circuits of T-depth one
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Novel constructions for the fault-tolerant Toffoli gate
• Hardware-efficient quantum random access memory with hybrid quantum acoustic systems
• Circuit-Based Quantum Random Access Memory for Classical Data
• On the robustness of bucket brigade quantum RAM
• Fault tolerant resource estimation of quantum random-access memories
• Trading T gates for dirty qubits in state preparation and unitary synthesis
• Resilience of quantum random access memory to generic noise
• On the Power of Quantum Memory
• A Robust Quantum Random Access Memory
• Circuit-based quantum random access memory for classical data with continuous amplitudes
• T-count and T-depth of any multi-qubit unitary
• Parallelising the Queries in Bucket Brigade Quantum RAM
• Scalable and High-Fidelity Quantum Random Access Memory in Spin-Photon Networks
• Convex optimization using quantum oracles
• Fault-tolerant quantum simulation of materials using Bloch orbitals
• Data centers with quantum random access memory and quantum networks
• Reducing the CNOT count for Clifford+T circuits on NISQ architectures
• Quantum random access memory via quantum walk
• Systems Architecture for Quantum Random Access Memory
• Quantum Data Center: Perspectives
• Optimal Usage of Quantum Random Access Memory in Quantum Machine Learning
• A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits
• Multi-qubit time-bin quantum RAM
• Resource-efficient simulation of noisy quantum circuits and application to network-enabled QRAM optimization
• Two-level Quantum Walkers on Directed Graphs II: An Application to qRAM
• Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian
• A Q# Implementation of a Quantum Lookup Table for Quantum Arithmetic Functions

Cited by in corpus (2)

• Hybrid Quantum-Classical Algorithm For Robust Optimization via Stochastic-Gradient Online Learning
• Refined Criteria for QRAM Error Suppression via Efficient Large-Scale QRAM Simulator