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.
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.
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. 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. Escaping the constraints of active QRAM 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. In summary, we conclude that cheap, asymptotically scalable passive QRAM is unlikely with existing proposals, due to fundamental obstacles that we highlight. These obstacles are deeply rooted in the requirements of QRAM, but are not provably inevitable; we hope that our results will help guide research into QRAM technologies that circumvent or mitigate these obstacles. 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.
Abstract. The most important computational problem on lattices is the shortest vector problem ([Formula: see text]). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for [Formula: see text]. We present the following results: (1) A new algorithm for [Formula: see text] that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer [Formula: see text], our algorithm takes [Formula: see text] time and requires [Formula: see text] memory. This tradeoff, which ranges from enumeration ([Formula: see text]) to sieving ([Formula: see text] constant), is a consequence of a new time-memory tradeoff for discrete Gaussian sampling above the smoothing parameter. (2) A quantum algorithm for [Formula: see text] that runs in time [Formula: see text] and requires [Formula: see text] classical memory and [Formula: see text] qubits. In a quantum random access memory (QRAM) model, this algorithm takes only [Formula: see text] time and requires a QRAM of size [Formula: see text], [Formula: see text] qubits and [Formula: see text] classical space. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [D. Aggarwal et al., Solving the shortest vector problem in 2 n time using discrete Gaussian sampling: Extended abstract, in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC), 2015, pp. 733–742] that has a time and space complexity [Formula: see text]. (3) A classical algorithm for [Formula: see text] that runs in time [Formula: see text] time and [Formula: see text] space. This improves over an algorithm of [Y. Chen, K. Chung, and C. Lai, Quantum Inf. Comput., 18 (2018), pp. 285–306] that has the same space complexity. The time complexity of our classical and quantum algorithms are obtained using a known upper bound on a quantity related to the lattice kissing number, which is [Formula: see text]. We conjecture that for most lattices this quantity is a [Formula: see text]. Assuming that this is the case, our classical algorithm runs in time [Formula: see text], our quantum algorithm runs in time [Formula: see text], and our quantum algorithm in a QRAM model runs in time [Formula: see text]. As a direct application of our result, using the reduction in [L. Ducas, Des. Codes. Cryptogr., 92 (2024), pp. 909–916], we obtain a provable quantum algorithm for the lattice isomorphism problem in the case of the trivial lattice [Formula: see text] ([Formula: see text] LIP ) that runs in time [Formula: see text]. Our algorithm requires a QRAM of size [Formula: see text], [Formula: see text] qubits and [Formula: see text] classical space.
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, greatly accelerating a wide range of computer processes. Despite its importance, there is a lack of comprehensive surveys that cover the entire spectrum of QRAM architectures. We fill this gap by providing a comprehensive review of QRAM, emphasizing its significance and viability in existing noisy quantum computers. By drawing comparisons with conventional RAM for ease of understanding, this survey clarifies the fundamental ideas and actions of QRAM. QRAM provides an exponential time advantage compared to its classical counterpart by reading and writing all data at once, which is achieved owing to storage of data in a superposition of states. Overall, we compare six different QRAM technologies in terms of their structure and workings, circuit width and depth, unique qualities, practical implementation, and drawbacks. In general, with the exception of trainable machine learning-based QRAMs, we observe that QRAM has exponential depth/width requirements in terms of the number of qubits/qudits and that most QRAM implementations are practical for superconducting and trapped-ion qubit systems.
This thesis studies the security of lattice-based and code-based cryptography, two leading approaches to post-quantum cryptography. Although several lattice-based and code-based schemes have been selected for standardization and deployment, these schemes and their underlying computational problems have received less scrutiny than those they aim to replace. Continued cryptanalysis is therefore essential to build confidence in the security of post-quantum cryptography. The first part of this thesis concerns the classical cryptanalysis of lattice-based cryptography. We provide an algorithm that solves the Short Integer Solution problem in subexponential time for nontrivial parameter regimes. Moreover, we develop a predictive model for analyzing the practical performance of module-BKZ, a module-lattice analog of the BKZ algorithm. The second part considers the quantum cryptanalysis of lattice-based and code-based cryptography, focusing on quantum speedups for sieving algorithms. We present a new quantum algorithm for 3-tuple lattice sieving that yields an improved time-memory trade-off for solving the Shortest Vector Problem. We also introduce quantum algorithms for code sieving and investigate their potential for attacking code-based cryptography. Together, these results provide new insights into the security of lattice-based and code-based cryptography and highlight several directions for future research.
Operating on the principles of quantum mechanics, quantum algorithms hold the promise for solving problems that are beyond the reach of the best-available classical algorithms. An integral part of realizing such speedup is the implementation of quantum queries, which read data into forms that quantum computers can process. Quantum random access memory (QRAM) is a promising architecture for realizing quantum queries. However, implementing QRAM in practice poses significant challenges, including query latency, memory capacity and fault-tolerance.
Using quantum algorithms to carry out ML tasks is what is known as Quantum Machine Learning (QML) and the methods developed within this field have the potential to outperform their classical counterparts in solving certain learning problems. The development of the field is partly dependent on that of a functional quantum random access memory (QRAM), called for by some of the algorithms devised. Such a device would store data in a superposition and could then be queried when algorithms require it, similarly to its classical counterpart, allowing for efficient data access. Taking an axiomatic approach to QRAM, this thesis provides the main considerations, assumptions and results regarding QRAM and yields a QRAM handbook and comprehensive introduction to the literature pertaining to it.