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
- Central question and hypothesis
- Why is this important?
- Model and method of analysis
- Key results
- Selected questions to be tested
- Linking works into a coherent study
- What does this change for cryptography?
- Limitations and alternative explanations
- Next experiment and test
- Conclusion
- Sources
1. Central question and hypothesis
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?
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
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
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
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
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
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
4.1 Lower Bound with Limited QRAM
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
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
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
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
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
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
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
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. | Question | What is checked in the article |
|---|---|---|
| 1 | What specific problem does the technology solve? | Reducing the cost of lattice sifting in a quantum model and assessing the feasibility of attacks on PQC. |
| 2 | What question seems paradoxical but can be tested? | Can a quantum algorithm be faster than a classical one, but not provide speedup without QRAM? |
| 4 | How 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 |
| 6 | What outcome would change the experts’ views? | Proof of quantum speedup without QRAM in the same query model. |
| 7 | What is the underlying physical mechanism? | Coherent data access, amplitude gain, quantum walks, address superposition. |
| 8 | The role of superposition, interference, entanglement, measurement | Superposition of QRAM addresses; interference in Grover/amplitude amplification; measurement during response extraction. |
| 9 | What effects are really needed? | Coherent access and amplitude gain are important for acceleration; entanglement alone is not a sufficient explanation. |
| 11 | What model assumptions might no longer hold? | Assumption 1 and 2; efficient replacement of QRAM; physical feasibility of QRAM. |
| 17 | What 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? |
| 25 | How is the problem translated into a quantum circuit? | Near-neighbor → LSF filters → amplitude gain → QRAM access to buckets. |
| 29 | Depth, number of operations, runs, connectivity | Query complexity, depth, and width are compared; the design without QRAM is considered separately. |
| 37 | To which classical method is the approach compared? | With classical LSF [12] and classical lower bound [40]. |
| 38 | Are the accuracy, success probability, resources the same? | Single-model comparison; QRAM, qubits, and depth are taken into account; polynomial factors are omitted. |
| 39 | What is claimed: theory, experiment or practical usefulness? | Theoretical lower bound and theoretical tradeoffs; no experimental data. |
| 42 | Can an improved classical algorithm change the conclusions? | The lower bound [40] gives a classical bound; improving it would require revising the comparison. |
| 43 | What is the basis for the conclusion? | Proof in query model, reduction to classical lower bound, subroutine analysis. |
| 44 | Control experiments and alternative explanations | An alternative is a QRAM-free scheme with exponential qubits; it does not violate the query lower bound. |
| 69 | What issues remain open? | Exact optimality of the tradeoff; lifting of assumptions 1–2; polynomial QRAM-less scheme. |
5.1. Profile cryptographic questions
| No. | Question | Answer within the article |
|---|---|---|
| 49 | What cryptographic problem is being considered? | Lattice SVP/near-neighbor; additionally, collision detection and multi-target preimage search. |
| 50 | Which quantum algorithm is applicable? | LSF + amplitude gain; quantum walks; limited QRAM version of Grover. |
| 51 | Resource estimates and acceptable error | Asymptotic estimates of time and QRAM; success probability is assumed to be fairly high; constants are not optimized. |
| 53 | The difference between QKD and post-quantum cryptography | The article is not about QKD, but about cryptanalysis of PQC candidates; QRAM is an attacker’s resource, not a communication protocol. |
| 70 | What further experiments will distinguish between the explanations? | Comparison of specific QRAM architectures; data replacement cost estimation; end-to-end BKZ modeling. |
| 74 | How 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
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 / result | Contribution | Role 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.2925d | Algorithmic basis for quantum modifications. |
| Laarhoven [42], Chailloux–Loyer [18] | Quantum search inside α-close filters; 20.2653d | First step: QRAM is used for amplitude gain. |
| Heiser [33] | Quantum search by α-close filters; 20.2571d | Enhanced by filter sampler and Grover search. |
| Bonnetain et al. [14] | Reusable quantum walks; 20.2563d | Best known result with full QRAM. |
| Chailloux et al. [19] | Collision finding without QRAM; 22n/5 | Shows that QRAM-less acceleration is possible in other tasks, but at a different cost. |
| Bindel et al. [13] | Quantum enumeration in limited depth | The question arises: will enumeration be more practical than sieving without large QRAM? |
| Albrecht et al. [5] | Specific estimates of quantum sifting | Shows that known quantum circuits require large depth and QRAM. |
6.1. Linking paragraph
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?
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
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
To transform a theoretical article into a testable research program, at least four steps are required.
- 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.
- Comparison of QRAM architectures. Estimate the cost of creating, connecting, and replacing data for specific QRAM offerings; apply these costs to tradeoff formulas.
- 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.
- 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
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
- 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.
- “Quantum Technologies: Research Article Questions” is a question constructor used to formulate testable questions and structure the article.
- Kirshanova E., Laarhoven T. Lower bounds on lattice sieving and information set decoding. CRYPTO 2021. Classical lower bound .
20.2925d + o(d) - Becker A., Ducas L., Gama N., Laarhoven T. New directions in nearest neighbor searching with applications to lattice sieving. SODA 2016. Classic LSF.
- Laarhoven T. Search problems in cryptography: from fingerprinting to lattice sieving. PhD thesis, 2016. Quantum LSF p .
20.2653d - Chailloux A., Loyer J. Lattice sieving via quantum random walks. ASIACRYPT 2021. Quantum walks and QRAM.
- Heiser M. Improved quantum hypercone locality sensitive filtering in lattice sieving. ePrint 2021/1295. Result .
20.2571d - Bonnetain X., Chailloux A., Schrottenloher A., Shen Y. Finding many collisions via reusable quantum walks: application to lattice sieving. EUROCRYPT 2023. Result .
20.2563d - Chailloux A., Naya-Plasencia M., Schrottenloher A. An efficient quantum collision search algorithm and implications on symmetric cryptography. ASIACRYPT 2017. QRAM-less collision finding.
- Bindel N., Bonnetain X., Tiepelt M., Virdia F. Quantum lattice enumeration in limited depth. CRYPTO 2024. Limited depth and practicality of enumeration.
- Albrecht M. et al. Estimating quantum speedups for lattice sieves. ASIACRYPT 2020. Specific resource estimates.
Pre-publication review
- 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
| Topic and audience | Quantum lattice cryptanalysis; researchers in PQC, quantum algorithms, and QRAM architectures. |
|---|---|
| The central question | Does quantum acceleration of lattice sieving necessarily require large QRAM? |
| Hypothesis and refutation | H1: Without QRAM, there is no speedup in the query model; refutation: a QRAM-less algorithm with polynomial qubits is below the classical bound. |
| Method | Query model analysis, reduction to classical lower bound, tradeoff comparison, QRAM-free circuit analysis. |
| Metrics | Query complexity, depth, width, number of qubits, QRAM size, asymptotic degree d. |
| Restrictions | Model, Assumption 1–2, efficient replacement of QRAM, no experiment, polynomial factors. |
| New contribution | A coherent interpretation of the lower bound, the compromise, and the QRAM-less scheme as different answers to the same resource question. |
| The next step | Compare specific QRAM architectures and end-to-end BKZ models under the same assumptions. |
