Does quantum lattice sieving require quantum RAM?

• URL: http://arxiv.org/abs/2410.15565v1
• Date: Mon, 21 Oct 2024 01:22:59 GMT
• Title: Does quantum lattice sieving require quantum RAM?
• Authors: Beomgeun Cho, Minki Hhan, Taehyun Kim, Jeonghoon Lee, Yixin Shen,
• Abstract summary: 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.
• Score: 6.159206988529989
• License:
• Abstract: In this paper, we study the requirement for quantum random access memory (QRAM) in quantum lattice sieving, a fundamental algorithm for lattice-based cryptanalysis. First, we obtain a lower bound on the cost of quantum lattice sieving with a bounded size QRAM. We do so in a new query model encompassing a wide range of lattice sieving algorithms similar to those in the classical sieving lower bound by Kirshanova and Laarhoven [CRYPTO 21]. This implies that, under reasonable assumptions, quantum speedups in lattice sieving require the use of QRAM. In particular, no quantum speedup is possible without QRAM. Second, we investigate the trade-off between the size of QRAM and the quantum speedup. We obtain a new interpolation between classical and quantum lattice sieving. Moreover, we show that further improvements require a novel way to use the QRAM by proving the optimality of some subroutines. An important caveat is that this trade-off requires a strong assumption on the efficient replacement of QRAM data, indicating that even speedups with a small QRAM are already challenging. Finally, we provide a circuit for quantum lattice sieving without using QRAM. Our circuit has a better depth complexity than the best classical algorithms but requires an exponential amount of qubits. To the best of our knowledge, this is the first quantum speedup for lattice sieving without QRAM in the standard quantum circuit model. We explain why this circuit does not contradict our lower bound, which considers the query complexity.

Related papers

• 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)
• QRAM: A Survey and Critique [1.52292571922932]
  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.
  arXiv  Detail & Related papers  (2023-05-17T15:48:48Z)
• 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)
• 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)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• 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)
• Towards understanding the power of quantum kernels in the NISQ era [79.8341515283403]
  We show that the advantage of quantum kernels is vanished for large size datasets, few number of measurements, and large system noise. Our work provides theoretical guidance of exploring advanced quantum kernels to attain quantum advantages on NISQ devices.
  arXiv  Detail & Related papers  (2021-03-31T02:41:36Z)
• Quantum random access memory via quantum walk [0.0]
  A novel concept of quantum random access memory (qRAM) employing a quantum walk is provided. Our scheme is fully parallelized. Consequently, only O(n) steps are required to access and retrieve O(2n) data in the form of quantum superposition states.
  arXiv  Detail & Related papers  (2020-08-31T04:54:12Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• 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.