Deterministic Construction of QFAs Based on the Quantum Fingerprinting Technique

A. Khadieva; M. Ziatdinov

doi:10.1134/S199508022302021X

Deterministic Construction of QFAs Based on the Quantum Fingerprinting Technique

A. Khadieva
, M. Ziatdinov

Eksakto zinātņu un tehnoloģiju fakultāte

Kazan Volga Region Federal University

Zinātniskās darbības rezultāts: Devums žurnālam › Zinātniskais raksts (žurnālā) › koleģiāli recenzēts

5 Atsauces (Scopus)

Kopsavilkums

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

Oriģinālvaloda	Angļu
Lapas (no-līdz)	713-723
Žurnāls	Lobachevskii Journal of Mathematics
Sējums	44
Izdevuma numurs	2
DOIs	https://doi.org/10.1134/S199508022302021X
Publikācijas statuss	Publicēts - febr. 2023

OECD Zinātnes nozare

1.2 Datorzinātne un informātika

Piekļuve Dokumentiem

10.1134/S199508022302021X

Citi faili un saites

Citēt šo

@article{c79e519f27c04898a35c9cd7e09b2ed9,

title = "Deterministic Construction of QFAs Based on the Quantum Fingerprinting Technique",

abstract = "Abstract: It is known that for some languages quantum finite automata are more efficient than classical counterparts. Particularly, a QFA recognizing the language MODp 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 MODp. We construct a QFA for a promise problem Palindromes and implement this QFA on the IBMQ simulator using qiskit library tools.",

keywords = "automata, palindrome, qiskit, quantum automata, quantum computing, quantum fingerprinting",

author = "A. Khadieva and M. Ziatdinov",

note = "Publisher Copyright: {\textcopyright} 2023, Pleiades Publishing, Ltd.",

year = "2023",

month = feb,

doi = "10.1134/S199508022302021X",

language = "English",

volume = "44",

pages = "713--723",

journal = "Lobachevskii Journal of Mathematics",

issn = "1995-0802",

publisher = "Pleiades Publishing",

number = "2",

}

TY - JOUR

T1 - Deterministic Construction of QFAs Based on the Quantum Fingerprinting Technique

AU - Khadieva, A.

AU - Ziatdinov, M.

PY - 2023/2

Y1 - 2023/2

N2 - Abstract: It is known that for some languages quantum finite automata are more efficient than classical counterparts. Particularly, a QFA recognizing the language MODp 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 MODp. We construct a QFA for a promise problem Palindromes and implement this QFA on the IBMQ simulator using qiskit library tools.

AB - Abstract: It is known that for some languages quantum finite automata are more efficient than classical counterparts. Particularly, a QFA recognizing the language MODp 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 MODp. We construct a QFA for a promise problem Palindromes and implement this QFA on the IBMQ simulator using qiskit library tools.

KW - automata

KW - palindrome

KW - qiskit

KW - quantum automata

KW - quantum computing

KW - quantum fingerprinting

UR - https://link.springer.com/article/10.1134/S199508022302021X

UR - https://www.scopus.com/pages/publications/85160927376

U2 - 10.1134/S199508022302021X

DO - 10.1134/S199508022302021X

M3 - Article

SN - 1995-0802

VL - 44

SP - 713

EP - 723

JO - Lobachevskii Journal of Mathematics

JF - Lobachevskii Journal of Mathematics

IS - 2

ER -

Deterministic Construction of QFAs Based on the Quantum Fingerprinting Technique

Kopsavilkums

OECD Zinātnes nozare

Piekļuve Dokumentiem

Citi faili un saites

Nospiedums

Citēt šo