**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 $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.

**Category / Keywords: **public-key cryptography / post-quantum cryptography, quantum computing, Karatsuba multiplication

**Original Publication**** (in the same form): **https://arxiv.org/abs/1910.02849

**Date: **received 8 Oct 2019

**Contact author: **Iggy at lafeberhof nl

**Available format(s): **PDF | BibTeX Citation

**Version: **20191010:124900 (All versions of this report)

**Short URL: **ia.cr/2019/1170

[ Cryptology ePrint archive ]