Paper 2019/1170 Original: eprint.iacr.org/2019/1170 ↗
Space-efficient quantum multiplication of polynomials for binary finite fields with sub-quadratic Toffoli gate count
Abstract
Multiplication is an essential step in a lot of calculations. In this paper we look at multiplication of 2 binary polynomials of degree at most $n-1$, modulo an irreducible polynomial of degree $n$ with $2n$ input and $n$ output qubits, without ancillary qubits, assuming no errors. With straightforward schoolbook methods this would result in a quadratic number of Toffoli gates and a linear number of CNOT gates. This paper introduces a new algorithm that uses the same space, but by utilizing space-efficient variants of Karatsuba multiplication methods it requires only $O(n^{\log_2(3)})$ Toffoli gates at the cost of a higher CNOT gate count: theoretically up to $O(n^2)$ but in examples the CNOT gate count looks a lot better.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2019-10-10: last updated
- 2019-10-10: published
- Short URL
- https://ia.cr/2019/1170
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2019/1170,
author = {Iggy van Hoof},
title = {Space-efficient quantum multiplication of polynomials for binary finite fields with sub-quadratic Toffoli gate count},
howpublished = {Cryptology {ePrint} Archive, Paper 2019/1170},
year = {2019},
url = {https://eprint.iacr.org/2019/1170}
}