Quantum Information & Computation
Volume 25, Issue 5
RESEARCH ARTICLE Open access

Implementation of Quantum Fourier Transform and Quantum Hashing for Quantum Devices with Arbitrary Qubit Connectivity Graphs

Kamil Khadiev, Aliya Khadieva, Zeyu Chen, Junde Wu

Author affiliations
  • Kamil Khadiev1
  • Aliya Khadieva1
  • Zeyu Chen2
  • Junde Wu2
  1. Institute of Computational Mathematics and Information Technologies, Kazan Federal University, Kazan Kremlyovskaya, 35, Russia; Zavoisky Physical-Technical Institute, FRC Kazan Scientific Center of RAS, Sibirsky tract, 10/7, Kazan, Russia
  2. School of Mathematics Sciences, Zhejiang University, Hangzhou, China

pp. 509-541 · 10.2478/qic-2025-0028

Read PDF View on Reference Global
On this page

Abstract

In the paper, we consider quantum circuits for quantum fingerprinting (quantum hashing) and quantum Fourier transform (QFT) algorithms. Quantum fingerprinting (quantum hashing) is a well-known technique for comparing large objects using small images. The QFT algorithm is a very popular technique used in many algorithms. We present a generic method for constructing quantum circuits for these algorithms for quantum devices with restrictions. Many quantum devices (e.g., based on superconductors) have restrictions on applying two-qubit gates. The restrictions are presented by a qubit connectivity graph. Typically, researchers consider only the linear nearest neighbor (LNN) architecture, but current devices have more complex graphs. We present a method for arbitrary connected graphs that minimizes the number of CNOT gates in the circuit. The heuristic version of the method is fast enough and works with O(n6) time complexity, where n is the number of qubits. The certain version of the algorithm has an exponential time complexity that is O(n2 2n). We compare quantum circuits built by our algorithm with quantum circuits optimized for specific graphs that are Linear-nearest-neighbor (LNN) architecture, “sun” (a cycle with tails, presented by the 16-qubit IBMQ device) and “two joint suns” (two joint cycles with tails, presented by the 27-qubit IBMQ device). Our generic method gives similar results with a few more CNOT gates. At the same time, our method allows us to construct a circuit for arbitrary connected graphs.
Open accessCC BY-NC-ND 4.0

Keywords

  • quantum circuits
  • quantum Fourier transform
  • QFT
  • quantum hashing
  • quantum fingerprinting
  • qubit connectivity graph

Suggested citation

Kamil Khadiev, Aliya Khadieva, Zeyu Chen, Junde Wu (2025). Implementation of Quantum Fourier Transform and Quantum Hashing for Quantum Devices with Arbitrary Qubit Connectivity Graphs. Quantum Information & Computation, 25(5), 509-541. https://doi.org/10.2478/qic-2025-0028

Download BibTeX

References (107)

  1. A Yu Kitaev (1995). “Quantum measurements and the abelian stabilizer problem”. arXiv preprint quant-ph/9511026.Google Scholar
  2. T. G. Draper (2000). “Addition on a quantum computer.” arXiv preprint quant-ph/0008033.Google Scholar
  3. G. Brassard, P. Høyer, M. Mosca, and A. Tapp (2022). “Quantum amplitude amplification and estimation.” Contemporary Mathematics, 305, 53–74.DOI: 10.1090/conm/305/05215Google Scholar
  4. A. W. Harrow, Avinatan Hassidim, and Seth Lloyd (2009). “Quantum algorithm for linear systems of equations.” Physical Review Letters, 103: 15, 150502.DOI: 10.1103/PhysRevLett.103.150502Google Scholar
  5. P. W Shor (1999). “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.” SIAM Review, 41: 2, 303–332.DOI: 10.1137/S0036144598347011Google Scholar
  6. L. Wright, C. Mc Keever, J. T. First, R. Johnston, J. Tillay, S. Chaney, M. Rosenkranz, and M. Lubasch (2024). “Noisy intermediate-scale quantum simulation of the one-dimensional wave equation.” Physical Review Research, 6, 043169.DOI: 10.1103/PhysRevResearch.6.043169Google Scholar
  7. T. Lee, R. Mittal, B. W. Reichardt, R. Špalek, and M. Szegedy (2011). “Quantum query complexity of state conversion.” In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 344–353. IEEE.DOI: 10.1109/FOCS.2011.75Google Scholar
  8. A. Belovs (2013). “Quantum walks and electric networks.” arXiv preprint arXiv:1302.3143.Google Scholar
  9. A. Belovs, A. M. Childs, S. Jeffery, R. Kothari, and F. Magniez (2013). “Time-efficient quantum walks for 3-distinctness”. In International Colloquium on Automata, Languages, and Programming, pp. 105–122. Springer.DOI: 10.1007/978-3-642-39206-1_10Google Scholar
  10. A. Montanaro (2020). “Quantum speedup of branch-and-bound algorithms.” Physical Review Research, 2: 1, 013056.DOI: 10.1103/PhysRevResearch.2.013056Google Scholar
  11. A. Montanaro (2018). “Quantum-walk speedup of backtracking algorithms.” Theory of Computing, 14: 15, 1–24.DOI: 10.4086/toc.2018.v014a015Google Scholar
  12. R. Cleve and J. Watrous (2000). “Fast parallel circuits for the quantum Fourier transform.” In Proceedings 41st Annual Symposium on Foundations of Computer Science, pp. 526–536. IEEE.DOI: 10.1109/SFCS.2000.892140Google Scholar
  13. Y. Nam, Y. Su, and D. Maslov (2020). “Approximate quantum Fourier transform with o (n log (n)) t gates.” NPJ Quantum Information, 6: 1, 26.DOI: 10.1038/s41534-020-0257-5Google Scholar
  14. B. Park and D. Ahn (2023). “Reducing cnot count in quantum Fourier transform for the linear nearestneighbor architecture.” Scientific Reports, 13: 1, 8638.DOI: 10.1038/s41598-023-35625-3Google Scholar
  15. M. A Nielsen and I. L Chuang (2010). Quantum computation and quantum information. Cambridge univ. Press.Google Scholar
  16. A.G. Fowler, S.J. Devitt, and L.C.L. Hollenberg (2004). „Implementation of Shor’s algorithm on a linear nearest neighbour qubit array.” Quantum Information & Computation, 4: 4, 237–251.DOI: 10.26421/QIC4.4-1Google Scholar
  17. M. Saeedi, R. Wille, and R. Drechsler (2011). “Synthesis of quantum circuits for linear nearest neighbor architectures.” Quantum Information Processing, 10, 355–377.DOI: 10.1007/s11128-010-0201-2Google Scholar
  18. A. Kole, K. Datta, and I. Sengupta (2017). “A new heuristic for n-dimensional nearest neighbor realization of a quantum circuit.” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 37: 1, 182–192.DOI: 10.1109/TCAD.2017.2693284Google Scholar
  19. A. Bhattacharjee, C. Bandyopadhyay, R. Wille, R. Drechsler, and H. Rahaman (2019). “Improved look-ahead approaches for nearest neighbor synthesis of 1d quantum circuits.” In 2019 32nd International Conference on VLSI Design and 2019 18th International Conference on Embedded Systems (VLSID), pp. 203–208. IEEE.DOI: 10.1109/VLSID.2019.00054Google Scholar
  20. A. Barenco, A. Ekert, K.-A. Suominen, and P. Törmä (1996). “Approximate quantum Fourier transform and decoherence.” Physical Review A, 54: 1, 139.DOI: 10.1103/PhysRevA.54.139Google Scholar
  21. Y. Takahashi, N. Kunihiro, and K. Ohta (2007). “The quantum Fourier transform on a linear nearest neighbor architecture.” Quantum Information & Computation, 7: 4, 383–391.DOI: 10.26421/QIC7.4-7Google Scholar
  22. B. Park and D. Ahn (2022). “T-count optimization of approximate quantum Fourier transform.” arXiv preprint arXiv:2203.07739.Google Scholar
  23. A. Khadieva (2024). “Quantum hashing algorithm implementation.: arXiv preprint. arXiv:quant-ph/2024.Google Scholar
  24. F. Ablayev and A. Vasiliev (2020). “Quantum hashing and Fourier transform.” In Journal of Physics: Conference Series, volume 1680, p. 012001. IOP Publishing.DOI: 10.1088/1742-6596/1680/1/012001Google Scholar
  25. R. Freivalds (1979). “Fast probabilistic algorithms.” In Mathematical Foundations of Computer Science 1979, vol. 74 of LNCS, pp. 57–69.DOI: 10.1007/3-540-09526-8_5Google Scholar
  26. A. Ambainis and R. Freivalds (1998). “1-way quantum finite automata: strengths, weaknesses and generalizations.” In FOCS’98, pp. 332–341. IEEE.DOI: 10.1109/SFCS.1998.743469Google Scholar
  27. A. Ambainis and N. Nahimovs (2008). “Improved constructions of quantum automata.” In TQC, volume 5106 of LNCS, pp. 47–56. Springer.DOI: 10.1007/978-3-540-89304-2_5Google Scholar
  28. A. Ambainis and N. Nahimovs (2009). “Improved constructions of quantum automata.” Theoretical Computer Science, 410: 20, 1916–1922.DOI: 10.1016/j.tcs.2009.01.027Google Scholar
  29. H. Buhrman, R. Cleve, J. Watrous, and R. De Wolf (2001). “Quantum fingerprinting.” Physical Review Letters, 87: 16, 167902.DOI: 10.1103/PhysRevLett.87.167902Google Scholar
  30. F. Ablayev, A. Gainutdinova, M. Karpinski, C. Moore, and C. Pollett (2005). “On the computational power of probabilistic and quantum branching program.” Information and Computation, 203: 2, 145–162.DOI: 10.1016/j.ic.2005.04.003Google Scholar
  31. F. Ablayev and A. Gainutdinova (2005). “Complexity of quantum uniform and nonuniform automata.” In Developments in Language Theory, vol. 3572 of LNCS, pp. 78–87. Springer.DOI: 10.1007/11505877_7Google Scholar
  32. F. Ablayev and A. Vasiliev (2009). “On quantum realisation of boolean functions by the fingerprinting technique.” Discrete Mathematics and Applications, 19: 6, 555–572.DOI: 10.1515/DMA.2009.037Google Scholar
  33. F. Ablayev and A. Vasiliev (2011). “Classical and quantum parallelism in the quantum fingerprinting method.” In International Conference on Parallel Computing Technologies, pp. 1–12. Springer.DOI: 10.1007/978-3-642-23178-0_1Google Scholar
  34. F. M. Ablayev and A. Vasiliev (2013). “Algorithms for quantum branching programs based on fingerprinting.” International Journal of Software and Informatics, 7: 4, 485–500.Google Scholar
  35. F.M. Ablayev and A.V. Vasiliev (2013). “Cryptographic quantum hashing.“Laser Physics Letters, 11: 2, 025202.DOI: 10.1088/1612-2011/11/2/025202Google Scholar
  36. F. Ablayev and A. Vasiliev (2014). “Computing Boolean functions via quantum hashing.” In Computing with New Resources: Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday, pp. 149–160.DOI: 10.1007/978-3-319-13350-8_11Google Scholar
  37. F.M. Ablayev, M.F. Ablayev, and A.V. Vasilev (2014). “Universal quantum hashing.” Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 156, 7–18.Google Scholar
  38. F. Ablayev and M. Ablayev (2015). “On the concept of cryptographic quantum hashing.” Laser Physics Letters, 12: 12, 125204.DOI: 10.1088/1612-2011/12/12/125204Google Scholar
  39. F. Ablayev, M. Ablayev, and A. Vasiliev (2016). “On the balanced quantum hashing.” Journal of Physics: Conference Series, 681, 012019.DOI: 10.1088/1742-6596/681/1/012019Google Scholar
  40. F. Ablayev, M. Ablayev, A. Vasiliev, and M. Ziatdinov (2016). “Quantum fingerprinting and quantum hashing. computational and cryptographical aspects.” Baltic Journal of Modern Computing, 4: 4, 860.DOI: 10.22364/bjmc.2016.4.4.17Google Scholar
  41. A. Vasiliev (2016). “Binary quantum hashing.” Russian Mathematics, 60: 9, 61–65.DOI: 10.3103/S1066369X16090073Google Scholar
  42. A Vasiliev, M Latypov, and M Ziatdinov (2017). “Minimizing collisions for quantum hashing.” Journal of Engineering and Applied Sciences, 12: 4, 877–880.Google Scholar
  43. F. Ablayev, M. Ablayev, K. Khadiev, and A. Vasiliev (2018). “Classical and quantum computations with restricted memory.” LNCS, 11011, 129–155.DOI: 10.1007/978-3-319-98355-4_9Google Scholar
  44. F. Ablayev, M. Ablayev, and A. Vasiliev (2018). “Computing quantum hashing in the model of quantum branching programs.” AIP Conference Proceedings, 1936, 020020.DOI: 10.1063/1.5025458Google Scholar
  45. A.V. Vasiliev, A.R. Vasilov, and M.A. Latypov (2019). “Analysis of properties of quantum hashing.” Journal of Mathematical Sciences, 241: 2, 117–124.DOI: 10.1007/s10958-019-04412-9Google Scholar
  46. F. Ablayev, M. Ablayev, and A. Vasiliev. (2020). “Quantum hashing and fingerprinting for quantum cryptography and computations.” International Computer Science Symposium in Russia, pp. 1–15. Springer.DOI: 10.1007/978-3-030-50026-9_1Google Scholar
  47. A. Vasiliev (2016). “Quantum hashing for finite Abelian groups.” Lobachevskii Journal of Mathematics, 37: 6, 753–757.DOI: 10.1134/S1995080216060184Google Scholar
  48. M. Ziatdinov (2016). “From graphs to keyed quantum hash functions.” Lobachevskii Journal of Mathematics, 37: 6, 705–712.DOI: 10.1134/S1995080216060202Google Scholar
  49. M Ziatdinov (2016). “Quantum hashing group approach.” Lobachevskii Journal of Mathematics, 37: 2, 222–226.DOI: 10.1134/S1995080216020165Google Scholar
  50. I. Zinnatullin (2023). “Cryptographic properties of the quantum hashing based on expander graphs.” Lobachevskii Journal of Mathematics, 44: 2, 776–787.DOI: 10.1134/S1995080223020397Google Scholar
  51. F. Ablayev and A. Vasiliev (2022). “Quantum hashing on the high-dimensional states.” In International Conference on Micro-and Nano-Electronics 2021, vol. 12157, pp. 565–570. SPIE.DOI: 10.1117/12.2624628Google Scholar
  52. F. Le Gall (2009). “Exponential separation of quantum and classical online space complexity.” Theory of Computing Systems, 45: 2, 188–202.DOI: 10.1007/s00224-007-9097-3Google Scholar
  53. F. Le Gall (2006). “Exponential separation of quantum and classical online space complexity.” In SPAA ’06, pp. 67–73. ACM.DOI: 10.1145/1148109.1148119Google Scholar
  54. F. Ablayev, M. Ablayev, K. Khadiev, N. Salihova, and A. Vasiliev (2022). “Quantum algorithms for string processing.” In Mesh Methods for Boundary-Value Problems and Applications, vol.141 of LNCSE.DOI: 10.1007/978-3-030-87809-2_1Google Scholar
  55. F. Ablayev, N. Salikhova, and M. Ablayev (2024). “Hybrid classical–quantum text search based on hashing.” Mathematics, 12: 12, 1858.DOI: 10.3390/math12121858Google Scholar
  56. K. Khadiev and A. Khadieva (2021). “Quantum online streaming algorithms with logarithmic memory.” International Journal of Theoretical Physics, 60, 608–616.DOI: 10.1007/s10773-019-04209-1Google Scholar
  57. Kamil Khadiev and Aliya Khadieva (2022). “Quantum and classical log-bounded automata for the online disjointness problem.” Mathematics, 10, 1.DOI: 10.3390/math10010143Google Scholar
  58. K. Khadiev, A. Khadieva, and I. Mannapov (2018). “Quantum online algorithms with respect to space and advice complexity.” Lobachevskii Journal of Mathematics, 39: 9, 1210–1220.DOI: 10.1134/S1995080218090421Google Scholar
  59. K. Khadiev, A. Khadieva, M. Ziatdinov, I. Mannapov, D. Kravchenko, A. Rivosh, and R. Yamilov (2022). “Twoway and one-way quantum and classical automata with advice for online minimization problems.” Theoretical Computer Science, 920, 76–94.DOI: 10.1016/j.tcs.2022.02.026Google Scholar
  60. A. Khadiev, K.and Khadieva, D. Kravchenko, I. Mannapov, A. Rivosh, and R. Yamilov (2023). “Quantum versus classical online streaming algorithms with logarithmic size of memory.” Lobachevskii Journal of Mathematics, 44: 2, 687–698.DOI: 10.1134/S1995080223020208Google Scholar
  61. K. Khadiev and A. Khadieva (2020). “Two-way quantum and classical automata with advice for online minimization problems.” In Formal Methods. FM 2019 International Workshops, pp. 428–442.DOI: 10.1007/978-3-030-54997-8_27Google Scholar
  62. K. Khadiev and A. Khadieva (2019). “Two-way quantum and classical machines with small memory for online minimization problems.” In International Conference on Micro and Nano-Electronics 2018, vol. 11022 of Proc. SPIE, p. 110222T.DOI: 10.1117/12.2522462Google Scholar
  63. K. Khadiev and A. Khadieva (2017). “Reordering method and hierarchies for quantum and classical ordered binary decision diagrams.” In CSR 2017, vol. 10304 of LNCS, pp. 162–175. Springer.DOI: 10.1007/978-3-319-58747-9_16Google Scholar
  64. K. Khadiev, A. Khadieva, and A. Knop. “Exponential separation between quantum and classical ordered binary decision diagrams, reordering method and hierarchies.” Natural Computing, 22: 4, 723–736.DOI: 10.1007/s11047-022-09904-3Google Scholar
  65. F. Ablayev, A. Gainutdinova, K. Khadiev, and A. Yakaryilmaz (2016). “Very narrow quantum OBDDs and width hierarchies for classical OBDDs.” Lobachevskii Journal of Mathematics, 37: 6, 670–682.DOI: 10.1134/S199508021606007XGoogle Scholar
  66. A Vasiliev (2016). “A model of quantum communication device for quantum hashing.” In Journal of Physics: Conference Series, vol. 681, p. 012020. IOP Publishing.DOI: 10.1088/1742-6596/681/1/012020Google Scholar
  67. A. Gainutdinova and A. Yakaryilmaz (2017). “Nondeterministic unitary obdds.” In P. Weil (ed.), Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 8-12, 2017, Proceedings, vol. 10304 of Lecture Notes in Computer Science, pp. 126–140. Springer.DOI: 10.1007/978-3-319-58747-9_13Google Scholar
  68. A. Yakaryilmaz and A. C. Cem Say (2010). “Languages recognized by nondeterministic quantum finite automata.” Quantum Information and Computation, 10: 9&10, 747–770.DOI: 10.26421/QIC10.9-10-3Google Scholar
  69. A. Gainutdinova and A. Yakaryilmaz (2018). “Unary probabilistic and quantum automata on promise problems.” Quantum Information Processing, 17: 2, 28.DOI: 10.1007/s11128-017-1799-0Google Scholar
  70. A. Gainutdinova and A. Yakaryilmaz (2015). “Unary probabilistic and quantum automata on promise problems.” In Developments in Language Theory, pp. 252–263. Springer.DOI: 10.1007/978-3-319-21500-6_20Google Scholar
  71. A. Khadieva and M. Ziatdinov (2023). “Deterministic construction of QFAS based on the quantum fingerprinting technique.” Lobachevskii Journal of Mathematics, 44: 2, 713–723.DOI: 10.1134/S199508022302021XGoogle Scholar
  72. D.O. Akatev, A.V. Vasiliev, N.M. Shafeev, F.M. Ablayev, and A.A. Kalachev (2022). “Multiqudit quantum hashing and its implementation based on orbital angular momentum encoding.” Laser Physics Letters, 19: 12, 125205.DOI: 10.1088/1612-202X/ac9ec3Google Scholar
  73. D.A. Turaykhanov, D.O. Akatev, A.V. Vasiliev, F.M. Ablayev, and A.A. Kalachev (2021). “Quantum hashing via single-photon states with orbital angular momentum.” Physical Review A, 104: 5, 052606.DOI: 10.1103/PhysRevA.104.052606Google Scholar
  74. S. Z. D. Plachta, M. Hiekkamäki, A. Yakaryilmaz, and R. Fickler (2022). “Quantum advantage using highdimensional twisted photons as quantum finite automata.” Quantum, 6, 752.DOI: 10.22331/q-2022-06-30-752Google Scholar
  75. Y.-Y. Zhao, K. Li, C. Li, S. Zheng, and Z. He (2023). “Experimental demonstration advantage of photonic finite automata.” In 2023 Asia Communications and Photonics Conference/2023 International Photonics and Optoelectronics Meetings (ACP/POEM), pp. 1–3. IEEE.DOI: 10.1109/ACP/POEM59049.2023.10369125Google Scholar
  76. M. Möttönen and J. J. Vartiainen (2006). „Decompositions of general quantum gates.” Trends in Quantum Computing Research, pp. 149. arXiv preprint quant-ph/0504100.Google Scholar
  77. V. Bergholm, J. J. Vartiainen, M. Möttönen, and M. M. Salomaa (2005). “Quantum circuits with uniformly controlled one-qubit gates.” Physical Review A—Atomic, Molecular, and Optical Physics, 71: 5, 052330.DOI: 10.1103/PhysRevA.71.052330Google Scholar
  78. I. Zinnatullin, K. Khadiev, and A. Khadieva (2023). “Efficient implementation of amplitude form of quantum hashing using state-of-the-art quantum processors.” Russian Microelectronics, 52: Suppl 1, S390–S394.DOI: 10.1134/S1063739723600620Google Scholar
  79. A. Khadieva, O Salehi, and A. Yakaryi lmaz (2024). “A representative framework for implementing quantum finite automata on real devices.” In Proceedings of UCNC 2024, vol. 14776 of LNCS, pp. 163–177.DOI: 10.1007/978-3-031-63742-1_12Google Scholar
  80. I. Zinnatullin and K. Khadiev (2025). “Efficient algorithms for quantum hashing.” In Proceedings of UCNC 2025, LNCS. arXiv preprint arXiv:2507.07002.DOI: 10.1007/978-3-032-15641-9_21Google Scholar
  81. M. Kālis (2018). “Kvantu algoritmu realizâcija fiziskâ kvantu datorâ.” Master’s thesis, University of Latvia.Google Scholar
  82. M. Ziiatdinov and A. Khadieva and A. Yakaryilmaz (2023). “Gaps for shallow implementation of quantum finite automata.” In Proceedings of AFL 2023, vol. 386 of Electronic Proceedings in Theoretical Computer Science, pp. 269–280. Open Publishing Association.DOI: 10.4204/EPTCS.386.21Google Scholar
  83. M. Ziiatdinov, A. Khadieva, and K. Khadiev(2025). “Shallow implementation of quantum fingerprinting with application to quantum finite automata.” Frontiers in Computer Science, 7, 2025.DOI: 10.3389/fcomp.2025.1519212Google Scholar
  84. A Vasiliev (2023). “Constant-depth algorithm for quantum hashing.” Russian Microelectronics, 52: Suppl 1, S399–S402.DOI: 10.1134/S106373972360067XGoogle Scholar
  85. F. Ablayev, M. Ablayev, J. Z. Huang, K. Khadiev, N. Salikhova, and D. Wu (2019). “On quantum methods for machine learning problems Part I: Quantum tools.” Big Data Mining and Analytics, 3: 1, 41–55.DOI: 10.26599/BDMA.2019.9020016Google Scholar
  86. K. Khadiev (2022). “Lecture notes on quantum algorithms.” arXiv preprint arXiv:2212.14205.Google Scholar
  87. T. H Cormen, C. E Leiserson, R. L Rivest, and C. Stein (2001). Introduction to Algorithms. McGraw-Hill.Google Scholar
  88. R. Bellman (1962). “Dynamic programming treatment of the travelling salesman problem.” Journal of the ACM (JACM), 9: 1, 61–63.DOI: 10.1145/321105.321111Google Scholar
  89. M. Held and R. M. Karp (1962). “A dynamic programming approach to sequencing problems.” Journal of the Society for Industrial and Applied Mathematics, 10: 1, 196–210.DOI: 10.1137/0110015Google Scholar
  90. A. Ambainis, K. Balodis, J. Iraids, M. Kokainis, K. Prûsis, and J. Vihrovs (2019). “Quantum speedups for exponential-time dynamic programming algorithms.” In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1783–1793. SIAM.DOI: 10.1137/1.9781611975482.107Google Scholar
  91. C. Y.-Y. Lin and H.-H. Lin (2015). “Upper bounds on quantum query complexity inspired by the Elitzur-Vaidman bomb tester.” In 30th Conference on Computational Complexity (CCC 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.Google Scholar
  92. C. Y.-Y. Lin and H.-H. Lin (2016). „Upper bounds on quantum query complexity inspired by the Elitzur-Vaidman bomb tester.” Theory of Computing, 12: 18, 1–35.Google Scholar
  93. C. Dürr, M. Heiligman, P. Høyer, and M. Mhalla (2006). “Quantum query complexity of some graph problems.” SIAM Journal on Computing, 35: 6, 1310–1328.DOI: 10.1137/050644719Google Scholar
  94. S. Arunachalam and R. de Wolf (2017). “Optimizing the number of gates in quantum search.” Quantum Information and Computation, 17: 3&4, 251–261.DOI: 10.26421/QIC17.3-4-4Google Scholar
  95. L. K. Grover (2002). “Trade-offs in the quantum search algorithm.” Physical Review A, 66: 5, 052314.DOI: 10.1103/PhysRevA.66.052314Google Scholar
  96. K. Khadiev, C. M. Bosch-Machado, Z. Chen, and J. Wu (2024). “Quantum algorithms for the shortest common superstring and text assembling problems.” Quantum Information and Computation, 24: 3–4, 267–294.DOI: 10.26421/QIC24.3-4-4Google Scholar
  97. J. Monnot, V. Th Paschos, and S. Toulouse (2003). “Approximation algorithms for the traveling salesman problem.” Mathematical Methods of Operations Research, 56, 387–405.DOI: 10.1007/s001860200239Google Scholar
  98. V. Th Paschos (2016). “An overview on polynomial approximation of np-hard problems.” Yugoslav Journal of Operations Research, 19: 1.DOI: 10.2298/YJOR0901003PGoogle Scholar
  99. S. Hougardy, F. Zaiser, and X. Zhong (2020). “The approximation ratio of the 2-opt heuristic for the metric traveling salesman problem.” Operations Research Letters, 48: 4, 401–404.DOI: 10.1016/j.orl.2020.05.007Google Scholar
  100. J. J. Bentley (1992). “Fast algorithms for geometric traveling salesman problems.” ORSA Journal on Computing, 4: 4, 387–411.DOI: 10.1287/ijoc.4.4.387Google Scholar
  101. G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi (2012). Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer Science & Business Media.Google Scholar
  102. W. Sun, X. Li, L. Yu, Z. Wang, G. Chen, and G. Yang (2025). “Mlqm: Machine learning approach for accelerating optimal qubit mapping.” Future Generation Computer Systems, 107906.DOI: 10.1016/j.future.2025.107906Google Scholar
  103. IBMQ. Transpiler.Google Scholar
  104. K. Khadiev (2025). “Git lab reposetory of the algorithms”. https://gitlab.com/kamilbek/qhqftoptimizer.Google Scholar
  105. A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter (1995). “Elementary gates for quantum computation.” Physical Review A, 52: 5, 3457.DOI: 10.1103/PhysRevA.52.3457Google Scholar
  106. F. Ablayev, A. Khasianov, and A. Vasiliev (2010). “On complexity of quantum branching programs computing equality like Boolean functions.” ECCC.Google Scholar
  107. R. Wille, A. Lye, and R. Drechsler (2014). “Exact reordering of circuit lines for nearest neighbor quantum architectures.” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 33: 12, 1818–1831.DOI: 10.1109/TCAD.2014.2356463Google Scholar