Paper 2026/2895

Concrete Quantum Circuit Implementations and Resource Estimates for the Quantum 3 and 4-Sieves

MohamadAli Khajeian, University of Tehran
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.