← Back to papers
Quantum Circuits for Toom-Cook Multiplication
Srijit Dutta, Debjyoti Bhattacharjee, A. Chattopadhyay·May 7, 2018·DOI: 10.1103/PhysRevA.98.012311
Computer SciencePhysics
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
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.