QRAM as the Hidden Price of Quantum Speedup: Lattice Sifting and Cryptanalysis

05.11.2026

A research paper examines why quantum acceleration for lattice sieving may require quantum random-access memory—and what this means for post-quantum cryptography. The paper explores the question: does quantum acceleration of lattice sieving necessarily require large QRAM? In the proposed model with limited QRAM, a lower bound is obtained: with a QRAM size of ,   the query complexity is no less than  .   This implies no quantum gain in this query model. Furthermore, a nontrivial tradeoff between QRAM size and time is demonstrated, and a QRAM-free scheme is constructed that is faster than the classical one in depth but requires an exponential number of qubits. This does not contradict the lower bound: different complexity models are compared.2s20.2925d − 2s + o(d)s = 0

Content

⚙️ Detailed research option

  1. Central question and hypothesis
  2. Why is this important?
  3. Model and method of analysis
  4. Key results
  5. Selected questions to be tested
  6. Linking works into a coherent study
  7. What does this change for cryptography?
  8. Limitations and alternative explanations
  9. Next experiment and test
  10. Conclusion
  11. Sources

1. Central question and hypothesis

⚙️ Detailed research option

Quantum algorithms for lattice cryptanalysis are often discussed in terms of their time asymptotics: classical sifting has a complexity of about  , while the best quantum variants have a complexity of about  . However, behind quantum acceleration lie resources that don’t always make the headlines: the circuit depth, the number of qubits, and QRAM—quantum RAM that allows access to data in a superposition of addresses.20.2925d + o(d)20.2563d + o(d)

The central question of the paper is:  is it possible to achieve quantum speedup of lattice sieving without large QRAM, or is QRAM a hidden cost of such speedup?

Hypothesis H1.  In a hash-based near-neighbor model encompassing known variants of lattice sifting, quantum speedup beyond the classical lower bound   is impossible without QRAM. If QRAM of size is allowed  , then the lower bound for query complexity is  .20.2925d + o(d)2s20.2925d − 2s + o(d)

Criterion for refuting H1.  It is sufficient to present, in the same query model, a QRAM-free algorithm using a polynomial number of qubits and depth that solves the near-neighbor problem with a significantly lower number of queries  . Such an algorithm has not yet been found; moreover, this work demonstrates why finding one requires a fundamentally new idea.20.2925d + o(d)

Second hypothesis H2.  There is a smooth tradeoff between classical and quantum sifting: the larger the allowed QRAM, the stronger the quantum speedup; however, small QRAM still requires strong assumptions about fast data replacement.

Third hypothesis H3.  Quantum acceleration without QRAM is possible in the standard circuit model only through an exponential number of qubits; such acceleration does not negate the lower bound on query complexity, because these are different measures of resources.

2. Why is this important?

⚙️ Detailed research option

Lattice cryptography is one of the leading candidates for post-quantum cryptography. Its security is assessed, among other things, by the complexity of solving the shortest vector problem (SVP). For a dimension,  d classical sifting requires time   and memory  ; enumeration requires polynomial memory but has superexponential complexity  . Therefore, the question of quantum sifting resources directly affects the feasibility of quantum attacks on PQC schemes.2O(d)2O(d)2O(d log d)

The problem is that QRAM isn’t just “another register.” Known QRAM architectures have fundamental limitations; some researchers consider QRAM expensive or potentially unrealistic. If quantum acceleration of sifting is impossible without large QRAM, then the practical value of such acceleration depends on whether efficient QRAM can be built. This changes priorities: perhaps quantum enumeration with full quadratic acceleration will be more practical than quantum sifting in a world without large QRAM.

Moreover, similar issues arise in symmetric cryptography: algorithms for collision detection and multi-target preimage search that do not require QRAM, but have worse complexity, are known. The work demonstrates a smooth tradeoff between QRAM and time for these tasks as well.

3. Model and method of analysis

⚙️ Detailed research option

The authors consider not a specific physical implementation, but  a query model  for hash-based near-neighbor algorithms. This is important: the lower bound is formulated for a class of algorithms, not for all conceivable quantum circuits.

3.1. Near-neighbor problem

⚙️ Detailed research option

Given a set of random vectors  , we need   to find almost all  , for which ,  for a query . Lattice sifting uses such near-neighbor subroutines to find “reducing pairs.”L ⊂ Sd−1xy ∈ L⟨x,y⟩ ≥ cos θ

3.2. Limited QRAM

⚙️ Detailed research option

QRAM allows for queries of the form [ ]   and, most importantly, accessing data in a superposition of addresses. This article discusses QRACM—quantum memory with classical data. If QRAM of size [ ] is available  , the algorithm can coherently operate on no more than [   ] elements at a time.|i⟩|0⟩ ↦ |i⟩|xi⟩2s2s

3.3 Two important assumptions

⚙️ Detailed research option

Assumption 1.  A coherent state of the form   for a subset of input vectors must be generated via QRAM access. In other words, it is assumed that there is no known efficient way to obtain such a superposition without QRAM.Σ αi|i⟩|vi⟩

Assumption 2.  A similar requirement applies to coherent access to filter indices.

Important:  This isn’t a claim that superposition can’t be achieved with a conventional circuit. Technically, it’s possible, but known methods require a large number of gates and depth. The assumptions state that efficient coherent access occurs through QRAM. That’s why the lower bound is conditional: it applies to an explicitly described model.

3.4 Method of proof

⚙️ Detailed research option

The idea of ​​the lower bound: if a quantum algorithm  A with QRAM size   makes   queries, then one can construct a classical algorithm  that simulates   and makes at most   classical queries. Then, the classical lower bound of Kirshanova and Laarhoven is applied: at least   queries. Hence  , , that is  , .2sqBA22s q20.2925d + o(d)22s q ≥ 20.2925d + o(d)q ≥ 20.2925d − 2s + o(d)

4. Key results

⚙️ Detailed research option

4.1 Lower Bound with Limited QRAM

⚙️ Detailed research option

For QRAM size,   the query complexity is not lower2s

2 0.2925d − 2s + o(d)

For  , s = 0 we obtain   the classical lower bound. In this model, there is no quantum acceleration without QRAM.20.2925d + o(d)

4.2. QRAM vs. Time Tradeoff

⚙️ Detailed research option

The work refines the interpolation between classical LSF and quantum variants. Specifically, the variant with a bucket search for each filter allows for   a QRAM size of approximately  .20.2653d + o(d)20.05778d + o(d)

4.3. Best known result with full QRAM

⚙️ Detailed research option

With unlimited QRAM, the best known complexity is   using reusable quantum walks. This defines the “lower right corner” of the tradeoff graph.20.2563d + o(d)

4.4. Scheme without QRAM

⚙️ Detailed research option

A quantum circuit without QRAM has been constructed that has a lower depth than classical algorithms but requires an exponential number of qubits. With   qubits, the time is approximately  . This is the first QRAM-less result in the standard circuit model, faster than the classical one, with minimal space  .20.207d20.279d20.207d

4.5 Symmetric cryptography

⚙️ Detailed research option

For collision detection with QRAM size,   the complexity obtained is  . For multi-target preimage search, it   is under certain constraints. This links lattice and symmetric cryptanalysis through the general idea of ​​limited QRAM.2γ22n/5 − γ/523n/7 − 2γ/7

4.6. Comparison of BKZ

⚙️ Detailed research option

If large QRAM is unavailable, quantum enumeration can outperform quantum sifting for relatively large block sizes. This is an important practical conclusion: the gain depends not only on the asymptotics but also on the resource model.

4.7 Why the QRAM-free circuit does not refute the lower bound

⚙️ Detailed research option

The QRAM-free scheme uses an exponential number of qubits and massive parallelism: comparisons are performed in parallel, so the depth is smaller than the classical one. However, the lower bound in the paper is an estimate of  query complexity , not depth or width. In the query model, the QRAM-free algorithm must still make at least as many   queries. The QRAM-free scheme does not violate this constraint; it changes the balance between depth, width, and number of qubits.20.2925d + o(d)

The main paradox:  Quantum acceleration can exist “in depth,” but not “in query complexity” without QRAM. Therefore, the question “is there acceleration?” is incorrect without specifying the complexity model and available resources.

5. Selected questions to be tested

⚙️ Detailed research option

The question constructor selected questions that directly relate to the hypothesis and do not turn the article into a review of the entire quantum field. Each question is assigned a testable meaning.

No.QuestionWhat is checked in the article
1What specific problem does the technology solve?Reducing the cost of lattice sifting in a quantum model and assessing the feasibility of attacks on PQC.
2What question seems paradoxical but can be tested?Can a quantum algorithm be faster than a classical one, but not provide speedup without QRAM?
4How to formulate a testable hypothesis and its refutation?H1: Lower bound  ; refutation – QRAM-less algorithm with polynomial qubits below the classical bound.20.2925d−2s
6What outcome would change the experts’ views?Proof of quantum speedup without QRAM in the same query model.
7What is the underlying physical mechanism?Coherent data access, amplitude gain, quantum walks, address superposition.
8The role of superposition, interference, entanglement, measurementSuperposition of QRAM addresses; interference in Grover/amplitude amplification; measurement during response extraction.
9What effects are really needed?Coherent access and amplitude gain are important for acceleration; entanglement alone is not a sufficient explanation.
11What model assumptions might no longer hold?Assumption 1 and 2; efficient replacement of QRAM; physical feasibility of QRAM.
17What do experts agree on, and where is the debate?Consensus: QRAM is hard. Debate: to what extent does the lower bound reflect all possible quantum algorithms?
25How is the problem translated into a quantum circuit?Near-neighbor → LSF filters → amplitude gain → QRAM access to buckets.
29Depth, number of operations, runs, connectivityQuery complexity, depth, and width are compared; the design without QRAM is considered separately.
37To which classical method is the approach compared?With classical LSF [12] and classical lower bound [40].
38Are the accuracy, success probability, resources the same?Single-model comparison; QRAM, qubits, and depth are taken into account; polynomial factors are omitted.
39What is claimed: theory, experiment or practical usefulness?Theoretical lower bound and theoretical tradeoffs; no experimental data.
42Can an improved classical algorithm change the conclusions?The lower bound [40] gives a classical bound; improving it would require revising the comparison.
43What is the basis for the conclusion?Proof in query model, reduction to classical lower bound, subroutine analysis.
44Control experiments and alternative explanationsAn alternative is a QRAM-free scheme with exponential qubits; it does not violate the query lower bound.
69What issues remain open?Exact optimality of the tradeoff; lifting of assumptions 1–2; polynomial QRAM-less scheme.

5.1. Profile cryptographic questions

⚙️ Detailed research option

No.QuestionAnswer within the article
49What cryptographic problem is being considered?Lattice SVP/near-neighbor; additionally, collision detection and multi-target preimage search.
50Which quantum algorithm is applicable?LSF + amplitude gain; quantum walks; limited QRAM version of Grover.
51Resource estimates and acceptable errorAsymptotic estimates of time and QRAM; success probability is assumed to be fairly high; constants are not optimized.
53The difference between QKD and post-quantum cryptographyThe article is not about QKD, but about cryptanalysis of PQC candidates; QRAM is an attacker’s resource, not a communication protocol.
70What further experiments will distinguish between the explanations?Comparison of specific QRAM architectures; data replacement cost estimation; end-to-end BKZ modeling.
74How will the conclusions change under different assumptions?With efficient QRAM, the gain remains; with expensive QRAM, it does not; without QRAM, only exponential-width circuit acceleration remains.

6. Connection of works into a consistent study

⚙️ Detailed research option

The paper doesn’t examine any single work in isolation. It builds a chain: classical lower bound → classical LSF → quantum improvements with QRAM → limited QRAM → QRAM-free scheme → applications to symmetric cryptography.

Work / resultContributionRole in the chain
Kirshanova, Laarhoven [40]Classical lower bound   in the near-neighbor model20.2925d + o(d)Baseline: What a quantum algorithm needs to beat.
Becker et al. [12]Classic LSF with optimal complexity 20.2925dAlgorithmic basis for quantum modifications.
Laarhoven [42], Chailloux–Loyer [18]Quantum search inside α-close filters; 20.2653dFirst step: QRAM is used for amplitude gain.
Heiser [33]Quantum search by α-close filters; 20.2571dEnhanced by filter sampler and Grover search.
Bonnetain et al. [14]Reusable quantum walks; 20.2563dBest known result with full QRAM.
Chailloux et al. [19]Collision finding without QRAM; 22n/5Shows that QRAM-less acceleration is possible in other tasks, but at a different cost.
Bindel et al. [13]Quantum enumeration in limited depthThe question arises: will enumeration be more practical than sieving without large QRAM?
Albrecht et al. [5]Specific estimates of quantum siftingShows that known quantum circuits require large depth and QRAM.

6.1. Linking paragraph

⚙️ Detailed research option

The paper [40] establishes a classical lower bound for a wide class of hash-based near-neighbor algorithms. The paper [12] achieves this bound with classical LSF. Quantum papers [42,18,33,14] improve the time but use QRAM for coherent access to filter data. The preprint arXiv:2410.15565v1 adds a limit on the QRAM size and shows that the gain smoothly disappears as QRAM decreases, while  s = 0 the classical bound remains for the query model. The QRAM-free scheme from Section 7 changes the depth-width balance but does not cancel the query lower bound. Therefore, the correct conclusion is not “quantum sifting is useless” but “its speedup is conditional and depends on QRAM and the resource model.”

7. What does this change for cryptography?

⚙️ Detailed research option

For post-quantum cryptography, not only the asymptotic exponent is important  d, but also the total cost of the attack. If QRAM is expensive, then:

  • quantum sifting may perform worse than quantum enumeration under realistic constraints;
  • PQC security assessments should explicitly state the QRAM model and data replacement assumptions;
  • the results of the view   cannot be automatically interpreted as a practical threat without assessing the QRAM and depth;20.2563d
  • In symmetric cryptography, small QRAM provides a limited but measurable gain; without QRAM, we are left with algorithms with worse complexity, but without quantum memory.

This doesn’t mean that PQC is “secure because of QRAM.” It means that cryptanalytic evaluations must be resource-fair: comparing algorithms under the same assumptions about memory, depth, number of qubits, and success probability.

8. Limitations and alternative explanations

⚙️ Detailed research option

Limitation 1. Query model ≠ all quantum circuits.  The lower bound is proven for a class of algorithms that follow the paper’s model. It does not prohibit the existence of a completely different algorithm outside this model.

Limitation 2. Assumptions 1 and 2.  They claim that coherent states of filter vectors and indices are only efficiently obtained via QRAM. This is reasonable for known methods, but does not mathematically prohibit all conceivable schemes.

Limitation 3. Efficient QRAM replacement.  Compromise algorithms assume that data in QRAM can be replaced in   for memory of size  . This is a very strong assumption. In the alternative “physical QRAM objects” model, creation costs  , but insertion costs  ; this mitigates, but does not eliminate, the problem.2o(s)2sO(N)O(1)

Limitation 4. Asymptotics and constants.  Estimates of the form   ignore polynomial factors. For real dimensions, constants and QRAM cost may dominate.20.2925d

Limitation 5. No experiment.  This is a theoretical study. It does not demonstrate physical QRAM or measure errors. Therefore, conclusions about the practical threat require a separate engineering analysis.

An alternative explanation:  One could speculate that quantum acceleration without QRAM is still possible through a completely new use of quantum circuits, such as massive parallelism with polynomial width. The paper does not describe such an algorithm; a QRAM-free circuit requires an exponential number of qubits. This leaves an open question but provides no counterexample to the lower bound.

9. Next experiment and verification

⚙️ Detailed research option

To transform a theoretical article into a testable research program, at least four steps are required.

  1. Formal verification of the lower bound.  Independently reproduce the reduction to the classical query model and verify where exactly Assumptions 1 and 2 are used.
  2. Comparison of QRAM architectures.  Estimate the cost of creating, connecting, and replacing data for specific QRAM offerings; apply these costs to tradeoff formulas.
  3. End-to-end BKZ model.  Compare BKZ + quantum enumeration, BKZ + quantum sifting with full QRAM, and BKZ + quantum sifting with limited QRAM with the same block size and success probability.
  4. Find a counterexample.  Try to build a QRAM-less algorithm with polynomial qubits and query complexity lower than  . If this succeeds, H1 will be refuted; if not, the bound will become even stronger.20.2925d

The criterion for success of the study  is not to “prove that QRAM is impossible,” but to show under which resource assumptions the quantum speedup of lattice sifting is preserved, and under which it disappears. This is a fair and verifiable statement.

10. Conclusion

⚙️ Detailed research option

Preprint arXiv:2410.15565v1 provides a strong argument that QRAM is not a minor detail, but a central resource for quantum acceleration of lattice sifting. In the bounded-QRAM query model, the lower bound   shows that without QRAM, quantum speedup beyond the classical bound is impossible. As QRAM increases, a smooth tradeoff emerges, but even small QRAM requires strong assumptions about efficient data replacement.20.2925d − 2s + o(d)

A QRAM-free design with an exponential number of qubits demonstrates that acceleration is possible in depth, but it doesn’t invalidate the query lower bound. This is an important methodological lesson: the question “is there a quantum advantage?” should always be accompanied by the question “under what resource model and at what memory cost?”

For post-quantum cryptography, the practical conclusion is cautious: security assessments based on quantum sifting must explicitly take into account QRAM. Otherwise, one could overestimate the feasibility of a quantum attack—or, conversely, underestimate the cost of its engineering implementation.

Sources and reference works

⚙️ Detailed research option

  1. arXiv:2410.15565v1. Preprint on the role of QRAM in quantum lattice sifting: lower bounds, QRAM-time tradeoff, and a QRAM-free scheme. Primary source of analysis.
  2. “Quantum Technologies: Research Article Questions” is a question constructor used to formulate testable questions and structure the article.
  3. Kirshanova E., Laarhoven T. Lower bounds on lattice sieving and information set decoding. CRYPTO 2021. Classical lower bound  .20.2925d + o(d)
  4. Becker A., ​​Ducas L., Gama N., Laarhoven T. New directions in nearest neighbor searching with applications to lattice sieving. SODA 2016. Classic LSF.
  5. Laarhoven T. Search problems in cryptography: from fingerprinting to lattice sieving. PhD thesis, 2016. Quantum LSF p  .20.2653d
  6. Chailloux A., Loyer J. Lattice sieving via quantum random walks. ASIACRYPT 2021. Quantum walks and QRAM.
  7. Heiser M. Improved quantum hypercone locality sensitive filtering in lattice sieving. ePrint 2021/1295. Result  .20.2571d
  8. Bonnetain X., Chailloux A., Schrottenloher A., ​​Shen Y. Finding many collisions via reusable quantum walks: application to lattice sieving. EUROCRYPT 2023. Result  .20.2563d
  9. Chailloux A., Naya-Plasencia M., Schrottenloher A. An efficient quantum collision search algorithm and implications on symmetric cryptography. ASIACRYPT 2017. QRAM-less collision finding.
  10. Bindel N., Bonnetain X., Tiepelt M., Virdia F. Quantum lattice enumeration in limited depth. CRYPTO 2024. Limited depth and practicality of enumeration.
  11. Albrecht M. et al. Estimating quantum speedups for lattice sieves. ASIACRYPT 2020. Specific resource estimates.

Pre-publication review

⚙️ Detailed research option

  • Theoretical lower bounds, asymptotic tradeoffs, and engineering predictions are separated.
  • It is indicated that the lower bound is conditional and is valid in the query model with Assumption 1–2.
  • It is not claimed that QRAM is physically impossible; its cost and limitations are discussed.
  • The QRAM-free circuit is not presented as a refutation of the lower bound: the difference between query complexity and circuit width is explained.
  • Comparisons with classical algorithms are given under the same asymptotic assumptions.
  • Polynomial factors, constants and absence of experiment are noted.
  • The reader is shown what new the article provides and what the next testable step is.

Article working card

⚙️ Detailed research option

Topic and audienceQuantum lattice cryptanalysis; researchers in PQC, quantum algorithms, and QRAM architectures.
The central questionDoes quantum acceleration of lattice sieving necessarily require large QRAM?
Hypothesis and refutationH1: Without QRAM, there is no speedup in the query model; refutation: a QRAM-less algorithm with polynomial qubits is below the classical bound.
MethodQuery model analysis, reduction to classical lower bound, tradeoff comparison, QRAM-free circuit analysis.
MetricsQuery complexity, depth, width, number of qubits, QRAM size, asymptotic degree  d.
RestrictionsModel, Assumption 1–2, efficient replacement of QRAM, no experiment, polynomial factors.
New contributionA coherent interpretation of the lower bound, the compromise, and the QRAM-less scheme as different answers to the same resource question.
The next stepCompare specific QRAM architectures and end-to-end BKZ models under the same assumptions.