Skip to main content

Advertisement

Springer Nature Link
Log in

Classification and transformations of quantum circuit decompositions for permutation operations

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

Efficient decomposition of permutation unitaries is vital as they frequently appear in quantum computing. In this paper, we identify the key properties that impact the decomposition process of permutation unitaries. Then, we classify these decompositions based on the identified properties, establishing a comprehensive framework for analysis. We demonstrate the applicability of the presented framework through the widely used multi-controlled Toffoli gate, revealing that the existing decompositions in the literature belong to only four out of ten identified classes. Motivated by this finding, we propose transformations that can adapt a given decomposition into a member of another class, enabling resource reduction.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Feynman, R.P.: Simulating physics with computers. Int. J. Theor. Phys. 21(6), 467–488 (1982)

    Article  MathSciNet  Google Scholar 

  2. Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212–219 (1996)

  3. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303–332 (1999)

    Article  ADS  MathSciNet  Google Scholar 

  4. Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization algorithm, Tech. Rep. MIT-CTP/4610 (2014)

  5. Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H., Zhou, X.-Q., Love, P.J., Aspuru-Guzik, A., O’Brien, J.L.: A variational eigenvalue solver on a photonic quantum processor. Nat. Commun. 5(1), 1–7 (2014)

    Article  Google Scholar 

  6. Kadowaki, T., Nishimori, H.: Quantum annealing in the transverse Ising model. Phys. Rev. E 58(5), 5355 (1998)

    Article  ADS  Google Scholar 

  7. Ibm quantum challenge 2019. https://github.com/quantum-challenge/2019/. [Accessed 11-03-2024]

  8. Santha, M.: Quantum walk based search algorithms. In: Proceedings of the 5th International Conference on Theory and Applications of Models of Computation, TAMC 2008, pp. 31–46. Springer (2008)

  9. Magano, D., Kumar, A., Kālis, M., Locāns, A., Glos, A., Pratapsi, S., Quinta, G., Dimitrijevs, M., Rivošs, A., Bargassa, P., et al.: Quantum speedup for track reconstruction in particle accelerators. Phys. Rev. D 105(7), 076012 (2022)

    Article  ADS  Google Scholar 

  10. Glos, A., Kokainis, M., Mori, R., Vihrovs, J.: Quantum speedups for dynamic programming on \(n\)-dimensional lattice graphs. In: 46th International Symposium on Mathematical Foundations of Computer Science, pp. 50:1–50:23 (2021)

  11. Ambainis, A., Balodis, K., Iraids, J., Kokainis, M., Prūsis, K., Vihrovs, J.: Quantum speedups for exponential-time dynamic programming algorithms. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1783–1793 (2019)

  12. Gilliam, A., Woerner, S., Gonciulea, C.: Grover adaptive search for constrained polynomial binary optimization. Quantum 5, 428 (2021)

    Article  Google Scholar 

  13. Bakó, B., Glos, A., Salehi, Ö., Zimborás, Z.: Prog-QAOA: framework for resource-efficient quantum optimization through classical programs, arXiv preprint arXiv:2209.03386 (2024)

  14. Pelofske, E., Bärtschi, A., Golden, J., Eidenbenz, S.: High-round QAOA for MAX \( k \)-SAT on trapped ion NISQ devices, arXiv preprint arXiv:2306.03238 (2023)

  15. Fijany, A., Williams, C.P.: Quantum wavelet transforms: fast algorithms and complete circuits, in Quantum Computing and Quantum Communications: First NASA International Conference, QCQC’98, pp. 10–33. Springer (1999)

  16. Botelho, L., Glos, A., Kundu, A., Miszczak, J.A., Salehi, Ö., Zimborás, Z.: Error mitigation for variational quantum algorithms through mid-circuit measurements. Phys. Rev. A 105(2), 022441 (2022)

    Article  ADS  Google Scholar 

  17. Barenco, A., Bennett, C.H., Cleve, R., DiVincenzo, D.P., Margolus, N., Shor, P., Sleator, T., Smolin, J.A., Weinfurter, H.: Elementary gates for quantum computation. Phys. Rev. A 52, 3457–3467 (1995)

    Article  ADS  Google Scholar 

  18. da Silva, A.J., Park, D.K.: Linear-depth quantum circuits for multiqubit controlled gates. Phys. Rev. A 106, 042602 (2022)

    Article  ADS  MathSciNet  Google Scholar 

  19. Maslov, D.: Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization. Phys. Rev. A 93(2), 022311 (2016)

    Article  ADS  Google Scholar 

  20. Amy, M., Ross, N.J.: Phase-state duality in reversible circuit design. Phys. Rev. A 104(5), 052602 (2021)

    Article  ADS  Google Scholar 

  21. Maslov, D.: Reversible Logic Synthesis Benchmarks Page. https://reversiblebenchmarks.github.io/8bitadderd1.html. [Online; accessed 28.04.2008]

  22. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2010)

    Google Scholar 

  23. Shende, V.V., Markov, I.L.: On the CNOT-cost of TOFFOLI gates. Quantum Inf. Comput. 9(5), 461–486 (2009)

    MathSciNet  Google Scholar 

  24. Sleator, T., Weinfurter, H.: Realizable universal quantum logic gates. Phys. Rev. Lett. 74(20), 4087 (1995)

    Article  ADS  MathSciNet  Google Scholar 

  25. DiVincenzo, D.P., Smolin, J.: Results on two-bit gate design for quantum computers. In: Proceedings of the Workshop on Physics and Computation, PhysComp’94, pp. 14–23 (1994)

  26. Birkan, U., Salehi, Ö., Olejar, V., Nurlu, C., Yakaryılmaz, A.: Implementing quantum finite automata algorithms on noisy devices. In: International Conference on Computational Science, pp. 3–16. Springer (2021)

  27. Zhang, K., Yu, K., Korepin, V.: Quantum search on noisy intermediate-scale quantum devices. Europhys. Lett. 140(1), 18002 (2022)

    Article  ADS  Google Scholar 

  28. Qiskit contributors, Qiskit: An open-source framework for quantum computing (2023)

  29. Baker, J.M., Duckering, C., Hoover, A., Chong, F.T.: Decomposing quantum generalized Toffoli with an arbitrary number of ancilla, arXiv preprint arXiv:1904.01671 (2019)

  30. Scott, N.O., Dueck, G.W.: Pairwise decomposition of Toffoli gates in a quantum circuit. In: Proceedings of the 18th ACM Great Lakes Symposium on VLSI, GLSVLSI ’08, pp. 231–236. Association for Computing Machinery (2008)

  31. Balauca, S., Arusoaie, A.: Efficient constructions for simulating multi controlled quantum gates. In: Proceedings of the International Conference on Computational Science, ICCS 2022, pp. 179–194. Springer (2022)

  32. Biswal, L., Bhattacharjee, D., Chattopadhyay, A., Rahaman, H.: Techniques for fault-tolerant decomposition of a multicontrolled Toffoli gate. Phys. Rev. A 100, 062326 (2019)

    Article  ADS  Google Scholar 

  33. Jones, C.: Low-overhead constructions for the fault-tolerant Toffoli gate. Phys. Rev. A 87, 022328 (2013)

    Article  ADS  Google Scholar 

  34. Selinger, P.: Quantum circuits of \(T\)-depth one. Phys. Rev. A 87, 042302 (2013)

    Article  ADS  Google Scholar 

  35. Miller, D.M.: Lower cost quantum gate realizations of multiple-control Toffoli gates. In: 2009 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, pp. 308–313 (2009)

  36. Miller, D.M., Wille, R., Sasanian, Z.: Elementary quantum gate realizations for multiple-control Toffoli gates. In: Proceedings of the 41st IEEE International Symposium on Multiple-Valued Logic, pp. 288–293 (2011)

  37. Kole, A., Datta, K.: Improved NCV gate realization of arbitrary size Toffoli gates. In: Proceedings of the 30th International Conference on VLSI Design and 16th International Conference on Embedded Systems, pp. 289–294 (2017)

  38. Biswal, L., Bandyopadhyay, C., Wille, R., Drechsler, R., Rahaman, H.: Improving the realization of multiple-control Toffoli gates using the NCVW quantum gate library. In: Proceedings of the 29th International Conference on VLSI Design and 15th International Conference on Embedded Systems, pp. 573–574 (2016)

  39. Maslov, D., Dueck, G.W., Miller, D.M., Negrevergne, C.: Quantum circuit simplification and level compaction. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 27(3), 436–444 (2008)

    Article  Google Scholar 

  40. Szyprowski, M., Kerntopf, P.: Low quantum cost realization of generalized Peres and Toffoli gates with multiple-control signals. In: Proceedings of the 13th IEEE International Conference on Nanotechnology, IEEE-NANO 2013, pp. 802–807 (2013)

  41. Ali, M.B., Hirayama, T., Yamanaka, K., Nishitani, Y.: Quantum cost reduction of reversible circuits using new Toffoli decomposition techniques. In: Proceedings of the International Conference on Computational Science and Computational Intelligence, CSCI 2015, pp. 59–64 (2015)

  42. Szyprowski, M., Kerntopf, P.: Reducing quantum cost of pairs of multi-control Toffoli gates. In: Proceedings of the 10th International Workshop on Boolean Problems, pp. 263–268 (2012)

  43. Wang, S., Baksi, A., Chattopadhyay, A.: A higher radix architecture for quantum carry-lookahead adder. Sci. Rep. 13(1), 16338 (2023)

    Article  ADS  Google Scholar 

Download references

Acknowledgements

A.G. has been partially supported by National Science Center under grant agreements 2019/33/B/ST6/02011, and 2020/37/N/ST6/02220. Ö.S. acknowledges support from National Science Center under grant agreement 2019/33/B/ST6/02011. The authors would like to thank Zoltán Zimborás and Jarosław Miszczak for discussions on the results presented in this paper. We acknowledge QWorld Association for organizing the remote internship program QIntern 2022 during which we initiated the work presented in this paper.

Author information

Author notes

  1. Ankit Khandelwal and Handy Kurniawan have contributed equally to this work.

Authors and Affiliations

  1. TCS Research, Tata Consultancy Services, Bengaluru, India

    Ankit Khandelwal

  2. Facultad de Informática, Universidad Complutense de Madrid, Madrid, Spain

    Handy Kurniawan

  3. Rashtreeya Vidyalaya Preuniversity College, Bengaluru, India

    Shraddha Aangiras

  4. Institute of Theoretical and Applied Informatics, Polish Academy of Sciences, Gliwice, Poland

    Özlem Salehi & Adam Glos

  5. QWorld Association, Tallinn, Estonia

    Özlem Salehi

  6. Algorithmiq Ltd, Kanavakatu 3C, 00160, Helsinki, Finland

    Özlem Salehi & Adam Glos

Authors
  1. Ankit Khandelwal
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Handy Kurniawan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shraddha Aangiras
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Özlem Salehi
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Adam Glos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Adam Glos.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supplementary Information

Below is the link to the electronic supplementary material.

Supplementary file 1 (pdf 253 KB)

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Khandelwal, A., Kurniawan, H., Aangiras, S. et al. Classification and transformations of quantum circuit decompositions for permutation operations. Quantum Inf Process 23, 322 (2024). https://doi.org/10.1007/s11128-024-04508-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11128-024-04508-5

Keywords

Search

Navigation