pith. sign in

arxiv: 2605.20789 · v1 · pith:PE6ZUZZFnew · submitted 2026-05-20 · 🪐 quant-ph · cs.DS

Circuits of Quantum Hashing and Quantum Fourier Transform for a Cactus as a Qubit Connectivity Graph

Kamil Khadiev , Ilnur Valeev This is my paper

Pith reviewed 2026-05-21 05:36 UTC · model grok-4.3

classification 🪐 quant-ph cs.DS
keywords quantum circuitsquantum hashingquantum Fourier transformcactus graphqubit connectivitycovering path problemgraph algorithms
0
0 comments X

The pith

Quantum hashing and Fourier transform circuits can be built in O(n^3) time when qubits connect as a cactus graph.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives an algorithm that builds quantum circuits for quantum hashing and the Quantum Fourier Transform under the restriction that two-qubit gates can only act between qubits joined by edges of a cactus graph. It reduces the task to finding a shortest non-simple 1-covering path and solves that graph problem in O(n^3) time, replacing an exponential search that works for arbitrary graphs. The resulting circuits are shallower because the path dictates an efficient order for the two-qubit operations. A reader cares because real quantum hardware often has fixed, sparse connectivity; a polynomial construction makes these algorithms more practical on such devices.

Core claim

When the qubit connectivity graph is a cactus, the shortest non-simple 1-covering path can be found in O(n^3) time; this path is used as a subroutine to construct an optimized shallow circuit for quantum hashing (fingerprinting) and to improve the circuit for the Quantum Fourier Transform.

What carries the argument

The shortest non-simple 1-covering path in the cactus graph, which orders the applications of two-qubit gates to respect connectivity while keeping the circuit shallow.

If this is right

  • Quantum hashing circuits become constructible in polynomial time on any device whose qubits form a cactus.
  • The same path subroutine yields an improved circuit for the Quantum Fourier Transform under the same connectivity restriction.
  • Circuit synthesis for other quantum algorithms can reuse the covering-path solution whenever the hardware graph is a cactus.
  • Exponential-time search over gate orders is replaced by a deterministic cubic-time procedure for this graph class.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Hardware designers could deliberately arrange qubits into cactus-like trees of cycles to obtain the polynomial circuit-construction benefit.
  • The covering-path technique might generalize to other sparse graphs that admit linear-time decompositions, such as outerplanar graphs.
  • Empirical tests on quantum simulators could measure the actual reduction in two-qubit gate count or depth achieved by the cactus ordering.

Load-bearing premise

The qubit connectivity graph must be exactly a cactus so the polynomial covering-path subroutine applies directly.

What would settle it

A concrete cactus on n vertices for which every algorithm that produces the shortest non-simple 1-covering path requires more than cubic time, or a quantum circuit built from that path that fails to respect the two-qubit gate restrictions.

Figures

Figures reproduced from arXiv: 2605.20789 by Ilnur Valeev, Kamil Khadiev.

Figure 1
Figure 1. Figure 1: Shallow circuit for quantum fingerprinting or quantum hashing algorithm Let us present the main idea of the algorithm. Let P be the shortest non￾simple 1-cover path for the cactus G that is the solution of 1-SNSCPP. (See the definition of 1-SNSCPP in Section 2). Initially, we associate the target qubit with the first vertex of the path P; and control qubits with other vertices of the graph. Because we can … view at source ↗
Figure 2
Figure 2. Figure 2: Representation of CRy, SW AP gates, and a pair CRy and SW AP gates using only basic gates. Theorem 1. The CNOT cost of the circuit for ℓ applications of quantum hash￾ing operator Us generated by the presented algorithm is (3k+ 2(n−k ′ ))ℓ−5ℓ+ 2, where k is the length of the 1-covering path P = (vi1 , . . . , vik ), and k ′ is the number of distinct vertices in P, and n is the number of vertices in the qubi… view at source ↗
Figure 3
Figure 3. Figure 3: A cactus as a qubits connectivity graph. The red path is the shortest path that visits all vertices at least once. It is used by [35]. The green path is the solution for the 1-SNSCP problem. It is used by our algorithm. The algorithm of [35] uses the shortest path P1 that visits all vertices at least once, which is presented as a red path on the figure. The length of the path is k = 10 and the CNOT cost of… view at source ↗
Figure 4
Figure 4. Figure 4: We can split the circuit for the QFT algorithm into a series of control [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Construction of the tree A by the vertex cactus T. Let us fix a vertex r as a root of the tree A. Assume that r corresponds to a single vertex in T. We use the dynamic programming approach [49] for developing an algorithm. Let us consider a vertex v ′ in T and the vertex u of A such that v ′ belongs to the block corresponding to u. Let us compute two values dl [v ′ ] and dp[v ′ ] for each vertex of T. They… view at source ↗
Figure 6
Figure 6. Figure 6: for an example [PITH_FULL_IMAGE:figures/full_fig_p012_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Choosing minimum from two options:just go by cycle and visit all edges except the largest one If the root r corresponds to a cycle, then we try all vertices of the cycle and try to remove each edge of the cycle one by one and return it. For each of these case we obtain the tree where the root corresponds to a single node. For a fixed root r and a fixed removed edge from the cycle if r belongs to a simple c… view at source ↗
Figure 8
Figure 8. Figure 8: Starting from j-th child, go throw all other children except i-th with coming back and finishing in i-th child. We choose the minimal result for all possible roots r and removed edges of the cycle if r belongs to a simple cycle. Let us estimate the complexity of the presented algorithm. Theorem 3. The presented algorithm solves the 1-SNSCP problem for a cactus, and the time complexity is O(n 3 ). (See Appe… view at source ↗
Figure 9
Figure 9. Figure 9: A quantum circuit for Quantum Fourier Transform algorithm for fully con￾nected 5 qubits The CRd gate is represented by basic gates that require two CNOT and three Rz gates [55]. Therefore, n 2−n CNOT gates are required to construct an n-qubit QFT circuit. At the same time, if a quantum device has the LNN architecture, then for implementing the QFT, the number of CNOT gates is much larger than n 2 −n [46]. … view at source ↗
Figure 10
Figure 10. Figure 10: Representation of CRd gate using only basic gates [PITH_FULL_IMAGE:figures/full_fig_p025_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Reduced representation of a pair CRd and SW AP gates using only basic gates Let us discuss the CNOT cost of the algorithm in the next theorem. Theorem 4 ([47]). The CNOT cost of the circuit that is generated using the presented algorithm is at most K + n 2 − n − 1, where K = Pn−1 r=1 len(Pr) is the sum of lengths of the the shortest covering paths Pr. We have two corollaries from this result. Firstly, we … view at source ↗
read the original abstract

We present a quantum circuit implementation of the quantum hashing algorithm (quantum fingerprinting) for a quantum device with restrictions on the application of two-qubit gates by a qubit connectivity graph. We present an optimization technique for the shallow circuit for quantum hashing in the case of a cactus as a qubit connectivity graph. The algorithm has $O(n^3)$ complexity to build the circuit, where $n$ is the number of qubits and $m$ is the number of connections (edges) in the graph. It is improvement compared to the existing exponential-time algorithm in the case of arbitrary graphs. The algorithm uses solution for the shortest non-simple 1-covering path problem as a subroutine. We present an $O(n^3)$-time solution for this graph-theory problem in the case of a cactus. This result can be interesting independently. The algorithm also used for improving of the quantum circuit for Quantum Fourier Transform.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript presents an O(n^3)-time algorithm for constructing quantum circuits implementing quantum hashing (fingerprinting) and the Quantum Fourier Transform on devices whose qubit connectivity graph is a cactus. The construction reduces to solving the shortest non-simple 1-covering path problem on the cactus, for which the authors supply a dedicated polynomial-time subroutine that improves on the exponential-time methods known for arbitrary graphs.

Significance. If the claimed algorithm and its complexity analysis hold, the work supplies a concrete, polynomial-time method for producing shallow circuits under a restricted but structurally interesting connectivity model. The independent graph-theoretic result on 1-covering paths in cacti may be of separate interest to algorithm designers working on block-structured graphs.

major comments (2)
  1. [Abstract] Abstract: the central claim of an O(n^3)-time algorithm for the shortest non-simple 1-covering path problem is stated without any proof sketch, recurrence, or complexity argument. Because this complexity bound is the load-bearing improvement over exponential-time general-graph methods, the absence of even a high-level derivation prevents assessment of correctness.
  2. [Algorithm description / reduction section] The reduction from quantum-circuit construction to the covering-path instance is described only at a high level; no explicit mapping from gate sequence to path cover or analysis of how the cactus block structure is exploited appears in the provided description. This mapping is essential to the claimed circuit optimization.
minor comments (2)
  1. [Abstract] Abstract, final sentence: grammatical issues ('The algorithm also used for improving of the quantum circuit') should be corrected to 'The algorithm is also used to improve the quantum circuit'.
  2. [Abstract] The abstract mentions both n (qubits) and m (edges) yet states complexity as O(n^3); clarify whether the bound is strictly O(n^3) or involves m, and state the dependence explicitly.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and constructive suggestions. We address each major comment below and outline the revisions we will make to strengthen the presentation.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim of an O(n^3)-time algorithm for the shortest non-simple 1-covering path problem is stated without any proof sketch, recurrence, or complexity argument. Because this complexity bound is the load-bearing improvement over exponential-time general-graph methods, the absence of even a high-level derivation prevents assessment of correctness.

    Authors: We agree that a high-level sketch of the O(n^3) argument is needed in the abstract to make the complexity claim assessable. In the revised manuscript we will add a concise description of the dynamic-programming recurrence that exploits the block-cut tree of the cactus, together with the O(n^3) bound that follows from processing each block in linear time after a quadratic preprocessing step on the cut vertices. revision: yes

  2. Referee: [Algorithm description / reduction section] The reduction from quantum-circuit construction to the covering-path instance is described only at a high level; no explicit mapping from gate sequence to path cover or analysis of how the cactus block structure is exploited appears in the provided description. This mapping is essential to the claimed circuit optimization.

    Authors: We accept that the reduction is currently presented at too high a level. The revised version will contain an explicit bijection between admissible two-qubit gate sequences on the cactus and non-simple 1-covering paths, together with a dedicated subsection that shows how the cactus block structure is used to decompose the path-finding problem into independent subproblems on each block while preserving the required gate ordering. revision: yes

Circularity Check

0 steps flagged

No significant circularity; explicit algorithmic construction

full rationale

The paper introduces a new O(n^3)-time algorithm for the shortest non-simple 1-covering path problem on cactus graphs and applies it as a subroutine to construct quantum circuits for hashing and QFT under the given connectivity restriction. This is a direct constructive result based on the block structure of cacti, with no equations, fitted parameters, or self-citations shown to reduce the central claim to its own inputs by definition. The derivation chain is self-contained as an independent graph-theoretic solution mapped to circuit depth optimization.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the standard quantum circuit model with connectivity constraints and on the existence of an efficient algorithm for the covering-path problem on cactus graphs; no free parameters or new physical entities are introduced.

axioms (1)
  • domain assumption Quantum circuits are built from one- and two-qubit gates whose two-qubit gates are allowed only between adjacent vertices in the given connectivity graph.
    Invoked in the opening paragraph when stating the restriction on two-qubit gates.

pith-pipeline@v0.9.0 · 5690 in / 1174 out tokens · 41472 ms · 2026-05-21T05:36:33.092773+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

60 extracted references · 60 canonical work pages · 1 internal anchor

  1. [1]

    A Nielsen and I

    M. A Nielsen and I. L Chuang.Quantum computation and quantum information. Cambridge univ. press, 2010

    work page 2010

  2. [2]

    Ablayev, M

    F. Ablayev, M. Ablayev, J. Z. Huang, K. Khadiev, N. Salikhova, and D. Wu. On quantum methods for machine learning problems part i: Quantum tools.Big Data Mining and Analytics, 3(1):41–55, 2019

    work page 2019

  3. [3]

    Ablayev, K

    F. Ablayev, K. Khadiev, A. Vasiliev, and M. Ziiatdinov. Theory and applications of quantum hashing.Quantum Reports, 7(2), 2025

    work page 2025

  4. [4]

    Fast probabilistic algorithms

    R¯ usin,š Freivalds. Fast probabilistic algorithms. InMathematical Foundations of Computer Science 1979, volume 74 ofLNCS, pages 57–69, 1979

    work page 1979

  5. [5]

    Ambainis and N

    A. Ambainis and N. Nahimovs. Improved constructions of quantum automata. Theoretical Computer Science, 410(20):1916–1922, 2009

    work page 1916

  6. [6]

    Quantum fingerprinting.Physical Review Letters, 87(16):167902, 2001

    Harry Buhrman, Richard Cleve, John Watrous, and Ronald De Wolf. Quantum fingerprinting.Physical Review Letters, 87(16):167902, 2001

    work page 2001

  7. [7]

    Ablayev, A

    F. Ablayev, A. Gainutdinova, M. Karpinski, C. Moore, and C. Pollett. On the com- putational power of probabilistic and quantum branching program.Information and Computation, 203(2):145–162, 2005

    work page 2005

  8. [8]

    Ablayev and A

    F. Ablayev and A. Vasiliev. Quantum hashing on the high-dimensional states. InInternational Conference on Micro-and Nano-Electronics 2021, volume 12157, pages 565–570. SPIE, 2022

    work page 2021

  9. [9]

    Exponential separation of quantum and classical online space complexity.Theory of Computing Systems, 45(2):188–202, 2009

    François Le Gall. Exponential separation of quantum and classical online space complexity.Theory of Computing Systems, 45(2):188–202, 2009

    work page 2009

  10. [10]

    Ablayev, M

    F. Ablayev, M. Ablayev, K. Khadiev, N. Salihova, and A. Vasiliev. Quantum algorithms for string processing. InMesh Methods for Boundary-Value Problems and Applications, volume 141 ofLNCSE, 2022

    work page 2022

  11. [11]

    Hybrid classical–quantum text search based on hashing.Mathematics, 12(12):1858, 2024

    Farid Ablayev, Nailya Salikhova, and Marat Ablayev. Hybrid classical–quantum text search based on hashing.Mathematics, 12(12):1858, 2024

    work page 2024

  12. [12]

    Khadiev and A

    K. Khadiev and A. Khadieva. Quantum online streaming algorithms with loga- rithmic memory.International Journal of Theoretical Physics, 60:608–616, 2021

    work page 2021

  13. [13]

    Quantum and classical log-bounded automata for the online disjointness problem.Mathematics, 10(1), 2022

    Kamil Khadiev and Aliya Khadieva. Quantum and classical log-bounded automata for the online disjointness problem.Mathematics, 10(1), 2022

    work page 2022

  14. [14]

    Khadiev, K.and Khadieva, D

    A. Khadiev, K.and Khadieva, D. Kravchenko, I. Mannapov, A. Rivosh, and R.Yamilov. Quantumversusclassicalonlinestreamingalgorithmswithlogarithmic size of memory.Lobachevskii Journal of Mathematics, 44(2):687–698, 2023

    work page 2023

  15. [15]

    Khadiev, A

    K. Khadiev, A. Khadieva, M. Ziatdinov, I. Mannapov, D. Kravchenko, A. Rivosh, and R. Yamilov. Two-way and one-way quantum and classical automata with advice for online minimization problems.Theoretical Computer Science, 920:76– 94, 2022

    work page 2022

  16. [16]

    Khadiev and A

    K. Khadiev and A. Khadieva. Two-way quantum and classical automata with ad- vice for online minimization problems. InFormal Methods. FM 2019 International Workshops, pages 428–442, 2020. Circuits of QH and QFT for a Cactus as a Qubit Connectivity Graph 15

    work page 2019

  17. [17]

    Khadiev and A

    K. Khadiev and A. Khadieva. Two-way quantum and classical machines with small memory for online minimization problems. InInternational Conference on Micro- and Nano-Electronics 2018, volume 11022 ofProc. SPIE, page 110222T, 2019

    work page 2018

  18. [18]

    Khadiev, A

    K. Khadiev, A. Khadieva, and I. Mannapov. Quantum online algorithms with respect to space and advice complexity.Lobachevskii Journal of Mathematics, 39(9):1210–1220, 2018

    work page 2018

  19. [19]

    Exponential separation be- tween quantum and classical ordered binary decision diagrams, reordering method and hierarchies.Natural Computing, 22(4):723–736, 2023

    Kamil Khadiev, Aliya Khadieva, and Alexander Knop. Exponential separation be- tween quantum and classical ordered binary decision diagrams, reordering method and hierarchies.Natural Computing, 22(4):723–736, 2023

    work page 2023

  20. [20]

    A model of quantum communication device for quantum hashing

    A Vasiliev. A model of quantum communication device for quantum hashing. In Journal of Physics: Conference Series, volume 681, page 012020, 2016

    work page 2016

  21. [21]

    Gainutdinova and A

    A. Gainutdinova and A. Yakaryılmaz. Nondeterministic unitary obdds. InCom- puter Science - Theory and Applications - CSR2017 Proceedings, volume 10304 of LNCS, pages 126–140, 2017

    work page 2017

  22. [22]

    Ziiatdinov, F

    M. Ziiatdinov, F. Farsian, F. Schilliró, and S. Distefano. Comparing quantum machine learning approaches in astrophysics. InIEEE Quantum Software (QSW), World Congress on SERVICES, 7 2025

    work page 2025

  23. [23]

    Multiqudit quantum hashing and its implementation based on orbital angular momentum encoding.Laser Physics Letters, 19(12):125205, 2022

    DO Akatev, AV Vasiliev, NM Shafeev, FM Ablayev, and AA Kalachev. Multiqudit quantum hashing and its implementation based on orbital angular momentum encoding.Laser Physics Letters, 19(12):125205, 2022

    work page 2022

  24. [24]

    Quan- tum hashing via single-photon states with orbital angular momentum.Physical Review A, 104(5):052606, 2021

    DA Turaykhanov, DO Akatev, AV Vasiliev, FM Ablayev, and AA Kalachev. Quan- tum hashing via single-photon states with orbital angular momentum.Physical Review A, 104(5):052606, 2021

    work page 2021

  25. [25]

    ZD Plachta, M

    S. ZD Plachta, M. Hiekkamäki, A. Yakaryılmaz, and R. Fickler. Quantum advan- tage using high-dimensional twisted photons as quantum finite automata.Quan- tum, 6:752, 2022

    work page 2022

  26. [26]

    Experimen- tal demonstration advantage of photonic finite automata

    Yuan-Yuan Zhao, Keren Li, Chao Li, Shenggen Zheng, and Zhixue He. Experimen- tal demonstration advantage of photonic finite automata. In2023 Asia Commu- nications and Photonics Conference/2023 International Photonics and Optoelec- tronics Meetings (ACP/POEM), pages 01–03. IEEE, 2023

    work page 2023

  27. [27]

    Quantum circuits with uniformly controlled one-qubit gates.Physical Review A—Atomic, Molecular, and Optical Physics, 71(5):052330, 2005

    Ville Bergholm, Juha J Vartiainen, Mikko Möttönen, and Martti M Salomaa. Quantum circuits with uniformly controlled one-qubit gates.Physical Review A—Atomic, Molecular, and Optical Physics, 71(5):052330, 2005

    work page 2005

  28. [28]

    Efficient implementation of ampli- tude form of quantum hashing using state-of-the-art quantum processors.Russian Microelectronics, 52(Suppl 1):S390–S394, 2023

    I Zinnatullin, K Khadiev, and A Khadieva. Efficient implementation of ampli- tude form of quantum hashing using state-of-the-art quantum processors.Russian Microelectronics, 52(Suppl 1):S390–S394, 2023

    work page 2023

  29. [29]

    Zinnatullin, K

    I. Zinnatullin, K. Khadiev, and I. Nikitin. Quantum random forest model predic- tion circuit gate complexity.Russian Microelectronics, 54(8):1449–1457, 2025

    work page 2025

  30. [30]

    Kvantu algoritmu realiz¯ acija fizisk¯ a kvantu dator¯ a

    M¯ artin,š K¯ alis. Kvantu algoritmu realiz¯ acija fizisk¯ a kvantu dator¯ a. Master’s thesis, University of Latvia, 2018

    work page 2018

  31. [31]

    Ziiatdinov and A

    M. Ziiatdinov and A. Khadieva, A.and Yakaryılmaz. Gaps for shallow implemen- tation of quantum finite automata. InProceedings of AFL 2023, volume 386 of EPTCS, pages 269–280, 2023

    work page 2023

  32. [32]

    Ziiatdinov, A

    M. Ziiatdinov, A. Khadieva, and K. Khadiev. Shallow implementation of quantum fingerprinting with application to quantum finite automata.Frontiers in Computer Science, 7:1519212, 2025

    work page 2025

  33. [33]

    Khadieva, O Salehi, and A

    A. Khadieva, O Salehi, and A. Yakaryılmaz. A representative framework for im- plementing quantum finite automata on real devices. InProceedings of UCNC 2024, volume 14776 ofLNCS, pages 163–177. 2024

    work page 2024

  34. [34]

    Quantum hashing algorithm implementation.arXiv preprint,

    Aliya Khadieva. Quantum hashing algorithm implementation.arXiv preprint,

    work page

  35. [35]

    16 K.Khadiev and I

    arXiv:2407.10136. 16 K.Khadiev and I. Valeev

    work page arXiv

  36. [36]

    Khadiev, A

    K. Khadiev, A. Khadieva, Z. Chen, and J. Wu. Implementation of quantum fourier transform and quantum hashing for a quantum device with arbitrary qubits con- nection graphs.Quantum Information & Computation, 25(2025):509–541, 2025

    work page 2025

  37. [37]

    Constant-depth algorithm for quantum hashing.Russian Microelec- tronics, 52(Suppl 1):S399–S402, 2023

    A Vasiliev. Constant-depth algorithm for quantum hashing.Russian Microelec- tronics, 52(Suppl 1):S399–S402, 2023

    work page 2023

  38. [38]

    Shallow circuit imple- mentation for the phase form of quantum hashing and local-sensitive hashing on ibmq noisy emulators.Russian Microelectronics, 53(8):1449–1457, 2025

    K Khadiev, D Melnikova, K Altinbayev, and A Khadieva. Shallow circuit imple- mentation for the phase form of quantum hashing and local-sensitive hashing on ibmq noisy emulators.Russian Microelectronics, 53(8):1449–1457, 2025

    work page 2025

  39. [39]

    Efficient algorithms for solving the shortest covering path problem.Transportation Science, 28(4):317–327, 1994

    John Current, Hasan Pirkul, and Erik Rolland. Efficient algorithms for solving the shortest covering path problem.Transportation Science, 28(4):317–327, 1994

    work page 1994

  40. [40]

    Boothe, Z

    P. Boothe, Z. Dvorák, A. M Farley, and A. Proskurowski. Graph covering via shortest paths.Congressus Numerantium, 187:145, 2007

    work page 2007

  41. [41]

    Quantum measurements and the Abelian Stabilizer Problem

    A Yu Kitaev. Quantum measurements and the abelian stabilizer problem.arXiv preprint quant-ph/9511026, 1995

    work page internal anchor Pith review Pith/arXiv arXiv 1995

  42. [42]

    Addition on a quantum computer.arXiv preprint quant- ph/0008033, 2000

    Thomas G Draper. Addition on a quantum computer.arXiv preprint quant- ph/0008033, 2000

    work page arXiv 2000

  43. [43]

    Brassard, P

    G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation.Contemporary Mathematics, 305:53–74, 2002

    work page 2002

  44. [44]

    Quantum algorithm for linear systems of equations.Physical review letters, 103(15):150502, 2009

    Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations.Physical review letters, 103(15):150502, 2009

    work page 2009

  45. [45]

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

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

    work page 1999

  46. [46]

    Ablayev and A

    F. Ablayev and A. Vasiliev. Quantum hashing and fourier transform. InJournal of Physics: Conf. Series, volume 1680, page 012001, 2020

    work page 2020

  47. [47]

    Park and D

    B. Park and D. Ahn. Reducing cnot count in quantum fourier transform for the linear nearest-neighbor architecture.Scientific Reports, 13(1):8638, 2023

    work page 2023

  48. [48]

    Khadiev, A

    K. Khadiev, A. Khadieva, V. Sagitov, and K. Khasanov. Quantum circuit for quan- tum fourier transform for arbitrary qubit connectivity graphs. InLatin American Symposium on Theoretical Informatics (LATIN) 2026, 2026

    work page 2026

  49. [49]

    K. Khadiev. Lecture notes on quantum algorithms.arXiv preprint arXiv:2212.14205, 2022

    work page arXiv 2022

  50. [50]

    McGraw-Hill, 2001

    T.HCormen,C.ELeiserson,R.LRivest,andC.Stein.Introduction to Algorithms. McGraw-Hill, 2001

    work page 2001

  51. [51]

    Ambainis and R

    A. Ambainis and R. Freivalds. 1-way quantum finite automata: strengths, weak- nesses and generalizations. InFOCS’98, pages 332–341. IEEE, 1998

    work page 1998

  52. [52]

    Improved constructions of quantum automata

    Andris Ambainis and Nikolajs Nahimovs. Improved constructions of quantum automata. InTQC, volume 5106 ofLNCS, pages 47–56. Springer, 2008

    work page 2008

  53. [53]

    Ablayev, A

    F. Ablayev, A. Khasianov, and A. Vasiliev. On complexity of quantum branching programs computing equality-like boolean functions.ECCC, 2010

    work page 2010

  54. [54]

    Ambainis and A

    A. Ambainis and A. Yakaryılmaz. Superiority of exact quantum automata for promise problems.Information Processing Letters, 112(7):289–291, 2012

    work page 2012

  55. [55]

    Ablayev, A

    F. Ablayev, A. Gainutdinova, K. Khadiev, and A. Yakaryılmaz. Very narrow quan- tum OBDDs and width hierarchies for classical OBDDs.Lobachevskii Journal of Mathematics, 37(6):670–682, 2016

    work page 2016

  56. [56]

    good” in the following sense. A set of parametersK={k1, . . . , kt}is called “good

    A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter. Elementary gates for quantum com- putation.Physical review A, 52(5):3457, 1995. Circuits of QH and QFT for a Cactus as a Qubit Connectivity Graph 17 A Quantum Fingerprinting or Quantum Hashing Let us present some basic concepts of quan...

    work page 1995

  57. [57]

    We constructg(x), that maps all acceptable inputs to0modulomand others to arbitrary non-zero (modulom) integers

    work page

  58. [58]

    collects

    After the necessary manipulations with the fingerprint, theH⊗log 2 t oper- ator is applied to the firstlog2 tqubits. This operation “collects” all cosine amplitudes at the all-zero state. That is, we obtain the state of the type |h′ σ⟩= 1 t tX i=1 cos 2πkig(σ) m |00. . .0⟩|0⟩+ 2tX i=2 αi|i⟩ 18 K.Khadiev and I. Valeev

    work page

  59. [59]

    Then we ac- cept the input if the outcome is the all-zero state

    This state is measured on the standard computational basis. Then we ac- cept the input if the outcome is the all-zero state. This happens with the probability P raccept(σ) = 1 t2 tX i=1 cos 2πkig(σ) m !2 , which is1for the inputs, whose image is0 modmand is bounded byεfor the others. Dueto[31,32,30],thealgorithmcanbeimplementedusingtheshallowcircuit prese...

    work page

  60. [60]

    The angleξ r corresponds to the qubitqr associated with the vertexv

    We assume that we havecR(u, v)procedure that applies the control rotation operatorCR y touas a control qubit andvas a target one. The angleξ r corresponds to the qubitqr associated with the vertexv. Additionally, we have sw ap(u, v)procedure that applies swap gate touandvqubits. Algorithm 1Implementation ofConstructForPath(P)procedure. Algo- rithm of cons...

    work page