Quantum binary quadratic form reduction

Nicolas David; Thomas Espitau; Akinori Hosoyamada

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 computing quadratic form reduction
Contact author(s): t espitau @ gmail com
History: 2022-04-22: received
Short URL: https://ia.cr/2022/466
License: 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},
      url = {https://eprint.iacr.org/2022/466}
}