Improved reversible and quantum circuits for Karatsuba-based integer\n multiplication

2017/06/11 by Alex Parent, Martin Roetteler, Parent, Alex +3 · 1 citation
Computer Science · #Quantum Computing Algorithms and Architecture #Coding theory and cryptography #Parallel Computing and Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1706.03419

Abstract

Integer arithmetic is the underpinning of many quantum algorithms, with\napplications ranging from Shor's algorithm over HHL for matrix inversion to\nHamiltonian simulation algorithms. A basic objective is to keep the required\nresources to implement arithmetic as low as possible. This applies in\nparticular to the number of qubits required in the implementation as for the\nforeseeable future this number is expected to be small. We present a reversible\ncircuit for integer multiplication that is inspired by Karatsuba's recursive\nmethod. The main improvement over circuits that have been previously reported\nin the literature is an asymptotic reduction of the amount of space required\nfrom O(n^1.585) to O(n^1.427). This improvement is obtained in exchange\nfor a small constant increase in the number of operations by a factor less than\n2 and a small asymptotic increase in depth for the parallel version. The\nasymptotic improvement are obtained from analyzing pebble games on complete\nternary trees.\n

Cited by

• Space-efficient quantum multiplication polynomials for binary finite fields with sub-quadratoc Toffoli gate count

Related

• Asymptotically Efficient Quantum Karatsuba Multiplication
• High Performance Quantum Modular Multipliers
• A Possible New Quantum Algorithm: Arithmetic with Large Integers via the Chinese Remainder Theorem
• Reversible addition circuit using one ancillary bit with application to quantum computing
• Design Automation and Design Space Exploration for Quantum Computers