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

Faculty of Science and Technology

Kazan Volga Region Federal University

Research output: Contribution to journal › Article › peer-review

5 Citations (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	713-723
Journal	Lobachevskii Journal of Mathematics
Volume	44
Issue number	2
DOIs	https://doi.org/10.1134/S199508022302021X
Publication status	Published - Feb 2023

Keywords

automata
palindrome
qiskit
quantum automata
quantum computing
quantum fingerprinting

OECD Field of Science

1.2 Computer and Information Sciences

Access to Document

10.1134/S199508022302021X

Cite this

@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

Abstract

Keywords

OECD Field of Science

Access to Document

Other files and links

Fingerprint

Cite this