Space-efficient quantum multiplication of polynomials for binary finite fields with sub-quadratic Toffoli gate count

Iggy van Hoof

Paper 2019/1170

Space-efficient quantum multiplication of polynomials for binary finite fields with sub-quadratic Toffoli gate count

Iggy van Hoof

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 $2 n$ 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: Published elsewhere. https://arxiv.org/abs/1910.02849
Keywords: post-quantum cryptography quantum computing Karatsuba multiplication
Contact author(s): Iggy @ lafeberhof nl
History: 2019-10-10: received
Short URL: https://ia.cr/2019/1170
License: CC BY

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}
}