Quantum Circuits for Toom-Cook Multiplication

Abstract

In this paper, we report efficient quantum circuits for integer multiplication using Toom-Cook algorithm. By analysing 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.

References in corpus (5)

• Roads towards fault-tolerant universal quantum computation
• High threshold universal quantum computation on the surface code
• Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
• Non-Fault Tolerant T-Gates for the [7,1,3] Quantum Error Correction Code
• Improved reversible and quantum circuits for Karatsuba-based integer multiplication

Cited by in corpus (4)

• Exhaustive search for optimal molecular geometries using imaginary-time evolution on a quantum computer
• First-quantized eigensolver for ground and excited states of electrons under a uniform magnetic field
• Black-Box Quantum State Preparation with Inverse Coefficients
• Quantum circuit to estimate pi using quantum amplitude estimation