Document Open Access Logo

Improved reversible and quantum circuits for Karatsuba-based integer multiplication

Authors Alex Parent, Martin Roetteler, Michele Mosca

PDF
Thumbnail PDF

File

LIPIcs.TQC.2017.7.pdf
  • Filesize: 0.81 MB
  • 15 pages

Document Identifiers

Author Details

Alex Parent
Martin Roetteler
Michele Mosca

Cite AsGet BibTex

Alex Parent, Martin Roetteler, and Michele Mosca. Improved reversible and quantum circuits for Karatsuba-based integer multiplication. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.TQC.2017.7

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 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.
Keywords
  • Quantum algorithms
  • reversible circuits
  • quantum circuits
  • integer multiplication
  • pebble games
  • Karatsuba's method

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Matthew Amy, Dmitri Maslov, Michele Mosca, and Martin Roetteler. A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Trans. on CAD of Integrated Circuits and Systems, 32(6):818-830, 2013. URL: http://dx.doi.org/10.1109/TCAD.2013.2244643.
  2. Charles H. Bennett. Logical reversibility of computation. IBM Journal of Research and Development, 17:525-532, 1973. Google Scholar
  3. Charles H. Bennett. Time/space trade-offs for reversible computation. SIAM Journal on Computing, 18:766-776, 1989. Google Scholar
  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. Google Scholar
  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. Google Scholar
  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. Google Scholar
  7. Alex Bocharov, Martin Roetteler, and Krysta M. Svore. Efficient synthesis of probabilistic quantum circuits with fallback. Physical Review A, 91:052317, 2015. Google Scholar
  8. Alex Bocharov, Martin Roetteler, and Krysta M. Svore. Efficient synthesis of universal Repeat-Until-Success circuits. Physical Review Letters, 114:080502, 2015. Google Scholar
  9. Siu Man Chan. Pebble games and complexity. PhD thesis, Electrical Engineering and Computer Science, UC Berkeley, 2013. Tech report: EECS-2013-145. Google Scholar
  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), pages 395-404, 2007. Google Scholar
  11. Brian D. Clader, Bryan C. Jacobs, and Chad R. Sprouse. Preconditioned quantum linear system algorithm. Phys. Rev. Lett., 110:250504, 2013. Google Scholar
  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. Google Scholar
  13. Steven A. Cuccaro, Thomas G. Draper, Samuel A. Kutin, and David Petrie Moulton. A new quantum ripple-carry addition circuit. http://arxiv.org/abs/quant-ph/0410184, 2004. Google Scholar
  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. Google Scholar
  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. Google Scholar
  16. Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for solving linear systems of equations. Phys. Rev. Lett., 103:150502, 2009. Google Scholar
  17. Anatoly Karatsuba and Yuri Ofman. Multiplication of many-digital numbers by automatic computers. Doklady Akad. Nauk SSSR, 145:293-294, 1962. Google Scholar
  18. 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. Google Scholar
  19. Emanuel Knill. An analysis of Bennett’s pebble game. arXiv.org preprint quant-ph/9508218. Google Scholar
  20. Balagopal Komarath, Jayalal Sarma, and Saurabh Sawlani. Pebbling meets coloring: reversible pebble game on trees. http://arxiv.org/abs/1604.05510. Google Scholar
  21. 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. Google Scholar
  22. Klaus-Jörn Lange, Pierre McKenzie, and Alain Tapp. Reversible space equals deterministic space. J. Comput. Syst. Sci., 60(2):354-367, 2000. Google Scholar
  23. Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization, 2016. arXiv:1610.06546. Google Scholar
  24. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. Google Scholar
  25. Neil J. Ross and Peter Selinger. Optimal ancilla-free Clifford+T approximation of z-rotations. Quantum Information & Computation, 16(11&12):901-953, 2016. Google Scholar
  26. Mehdi Saeedi and Igor L. Markov. Constant-optimized quantum circuits for modular multiplication and exponentiation. Quantum Information and Computation, 12(5&6):361-394, 2012. Google Scholar
  27. Mehdi Saeedi and Igor L. Markov. Synthesis and optimization of reversible circuits - a survey. ACM Comput. Surv., 45(2):21, 2013. Google Scholar
  28. Peter Selinger. Quantum circuits of T-depth one. Phys. Rev. A, 87:042302, 2013. Google Scholar
  29. Peter Selinger. Efficient Clifford+T approximation of single-qubit operators. Quantum Information & Computation, 15(1-2):159-180, 2015. Google Scholar
  30. Peter W. Shor. Algorithms for quantum computation: discrete logarithm and factoring. In Proc. FOCS'94, pages 124-134. IEEE Computer Society Press, 1994. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact