Paper 2022/466

Quantum binary quadratic form reduction

Nicolas David, Thomas Espitau, and Akinori Hosoyamada

Abstract

Quadratic form reduction enjoys broad uses both in classical and quantum algorithms such as in the celebrated LLL algorithm for lattice reduction. In this paper, we propose the first quantum circuit for definite binary quadratic form reduction that achieves O(n log n) depth, O(n^2) width and O(n^2 log(n)) quantum gates. The proposed work is based on a binary variant of the reduction algorithm of the definite quadratic form. As side results, we show a quantum circuit performing bit rotation with O(log n) depth, O(n) width, and O(n log n) gates, in addition to a circuit performing integer logarithm computation with O(log n) depth, O(n) width, and O(n) gates.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. Minor revision.
Keywords
quantum computingquadratic form reduction
Contact author(s)
t espitau @ gmail com
History
2022-04-22: received
Short URL
https://ia.cr/2022/466
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/466,
      author = {Nicolas David and Thomas Espitau and Akinori Hosoyamada},
      title = {Quantum binary quadratic form reduction},
      howpublished = {Cryptology ePrint Archive, Paper 2022/466},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/466}},
      url = {https://eprint.iacr.org/2022/466}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.