QRAM: A Survey and Critique

• URL: http://arxiv.org/abs/2305.10310v1
• Date: Wed, 17 May 2023 15:48:48 GMT
• Title: QRAM: A Survey and Critique
• Authors: Samuel Jaques, Arthur G. Rattew
• Abstract summary: Quantum random-access memory (QRAM) is a mechanism to access data based on addresses which are themselves a quantum state. We use two primary categories of QRAM from the literature: active and passive. In summary, we conclude that cheap, scalableally passive QRAM is unlikely with existing proposals.
• Score: 1.52292571922932
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum random-access memory (QRAM) is a mechanism to access data (quantum or classical) based on addresses which are themselves a quantum state. QRAM has a long and controversial history, and here we survey and expand arguments and constructions for and against. We use two primary categories of QRAM from the literature: (1) active, which requires external intervention and control for each QRAM query (e.g. the error-corrected circuit model), and (2) passive, which requires no external input or energy once the query is initiated. In the active model, there is a powerful opportunity cost argument: in many applications, one could repurpose the control hardware for the qubits in the QRAM (or the qubits themselves) to run an extremely parallel classical algorithm to achieve the same results just as fast. Escaping these constraints requires ballistic computation with passive memory, which creates an array of dubious physical assumptions, which we examine in detail. Considering these details, in everything we could find, all non-circuit QRAM proposals fall short in one aspect or another. We apply these arguments in detail to quantum linear algebra and prove that most asymptotic quantum advantage disappears with active QRAM systems, with some nuance related to the architectural assumptions. In summary, we conclude that cheap, asymptotically scalable passive QRAM is unlikely with existing proposals, due to fundamental limitations that we highlight. We hope that our results will help guide research into QRAM technologies that attempt to circumvent or mitigate these limitations. Finally, circuit-based QRAM still helps in many applications, and so we additionally provide a survey of state-of-the-art techniques as a resource for algorithm designers using QRAM.

Related papers

• Does quantum lattice sieving require quantum RAM? [6.159206988529989]
  We study the requirement for quantum random access memory (QRAM) in quantum lattice sieving. In particular, no quantum speedup is possible without QRAM. We show that further improvements require a novel way to use the QRAM.
  arXiv  Detail & Related papers  (2024-10-21T01:22:59Z)
• QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum Circuits [82.50620782471485]
  QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits. It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness. Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
  arXiv  Detail & Related papers  (2024-01-10T22:33:00Z)
• Systems Architecture for Quantum Random Access Memory [0.6386668251980657]
  Quantum random access memory (QRAM) is a promising architecture for realizing quantum queries. We show how to leverage the intrinsic biased-noise resilience of the proposed QRAM for implementation on either Noisy Intermediate-Scale Quantum (NISQ) or Fault-Tolerant Quantum Computing (FTQC) hardware.
  arXiv  Detail & Related papers  (2023-06-05T20:52:28Z)
• Quantum Random Access Memory For Dummies [4.608607664709314]
  Quantum Random Access Memory (QRAM) has the potential to revolutionize the area of quantum computing. QRAM uses quantum computing principles to store and modify quantum or classical data efficiently.
  arXiv  Detail & Related papers  (2023-05-02T03:24:16Z)
• Efficient and Error-Resilient Data Access Protocols for a Limited-Sized Quantum Random Access Memory [7.304498344470287]
  We focus on the access of larger data sizes without keeping on increasing the size of the QRAM. We propose a novel protocol for loading data with larger word lengths $k$ without increasing the number of QRAM levels $n$. By exploiting the parallelism in the data query process, our protocol achieves a time complexity of $O(n+k)$ and improves error scaling performance.
  arXiv  Detail & Related papers  (2023-03-09T12:21:18Z)
• Approximate Quantum Random Access Memory Architectures [7.509129971169722]
  Quantum supremacy in many applications using well-known quantum algorithms rely on availability of data in quantum format. We propose an approximate Parametric Quantum Circuit (PQC) based QRAM which takes address lines as input and gives out the corresponding data in these address lines as the output. We present two applications of the proposed PQC-based QRAM namely, storage of binary data and storage of machine learning (ML) dataset for classification.
  arXiv  Detail & Related papers  (2022-10-24T19:53:28Z)
• Iterative Qubits Management for Quantum Index Searching in a Hybrid System [56.39703478198019]
  IQuCS aims at index searching and counting in a quantum-classical hybrid system. We implement IQuCS with Qiskit and conduct intensive experiments. Results demonstrate that it reduces qubits consumption by up to 66.2%.
  arXiv  Detail & Related papers  (2022-09-22T21:54:28Z)
• A hybrid quantum image edge detector for the NISQ era [62.997667081978825]
  We propose a hybrid method for quantum edge detection based on the idea of a quantum artificial neuron. Our method can be practically implemented on quantum computers, especially on those of the current noisy intermediate-scale quantum era.
  arXiv  Detail & Related papers  (2022-03-22T22:02:09Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• Parallelising the Queries in Bucket Brigade Quantum RAM [69.43216268165402]
  Quantum algorithms often use quantum RAMs (QRAM) for accessing information stored in a database-like manner. We show a systematic method to significantly reduce the effective query time by using Clifford+T gate parallelism. We conclude that, in theory, fault-tolerant bucket brigade quantum RAM queries can be performed approximately with the speed of classical RAM.
  arXiv  Detail & Related papers  (2020-02-21T14:50:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.