Shallow Implementation of Quantum Fingerprinting with Application to Quantum Finite Automata

Aliya Khadieva; Kamil Khadiev; Mansur Ziiatdinov

REVIEW 4 major objections 4 minor 55 references

Shallow Implementation of Quantum Fingerprinting with Application to Quantum Finite Automata

T0 review · 4 major / 4 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 Generalized arithmetic progressions yield explicit MOD_p fingerprint coefficients with logarithmic circuit depth, and the shallow circuit separates member from non-member words on noisy-device emulations where the standard circuit fails.

desk verdict The central theorem is vacuous for epsilon<1 because a proper GAP cannot fit in Z_p with the chosen m; the noisy-device experiments are a useful heuristic but do not rescue the theory. read the letter →

arxiv 2412.18823 v1 pith:XH56UTHA submitted 2024-12-25 quant-ph cs.CRcs.FL

Mansur Ziiatdinov , Aliya Khadieva , Kamil Khadiev This is my paper · ORCID

classification quant-phcs.CRcs.FL MSC 68Q1268Q4511B2581P68 PACS 03.67.Lx

keywords quantumfingerprintingfiniteautomatashallowcircuitsgeneralizedarithmeticprogressionsadditivecombinatoricsMOD_planguagecircuitdepthhashing

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 fingerprinting normally buys a short state at the price of a long sequence of unitary operations; this paper argues that for MOD_p automata the right resource to optimize is circuit depth, not qubit width. It proposes explicit coefficient sets built from generalized arithmetic progressions, meaning all subset sums of a small generating set $T$, and claims that these sets achieve any target error $\varepsilon$ with a circuit of depth $\lceil \log p - 2\log\varepsilon\rceil$, comparable to the depth of the best probabilistic construction. If the claim holds, quantum finite automata for MOD_p become implementable on near-term noisy hardware with only a handful of qubits; emulations for MOD_17 separate accepted from rejected words using 4 qubits, while the standard deep circuit cannot. The shallow circuit's measured error is at most about twice the standard circuit's on an ideal device, and substantially better under noise, which is the regime that matters for current machines.

What carries the argument

The load-bearing object is the generalized arithmetic progression $B = \{2t_0 + n_1 t_1 + \cdots + n_m t_m \mid 0 \le n_i < 3\}$; B being proper means its $3^m$ elements are all distinct in $\mathbb{Z}_p$, which is what lets the proof count representations $a+b=n$ exactly. That count gives the additive-energy estimate $E(A,A) \le 2^{3m}$, and the Fourier-bias inequality from Theorem 1 converts the energy estimate into the fingerprint error bound $\varepsilon(A) \le \sqrt{p}/\sqrt{d}$. On the implementation side, the subset-sum structure of $A$ is computed by a depth-$m$ circuit of controlled rotations, so the exponential circuit depth of the naive fingerprint is replaced by a logarithmic one.

What would settle it

Check the cardinality needed for a proper GAP: for any candidate $(t_0, T)$ with $m = \lceil \log p - 2\log\varepsilon\rceil$ (base 2), the set $B$ has $3^m$ elements and lives in a group of size $p$; a direct substitution gives $3^m > p$ for every $\varepsilon < 1$, so no such proper $B$ exists. A numerical cross-check is to compute the actual $\varepsilon(A)$ for the paper's $p=17$, $m=3$ heuristic set $K=\{4,8,12,6\}$ and verify whether the measured maximum squared Fourier sum falls below any non-vacuous bound the theorem could assign for those parameters.

Watch

Extended reading notes

Core claim

The paper's central claim is that a coefficient set $A = \{t_0 + \sum_{t\in S} t \mid S \subseteq T\}$ of $2^m$ elements works as a quantum fingerprint for MOD_p, provided the doubled set $B = \{2t_0 + n_1 t_1 + \cdots + n_m t_m \mid 0 \le n_i < 3\}$ is a proper generalized arithmetic progression. Properness makes every representation $a+b=n$ unique up to the choice of which summand contributes $t_i$ in positions where the coefficient of $t_i$ in $n$ is 1; counting these choices bounds the additive energy by $E(A,A) \le 2^{3m}$. Combining this with the Fourier-bias inequality of the paper's Theorem 1 gives $\varepsilon(A) \le \sqrt{p}/\sqrt{d}$, and inserting $d=2^m$ with $m = \lceil \log p - 2\log\varepsilon\rceil$ pushes the error below $\varepsilon$. Corollary 1 then states that the circuit for the transition operator $U_a(A)$ has depth $\lceil \log p - 2\log\varepsilon\rceil$, which the paper presents as an explicit shallow fingerprinting construction with depth comparable to the probabilistic method.

Load-bearing premise

The entire error bound depends on the unproven existence, for the stated $m = \lceil \log p - 2\log\varepsilon\rceil$, of a proper generalized arithmetic progression $B = \{2t_0 + n_1 t_1 + \cdots + n_m t_m \mid 0 \le n_i < 3\}$ in $\mathbb{Z}_p$, and because properness requires $3^m \le p$ while the base-2 logarithm used in the paper gives $3^m > p$ whenever $\varepsilon < 1$, this existence is not established by the proof.

Editorial extensions

If this is right

MOD_p languages can be recognized by quantum finite automata whose transition circuit has depth $O(\log p)$, so the number of sequential unitary operations no longer grows exponentially in the number of fingerprint qubits.
The explicit coefficient set has provable error below any chosen $\varepsilon$, with depth within a constant factor of the probabilistic method, giving a deterministic and reproducible construction for near-term hardware.
On a noisy-device emulator, the shallow four-qubit circuit for MOD_17 accepts member words above a threshold $\lambda+\varepsilon$ and rejects non-members below $\lambda-\varepsilon$, while the standard circuit fails to separate most multiples of $p$.
Implementing the shallow circuit on linearly connected qubits needs about $3m+3$ CX gates, versus $O(m2^m)$ for a straightforward decomposition of the standard circuit, reducing the connectivity bottleneck on current devices.

Reading between the lines

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

The proof only needs the coefficient set to have small additive energy, so the same GAP-based construction should extend to other automata or fingerprinting tasks whose error is controlled by Fourier bias of the coefficient set, not just MOD_p.
The experiments suggest the shallow circuit's advantage grows with noise: on ideal hardware its error is at most about twice the standard circuit's, but under noise it outperforms it, so depth reduction may be the more important optimization for NISQ and early error-corrected devices.
A direct hardware run of the shallow MOD_17 circuit, measuring acceptance counts for word lengths up to 128, would test the cutpoint separation seen in emulation; if real gate noise preserves the gap, the construction becomes a practical building block.
The paper leaves open whether logarithmic depth is optimal; a natural follow-up is to prove a lower bound of $\Omega(\log p - 2\log\varepsilon)$ for any explicit Fourier-bias-$\varepsilon$ coefficient set, which would make the construction depth-optimal.

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.

Desk Editor's Note

read the letter

Two things to know up front. The GAP-based shallow fingerprinting construction is not new; it appeared in the authors' AFL 2023 paper, which they cite. And the central theorem as stated here is vacuous: the hypothesis that B is a proper GAP cannot be satisfied for any epsilon<1, which is the only regime that matters for bounded-error automata. The parameter m = ceil(log p - 2 log epsilon) forces 3^m > p, while properness of a GAP in Z_p requires 3^m <= p. So the additive-energy bound that drives the proof has no valid instance. The error bound epsilon(A) <= sqrt(p/2^m) then cannot get below 1 for any m that fits in Z_p.

The paper does do some things well. The shallow circuit that computes the fingerprint using subset-sum coefficients is a legitimate and interesting idea, and the numerical study on a noisy IBMQ emulator for MOD_17 is useful: it shows the shallow circuit separates members from non-members with a clear threshold, while the standard circuit fails. The authors are honest that the coefficients in the experiments are obtained by heuristic optimization, not by instantiating the GAP construction, so they do not overclaim the numerics as evidence for the theorem.

The soft spots are the ones you'd expect from the vacuous theorem. The proof of Theorem 2 relies crucially on uniqueness of representations in B; if B is not proper, the counting of R_n(A) and the bound E(A,A) <= 3^m break down. The paper also leans heavily on the prior conference paper for the core construction, so the genuinely new contribution here is mostly the numerical section, which is a small demonstration rather than a general result. The AIKPS comparison in Theorem 3 is a straightforward application of known results.

Who should read this? Anyone working on depth-optimized quantum fingerprinting or QFAs on NISQ hardware might find the noisy-device data worth a look. But the theoretical claim that GAPs give logarithmic-depth fingerprints is unsupported, and the paper as written cannot be accepted as a research contribution.

I would still send it to referees rather than desk-reject, because the shallow-circuit idea and the empirical results could, with a corrected analysis, be a useful paper. But as it stands, the main theorem is not just weak; it is vacuous in the only parameter regime that matters.

Referee Report

4 major / 4 minor

Summary. The paper proposes a shallow quantum circuit for quantum fingerprinting, aimed at the MOD_p quantum finite automata of Ambainis and Nahimovs. The main construction (Section 3, Theorem 2) chooses a set T of m elements of Z_p, forms A as the set of all subset sums, and claims that if a related 3-adic generalized arithmetic progression B is proper then the fingerprinting error is at most ε, with circuit depth ceil(log p − 2 log ε). A second depth bound is given for AIKPS-style coefficient sequences, and Section 4 reports numerical experiments comparing the proposed shallow circuit with the standard circuit on noiseless and noisy models. The central theoretical claim is Theorem 2 and its Corollary 1.

Significance. An explicit O(log p)-depth implementation of quantum fingerprinting would be a genuinely useful contribution: existing constructions have depth proportional to the number d=2^m of coefficients, and the paper correctly identifies circuit depth rather than width as the practical bottleneck on NISQ devices. The numerical experiments, with code made available, are also a useful practical data point. However, the main theorem's hypothesis is unsatisfiable in exactly the parameter regime needed for bounded-error automata, so the advertised construction is not established. I therefore cannot recommend acceptance.

major comments (4)

[Section 3, Theorem 2] The hypothesis of Theorem 2 is vacuous for every nontrivial error bound. A proper GAP B in Z_p with side lengths 3 has exactly 3^m distinct elements, so properness requires 3^m ≤ p. With m = ceil(log p − 2 log ε), using base-2 logarithms, one has 3^m ≥ (p/ε^2)^{log_2 3} > p whenever ε < 1 and p ≥ 2; the same conclusion holds if the logarithms are taken in any base b > 1. Thus no t0,T satisfying the hypothesis exists in the bounded-error regime ε < 1. The uniqueness of representations in B, on which the counting of R_n(A) and the bound E(A,A) ≤ 2^{3m} depend, is therefore never available. Corollary 1, the 'GAPs method' row of the table in the introduction, and the conclusion's claim of provable shallow fingerprinting are all unsupported by this theorem.
[Section 3, proof of Theorem 2] The Fourier-bias step of the proof is algebraically inconsistent as printed. Applying Theorem 1 with ambient group Z_p would give ||A||_U^4 ≤ E(A,A)/p^3 − (|A|/p)^4, but the displayed derivation writes denominators 2^{3·2^m} and 2^{4·2^m}, then concludes ||A||_U ≤ d^{3/4}/p^{3/4}. No relation p = 2^d has been introduced: in Section 2, p is the size of the domain of the fingerprinting function, while d = 2^m. As written, this step does not prove the stated bound on ||A||_U.
[Section 3, Theorem 2 parameter regime] Even if one repaired Theorem 2 by choosing m as large as properness permits, the proof's own error estimate would remain vacuous. Properness imposes m ≤ log_3 p, so the bound ε(A) ≤ (p/2^m)^{1/2} gives ε(A) ≥ p^{(1−log_3 2)/2} > 1 for all p ≥ 2. Hence the issue is not merely a wrong choice of m in the theorem statement; the proof as a whole cannot yield a bounded-error guarantee for any coefficient set generated by a proper 3-adic GAP of this form.
[Section 4] The numerical experiments do not instantiate Theorem 2, so they cannot supply empirical support for the theorem's depth–error tradeoff. The coefficient sets are found by coordinate descent or brute-force optimization, and the paper does not report whether the resulting K has the subset-sum structure required by the construction, nor whether the associated B is a proper GAP. The experimental comparison may still be of independent interest, but it does not address the failure of the central theoretical claim.

minor comments (4)

[Section 2] In the definition of the Fourier transform, the notation c1_A(0) should presumably be \widehat{1_A}(0), and the normalization of the Fourier transform should be stated explicitly.
[Section 3, Theorem 2] The theorem states ε(A) ≤ ε, but the automaton error is a function of the coefficient multiset K; please clarify that |A| = d and that no subset-sum collisions occur, or reformulate the statement for multisets.
[Section 4.1] For m = 3 control qubits, the shallow construction requires 2^3 = 8 coefficients, but the reported optimal set K = {4, 8, 12, 6} has four elements; please clarify this inconsistency.
[Page 2] The definition of the state set contains a typo: 'Q = {q1,0, q1,1, ..., qd,0, dd,1}' should read 'qd,1' instead of 'dd,1'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 2's error/depth proof is conditional and self-contained, though its proper-GAP hypothesis is left uninstantiated.

full rationale

The central derivation is Theorem 2, which claims that if B is a proper GAP of the stated form, then the subset-sum set A has epsilon(A) <= epsilon. The proof is written out in the paper: it counts representations in A, bounds the additive energy E(A,A) <= 2^{3m}, applies the external Tao-Vu Fourier-bias inequality (Theorem 1, [42]), and then algebraically converts the bias bound into epsilon(A) <= p^{1/2}/d^{1/2}. The final inequality follows from the choice m = ceil(log p - 2 log epsilon). None of these steps equates the conclusion to the hypothesis by construction: properness is a genuine assumption used to make representations unique, not a restatement of small Fourier bias. The depth bound in Corollary 1 is simply the number of rotation layers in the shallow circuit of Figure 2, i.e., m, and is not derived by renaming a fitted quantity. The numerical experiments in Section 4 optimize coefficient sets with coordinate descent and then evaluate their errors; the paper does not present those optimized sets as predictions of Theorem 2. Self-citations appear, but they are background/provenance references or known lower bounds, not the load-bearing step; the proof of Theorem 2 rests on the quoted Tao-Vu result and the Ambainis-Nahimovs automaton construction. I therefore find no circular step. A separate concern, which is a correctness gap rather than circularity, is that the paper never constructs a proper GAP B of dimension ceil(log p - 2 log epsilon) in Z_p, and for epsilon < 1 that hypothesis is in fact incompatible with properness because 3^m > p; this makes the theorem's antecedent empty but does not make the conditional derivation circular.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central theorem rests on the cited Tao-Vu inequality, the automaton error formula, the assumption that a proper GAP with the stated parameters exists, and the depth-O(m) circuit from [26]. The existence assumption is unsatisfiable in the small-error regime, which is why soundness is low. No free physical parameters are fitted to the theoretical claim; the experimental coefficient search is a separate numerical exercise.

free parameters (1)

GAP basis t0, t1, ..., tm in Z_p = not constructed; in numerical experiments chosen by brute force or coordinate descent, e.g. four angles for p=17
The theorem assumes such a basis exists, but gives no explicit construction. Existence is incompatible with the stated m for bounded error, and the experiments rely on heuristic search to find the angles.

assumptions (4)

standard math Tao-Vu Fourier bias/additive energy inequality (Theorem 1)
Used to convert the additive energy bound into a Fourier bias bound in the proof of Theorem 2.
domain assumption Automaton error Pe is bounded by epsilon(K) = max_x |(1/d^2)|sum_j exp(2 pi i k_j x/p)|^2|
This relation comes from the QFA model of Ambainis and Nahimovs; it is the basis for the error analysis.
domain assumption B being a proper GAP in Z_p makes subset sums A distinct and representations unique
The proof of R_n(A) = 2^|c1| depends on uniqueness of the representation n = 2t0 + sum gamma_i t_i, which requires properness. This assumption is unsatisfiable for the stated m when epsilon < 1.
domain assumption The shallow circuit of Figure 2 computes U_a(A) with depth O(m), from Kalis thesis [26]
The depth claim for the construction relies on this circuit implementation.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Shallow Implementation of Quantum Fingerprinting with Application to Quantum Finite Automata." pith.science (2026). https://pith.science/paper/XH56UTHA

@misc{pith2026241218823,
  author       = {Pith},
  title        = {Pith review of: Shallow Implementation of Quantum Fingerprinting with Application to Quantum Finite Automata},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XH56UTHA}},
  note         = {Machine review of arXiv:2412.18823}
}

abstract

Quantum fingerprinting is a technique that maps classical input word to a quantum state. The obtained quantum state is much shorter than the original word, and its processing uses less resources, making it useful in quantum algorithms, communication, and cryptography. One of the examples of quantum fingerprinting is quantum automata algorithm for $MOD_{p}=\{a^{i\cdot p} \mid i \geq 0\}$ languages, where $p$ is a prime number. However, implementing such an automaton on the current quantum hardware is not efficient. Quantum fingerprinting maps a word $x \in \{0,1\}^{n}$ of length $n$ to a state $\ket{\psi(x)}$ of $O(\log n)$ qubits, and uses $O(n)$ unitary operations. Computing quantum fingerprint using all available qubits of the current quantum computers is infeasible due to a large number of quantum operations. To make quantum fingerprinting practical, we should optimize the circuit for depth instead of width in contrast to the previous works. We propose explicit methods of quantum fingerprinting based on tools from additive combinatorics, such as generalized arithmetic progressions (GAPs), and prove that these methods provide circuit depth comparable to a probabilistic method. We also compare our method to prior work on explicit quantum fingerprinting methods.

Figures

Figures reproduced from arXiv: 2412.18823 by the authors.

**Figure 9.** When analyzing the data, only few members like i = p, i = 2p, i = 4p, and i = 7p can be separated from non-members. Other members of MODp cannot be separated from members, for example i = 3p, i = 5p, and i = 6p. In addition, we can see that the number P˜(1) > P˜(p). Our algorithm cannot find a set K that violates this condition. At the same time, we can ignore i = 1 because it can be checked with additional conditio… view at source ↗

**Figure 1.** Deep fingerprinting circuit example. Gate Uj is a rotation Ry(4πkjx/p). Controls in controlled gates run over all binary strings of length s . . . . . . . . . . . . |0⟩ H |0⟩ H |0⟩ H |0⟩ R1 R2 Rm R0 [PITH_FULL_IMAGE:figures/full_fig_p014_1.png] view at source ↗

**Figure 2.** Shallow fingerprinting circuit example. Gate Rj is a rotation Ry(4πtjx/p) . . . . . . . . . . . . |0⟩ H |0⟩ H |0⟩ H |0⟩ Rj,1 Rj,2 Rj,w−1 Rj [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗

Figures from the paper (6 more)

**Figure 3.** Figure 3: Circuit Cj for AIKPS subsequence. Gate Rj is a rotation Ry(4π(r −1 j )/p). Gate Rj,k is a rotation Ry(2k−1 · 4π(r −1 j )/p) References 1. Ablayev, F., Ablayev, M., Khadiev, K., Vasiliev, A.: Classical and quantum computations with restricted memory. LNCS 11011, 129–15…

**Figure 4.** Figure 4: Circuit for Ua(T). Gate Rj is a rotation Ry(4π(r −1 j )/p). Gate Rj,k is a rotation Ry(2k−1 · 4π(r −1 j )/p) 2. Ablayev, F., Gainutdinova, A., Khadiev, K., Yakaryılmaz, A.: Very narrow quantum OBDDs and width hierarchies for classical OBDDs. Lobachevskii Journal of Ma…

**Figure 5.** Figure 5: Computational errors for m = 3, 4, 5 of original and shallow automata 13. Ablayev, F., Vasiliev, A.: Quantum hashing and fourier transform. In: Journal of Physics: Conference Series. vol. 1680, p. 012001. IOP Publishing (2020) 16 [PITH_FULL_IMAGE:figures/full_fig_p016…

**Figure 6.** Figure 6: Proportions of the shallow automaton errors over the original automaton errors for m = 3, 4, 5 and different values of p 14. Ablayev, F., Vasiliev, A.: Quantum hashing on the high-dimensional states. In: International Conference on Micro-and Nano-Electronics 2021. vol.…

**Figure 7.** Figure 7: Shallow circuit that uses Rz operators [PITH_FULL_IMAGE:figures/full_fig_p018_7.png]

**Figure 9.** Figure 9: Computational errors for m = 3 of standard fingerprinting scheme automata for noisy device Mathematical Society Publishing House (Sep 2021). https://doi.org/10.4171/ Automata-2/17 21. Birkan, U., Salehi, O., Olejar, V., Nurlu, C., Yakaryılmaz, A.: Implementing quan- ¨ …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

55 extracted references · 49 canonical work pages

[1]

LNCS 11011, 129–155 (2018) 14 Fig

Ablayev, F., Ablayev, M., Khadiev, K., Vasiliev, A.: Classical and quantum com- putations with restricted memory. LNCS 11011, 129–155 (2018) 14 Fig. 4.Circuit for Ua(T ). Gate Rj is a rotation Ry(4π(r−1 j )/p). Gate Rj,k is a rotation Ry(2k−1 · 4π(r−1 j )/p)

work page 2018
[2]

Lobachevskii Journal of Mathematics 37(6), 670–682 (2016)

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

work page 2016
[3]

Discrete Mathematics and Applications 19(6), 555–572 (2009)

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

work page 2009
[4]

Uchenye Zapiski Kazanskogo Universiteta

Ablayev, F.M., Ablayev, M.F., Vasilev, A.V.: Universal quantum hashing. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki 156, 7–18 (2014)

work page 2014
[5]

Laser Physics Letters 12(12), 125204 (2015)

Ablayev, F., Ablayev, M.: On the concept of cryptographic quantum hashing. Laser Physics Letters 12(12), 125204 (2015)

work page 2015
[6]

In: Mesh Methods for Boundary-Value Problems and Applications

Ablayev, F., Ablayev, M., Khadiev, K., Salihova, N., Vasiliev, A.: Quantum algo- rithms for string processing. In: Mesh Methods for Boundary-Value Problems and Applications. Lecture Notes in Computational Science and Engineering, vol. 141 (2022)

2022
[7]

In: Journal of Physics: Conference Series

Ablayev, F., Ablayev, M., Vasiliev, A.: On the balanced quantum hashing. In: Journal of Physics: Conference Series. vol. 681, p. 012019. IOP Publishing (2016)

work page 2016
[8]

In: AIP Conference Proceedings

Ablayev, F., Ablayev, M., Vasiliev, A.: Computing quantum hashing in the model of quantum branching programs. In: AIP Conference Proceedings. vol. 1936, p. 020020. AIP Publishing LLC (2018)

work page 2018

Show all 55 references

[9]

In: International Computer Science Symposium in Russia

Ablayev, F., Ablayev, M., Vasiliev, A.: Quantum hashing and fingerprinting for quantum cryptography and computations. In: International Computer Science Symposium in Russia. pp. 1–15. Springer (2020)

2020
[10]

Computational and Cryptographical Aspects

Ablayev, F., Ablayev, M., Vasiliev, A., Ziatdinov, M.: Quantum Fingerprinting and Quantum Hashing. Computational and Cryptographical Aspects. Baltic Journal of Modern Computing 4(4), 860–875 (Dec 2016). https://doi.org/10.22364/bjmc. 2016.4.4.17

2016 doi
[11]

In: International Conference on Parallel Computing Technologies

Ablayev, F., Vasiliev, A.: Classical and quantum parallelism in the quantum finger- printing method. In: International Conference on Parallel Computing Technologies. pp. 1–12. Springer (2011)

2011
[12]

Com- puting with New Resources: Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday pp

Ablayev, F., Vasiliev, A.: Computing boolean functions via quantum hashing. Com- puting with New Resources: Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday pp. 149–160 (2014) 15 Fig. 5.Computational errors for m = 3, 4, 5 of original and shallow automata

2014
[13]

In: Journal of Physics: Conference Series

Ablayev, F., Vasiliev, A.: Quantum hashing and fourier transform. In: Journal of Physics: Conference Series. vol. 1680, p. 012001. IOP Publishing (2020) 16 Fig. 6.Proportions of the shallow automaton errors over the original automaton errors for m = 3, 4, 5 and different values of p

2020
[14]

In: International Conference on Micro-and Nano-Electronics 2021

Ablayev, F., Vasiliev, A.: Quantum hashing on the high-dimensional states. In: International Conference on Micro-and Nano-Electronics 2021. vol. 12157, pp. 565–

2021
[15]

Ablayev, F.M., Vasiliev, A.: Algorithms for quantum branching programs based on fingerprinting. Int. J. Software and Informatics 7(4), 485–500 (2013) 17 Fig. 7.Shallow circuit that uses Rz operators Fig. 8.Computational errors for m = 3 of shallow automata for noisy device

2013
[16]

Laser Physics Letters 11(2), 025202 (2013)

Ablayev, F., Vasiliev, A.: Cryptographic quantum hashing. Laser Physics Letters 11(2), 025202 (2013)

2013
[17]

Bulletin of the London Mathematical Society 22(6), 583–590 (Nov 1990)

Ajtai, M., Iwaniec, H., Koml´ os, J., Pintz, J., Szemer´ edi, E.: Construction of a thin set with small fourier coefficients. Bulletin of the London Mathematical Society 22(6), 583–590 (Nov 1990). https://doi.org/10.1112/blms/22.6.583

1990 doi
[18]

In: FOCS’98

Ambainis, A., Freivalds, R.: 1-way quantum finite automata: strengths, weaknesses and generalizations. In: FOCS’98. pp. 332–341. IEEE (1998)

1998
[19]

Theo- retical Computer Science 410(20), 1916–1922 (2009)

Ambainis, A., Nahimovs, N.: Improved constructions of quantum automata. Theo- retical Computer Science 410(20), 1916–1922 (2009). https://doi.org/10.1016/ j.tcs.2009.01.027

2009
[20]

In: ´Eric Pin, J

Ambainis, A., Yakaryılmaz, A.: Automata and quantum computing. In: ´Eric Pin, J. (ed.) Handbook of Automata Theory, vol. 2, chap. 39, pp. 1457–1493. European 18 Fig. 9.Computational errors for m = 3 of standard fingerprinting scheme automata for noisy device Mathematical Socie...

2021
[21]

In: International Conference on Computational Science

Birkan, U., Salehi, ¨O., Olejar, V., Nurlu, C., Yakaryılmaz, A.: Implementing quan- tum finite automata algorithms on noisy devices. In: International Conference on Computational Science. pp. 3–16. Springer (2021). https://doi.org/10.1007/ 978-3-030-77980-1$_$1

2021
[22]

Physical Review Letters 87(16), 167902 (Sep 2001)

Buhrman, H., Cleve, R., Watrous, J., de Wolf, R.: Quantum Fingerprinting. Physical Review Letters 87(16), 167902 (Sep 2001). https://doi.org/10.1103/ PhysRevLett.87.167902

2001
[23]

Physical Review A 100, 032328 (Sep 2019)

Cross, A.W., Bishop, L.S., Sheldon, S., Nation, P.D., Gambetta, J.M.: Validating quantum computers using randomized model circuits. Physical Review A 100, 032328 (Sep 2019). https://doi.org/10.1103/PhysRevA.100.032328

2019 doi
[24]

In: Weil, P

Gainutdinova, A., Yakaryılmaz, A.: Nondeterministic unitary obdds. In: Weil, P. (ed.) Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 8-12, 2017, Proceed- ings. Lecture Notes in Computer Scienc...

2017 doi
[25]

IBM: Eagle’s quantum performance progress (2022), https://research.ibm.com/ blog/eagle-quantum-processor-performance

2022
[26]

Master’s thesis, Uni- versity of Latvia (2018)

K¯ alis, M.: Kvantu Algoritmu Realiz¯ acija Fizisk¯ a Kvantu Dator¯ a (Quantum Algo- rithm Implementation on a Physical Quantum Computer). Master’s thesis, Uni- versity of Latvia (2018)

2018
[27]

In: CSR 2017, LNCS, vol

Khadiev, K., Khadieva, A.: Reordering method and hierarchies for quantum and classical ordered binary decision diagrams. In: CSR 2017, LNCS, vol. 10304, pp. 162–175. Springer (2017)

2017
[28]

International Journal of Theoretical Physics 60, 608–616 (2021)

Khadiev, K., Khadieva, A.: Quantum online streaming algorithms with logarithmic memory. International Journal of Theoretical Physics 60, 608–616 (2021). https: 19 //doi.org/10.1007/s10773-019-04209-1

2021 doi
[29]

Mathematics 10(1) (2022)

Khadiev, K., Khadieva, A.: Quantum and classical log-bounded automata for the online disjointness problem. Mathematics 10(1) (2022). https://doi.org/10. 3390/math10010143

2022
[30]

Natural Computing pp

Khadiev, K., Khadieva, A., Knop, A.: Exponential separation between quan- tum and classical ordered binary decision diagrams, reordering method and hierarchies. Natural Computing pp. 1–14 (2022). https://doi.org/10.1007/ s11047-022-09904-3

2022
[31]

In: Proceedings of UCNC 2024, LNCS, vol

Khadieva, A., Salehi, O., Yakaryılmaz, A.: A representative framework for imple- menting quantum finite automata on real devices. In: Proceedings of UCNC 2024, LNCS, vol. 14776 (2024)

2024
[32]

Khadieva, A.: Optimal parameters computing code (2023), https://github.com/aliyakhadi/Parameters counting

2023
[33]

Lobachevskii Journal of Mathematics44(2), 713–723 (Feb 2023)

Khadieva, A., Ziatdinov, M.: Deterministic construction of qfas based on the quan- tum fingerprinting technique. Lobachevskii Journal of Mathematics44(2), 713–723 (Feb 2023). https://doi.org/10.1134/S199508022302021X

2023 doi
[34]

Le Gall, F.: Exponential separation of quantum and classical online space com- plexity. pp. 67–73. SPAA ’06, ACM (2006)

2006
[35]

Theory of Computing Systems 45(2), 188–202 (2009)

Le Gall, F.: Exponential separation of quantum and classical online space com- plexity. Theory of Computing Systems 45(2), 188–202 (2009)

2009
[36]

The- oretical Computer Science 237(1-2), 275–306 (Apr 2000)

Moore, C., Crutchfield, J.P.: Quantum automata and quantum grammars. The- oretical Computer Science 237(1-2), 275–306 (Apr 2000). https://doi.org/10. 1016/S0304-3975(98)00191-1
[37]

Trends in Quantum Computing Research (2006)

M¨ ott¨ onen, M., Vartiainen, J.J.: Decompositions of general quantum gates. Trends in Quantum Computing Research (2006). https://doi.org/10.48550/ARXIV. QUANT-PH/0504100

2006 doi
[38]

Quantum 2, 79 (2018)

Preskill, J.: Quantum computing in the nisq era and beyond. Quantum 2, 79 (2018)

2018
[39]

Combinatorics, Probability and Computing 2(4), 513–518 (Dec 1993)

Razborov, A., Szemer´ edi, E., Wigderson, A.: Constructing small sets that are uni- form in arithmetic progressions. Combinatorics, Probability and Computing 2(4), 513–518 (Dec 1993). https://doi.org/10.1017/S0963548300000870

1993 doi
[40]

https://doi.org/10.48550/arXiv.2107.02262

Salehi, ¨O., Yakaryılmaz, A.: Cost-efficient qfa algorithm for quantum computers (2021). https://doi.org/10.48550/arXiv.2107.02262

2021 doi arXiv
[41]

In: Computing with New Resources, pp

Say, A.C.C., Yakaryılmaz, A.: Quantum finite automata: A modern introduction. In: Computing with New Resources, pp. 208–222. Springer (2014). https://doi. org/10.1007/978-3-319-13350-8$_$16

2014 doi
[42]

Tao, T., Vu, V.: Additive combinatorics, Cambridge Studies in Advanced Mathe- matics, vol. 105. Cambridge University Press (2006). https://doi.org/10.1017/ CBO9780511755149

2006
[43]

In: Journal of Physics: Conference Series

Vasiliev, A.: A model of quantum communication device for quantum hashing. In: Journal of Physics: Conference Series. vol. 681, p. 012020. IOP Publishing (2016)

2016
[44]

Journal of Engineering and Applied Sciences 12(4), 877–880 (2017)

Vasiliev, A., Latypov, M., Ziatdinov, M.: Minimizing collisions for quantum hash- ing. Journal of Engineering and Applied Sciences 12(4), 877–880 (2017)

2017
[45]

Russian Mathematics 60(9), 61–65 (2016)

Vasiliev, A.: Binary quantum hashing. Russian Mathematics 60(9), 61–65 (2016)

2016
[46]

Lobachevskii Journal of Mathematics 37(6), 753–757 (2016)

Vasiliev, A.: Quantum hashing for finite abelian groups. Lobachevskii Journal of Mathematics 37(6), 753–757 (2016)

2016
[47]

Journal of Mathematical Sciences 241(2), 117–124 (2019)

Vasiliev, A., Vasilov, A., Latypov, M.: Analysis of properties of quantum hashing. Journal of Mathematical Sciences 241(2), 117–124 (2019)

2019
[48]

https://doi.org/10.48550/ ARXIV.2110.14108

Wack, A., Paik, H., Javadi-Abhari, A., Jurcevic, P., Faro, I., Gambetta, J.M., Johnson, B.R.: Quality, speed, and scale: three key attributes to measure the per- 20 formance of near-term quantum computers (2021). https://doi.org/10.48550/ ARXIV.2110.14108

2021 doi arXiv
[49]

Mathematical programming 151(1), 3–34 (Mar 2015)

Wright, S.J.: Coordinate descent algorithms. Mathematical programming 151(1), 3–34 (Mar 2015). https://doi.org/10.1007/s10107-015-0892-3

2015 doi
[50]

Quantum Inf

Yakaryılmaz, A., Say, A.C.C.: Languages recognized by nondeterministic quantum finite automata. Quantum Inf. Comput. 10(9&10), 747–770 (2010). https://doi. org/10.26421/QIC10.9-10-3 , https://doi.org/10.26421/QIC10.9-10-3

2010 doi
[51]

group approach

Ziatdinov, M.: Quantum hashing. group approach. Lobachevskii Journal of Math- ematics 37(2), 222–226 (2016)

2016
[52]

Lobachevskii Jour- nal of Mathematics 37(6), 705–712 (2016)

Ziatdinov, M.: From graphs to keyed quantum hash functions. Lobachevskii Jour- nal of Mathematics 37(6), 705–712 (2016)

2016
[53]

In: Zsolt Gazdag, S.I., Kovasznai, G

Ziiatdinov, M., Khadieva, A., Yakaryılmaz, A.: Gaps for shallow implementation of quantum finite automata. In: Zsolt Gazdag, S.I., Kovasznai, G. (eds.) Proceedings of the 16th International Conference on Automata and Formal Languages (AFL 2023), Eger, Hungary, September 5-7, 2...

2023 doi
[54]

Lobachevskii Journal of Mathematics 44(2), 776–787 (2023)

Zinnatullin, I.: Cryptographic properties of the quantum hashing based on ex- pander graphs. Lobachevskii Journal of Mathematics 44(2), 776–787 (2023)

2023
[55]

Russian Mi- croelectronics 52(Suppl 1), S390–S394 (2023) 21

Zinnatullin, I., Khadiev, K., Khadieva, A.: Efficient implementation of amplitude form of quantum hashing using state-of-the-art quantum processors. Russian Mi- croelectronics 52(Suppl 1), S390–S394 (2023) 21

2023

Pith tools

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

[1] [1]

LNCS 11011, 129–155 (2018) 14 Fig

Ablayev, F., Ablayev, M., Khadiev, K., Vasiliev, A.: Classical and quantum com- putations with restricted memory. LNCS 11011, 129–155 (2018) 14 Fig. 4.Circuit for Ua(T ). Gate Rj is a rotation Ry(4π(r−1 j )/p). Gate Rj,k is a rotation Ry(2k−1 · 4π(r−1 j )/p)

work page 2018

[2] [2]

Lobachevskii Journal of Mathematics 37(6), 670–682 (2016)

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

work page 2016

[3] [3]

Discrete Mathematics and Applications 19(6), 555–572 (2009)

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

work page 2009

[4] [4]

Uchenye Zapiski Kazanskogo Universiteta

Ablayev, F.M., Ablayev, M.F., Vasilev, A.V.: Universal quantum hashing. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki 156, 7–18 (2014)

work page 2014

[5] [5]

Laser Physics Letters 12(12), 125204 (2015)

Ablayev, F., Ablayev, M.: On the concept of cryptographic quantum hashing. Laser Physics Letters 12(12), 125204 (2015)

work page 2015

[6] [6]

In: Mesh Methods for Boundary-Value Problems and Applications

Ablayev, F., Ablayev, M., Khadiev, K., Salihova, N., Vasiliev, A.: Quantum algo- rithms for string processing. In: Mesh Methods for Boundary-Value Problems and Applications. Lecture Notes in Computational Science and Engineering, vol. 141 (2022)

2022

[7] [7]

In: Journal of Physics: Conference Series

Ablayev, F., Ablayev, M., Vasiliev, A.: On the balanced quantum hashing. In: Journal of Physics: Conference Series. vol. 681, p. 012019. IOP Publishing (2016)

work page 2016

[8] [8]

In: AIP Conference Proceedings

Ablayev, F., Ablayev, M., Vasiliev, A.: Computing quantum hashing in the model of quantum branching programs. In: AIP Conference Proceedings. vol. 1936, p. 020020. AIP Publishing LLC (2018)

work page 2018