Deterministic construction of QFAs based on the quantum fingerprinting technique

DOI10.1134/S199508022302021XarXiv2212.14442OpenAlexW4377234973MaRDI QIDQ6043928FDOQ6043928

Authors: Aliya Khadieva, Mansur Ziatdinov 

Publication date: 25 May 2023

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

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.

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)

Cites Work

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

Cited In (2)

• GAPs for Shallow Implementation of Quantum Finite Automata
• Title not available (Why is that?)

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)