Paper 2026/2895
Concrete Quantum Circuit Implementations and Resource Estimates for the Quantum 3 and 4-Sieves
Abstract
Chailloux and Loyer (2023) introduced quantum 3- and 4-sieve algorithms for the Shortest Vector Problem (SVP) with asymptotic analyses, but concrete circuit implementations remain unexplored. We present the first complete reversible circuits for both algorithms, designing inner-product predicates with signed symmetric squaring across three architectures (low-qubit, balanced, and low-depth). We validate these circuits using exact sparse state-vector simulations that match an independent mathematical model to a precision of \(10^{-13}\). Crucially, we show that the original amplitude-amplification oracle fails when inner Grover searches are approximate and correct it to test the full configuration. Applying our arithmetic techniques to the published NV 2-sieve oracle reduces its T-count by \(9.4-14\times\) and T-depth by over three orders of magnitude. Finally, we provide exact per-call logical resource estimates for the configuration predicates and the NV oracle at cryptographic dimensions, detailing the architectural trade-offs for the core predicates used in quantum tuple sieving.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Quantum cryptanalysisLattice sievingShortest Vector ProblemQuantum circuitsResource estimation
- Contact author(s)
- khajeian @ ut ac ir
- History
- 2026-11-19: approved
- 2026-11-14: received
- See all versions
- Short URL
- https://ia.cr/2026/2895
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2895,
author = {MohamadAli Khajeian},
title = {Concrete Quantum Circuit Implementations and Resource Estimates for the Quantum 3 and 4-Sieves},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2895},
year = {2026},
url = {https://eprint.iacr.org/2026/2895}
}