Deterministic construction of QFAs based on the quantum fingerprinting technique

DOI10.1134/S199508022302021XMaRDI QIDQ6043928zbMATH OpenOpenAlexFDO

Authors Aliya Khadieva, Mansur Ziatdinov

Publication date 25 May 2023

Published in Lobachevskii Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2212.14442

zbMATH Keywords

quantum automataautomataquantum computingpalindromequantum fingerprintingqiskit

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Foundations, quantum information and its processing, quantum axioms, and philosophy (81Pxx)

Abstract: It is known that for some languages quantum finite automata are more efficient than classical counterparts. Particularly, a QFA recognizing the language $MO{D}_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 $MO{D}_p$. We construct a QFA for a promise problem $Palindrom{e}_s$ and implement this QFA on the IBMQ simulator using qiskit library tools.

Cites work

• scientific article; zbMATH DE number 1688355 (Why is no real title available?)
• scientific article; zbMATH DE number 1839432 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 1405684 (Why is no real title available?)
• Algebraic results on quantum automata
• Automata and quantum computing
• Branching Programs and Binary Decision Diagrams
• Classical and Quantum Computations with Restricted Memory
• Construction of a Thin Set with small Fourier Coefficients
• Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications
• Developments in Language Theory
• Error-Free Affine, Unitary, and Probabilistic OBDDs
• Error-free affine, unitary, and probabilistic OBDDs
• Exact results for accepting probabilities of quantum automata.
• Exponential separation of quantum and classical online space complexity
• Improved Constructions of Quantum Automata
• Improved constructions of quantum automata
• Languages recognized by nondeterministic quantum finite automata
• Lower bounds and hierarchies for quantum memoryless communication protocols and quantum ordered binary decision diagrams with repeated test
• On quantum realisation of Boolean functions by the fingerprinting technique
• On the computational power of probabilistic and quantum branching program
• Quantum algorithms for string processing
• Quantum automata and quantum grammars
• Quantum online streaming algorithms with logarithmic memory
• Reordering method and hierarchies for quantum and classical ordered binary decision diagrams
• State succinctness of two-way finite automata with quantum and classical states
• Superiority of exact quantum automata for promise problems
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs

Cited in

(2)

• GAPs for Shallow Implementation of Quantum Finite Automata
• scientific article; zbMATH DE number 5320265 (Why is no real title available?)

This page was built for publication: Deterministic construction of QFAs based on the quantum fingerprinting technique

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6043928)