Pith. sign in

REVIEW 5 major objections 5 minor 71 references

Quantum Hashing Circuit Optimization for Arbitrary Qubit Connectivity Graphs Based on 1-Covering Path

T0 review · 5 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Quantum hashing circuits can be routed on any chip graph via a shortest 1-covering path.

desk verdict The 1-covering-path compilation idea is real, but the submitted Algorithm 4 does not match Theorem 1's CNOT count, so the central claim needs repair. read the letter →

arxiv 2608.09134 v1 pith:JW6ME47J submitted 2026-08-10 quant-ph

Kamil Khadiev , Aliya Khadieva , Vadim Sagitov , Kamil Khasanov , Mansur Ziatdinov This is my paper · ORCID
classification quant-ph PACS 03.67.Lx
keywords quantumhashingfingerprintingCNOTcostqubitconnectivitygraph1-coveringpathshallowcircuitfiniteautomatasynthesis
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Quantum hashing, or quantum fingerprinting, encodes a string into a short quantum state that can be used to test equality with bounded error. This paper gives a circuit-rewriting algorithm that implements the repeated hashing operator on any device whose two-qubit gates are limited by a qubit connectivity graph. The idea is to walk the target qubit along a shortest non-simple path that covers every qubit either by visiting it or by being adjacent to it, a 1-covering path, applying controlled rotations to unused neighbors and swapping the target along the path. For $\ell$ applications the CNOT cost is $(3k+2(n-k'))\ell-5\ell+2$, where $k$ is the path length and $k'$ is the number of distinct vertices visited. The result matters because CNOT gates are the expensive hardware operation, and the paper reports a 16-17% reduction over the earlier arbitrary-graph construction on grid architectures while matching specialized circuits on others.

What carries the argument

The load-bearing object is the shortest non-simple 1-covering path (1-SNSCP): a walk that may revisit vertices and whose visited set, together with all neighbors of visited vertices, is the whole vertex set. The path supplies the route of the target qubit, so every qubit either receives a controlled rotation directly or acts as the control for one without long-range routing. The exact solver computes, for every subset $S$ of vertices and last vertex $v$, the shortest walk $D(S,v)$ that visits all of $S$ and ends at $v$, and keeps only those $S$ whose closed neighborhood is all of $V$; this costs $O((m+n)2^n)$. The approximate solver combines a connected dominating set with an Euler tour of the induced subgraph, giving a $2(\ln\Delta+3)$-approximation in $O((n+m)\log n)$ time. The circuit-level economy is that a controlled rotation followed by a SWAP can be rewritten with three CNOTs instead of five, because two consecutive CNOTs cancel.

What would settle it

For a small prime $p$ and target error $\varepsilon$ for the $MOD_p$ automaton, search for a good parameter set of size $t=\lceil(2/\varepsilon)\ln 2p\rceil$ that satisfies the shallow circuit's angle constraints, then implement the generated circuit on a $7\times6$ grid and count CNOTs: if no such parameter set exists the circuit cannot realize the hashing operator, and if the count differs from $(3k+2(n-k'))\ell-5\ell+2$ the cost formula fails.

Watch

Extended reading notes

Core claim

The paper's central claim is that the shallow quantum hashing operator $U_s$ can be implemented on any connected qubit connectivity graph with CNOT cost $(3k+2(n-k'))\ell-5\ell+2$ for $\ell$ applications, where $P=(v_{i_1},\dots,v_{i_k})$ is the shortest 1-covering path and $k'$ is the number of distinct vertices in $P$. The construction begins with a shortest non-simple path whose visited vertices together with their neighbors cover all vertices. The target qubit starts at the first path vertex, and for each path edge the algorithm applies a controlled rotation to every neighboring vertex not yet used, then to the next path vertex, then swaps the target along the edge; on alternating applications the traversal direction reverses, which lets two adjacent controlled rotations merge. The paper proves this cost formula and shows that the generic method recovers the specialized LNN cost, matches the circuits for the 16-qubit and 27-qubit device graphs, and improves on the earlier arbitrary-graph method on grids, where a $7\times6$ grid costs 101 CNOT gates instead of 123 for $\ell=1$.

Load-bearing premise

The construction assumes that the rotation angles required by the shallow circuit can be realized with the same number of qubits as the standard quantum hashing circuit; the paper states in Appendix A that it is not known whether this is possible, and if it is not, the CNOT savings do not implement the intended hash.

Editorial extensions

If this is right

  • For any connected connectivity graph, the CNOT cost lies between $2n\ell-4\ell+2$ and $6n\ell-7\ell+2$, with the exact value set by the shortest 1-covering path.
  • On linear nearest-neighbor chains, the generic construction reproduces the cost of the specialized LNN circuit, so a single algorithm covers that common layout.
  • On grids with odd rows and even columns, the saving over the earlier arbitrary-graph method is more than 16% for a $7\times6$ grid, namely 101 CNOTs versus 123.
  • The method is demonstrated on the $MOD_p$ and $EQ_p$ quantum automata, and the cost formula scales with input length $\ell$ because even-numbered applications reverse the path and merge gates.
  • The paper argues the same rewriting applies to any circuit made of long CNOT sequences, such as those in the textbook quantum Fourier transform.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the Appendix A caveat is settled negatively, meaning the shallow circuit's rotation angles require exponentially more qubits, the algorithm's saving becomes a trade-off of extra qubits for fewer CNOTs rather than an unconditional improvement.
  • The same target-qubit-walk routing could be applied to other CNOT-heavy one-target subcircuits, such as stages of phase estimation, though the paper demonstrates only hashing.
  • A polynomial-time exact 1-SNSCP solver for grid-like device graphs would make the optimization routine practical for large chips; the paper leaves that as an open question.
  • The length of the shortest 1-covering path could serve as a hardware design metric: chips whose connectivity graphs have shorter such paths are cheaper for this family of circuits.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 5 minor

Summary. The paper proposes a method for compiling a sequence of shallow quantum hashing (quantum fingerprinting) operators U_s onto an arbitrary qubit connectivity graph. The method is based on a shortest non-simple 1-covering path P: the target qubit moves along P, controlled rotations are applied to qubits outside P, and SWAP gates move the target. The main theoretical claim (Theorem 1) is a closed-form CNOT-cost formula, (3k+2(n-k'))ℓ-5ℓ+2, for ℓ applications of U_s, with corollary bounds between 2nℓ-4ℓ+2 and 6nℓ-7ℓ+2. The paper also gives an exact exponential-time algorithm and a polynomial-time approximation algorithm for the 1-SNSCP problem, and demonstrates the method on MOD_p and EQ_p automata, including a grid graph example with a reported 16%-17% CNOT reduction over the prior method [49].

Significance. If the CNOT-cost formula and its proof are correct, the paper offers a genuinely useful compilation heuristic for limited-connectivity quantum devices, and the 1-SNSCP formulation has independent algorithmic interest. The strength of the work is that it makes explicit, parameter-free cost formulas and compares them directly with a prior construction [49], rather than fitting constants to data. The exact and approximate algorithms for the 1-covering path problem are also presented in detail. However, the central formula is currently not established by the manuscript: the proof in Appendix H counts a structure that Algorithm 4 does not produce, and the paper itself flags a critical open limitation in Appendix A about whether the shallow circuit uses the same number of qubits for the required hash parameters.

major comments (5)
  1. [Appendix F, Algorithm 4; Section 3.2, Theorem 1] The CNOT counting in Appendix H is inconsistent with Algorithm 4 as written. U is initialized to empty, and the conditions in Steps 3 and 6 only test membership in U (and, in Step 3, that v' is not the next path vertex); vertices of the covering path P are not excluded. On a 4-cycle v1-v2-v3-v4-v1 with shortest 1-covering path P=(v1,v2), literal execution gives: Step 3 adds cR(v4,v1); Step 4 adds cR(v2,v1) and U={v4,v2}; Step 5 swaps v1 and v2; Step 6 then adds both cR(v1,v2) and cR(v3,v2). The CNOT count is 4·2+3=11, whereas Theorem 1 predicts (3·2+2·2)-5+2=7. The extra cR(v1,v2) also breaks the single-use-per-control structure on which the proof's counting relies. To make the theorem correct, Steps 3 and 6 must explicitly skip every vertex of P (or U must be initialized with all path vertices), and the proof must count the resulting number of single CR_y gates accordingly.
  2. [Appendix H, proof of Theorem 1] The proof states that 'for two sequential applications of Us, one CR_y operator disappears' and uses this to derive the -5ℓ term. This cancellation is load-bearing and is not proven at the gate level. The manuscript should provide an explicit circuit identity or an induction showing that, for arbitrary P and arbitrary neighbor orderings, exactly one CR_y gate cancels at each boundary between consecutive U_s applications, including the role of the first and last neighbors of the path endpoints.
  3. [Section 3.2, grid example] The algebra in the grid example contains an arithmetic error. The displayed expansion reads 3((t+1)(q-1)/2 - 2) + 2(qt - ((t+1)(q-1)/2 - 1)) = 2qt + (t+1)(q-1)/2 - 3, but the correct value is 2qt + (t+1)(q-1)/2 - 4. The numerical values 101 and 123 for q=7, t=6 are consistent with the corrected expression, so the qualitative 16%-17% improvement claim survives, but the displayed formula should be corrected.
  4. [Appendix I, proof of Corollary 1] The proof says that after setting k=2n-2, 'the maximum possible number of distinct vertex in P is n-2.' This is not justified and appears to be the wrong direction: the number of distinct vertices in a walk of length 2n-2 is at most n, not at most n-2, and since the cost formula decreases as k' increases, the upper bound on CNOT cost requires a lower bound on k', not an upper bound. Please either prove the needed lower bound or revise the argument for the claimed range 2nℓ-4ℓ+2 to 6nℓ-7ℓ+2.
  5. [Appendix A, quantum fingerprinting caveat] Appendix A explicitly states that 'it is not known whether we can keep the same number of qubits or should we increase the number of qubits exponentially' when using the shallow circuit from [46,47]. This is a load-bearing caveat for the paper's stated application: the constructed circuit implements U_s, and the claim that this is a circuit for the quantum hashing transformation assumes that 'good' angles exist at the same qubit count n. The paper should state prominently that the CNOT-cost guarantees apply to the U_s circuit, and that equivalence to the hashing transformation for fixed n is an empirical assumption inherited from [46,47].
minor comments (5)
  1. [Appendix F, Algorithm 4, Step 5] The line 'sw ap(vj, vj+1)' uses vj and vj+1 while the path was defined as P=(v_i1,...,v_ik); the notation should be consistent, e.g., sw ap(v_{i_j}, v_{i_{j+1}}).
  2. [Appendix C heading] The heading 'Implementation of the ProcedureShor testP a ths for Shortest Paths Searching' contains a corrupted word; it should read 'ShortestPaths'.
  3. [Abstract and Section 3.2] The reported improvement is described variously as '16%-17%' and 'more than 16%'; for the q=7, t=6 example the improvement is 22/123 ≈ 17.9%, so the percentages should be harmonized.
  4. [Section 3.2, grid example] The phrase 'CNOT coast' should be 'CNOT cost'.
  5. [References] Reference [54] is listed as 'Rigetti Computing. Quantum computing, 1987'; if this is a website reference, it should include the URL and an accessed date, and the year appears to be a typo.

Circularity Check

0 steps flagged · score 0.0 of 10

The paper's CNOT-cost derivation is a direct gate count from the algorithm's own construction; no fitted parameters are presented as predictions, and no load-bearing argument reduces to a self-citation.

full rationale

The derivation of Theorem 1 is self-contained: it counts the outputs of Algorithm 4 (pairs of CR_y plus SWAP at cost 3, lone SWAP at cost 3, lone CR_y at cost 2, with cancellations between consecutive applications) and expresses the total in terms of the path length k and the number n-k' of off-path vertices. These inputs are graph-theoretic parameters of the connectivity graph, not fitted constants, and the formula (3k+2(n-k'))ℓ-5ℓ+2 follows by arithmetic from the counting. The comparison to [49] and to the LNN/Eagle circuits is likewise a direct evaluation of published formulas; no benchmark data are used to set a parameter that is later called a prediction. The only load-bearing appeal to the authors' own prior work is the shallow U_s representation from [46,47] and [45]; the paper explicitly flags the open status of the parameter existence in Appendix A ('it is not known whether we can keep the same number of qubits or should we increase the number of qubits exponentially'), so this is a disclosed validity assumption rather than a circular justification. A separate issue is that the proof of Theorem 1 counts exactly n-k' single CR_y gates while the literal pseudocode of Algorithm 4 (Steps 3 and 6) does not exclude path vertices from those gates; that is an internal correctness or exposition risk, not a circular reduction. No step of the derivation is equivalent by definition to its own input, and no fitted quantity is relabeled as a prediction.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim depends on the shallow circuit construction from prior work (whose parameter existence is unproven) and on a merge assumption in the CNOT cost proof. No free parameters are fitted in this paper.

assumptions (5)
  • domain assumption The qubit connectivity graph is connected and undirected, and two-qubit gates are only allowed on edges.
    All construction steps in Section 3.2 assume G=(V,E) is a connected undirected graph.
  • domain assumption The standard CNOT decompositions of CR_y and SWAP (Figures 2 and 3) have the stated costs (2, 3, and 3 for the pair).
    The CNOT cost formula in Theorem 1 is built on these decompositions.
  • ad hoc to paper The shallow circuit from [46,47] implements the quantum hashing transformation with the same number of qubits using 'good' angles that are linear combinations of the original angles.
    Appendix A states this is not known in general, only supported by computational experiments; the paper's circuit assumes it.
  • ad hoc to paper For the shortest 1-covering path, one CR_y gate can always be merged at each boundary between two applications of the hashing operator.
    The proof of Theorem 1 in Appendix H relies on this merge to subtract 2(ℓ-1) CNOTs, but the proof does not analyze when the merge condition holds.
  • standard math Standard graph algorithms (BFS, DP over subsets, Euler tour) are correct and have the stated complexities.
    Used in Section 4 for shortest paths, D(S,v) computation, and the approximation algorithm.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Hashing Circuit Optimization for Arbitrary Qubit Connectivity Graphs Based on 1-Covering Path." pith.science (2026). https://pith.science/paper/JW6ME47J

@misc{pith2026260809134,
  author       = {Pith},
  title        = {Pith review of: Quantum Hashing Circuit Optimization for Arbitrary Qubit Connectivity Graphs Based on 1-Covering Path},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JW6ME47J}},
  note         = {Machine review of arXiv:2608.09134}
}
abstract

One of the obstacles to the widespread adoption of quantum computing is the problem of efficient circuit synthesis. Current quantum hardware has limited connections between qubits, with each qubit connected to only a few others. This means that the circuit has to be transformed to accommodate this. In this paper, we present an algorithm that converts a circuit containing a sequence of CNOT gates into a form that is suitable for arbitrary quantum computer architectures. Although we demonstrate the algorithm only in the context of quantum fingerprinting, similar gate sequences are prevalent in quantum algorithms; for instance, they are present in the textbook quantum Fourier transform. We present a quantum circuit implementation of the quantum hashing algorithm (quantum fingerprinting algorithm) for a quantum device with restrictions on the application of two-qubit gates that are expressed as a qubit connectivity graph. As an example of usage of the technique, we apply it to quantum finite automata recognizing the unary $MOD_p=\{a^\ell: \ell \bmod p=0\}$ language, and the $EQ_p=\{a^\ell b^r: \ell \equiv r \pmod p\}$ language. Given the enhancements that our algorithm provides~-- for instance, in one case it achieves a 16\%--17\% decrease in CNOT circuit cost~-- we believe it could also be useful in a broader quantum compilation context.

Figures

Figures reproduced from arXiv: 2608.09134 by the authors.

Figure 1
Figure 1. Shallow circuit for quantum fingerprinting or quantum hashing algorithm Here, we assume that we have a solution for the 1-SNSCP problem presented in Section 4. Let qi be the logical qubits of the original circuit. Let the qubits of a physical device be associated with the vertices of the graph G, and we call them vi . The algorithm for constructing a circuit is the following. Step 1. We find the shortest 1-covering … view at source ↗
Figure 2
Figure 2. Representation of CRy and SW AP gates using only basic gates Two sequential operators CRy and SW AP that are cR(u, v) and swap(u, v) procedures can be represented by a circuit in [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Representation of a pair CRy and SW AP gates using only basic gates Let us look at the CNOT cost of these operators, that is, the number of CNOT gates in the circuit. We can say that CNOT cost of cR(u, v) is 2; CNOT cost of swap(u, v) is 3; CNOT cost of two sequential operators cR(u, v) and cnot(u, v) is 3. Finally, we can discuss the CNOT cost of the constructed circuit for ℓ applications of quantum hashing operato… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: A quantum circuit for one application of operator Us for Quantum hashing (quantum fingerprinting) algorithm in the case of 5 qubits LNN architecture device Lemma 2. The CNOT cost of the circuit for ℓ applications of the quantum hashing operator Us generated by the pres…
Figure 5
Figure 5. Figure 5: 16-qubit Falcon r4P and 27-qubit Falcon r5.11 architectures of IBMQ When we compare our result with [49], we can see that the maximal possible CNOT cost of a circuit can be 6nℓ − 7ℓ + 2 for our method and 6nℓ − 4ℓ + 2 for [49]. Let us present an example of a graph in w…
Figure 6
Figure 6. Figure 6: A grid architecture with 7 rows and 6 columns. The green line is the shortest 1-covering path (for our algorithm). The red line is the shortest path that visits all vertices at least once (for algorithm of [49]). Our algorithm constructs a path that visits (t+ 1) q−1 2…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

71 extracted references · 33 canonical work pages

  1. [49]

    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

    2025

  2. [1]

    A Nielsen and I

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

    2010

  3. [2]

    Ambainis

    A. Ambainis. Understanding quantum algorithms via query complexity. InProc. Int. Conf. of Math. 2018, volume 4, pages 3283–3304, 2018

    work page 2018

  4. [3]

    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

    2019

  5. [4]

    Ablayev, K

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

    2025

  6. [5]

    Ablayev and A

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

    2020

  7. [6]

    Quantum hashing algorithm implementation.arXiv preprint,

    Aliya Khadieva. Quantum hashing algorithm implementation.arXiv preprint,

  8. [7]

    Fast probabilistic algorithms

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

    1979

Show all 71 references
  1. [8]

    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

    1998

  2. [9]

    Improved constructions of quantum automata

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

    2008

  3. [10]

    Ambainis and N

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

    1916

  4. [11]

    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

    2001

  5. [12]

    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

    2005

  6. [13]

    Ablayev and A

    F. Ablayev and A. Gainutdinova. Complexity of quantum uniform and nonuniform automata. InDevelopments in Language Theory, volume 3572 ofLNCS, pages 78–

  7. [14]

    Ablayev and A

    F. Ablayev and A. Vasiliev. On quantum realisation of boolean functions by the fingerprinting technique.Discrete Mathematics and Applications, 19(6):555–572, 2009

    2009

  8. [15]

    Cryptographic quantum hashing.Laser Physics Letters, 11(2):025202, 2013

    FM Ablayev and AV Vasiliev. Cryptographic quantum hashing.Laser Physics Letters, 11(2):025202, 2013

    2013

  9. [16]

    Quan- tum fingerprinting and quantum hashing

    Farid Ablayev, Marat Ablayev, Alexander Vasiliev, and Mansur Ziatdinov. Quan- tum fingerprinting and quantum hashing. computational and cryptographical as- pects.Baltic Journal of Modern Computing, 4(4):860, 2016

    2016

  10. [17]

    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

    2009

  11. [18]

    Exponential separation of quantum and classical online space complexity

    François Le Gall. Exponential separation of quantum and classical online space complexity. SPAA ’06, pages 67–73. ACM, 2006

    2006

  12. [19]

    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

    2022

  13. [20]

    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

    2024

  14. [21]

    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

    2021

  15. [22]

    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

    2022

  16. [23]

    Khadiev and A

    K. Khadiev and A. Khadieva. Reordering method and hierarchies for quantum and classical ordered binary decision diagrams. InCSR 2017, volume 10304 ofLNCS, pages 162–175. Springer, 2017

    2017

  17. [24]

    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

    2023

  18. [25]

    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

    2016

  19. [26]

    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

    2016

  20. [27]

    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

    2012

  21. [28]

    Automata and quantum computing

    Andris Ambainis and Abuzer Yakaryılmaz. Automata and quantum computing. Handbook of Automata Theory, pages 1457–1493, 2021

    2021

  22. [29]

    Deterministic construction of qfas based on the quantum fingerprinting technique.Lobachevskii Journal of Mathematics, 44(2):713–723, 2023

    Aliya Khadieva and Mansur Ziatdinov. Deterministic construction of qfas based on the quantum fingerprinting technique.Lobachevskii Journal of Mathematics, 44(2):713–723, 2023. Title Suppressed Due to Excessive Length 15

    2023

  23. [30]

    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

    2017

  24. [31]

    Languagesrecognizedbynondeterministic quantum finite automata.Quantum Information and Computation, 10(9&10):747– 770, 2010

    AbuzerYakaryılmazandA.C.CemSay. Languagesrecognizedbynondeterministic quantum finite automata.Quantum Information and Computation, 10(9&10):747– 770, 2010

    2010

  25. [32]

    Gainutdinova and A

    A. Gainutdinova and A. Yakaryılmaz. Unary probabilistic and quantum automata on promise problems.Quantum Information Processing, 17(2):28, 2018

    2018

  26. [33]

    Gainutdinova and A

    A. Gainutdinova and A. Yakaryılmaz. Unary probabilistic and quantum au- tomata on promise problems. InDevelopments in Language Theory, pages 252–263. Springer, 2015

    2015

  27. [34]

    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

    2025

  28. [35]

    Beyond classical: The role of data encoding in quantum regression on air quality prediction

    Mansur Ziiatdinov and Salvatore Distefano. Beyond classical: The role of data encoding in quantum regression on air quality prediction. InIEEE Quantum Ar- tificial Intelligence, Naples, Italy, 11 2025

    2025

  29. [36]

    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

    2022

  30. [37]

    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

    2021

  31. [38]

    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

    2022

  32. [39]

    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

    2023

  33. [40]

    Decompositions of general quantum gates

    Mikko Möttönen and Juha J Vartiainen. Decompositions of general quantum gates. Trends in quantum computing research, pages 149–170, 2006

    2006

  34. [41]

    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

    2005

  35. [42]

    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

    2023

  36. [43]

    Quantum random forest model prediction circuit gate complexity.Russian Microelectronics, 54(8):1442–1448, 2025

    K Khadiev, L Safina, and I Zinnatullin. Quantum random forest model prediction circuit gate complexity.Russian Microelectronics, 54(8):1442–1448, 2025

    2025

  37. [44]

    Safina, K

    L. Safina, K. Khadiev, I. Zinnatullin, and A. Khadieva. Quantum circuit for ran- dom forest prediction.Russian Microelectronics, 52(Suppl 1):S384–S389, 2023

    2023

  38. [45]

    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

    2018

  39. [46]

    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

    2023

  40. [47]

    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. 16 K. Khadiev et al

    2025

  41. [48]

    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

    2024

  42. [50]

    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

    2023

  43. [51]

    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

    2025

  44. [52]

    Quantum error correction below the surface code threshold.Nature, 638:27, 2025

    I Trond, Markus Ansmann, Frank Arute, Kunal Arya, Abraham Asfaw, Nikita Astrakhantsev, Juan Atalaya, Ryan Babbush, Dave Bacon, Brian Ballard, et al. Quantum error correction below the surface code threshold.Nature, 638:27, 2025

    2025

  45. [53]

    Establishing a new benchmark in quantum computational advantage with 105-qubit zuchongzhi 3.0 processor

    Dongxin Gao, Daojin Fan, Chen Zha, Jiahao Bei, Guoqing Cai, Jianbin Cai, Sirui Cao, Fusheng Chen, Jiang Chen, Kefu Chen, et al. Establishing a new benchmark in quantum computational advantage with 105-qubit zuchongzhi 3.0 processor. Physical Review Letters, 134(9):090601, 2025

    2025

  46. [54]

    Quantum computing, 1987

    Rigetti Computing. Quantum computing, 1987. https://www.rigetti.com/

    1987

  47. [55]

    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

    1994

  48. [56]

    McGraw-Hill, 2001

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

    2001

  49. [57]

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

    2022 arXiv

  50. [58]

    Ablayev, A

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

    2010

  51. [59]

    Classical and quantum parallelism in the quantum fingerprinting method

    Farid Ablayev and Alexander Vasiliev. Classical and quantum parallelism in the quantum fingerprinting method. InInternational Conference on Parallel Comput- ing Technologies, pages 1–12. Springer, 2011

    2011

  52. [60]

    M Ablayev and A

    F. M Ablayev and A. Vasiliev. Algorithms for quantum branching programs based on fingerprinting.Int. J. Software and Informatics, 7(4):485–500, 2013

    2013

  53. [61]

    Ant colonies for the travelling sales- man problem.Biosystems, 43(2):73–81, 1997

    Marco Dorigo and Luca Maria Gambardella. Ant colonies for the travelling sales- man problem.Biosystems, 43(2):73–81, 1997

    1997

  54. [62]

    The traveling salesman problem: a case study.Local search in combinatorial optimization, pages 215–310, 1997

    David S Johnson and Lyle A McGeoch. The traveling salesman problem: a case study.Local search in combinatorial optimization, pages 215–310, 1997

    1997

  55. [63]

    Approximation algorithms for connected domi- nating sets.Algorithmica, 20:374–387, 1998

    Sudipto Guha and Samir Khuller. Approximation algorithms for connected domi- nating sets.Algorithmica, 20:374–387, 1998

    1998

  56. [64]

    Christofides

    N. Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. InOperations Research Forum, volume 3, page 20, 2022

    2022

  57. [65]

    On some extremal walks in graphs (in russian).Upravlyaemye sistemy, (17):76–79, 1978

    Anatoliy Serdyukov. On some extremal walks in graphs (in russian).Upravlyaemye sistemy, (17):76–79, 1978

    1978

  58. [66]

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

    René van Bevern and Viktoriia A Slugina. A historical note on the 3/2- approximationalgorithmforthemetrictravelingsalesmanproblem.Historia Math- ematica, 53:118–127, 2020. Title Suppressed Due to Excessive Length 17 A Quantum Fingerprinting or Quantum Hashing Let us present so...

    2020

  59. [67]

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

  60. [68]

    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⟩+...

  61. [69]

    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 ...

  62. [70]

    that allows us to do the next actions in constant time: –Add(queue, v)adds an element to the queue; Title Suppressed Due to Excessive Length 19 –Remove(queue)removes an element from the queue and returns the ele- ment; –Init()returns an empty queue; –isEmpty(queue)returnsT rue...

  63. [71]

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

    We assume that we havecR(u, v)procedure that applies the control rotation Title Suppressed Due to Excessive Length 21 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)p...

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.