Space-efficient quantum multiplication polynomials for binary finite fields with sub-quadratoc Toffoli gate count (pp721-735)
          Iggy van Hoof
          doi: https://doi.org/10.26421/QIC20.9-10-1
Abstracts: 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.
Key words: Quantum algorithm, Karatsuba multiplication, Binary polynomials