### 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.

Available format(s)
Category
Implementation
Publication info
Preprint. Minor revision.
Keywords
Contact author(s)
t espitau @ gmail com
History
Short URL
https://ia.cr/2022/466

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.