Quantum circuits for Toom-Cook multiplication

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 gam...

Full description

Saved in:
Bibliographic Details
Main Authors: Dutta, Srijit, Bhattacharjee, Debjyoti, Chattopadhyay, Anupam
Other Authors: School of Computer Science and Engineering
Format: Article
Language:English
Published: 2018
Subjects:
Quantum Circuits
Toom-Cook Multiplication
DRNTU::Engineering::Computer science and engineering
Online Access:https://hdl.handle.net/10356/88272
http://hdl.handle.net/10220/45676
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
Description
Summary: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.

Similar Items