Improved reversible and quantum circuits for Karatsuba-based integer multiplication
From MaRDI portal
Abstract: Integer arithmetic is the underpinning of many quantum algorithms, with applications ranging from Shor's algorithm over HHL for matrix inversion to Hamiltonian simulation algorithms. A basic objective is to keep the required resources to implement arithmetic as low as possible. This applies in particular to the number of qubits required in the implementation as for the foreseeable future this number is expected to be small. We present a reversible circuit for integer multiplication that is inspired by Karatsuba's recursive method. The main improvement over circuits that have been previously reported in the literature is an asymptotic reduction of the amount of space required from to . This improvement is obtained in exchange for a small constant increase in the number of operations by a factor less than and a small asymptotic increase in depth for the parallel version. The asymptotic improvement are obtained from analyzing pebble games on complete ternary trees.
Recommendations
- Constant-optimized quantum circuits for modular multiplication and exponentiation
- Quantum circuits for \(\mathbb F_{2^n}\)-multiplication with subquadratic gate count
- A logarithmic-depth quantum carry-lookahead adder
- Quantum reversible circuits for \(\mathrm{GF}(2^8)\) multiplication based on composite field arithmetic operations
- A fast quantum circuit for addition with few qubits
Cites work
- A quantum algorithm for computing the unit group of an arbitrary degree number field
- Constant-optimized quantum circuits for modular multiplication and exponentiation
- Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- Logical Reversibility of Computation
- Pebbling meets coloring: reversible pebble game on trees
- Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
- Practical Approximation of Single-Qubit Unitaries by Single-Qubit Quantum Clifford and T Circuits
- Reversible space equals deterministic space
- REVS: a tool for space-optimized reversible circuit synthesis
- Synthesis and optimization of reversible circuits -- a survey
- Time/Space Trade-Offs for Reversible Computation
Cited in
(9)- Efficient quantum circuit of Proth number modular multiplication
- An improved quantum principal component analysis algorithm based on the quantum singular threshold method
- T-count optimized Wallace tree integer multiplier for quantum computing
- Quantum circuits for \(\mathbb F_{2^n}\)-multiplication with subquadratic gate count
- Optimized reversible quantum circuits for \(\mathbb{F}_{2^8}\) multiplication
- Quantum reversible circuits for \(\mathrm{GF}(2^8)\) multiplication based on composite field arithmetic operations
- Quantum circuits for high-degree and half-multiplication for post-quantum analysis
- Concrete analysis of quantum lattice enumeration
- Improved quantum circuits for elliptic curve discrete logarithm problems on Ed25519
This page was built for publication: Improved reversible and quantum circuits for Karatsuba-based integer multiplication
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4637981)
