Quantum circuits for Toom-Cook multiplication

In this paper, we report efficient quantum circuits for integer multiplication using the Toom-Cook algorithm. By analyzing the recursive tree structure of the algorithm, we obtained a bound on the count of Toffoli gates and qubits. These bounds are further improved by employing reversible pebble games through uncomputing the intermediate results. The asymptotic bounds for different performance metrics of the proposed quantum circuit are superior to the prior implementations of multiplier circuits using schoolbook and Karatsuba algorithms.

Figure 1

Recursion tree structure of the Toom-2.5 implementation.

Figure 2

The quantum circuit for computing integer multiplication results using the Toom-2.5 algorithm. The compute blocks are then run backwards (uncomputed) to set the garbage outputs ($g$) back to 0 (not shown in the figure).

Figure 3

Comparison of the quantum multiplier implementations based on (a) Toffoli count, (b) Toffoli depth, and (c) number of qubits.

Figure 4

Variation in cnot counts across different implementations with increasing input size.