The DOI matches its DataCite record; 1 of the 1 references it cites were found in a registry or an index.
Improved reversible and quantum circuits for Karatsuba-based integer multiplication
Open accessAbstract
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 O(n^1.585) to O(n^1.427). This improvement is obtained in exchange for a small constant increase in the number of operations by a factor less than 2 and a small asymptotic increase in depth for the parallel version. The asymptotic improvement are obtained from analyzing pebble games on complete ternary trees.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Attempting to fix the problem of naive translation of Karatsuba multiplication can result in the space complexity increasing, though it is possible to solve this problem.
“Attempting to fix this problem can result in the space complexity increasing [65], though it is possible to solve this problem [34].”
From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [65]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits
Amy, M., Maslov, D., Mosca, M., & Roetteler, M. (2013) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2013.2244643 · Cited by 549 · cited 1×
“Furthermore, we refer the reader to [1] for more information about the definition of T -depth and possible time-space tradeoffs for implementing Toffoli gates and other reversible gates over the Clifford+ T gate set.”
MethodSelf-citation
Flagged first, then by citations
Research works printed but not linked: 21
- 2 Charles H. Bennett. Logical reversibility of computation. IBM Journal of Research and Development , 17:525-532, 1973.
- 3 Charles H. Bennett. Time/space trade-offs for reversible computation. SIAM Journal on Computing , 18:766-776, 1989.
- 4 Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Exponential improvement in precision for simulating sparse Hamiltonians. In Symposium on Theory of Computing, STOC 2014 , pages 283-292, 2014.
- 5 Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015 , pages 792-809, 2015.
- 6 Jean-François Biasse and Fang Song. Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 , pages 893-902, 2016.
- 7 Alex Bocharov, Martin Roetteler, and Krysta M. Svore. Efficient synthesis of probabilistic quantum circuits with fallback. Physical Review A , 91:052317, 2015.
- 8 Alex Bocharov, Martin Roetteler, and Krysta M. Svore. Efficient synthesis of universal Repeat-Until-Success circuits. Physical Review Letters , 114:080502, 2015.
- 9 Siu Man Chan. Pebble games and complexity . PhD thesis, Electrical Engineering and Computer Science, UC Berkeley, 2013. Tech report: EECS-2013-145.
- 10 Andrew M. Childs, Leonard J. Schulman, and Umesh V. Vazirani. Quantum algorithms for hidden nonlinear structures. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007) .
- 12 Richard Cleve and John Watrous. Fast parallel circuits for the quantum Fourier transform. In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA , pages 526-536, 2000.
- 13 Steven A. Cuccaro, Thomas G. Draper, Samuel A. Kutin, and David Petrie Moulton. A new quantum ripple-carry addition circuit. 2004. http://arxiv.org/abs/quant-ph/0410184. · arXiv
- 14 Kirsten Eisenträger, Sean Hallgren, Alexei Y. Kitaev, and Fang Song. A quantum algorithm for computing the unit group of an arbitrary degree number field. In Symposium on Theory of Computing, STOC 2014 , pages 293-302, 2014.
- 15 Sean Hallgren. Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem. J. ACM , 54(1):4:1-4:19, 2007.
- 19 Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits. Physical Review Letters , 110:190502, 2013.
- 22 Luis Antonio Brasil Kowada, Renato Portugal, and Celina Miraglia Herrera de Figueiredo. Reversible Karatsuba's algorithm. Journal of Universal Computer Science , 12(5):499-511, 2006.
- 23 Klaus-Jörn Lange, Pierre McKenzie, and Alain Tapp. Reversible space equals deterministic space. J. Comput. Syst. Sci. , 60(2):354-367, 2000.
- 24 Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization, 2016. arXiv:1610.06546. · arXiv
- 25 Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information . Cambridge University Press, 2000.
- 28 Mehdi Saeedi and Igor L. Markov. Synthesis and optimization of reversible circuits - a survey. ACM Comput. Surv. , 45(2):21, 2013.
- 30 Peter Selinger. Efficient Clifford+ T approximation of single-qubit operators. Quantum Information & Computation , 15(1-2):159-180, 2015.
- 31 Peter W. Shor. Algorithms for quantum computation: discrete logarithm and factoring. In Proc. FOCS'94 , pages 124-134. IEEE Computer Society Press, 1994.
Cited by
Sorted by citations
How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
Gidney, C., & Ekerå, M. (2021) · Quantum · doi:10.22331/q-2021-04-15-433 · Cited by 830
Metadata
- Authors
- Parent, A., Roetteler, M., & Mosca, M.
- Affiliations
- University of Waterloo (CA)
- Microsoft (United States) (US)
- Canadian Institute for Advanced Research (CA)
- Venue
- Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- Publisher
- Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- Published
- 2018
- Volume
- 73
- Pages
- 15
- ISSN
- 2331-8422 (ISSN-L)
- OpenAlex
- W2625960098
- Cited by
- 24
- References
- 1
- Citations by year
- 2025: 1 · 2024: 2 · 2023: 6 · 2022: 1 · 2021: 2 · 2020: 5 · 2019: 4 · 2018: 3
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) (submittedVersion, cc-by)
- arXiv (Cornell University)
- Leibniz international proceedings in informatics (cc-by)
- Conference on Theory of Quantum Computation, Communication and Cryptography
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Quantum-Dot Cellular Automata
- Keywords
- reversible circuits, quantum circuits, integer multiplication, Karatsuba algorithm, pebble games, ternary trees, circuit depth, quantum arithmetic
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
