Some languages recognized by two-way finite automata with quantum and classical states

DOI10.1142/S0129054112500141zbMATH Open1259.68117DBLPjournals/ijfcs/ZhengQL12arXiv1112.2844OpenAlexW2118222027WikidataQ62049413 ScholiaQ62049413MaRDI QIDQ4902896FDOQ4902896

Authors: Shenggen Zheng, Lvzhou Li, Daowen Qiu 

Publication date: 18 January 2013

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Abstract: {it Two-way finite automata with quantum and classical states} (2QCFA) were introduced by Ambainis and Watrous, and it was shown that 2QCFA have superiority over {it two-way probabilistic finite automata} (2PFA) for recognizing some non-regular languages such as the language $L_{eq}=a^n{b}^{n}midninmathbfN$ and the palindrome language $L_{pal}=omegain{a,b}^{\ast }midomega=omeg{a}^R$, where $x^R$ is $x$ in the reverse order. It is interesting to find more languages like these that witness the superiority of 2QCFA over 2PFA. In this paper, we consider the language $L_m=xcymidSigma=a,b,c,x,yin{a,b}^{\ast },cinSigma,|x|=|y|$ that is similar to the middle language $L_{middle}=xaymidx,yinSigm{a}^{\ast },ainSigma,|x|=|y|$. We prove that the language $L_m$ can be recognized by 2QCFA with one-sided error in polynomial expected time. Also, we show that $L_m$ can be recognized by 2PFA with bounded error, but only in exponential expected time. Thus $L_m$ is another witness of the fact that 2QCFA are more powerful than their classical counterparts.

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

Recommendations

• Two-way finite automata with quantum and classical states.
• State succinctness of two-way finite automata with quantum and classical states
• Two-tape finite automata with quantum and classical states
• Succinctness of two-way probabilistic and quantum finite automata
• scientific article; zbMATH DE number 1512863

zbMATH Keywords

quantum finite automatacomputing modelsprobabilistic finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Quantum algorithms and complexity in the theory of computing (68Q12)

Cites Work

• Two-way finite automata with quantum and classical states.
• Title not available (Why is that?)
• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• Title not available (Why is that?)
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Unbounded-error quantum computation with small space bounds
• Title not available (Why is that?)
• Quantum automata and quantum grammars
• Hierarchy and equivalence of multi-letter quantum finite automata
• Algebraic results on quantum automata
• Determining the equivalence for one-way quantum finite automata
• Characterizations of 1-Way Quantum Finite Automata
• Finite state verifiers I
• A note on quantum sequential machines
• A lower bound for probabilistic algorithms for finite state machines
• Two-tape finite automata with quantum and classical states
• Efficient probability amplification in two-way quantum finite automata

Cited In (9)

• State succinctness of two-way finite automata with quantum and classical states
• Two-tape finite automata with quantum and classical states
• From quantum query complexity to state complexity
• Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
• Two-way finite automata with quantum and classical states.
• Potential of quantum finite automata with exact acceptance
• Title not available (Why is that?)
• On the power of two-way multihead quantum finite automata
• Application of distributed semi-quantum computing model in phase estimation

This page was built for publication: Some languages recognized by two-way finite automata with quantum and classical states

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