References
- A Yu Kitaev (1995). “Quantum measurements and the abelian stabilizer problem”. arXiv preprint quant-ph/9511026.
- T. G. Draper (2000). “Addition on a quantum computer.” arXiv preprint quant-ph/0008033.
- G. Brassard, P. Høyer, M. Mosca, and A. Tapp (2022). “Quantum amplitude amplification and estimation.” Contemporary Mathematics, 305, 53–74.
- A. W. Harrow, Avinatan Hassidim, and Seth Lloyd (2009). “Quantum algorithm for linear systems of equations.” Physical Review Letters, 103: 15, 150502.
- P. W Shor (1999). “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.” SIAM Review, 41: 2, 303–332.
- 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.
- 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.
- A. Belovs (2013). “Quantum walks and electric networks.” arXiv preprint arXiv:1302.3143.
- 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.
- A. Montanaro (2020). “Quantum speedup of branch-and-bound algorithms.” Physical Review Research, 2: 1, 013056.
- A. Montanaro (2018). “Quantum-walk speedup of backtracking algorithms.” Theory of Computing, 14: 15, 1–24.
- 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.
- 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.
- B. Park and D. Ahn (2023). “Reducing cnot count in quantum Fourier transform for the linear nearestneighbor architecture.” Scientific Reports, 13: 1, 8638.
- M. A Nielsen and I. L Chuang (2010). Quantum computation and quantum information. Cambridge univ. Press.
- 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.
- M. Saeedi, R. Wille, and R. Drechsler (2011). “Synthesis of quantum circuits for linear nearest neighbor architectures.” Quantum Information Processing, 10, 355–377.
- 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.
- 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.
- A. Barenco, A. Ekert, K.-A. Suominen, and P. Törmä (1996). “Approximate quantum Fourier transform and decoherence.” Physical Review A, 54: 1, 139.
- 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.
- B. Park and D. Ahn (2022). “T-count optimization of approximate quantum Fourier transform.” arXiv preprint arXiv:2203.07739.
- A. Khadieva (2024). “Quantum hashing algorithm implementation.: arXiv preprint. arXiv:quant-ph/2024.
- F. Ablayev and A. Vasiliev (2020). “Quantum hashing and Fourier transform.” In Journal of Physics: Conference Series, volume 1680, p. 012001. IOP Publishing.
- R. Freivalds (1979). “Fast probabilistic algorithms.” In Mathematical Foundations of Computer Science 1979, vol. 74 of LNCS, pp. 57–69.
- A. Ambainis and R. Freivalds (1998). “1-way quantum finite automata: strengths, weaknesses and generalizations.” In FOCS’98, pp. 332–341. IEEE.
- A. Ambainis and N. Nahimovs (2008). “Improved constructions of quantum automata.” In TQC, volume 5106 of LNCS, pp. 47–56. Springer.
- A. Ambainis and N. Nahimovs (2009). “Improved constructions of quantum automata.” Theoretical Computer Science, 410: 20, 1916–1922.
- H. Buhrman, R. Cleve, J. Watrous, and R. De Wolf (2001). “Quantum fingerprinting.” Physical Review Letters, 87: 16, 167902.
- 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.
- 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.
- F. Ablayev and A. Vasiliev (2009). “On quantum realisation of boolean functions by the fingerprinting technique.” Discrete Mathematics and Applications, 19: 6, 555–572.
- 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.
- 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.
- F.M. Ablayev and A.V. Vasiliev (2013). “Cryptographic quantum hashing.“Laser Physics Letters, 11: 2, 025202.
- 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.
- 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.
- F. Ablayev and M. Ablayev (2015). “On the concept of cryptographic quantum hashing.” Laser Physics Letters, 12: 12, 125204.
- F. Ablayev, M. Ablayev, and A. Vasiliev (2016). “On the balanced quantum hashing.” Journal of Physics: Conference Series, 681, 012019.
- 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.
- A. Vasiliev (2016). “Binary quantum hashing.” Russian Mathematics, 60: 9, 61–65.
- A Vasiliev, M Latypov, and M Ziatdinov (2017). “Minimizing collisions for quantum hashing.” Journal of Engineering and Applied Sciences, 12: 4, 877–880.
- F. Ablayev, M. Ablayev, K. Khadiev, and A. Vasiliev (2018). “Classical and quantum computations with restricted memory.” LNCS, 11011, 129–155.
- F. Ablayev, M. Ablayev, and A. Vasiliev (2018). “Computing quantum hashing in the model of quantum branching programs.” AIP Conference Proceedings, 1936, 020020.
- 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.
- 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.
- A. Vasiliev (2016). “Quantum hashing for finite Abelian groups.” Lobachevskii Journal of Mathematics, 37: 6, 753–757.
- M. Ziatdinov (2016). “From graphs to keyed quantum hash functions.” Lobachevskii Journal of Mathematics, 37: 6, 705–712.
- M Ziatdinov (2016). “Quantum hashing group approach.” Lobachevskii Journal of Mathematics, 37: 2, 222–226.
- I. Zinnatullin (2023). “Cryptographic properties of the quantum hashing based on expander graphs.” Lobachevskii Journal of Mathematics, 44: 2, 776–787.
- 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.
- F. Le Gall (2009). “Exponential separation of quantum and classical online space complexity.” Theory of Computing Systems, 45: 2, 188–202.
- F. Le Gall (2006). “Exponential separation of quantum and classical online space complexity.” In SPAA ’06, pp. 67–73. ACM.
- 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.
- F. Ablayev, N. Salikhova, and M. Ablayev (2024). “Hybrid classical–quantum text search based on hashing.” Mathematics, 12: 12, 1858.
- K. Khadiev and A. Khadieva (2021). “Quantum online streaming algorithms with logarithmic memory.” International Journal of Theoretical Physics, 60, 608–616.
- Kamil Khadiev and Aliya Khadieva (2022). “Quantum and classical log-bounded automata for the online disjointness problem.” Mathematics, 10, 1.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- A Vasiliev (2016). “A model of quantum communication device for quantum hashing.” In Journal of Physics: Conference Series, vol. 681, p. 012020. IOP Publishing.
- 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.
- A. Yakaryilmaz and A. C. Cem Say (2010). “Languages recognized by nondeterministic quantum finite automata.” Quantum Information and Computation, 10: 9&10, 747–770.
- A. Gainutdinova and A. Yakaryilmaz (2018). “Unary probabilistic and quantum automata on promise problems.” Quantum Information Processing, 17: 2, 28.
- A. Gainutdinova and A. Yakaryilmaz (2015). “Unary probabilistic and quantum automata on promise problems.” In Developments in Language Theory, pp. 252–263. Springer.
- A. Khadieva and M. Ziatdinov (2023). “Deterministic construction of QFAS based on the quantum fingerprinting technique.” Lobachevskii Journal of Mathematics, 44: 2, 713–723.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- I. Zinnatullin and K. Khadiev (2025). “Efficient algorithms for quantum hashing.” In Proceedings of UCNC 2025, LNCS. arXiv preprint arXiv:2507.07002.
- M. Kālis (2018). “Kvantu algoritmu realizâcija fiziskâ kvantu datorâ.” Master’s thesis, University of Latvia.
- 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.
- 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.
- A Vasiliev (2023). “Constant-depth algorithm for quantum hashing.” Russian Microelectronics, 52: Suppl 1, S399–S402.
- 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.
- K. Khadiev (2022). “Lecture notes on quantum algorithms.” arXiv preprint arXiv:2212.14205.
- T. H Cormen, C. E Leiserson, R. L Rivest, and C. Stein (2001). Introduction to Algorithms. McGraw-Hill.
- R. Bellman (1962). “Dynamic programming treatment of the travelling salesman problem.” Journal of the ACM (JACM), 9: 1, 61–63.
- 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.
- 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.
- 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.
- 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.
- 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.
- S. Arunachalam and R. de Wolf (2017). “Optimizing the number of gates in quantum search.” Quantum Information and Computation, 17: 3&4, 251–261.
- L. K. Grover (2002). “Trade-offs in the quantum search algorithm.” Physical Review A, 66: 5, 052314.
- 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.
- J. Monnot, V. Th Paschos, and S. Toulouse (2003). “Approximation algorithms for the traveling salesman problem.” Mathematical Methods of Operations Research, 56, 387–405.
- V. Th Paschos (2016). “An overview on polynomial approximation of np-hard problems.” Yugoslav Journal of Operations Research, 19: 1.
- 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.
- J. J. Bentley (1992). “Fast algorithms for geometric traveling salesman problems.” ORSA Journal on Computing, 4: 4, 387–411.
- 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.
- 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.
- IBMQ. Transpiler.
- K. Khadiev (2025). “Git lab reposetory of the algorithms”. https://gitlab.com/kamilbek/qhqftoptimizer.
- 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.
- F. Ablayev, A. Khasianov, and A. Vasiliev (2010). “On complexity of quantum branching programs computing equality like Boolean functions.” ECCC.
- 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.