Geodesic
Universal hash functions from quantum procedures
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 162 (2020) no. 3, pp. 259-268 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

Modern quantum technologies are NISQ (Noisy Intermediate-Scale Quantum) devices, which are used to create insufficiently accurate quantum computers with low computing power. However, quantum technologies have advanced considerably during the past years. Thus, the issue of demonstrating “quantum supremacy” in the era of NISQ technologies is on the agenda. This study demonstrates that “quantum supremacy” is forthcoming. We propose procedures for constructing a universal family of hash functions based on a quantum hashing process that maps the original sequence $w$ to a quantum hash state and then by random transformation to the state $\mid{\psi}$ and generating the sequence $u$, which is an approximate description of the state $\mid{\psi}$. We proved that the proposed procedure generates a family of nondeterministic hash functions $\mathcal{F}$, which allow us to reliably distinguish between different arguments. The $\mathcal{F}$ family can be considered an $\epsilon$-universal family of nondeterministic hash functions. We assume that the development of this research area will cast light on the effect of “quantum supremacy” and will also have a certain impact on the advance of post-quantum cryptography.
Keywords: quantum hash functions, universal hash family, quantum supremacy. 
@article{UZKU_2020_162_3_a1,
     author = {F. M. Ablayev and M. T. Ziatdinov},
     title = {Universal hash functions from quantum procedures},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {259--268},
     year = {2020},
     volume = {162},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a1/}
}
TY  - JOUR
AU  - F. M. Ablayev
AU  - M. T. Ziatdinov
TI  - Universal hash functions from quantum procedures
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2020
SP  - 259
EP  - 268
VL  - 162
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a1/
LA  - ru
ID  - UZKU_2020_162_3_a1
ER  - 
%0 Journal Article
%A F. M. Ablayev
%A M. T. Ziatdinov
%T Universal hash functions from quantum procedures
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2020
%P 259-268
%V 162
%N 3
%U http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a1/
%G ru
%F UZKU_2020_162_3_a1
F. M. Ablayev; M. T. Ziatdinov. Universal hash functions from quantum procedures. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 162 (2020) no. 3, pp. 259-268. http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a1/

[1] Feynman R. P., “Quantum mechanical computers”, Opt. News, 11:2 (1985), 11–20 | DOI | MR

[2] Manin Yu.I., Computable and Noncomputable, Sov. Radio, M., 1980, 128 pp. (In Russian)

[3] Shor P. W., “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM Rev., 41:2 (1999), 303–332 | DOI | MR | Zbl

[4] Preskill J., “Quantum computing in the NISQ era and beyond”, Quantum, 2 (2018), 79 | DOI

[5] Harrow A. W., Montanaro A., “Quantum computational supremacy”, Nature, 549:7671 (2017), 203–209 | DOI

[6] Carter J.L, Wegman M. N., “Universal classes of hash functions”, J. Comput. Syst. Sci., 18:2 (1979), 143–154 | DOI | MR | Zbl

[7] Thorup M., High speed hashing for integers and strings, 2015, arXiv: 1504.06804

[8] Stinson D. R., Paterson M., Cryptography: Theory and Practice, Chapman and Hall/CRC, 2018, 598 pp. | MR

[9] Luby M., Wigderson A., “Pairwise independence and derandomization”, Found. Trends Theor. Comput. Sci., 1:4 (2005), 237–301 | DOI | MR

[10] Ablayev F., Ablayev M., Vasiliev A., Ziatdinov M., “Quantum fingerprinting and quantum hashing. Computational and cryptographical aspects”, Balt. J. Mod. Comput., 4:4 (2016), 860–875 | DOI | MR

[11] Diestel J., Spalsbury A., The Joys of Haar Measure, Am. Math. Soc., Providence, RI, 2014, xiv+320 pp. | MR | Zbl

[12] Ablayev F. M., Vasiliev A. V., Quantum Hashing for Quantum Communications, LAMBERT Acad. Publ., Saarbrucken, 2015, 84 pp. (In Russian)

[13] Radhakrishnan J., Rötteler M., Sen P., “Random measurement bases, quantum state distinction and applications to the hidden subgroup problem”, Algorithmica, 55:3 (2009), 490–516 | DOI | MR | Zbl

[14] Mohseni M., Read P., Neven H., Boixo S., Denchev V., Babbush R., Fowler A., Smelyanskiy V., Martinis J., “Commercialize quantum technologies in five years”, Nature, 543:7644 (2017), 171–174 | DOI

[15] Gambetta J. M., Chow J. M., Steffen M., “Building logical qubits in a superconducting quantum computing system”, npj Quantum Inf., 3 (2017), 2, 1–7 | DOI

[16] Svore K., Geller A., Troyer M., Azariah J., Granade C., Heim B., Kliuchnikov V., Mykhailova M., Paz A., Roetteler M., “Q#: Enabling scalable quantum computing and development with a high-level DSL”, RWDSL: Proc. Real World Domain Specific Languages Workshop 2018 (Vienna, 2018), 2018, 7, 1–10 | DOI

[17] Gottesman D., Chuang I. L., Quantum digital signatures, 2001, arXiv: quant-ph/0105032

[18] Gavinsky D., Ito T., Electronic Colloquium on Computational Complexity, Report No 165, 2010 https://eccc.weizmann.ac.il/report/2010/165/ | Zbl