It is has been shown that Quantum Finite Automata can recognize at least some non-regular languages. What is the relationship between the number of states in a qfa and the number of non-regular languages it can recognize? Is there a relationship at all or has it not yet been established?

I have been unable to find a paper that addresses this in an overtly and understandable way. More specifically, for any one specific type (ex/ 1-way MM-QFA), has any such relationship been established for the class it recognizes? I know different types of QFAs have different closure properties and other characteristics that can make them vastly different and bounds have been established for some, but I'm wondering if anyone knows of, has seen, or knows who to contact regarding the relationship between teh number of states in a qfa and its recognition properties? Or, if this question is totally mute and I'm looking at it wrong, tell me why. I have read into some of Freivalds' research where he touches on this, but can't find any theorems, proofs, lemmas, ect. that hammer it out, if anyone has done so at all. There is a possibility that this question is open and that's why I havent found an answer. Any help you can give would be appreciated.

  • $\begingroup$ Are you trying to ask, after fixing a QFA model and an error-type (exact - (two-sided or one-sided) bounded-error or unbounded-error), whether there is a language recognized by (n+k)-state QFA but not by n-state QFA, where n,k>0? $\endgroup$ – Abuzer Yakaryilmaz Apr 16 '13 at 7:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.