Mansur Ziatdinov
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Mansur Ziatdinov has a total of 16 co-authors. Here are the top co-authors by number of shared publications:
- Kamil Khadiev
Institute of Computational Mathematics and IT Kazan Federal University Kazan, Russia Zavoisky Physical-Technical Institute FRC Kazan Scientific Center of RAS Kazan,Russia
4 shared publications - Aliya Khadieva
Kazan Federal University Kazan Russia
2 shared publications - Abuzer Yakaryılmaz
Center for Quantum Computer Science University of Latvia Street LV-1586 Rīga Latvia
1 shared publication - Alexander Rivosh
University of Latvia Riga Latvia
1 shared publication - Alexander Vasiliev
Kazan Federal University
1 shared publication Aliya Khadieva
Institute of Computational Mathematics and Information Technologies, Kazan Federal University, Kazan, Russia
1 shared publication
Latest Publications
- Open Access
Towards Efficient Function Optimisation with Quantum–Classical Hybrid Search
Finding the global minimum of a function with many local extrema is well known to be a challenging computational task. We propose a hybrid quantum–classical algorithm for this optimisation problem, based on a combination of Grover quantum search and the classical Newton–Raphson method. The approach is tailored to situations with a large number of false minima. The main idea is to use quantum search to efficiently locate the vicinity of the true optimum, after which a classical algorithm can solve the problem in only a few iterations. We specifically address the nontrivial question of choosing the discretisation of the function domain, which is critical for quantum approaches to optimisation of continuous functions. While we do not expect that this method will always be superior, we identify a paradigmatic case of a function for which we demonstrate that, remarkably, our hybrid method quadratically outperforms a purely classical approach (measuring performance by the number of function/oracle calls). We evaluate key performance metrics of the algorithm in numerical experiments. We furthermore discuss its possible extensions as well as the potential relevance of hybrid approaches in the context of quantum cognition.
Open AccessTowards Efficient Function Optimisation with Quantum–Classical Hybrid Search
Finding the global minimum of a function with many local extrema is well known to be a challenging computational task. We propose a hybrid quantum–classical algorithm for this optimisation problem, based on a combination of Grover quantum search and the classical Newton–Raphson method. The approach is tailored to situations with a large number of false minima. The main idea is to use quantum search to efficiently locate the vicinity of the true optimum, after which a classical algorithm can solve the problem in only a few iterations. We specifically address the nontrivial question of choosing the discretisation of the function domain, which is critical for quantum approaches to optimisation of continuous functions. While we do not expect that this method will always be superior, we identify a paradigmatic case of a function for which we demonstrate that, remarkably, our hybrid method quadratically outperforms a purely classical approach (measuring performance by the number of function/oracle calls). We evaluate key performance metrics of the algorithm in numerical experiments. We furthermore discuss its possible extensions as well as the potential relevance of hybrid approaches in the context of quantum cognition.
- Open Access
- 16 May 2025
- Published by Frontiers Media SA in Frontiers in Computer Science
- Vol. 7, 1519212
Shallow implementation of quantum fingerprinting with application to quantum finite automata
Quantum fingerprinting is a technique that maps a classical input word to a quantum state. The obtained quantum state is much shorter than the original word, and its processing uses fewer resources, making it useful in quantum algorithms, communication, and cryptography. One of the examples of quantum fingerprinting is the quantum automata algorithm for languages, where p is a prime number. However, implementing such an automaton on current quantum hardware is not efficient. Quantum fingerprinting maps a word x∈{0, 1}n of length n to a state |ψ(x)〉 of O(logn) qubits, and uses O(n) unitary operations. Computing quantum fingerprint using all available qubits of the current quantum computers is infeasible due to many 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. We provide a series of numerical experiments with implementation of the quantum automata for MOD17 language on noisy simulators of IBMQ quantum devices. We show that shallow implementation based on GAPs produces results with much smaller computational error compared to standard deep circuit implementation. Despite the fact that on the ideal quantum computational device, the opposite situation arises. We show that the shallow circuit for the quantum automaton is better for near-future quantum computational devices.- 16 May 2025
- Published by Frontiers Media SA in Frontiers in Computer Science
- Vol. 7, 1519212
Open AccessShallow implementation of quantum fingerprinting with application to quantum finite automata
Quantum fingerprinting is a technique that maps a classical input word to a quantum state. The obtained quantum state is much shorter than the original word, and its processing uses fewer resources, making it useful in quantum algorithms, communication, and cryptography. One of the examples of quantum fingerprinting is the quantum automata algorithm for languages, where p is a prime number. However, implementing such an automaton on current quantum hardware is not efficient. Quantum fingerprinting maps a word x∈{0, 1}n of length n to a state |ψ(x)〉 of O(logn) qubits, and uses O(n) unitary operations. Computing quantum fingerprint using all available qubits of the current quantum computers is infeasible due to many 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. We provide a series of numerical experiments with implementation of the quantum automata for MOD17 language on noisy simulators of IBMQ quantum devices. We show that shallow implementation based on GAPs produces results with much smaller computational error compared to standard deep circuit implementation. Despite the fact that on the ideal quantum computational device, the opposite situation arises. We show that the shallow circuit for the quantum automaton is better for near-future quantum computational devices. - Open Access
- 15 May 2025
- Published by MDPI AG in Quantum Reports
- Vol. 7 (2) , 24
Theory and Applications of Quantum Hashing
We review recent results on quantum one-way functions, including quantum fingerprinting or quantum hashing (we use these two terms as synonyms even though they have very small difference). This includes the analysis of their properties, different modifications, circuit implementation on an IBM Q platform, as well as on an experimental quantum setup. We discuss computational aspects of quantum hashing, its cryptographic properties and possible usage in communication protocols and algorithms.
- 15 May 2025
- Published by MDPI AG in Quantum Reports
- Vol. 7 (2) , 24
Open AccessTheory and Applications of Quantum Hashing
We review recent results on quantum one-way functions, including quantum fingerprinting or quantum hashing (we use these two terms as synonyms even though they have very small difference). This includes the analysis of their properties, different modifications, circuit implementation on an IBM Q platform, as well as on an experimental quantum setup. We discuss computational aspects of quantum hashing, its cryptographic properties and possible usage in communication protocols and algorithms.
- Open Access
- 20 November 2023
- Published by MDPI AG in Mathematics
- Vol. 11 (22) , 4707
Noisy Tree Data Structures and Quantum Applications
We suggest a new technique for developing noisy tree data structures. We call it a “walking tree”. As applications of the technique we present a noisy Self-Balanced Binary Search Tree (we use a Red–Black tree as an implementation) and a noisy segment tree. The asymptotic complexity of the main operations for the tree data structures does not change compared to the case without noise. We apply the data structures in quantum algorithms for several problems on strings like the string-sorting problem and auto-complete problem. For both problems, we obtain quantum speed-up. Moreover, for the string-sorting problem, we show a quantum lower bound.
- 20 November 2023
- Published by MDPI AG in Mathematics
- Vol. 11 (22) , 4707
Open AccessNoisy Tree Data Structures and Quantum Applications
We suggest a new technique for developing noisy tree data structures. We call it a “walking tree”. As applications of the technique we present a noisy Self-Balanced Binary Search Tree (we use a Red–Black tree as an implementation) and a noisy segment tree. The asymptotic complexity of the main operations for the tree data structures does not change compared to the case without noise. We apply the data structures in quantum algorithms for several problems on strings like the string-sorting problem and auto-complete problem. For both problems, we obtain quantum speed-up. Moreover, for the string-sorting problem, we show a quantum lower bound.
- Open Access
- 3 September 2023
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 386, 269-280
GAPs for Shallow Implementation of Quantum Finite Automata
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 algorithms for MOD p = {a i•p | i ≥ 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 ∈ {0, 1} n of length n to a state |ψ(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.
- 3 September 2023
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 386, 269-280
Open AccessGAPs for Shallow Implementation of Quantum Finite Automata
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 algorithms for MOD p = {a i•p | i ≥ 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 ∈ {0, 1} n of length n to a state |ψ(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.
- 1 February 2023
- Published by Pleiades Publishing Ltd in Lobachevskii Journal of Mathematics
- Vol. 44 (2) , 713-723
Deterministic Construction of QFAs Based on the Quantum Fingerprinting Technique
It is known that for some languages quantum finite automata are more efficient than classical counterparts. Particularly, a QFA recognizing the language \(MOD_{p}\) has an exponential advantage over the classical finite automata. However, the construction of such QFA is probabilistic. In the current work, we propose a deterministic construction of the QFA for the language \(MOD_{p}\). We construct a QFA for a promise problem \(Palindrome_{s}\) and implement this QFA on the IBMQ simulator using qiskit library tools.- 1 February 2023
- Published by Pleiades Publishing Ltd in Lobachevskii Journal of Mathematics
- Vol. 44 (2) , 713-723
Deterministic Construction of QFAs Based on the Quantum Fingerprinting Technique
It is known that for some languages quantum finite automata are more efficient than classical counterparts. Particularly, a QFA recognizing the language \(MOD_{p}\) has an exponential advantage over the classical finite automata. However, the construction of such QFA is probabilistic. In the current work, we propose a deterministic construction of the QFA for the language \(MOD_{p}\). We construct a QFA for a promise problem \(Palindrome_{s}\) and implement this QFA on the IBMQ simulator using qiskit library tools.- 1 February 2023
- Published by Pleiades Publishing Ltd in Lobachevskii Journal of Mathematics
- Vol. 44 (2) , 669-679
Identification of Quantum Hashes: Numerical Experiment
The problem of reliable identification of quantum hash states, which are images of quantum hash functions, is considered. It is shown that this can be done with a high probability for a linear number of \(O(n/(1-\epsilon^{2}))\) experiments when hashing words of length \(n\) with \(\epsilon\)-resistance to collisions. The results of a numerical experiment on the implementation of the procedure are presented, demonstrating the result of the above. We provide such an experiment to simulate quantum hashing for binary words of length 5.- 1 February 2023
- Published by Pleiades Publishing Ltd in Lobachevskii Journal of Mathematics
- Vol. 44 (2) , 669-679
Identification of Quantum Hashes: Numerical Experiment
The problem of reliable identification of quantum hash states, which are images of quantum hash functions, is considered. It is shown that this can be done with a high probability for a linear number of \(O(n/(1-\epsilon^{2}))\) experiments when hashing words of length \(n\) with \(\epsilon\)-resistance to collisions. The results of a numerical experiment on the implementation of the procedure are presented, demonstrating the result of the above. We provide such an experiment to simulate quantum hashing for binary words of length 5.- 1 January 2022
- Published by Keldysh Institute of Applied Mathematics
- p. 71-74
Lower bound of quantum request complexity of radix sort
In the classical case, sorting N elements requires O(N log N) pairwise comparisons. So many comparisons required and in the quantum case. But for radix sort use quantum computing allows you to gain an advantage over classical: instead of O(NL) operations to sort N elements from L symbols in the quantum case requires O(N sqrt{L / log N}) operations, which coincides with the well-known upper bound with up to logarithmic factors.
- 1 January 2022
- Published by Keldysh Institute of Applied Mathematics
- p. 71-74
Lower bound of quantum request complexity of radix sort
In the classical case, sorting N elements requires O(N log N) pairwise comparisons. So many comparisons required and in the quantum case. But for radix sort use quantum computing allows you to gain an advantage over classical: instead of O(NL) operations to sort N elements from L symbols in the quantum case requires O(N sqrt{L / log N}) operations, which coincides with the well-known upper bound with up to logarithmic factors.
- Open Access
Quantum versus Classical Online Streaming Algorithms with Advice
We consider online algorithms with respect to the competitive ratio. Here, we investigate quantum and classical one-way automata with non-constant size of memory (streaming algorithms) as a model for online algorithms. We construct problems that can be solved by quantum online streaming algorithms better than by classical ones in a case of logarithmic or sublogarithmic size of memory, even if classical online algorithms get advice bits. Furthermore, we show that a quantum online algorithm with a constant number of qubits can be better than any deterministic online algorithm with a constant number of advice bits and unlimited computational power.
Open AccessQuantum versus Classical Online Streaming Algorithms with Advice
We consider online algorithms with respect to the competitive ratio. Here, we investigate quantum and classical one-way automata with non-constant size of memory (streaming algorithms) as a model for online algorithms. We construct problems that can be solved by quantum online streaming algorithms better than by classical ones in a case of logarithmic or sublogarithmic size of memory, even if classical online algorithms get advice bits. Furthermore, we show that a quantum online algorithm with a constant number of qubits can be better than any deterministic online algorithm with a constant number of advice bits and unlimited computational power.
- 20 September 2018
- Published by Pleiades Publishing Ltd in Lobachevskii Journal of Mathematics
- Vol. 39 (7) , 1039-1045
Attacking Quantum Hashing. Protocols and Their Cryptanalysis
Quantumhash functions are similar to classical (cryptographic) hash functions and their security is guaranteed by physical laws. However, security of a primitive does not automatically mean that...
- 20 September 2018
- Published by Pleiades Publishing Ltd in Lobachevskii Journal of Mathematics
- Vol. 39 (7) , 1039-1045
Attacking Quantum Hashing. Protocols and Their Cryptanalysis
Quantumhash functions are similar to classical (cryptographic) hash functions and their security is guaranteed by physical laws. However, security of a primitive does not automatically mean that...