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

2019/10/07 by van Hoof, Iggy · 1 citation
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.1910.02849

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₂(3)) Toffoli gates at the cost of a higher CNOT gate count: theoretically up to O(n²) but in examples the CNOT gate count looks a lot better.

Cited by

• Asymptotic yet practical optimization of quantum circuits implementing GF(2^m) multiplication and division operations

Related

• Quantum binary field multiplication with subquadratic Toffoli gate count and low space-time cost
• Asymptotic yet practical optimization of quantum circuits implementing GF(2^m) multiplication and division operations
• Asymptotically Efficient Quantum Karatsuba Multiplication
• Quantum schoolbook multiplication with fewer Toffoli gates
• Multi-qubit Toffoli with exponentially fewer T gates