Abstract
Efficient quantum circuits of algebraic operations are vital for quantum algorithms. In this paper, we propose a novel fault-tolerant quantum divider based on long division algorithm using Clifford+T gates. Firstly, two efficient quantum subtractors are designed which we call them equal-bit subtractor and unequal-bit subtractor. The advantage of these quantum subtractors is that the number of the constant inputs is 2, which will dramatically reduce the qubit cost. Then, based on the quantum comparator and the quantum subtractors, we propose a novel fault-tolerant quantum divider. Compared with existing work, the proposed quantum divider has better performances in quantum cost, T-depth, T-count, qubit cost, constant inputs and garbage outputs. Finally, we simulate these algorithms on IBM Quantum Experience (IBM Q Experience) platform, and the probability histograms show that these algorithms are feasible and efficient.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Data availability
No datasets were generated or analyzed during the current study.
References
Peter, W.S.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303–332 (1999)
Lov, K.G.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79(2), 325 (1997)
Paul, B.: The computer as a physical system: a microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines. J. Stat. Phys. 22(5), 563–591 (1980)
David, D.: Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A Math. Phys. Sci. 400(1818), 97–117 (1985)
Sean, H.: Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem. In: Proc. Thiry Fourth Annual ACM Sympos. Theory Comput., pp. 653–658 (2002)
Wim, V.D., Sean, H.: Efficient quantum algorithms for shifted quadratic character problems, arXiv preprint arXiv:quant-ph/0011067 (2000)
Wim, V.D., Sean, H., Lawrence, I.: Quantum algorithms for some hidden shift problems. SIAM J. Comput. 36(3), 763–778 (2006)
Guodong, S., Shenghui, S., Maozhi, S.: Quantum algorithm for polynomial root finding problem. In: 2014 Tenth International Conference on Computational Intelligence and Security, pp. 469–473 (2014)
Aram, W., Avinatan, H., Seth, L.: Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103(15), 150502 (2009)
Glenn, B., Chris, L., Charles, C.: Quantum image processing (quip). In: 32nd Applied Imagery Pattern Recognition Workshop, 2003. Proceedings, pp. 39–44 (2003)
Wim, V.D., Igor, E.S.: Classical and quantum algorithms for exponential congruences. In: Workshop on Quantum Computation, Communication, and Cryptography, pp. 1–10 (2008)
Mathias, S., Martin, R., Nathan, W., Giovanni, D.M.: Design automation and design space exploration for quantum computers. In: Design, Automation & Test in Europe Conference & Exhibition (DATE), pp. 470–475 (2017)
Mihir, K.B., Stuart, H., Anargyros, P., Iasonas, P.: Quantum algorithms and circuits for scientific computing. arXiv preprint arXiv:1511.08253 (2015)
Xinlan, Z., Debbie, W.L., Isaac, L.C.: Methodology for quantum logic gate construction. Phys. Rev. A 62(5), 052316 (2000)
Matthew, A., Dmitri, M., Michele, M.: Polynomial-time \(T\)-depth optimization of Clifford+ \(T\) circuits via matroid partitioning. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 33(10), 1476–1489 (2014)
Alexandru, P., Ilia, P., Kae, N., Simon, J.D.: Fault-tolerant, high-level quantum circuits: form, compilation and description. Quant. Sci. Technol. 2(2), 025003 (2017)
Harry, B., Richard, C., Monique, L., Noah, L., Alexander, S., Falk, U.: New limits on fault-tolerant quantum computation. In: 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pp. 411–419 (2016)
David, G., Vadym, K., Michele, M., Vincent, R.: An algorithm for the \(T\)-count. arXiv preprint arXiv:1308.4134 (2013)
Oscar, P.B., Tal, N., Matthew, P., Vwani, R., Farrokh, V.: A new universal and fault-tolerant quantum basis. Inf. Process. Lett. 75(3), 101–107 (2000)
Ismail, G., Lamjed, T., Bouraoui, O.: Division circuit using reversible logic gates. In: 2018 International Conference on Advanced Systems and Electric Technologies (IC_ASET), pp. 60–65 (2018)
Noor, M.N., Adnan, H., Mutasimul, H., Lafifa, J., Hafiz, M.H.B.: Novel reversible division hardware. In: 2009 52nd IEEE International Midwest Symposium on Circuits and Systems, pp. 1134–1138 (2009)
Faraz, D., Majid, H.: A novel nanometric fault tolerant reversible divider. Int. J. Phys. Sci. 6(24), 5671–5681 (2011)
Hafiz, M.H.B., Solaiman, M.M.: Design of a compact reversible fault tolerant division circui. Microelectron. J. 51, 15–29 (2016)
Ali, B., Majid, H.: Optimised reversible divider circuit. Int. J. Innovative Comput. Appl. 7(1), 13–33 (2016)
Lafifa, J., Hafiz, M.H.B.: Efficient approaches to design a reversible floating point divider. In: 2013 IEEE International Symposium on Circuits and Systems (ISCAS), pp. 3004–3007 (2013)
Sayanton, V.D., Hafiz, M.H.B., Lafifa, J.: An efficient design technique of a quantum divider circuit. In: 2016 IEEE International Symposium on Circuits and Systems (ISCAS), pp. 2102–2105 (2016)
Himanshu, T., Edgard, M.C., TSS, V., Travis, H.: Quantum circuit designs of integer division optimizing \(T\)-count and \(T\)-depth. In: IEEE Transactions on Emerging Topics in Computing (2019)
Michael, A.N., Isaac, C.: Quantum computation and quantum information. American Association of Physics Teachers (2002)
Tycho, S., Harald, W.: Realizable universal quantum logic gates. Phys. Rev. Lett. 74(20), 4087 (1995)
Suzhen, Y., Chao, W., Bo, H., Yu, G.: The dual-threshold quantum image segmentation algorithm and its simulation. Quantum Inf. Process. 19(12), 1–21 (2020)
Haiying, X., Haisheng, L., Han, Z., Yan, L., Jing, Z.: Novel multi-bit quantum comparators and their application in image binarization. Quantum Inf. Process. 18(7), 1–17 (2019)
Himanshu, T., Nagarajan, R.: Design of efficient reversible logic-based binary and BCD adder circuits. ACM J. Emerg. Technol. Comput. Syst. (JETC) 9(3), 1–31 (2013)
Hafiz, M.H.B., Ahsan, R.C.: Design of a compact reversible binary coded decimal adder circuit. J. Syst. Architect. 52(5), 272–282 (2006)
Ashis, K.W., Mahmudul, M.H., Ahsan, R.C., Hafiz, M.H.B.: Efficient approaches for designing reversible binary coded decimal adders. Microelectron. J. 39(12), 1693–1703 (2008)
Michael, K.T., Robert, G.: Optimized reversible binary-coded decimal adders. J. Syst. Architect. 54(7), 697–706 (2008)
Majid, M., Mohammad, E., Majid, H., Abbas, B.: Design and optimization of reversible bcd adder/subtractor circuit for quantum and nanotechnology based systems. World Appl. Sci. J. 4(6), 787–792 (2008)
Majid, M., Majid, H., Mohammad, E., Keiva, N.: Minimization and optimization of reversible BCD-Full adder/subtractor using genetic algorithm and Don’t Care concept. Int. J. Quantum Inf. 7(05), 969–989 (2009)
Gadi, A., Thomas, A., Panagiotis, B., Luciano, B., Yael, B.H., David, B.: Qiskit: An open-source framework for quantum computing. Accessed on Mar 16 (2019)
Acknowledgements
The authors would like to acknowledge the financial support of the National Natural Science Foundation of China (61801061), The Natural Science Foundation of Chongqing(CSTC2016jcyjA0028), The Scientific and Technological Research Program of Chongqing Municipal Education Commission(KJQN201800607, KJ1704090), and the valuable inputs of the reviewers.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Yuan, S., Gao, S., Wen, C. et al. A novel fault-tolerant quantum divider and its simulation. Quantum Inf Process 21, 182 (2022). https://doi.org/10.1007/s11128-022-03523-8
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11128-022-03523-8