ترغب بنشر مسار تعليمي؟ اضغط هنا

On equivalence, languages equivalence and minimization of multi-letter and multi-letter measure-many quantum automata

146   0   0.0 ( 0 )
 نشر من قبل Tianrong Lin
 تاريخ النشر 2012
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English
 تأليف Tianrong Lin




اسأل ChatGPT حول البحث

We first show that given a $k_1$-letter quantum finite automata $mathcal{A}_1$ and a $k_2$-letter quantum finite automata $mathcal{A}_2$ over the same input alphabet $Sigma$, they are equivalent if and only if they are $(n_1^2+n_2^2-1)|Sigma|^{k-1}+k$-equivalent where $n_1$, $i=1,2$, are the numbers of state in $mathcal{A}_i$ respectively, and $k=max{k_1,k_2}$. By applying a method, due to the author, used to deal with the equivalence problem of {it measure many one-way quantum finite automata}, we also show that a $k_1$-letter measure many quantum finite automaton $mathcal{A}_1$ and a $k_2$-letter measure many quantum finite automaton $mathcal{A}_2$ are equivalent if and only if they are $(n_1^2+n_2^2-1)|Sigma|^{k-1}+k$-equivalent where $n_i$, $i=1,2$, are the numbers of state in $mathcal{A}_i$ respectively, and $k=max{k_1,k_2}$. Next, we study the language equivalence problem of those two kinds of quantum finite automata. We show that for $k$-letter quantum finite automata, the non-strict cut-point language equivalence problem is undecidable, i.e., it is undecidable whether $L_{geqlambda}(mathcal{A}_1)=L_{geqlambda}(mathcal{A}_2)$ where $0<lambdaleq 1$ and $mathcal{A}_i$ are $k_i$-letter quantum finite automata. Further, we show that both strict and non-strict cut-point language equivalence problem for $k$-letter measure many quantum finite automata are undecidable. The direct consequences of the above outcomes are summarized in the paper. Finally, we comment on existing proofs about the minimization problem of one way quantum finite automata not only because we have been showing great interest in this kind of problem, which is very important in classical automata theory, but also due to that the problem itself, personally, is a challenge. This problem actually remains open.



قيم البحث

اقرأ أيضاً

We consider the problem of studying the simulation capabilities of the dynamics of arbitrary networks of finite states machines. In these models, each node of the network takes two states 0 (passive) and 1 (active). The states of the nodes are update d in parallel following a local totalistic rule, i.e., depending only on the sum of active states. Four families of totalistic rules are considered: linear or matrix defined rules (a node takes state 1 if each of its neighbours is in state 1), threshold rules (a node takes state 1 if the sum of its neighbours exceed a threshold), isolated rules (a node takes state 1 if the sum of its neighbours equals to some single number) and interval rule (a node takes state 1 if the sum of its neighbours belong to some discrete interval). We focus in studying the simulation capabilities of the dynamics of each of the latter classes. In particular, we show that totalistic automata networks governed by matrix defined rules can only implement constant functions and other matrix defined functions. In addition, we show that t by threshold rules can generate any monotone Boolean functions. Finally, we show that networks driven by isolated and the interval rules exhibit a very rich spectrum of boolean functions as they can, in fact, implement any arbitrary Boolean functions. We complement this results by studying experimentally the set of different Boolean functions generated by totalistic rules on random graphs.
The Code Equivalence problem is that of determining whether two given linear codes are equivalent to each other up to a permutation of the coordinates. This problem has a direct reduction to a nonabelian hidden subgroup problem (HSP), suggesting a po ssible quantum algorithm analogous to Shors algorithms for factoring or discrete log. However, we recently showed that in many cases of interest---including Goppa codes---solving this case of the HSP requires rich, entangled measurements. Thus, solving these cases of Code Equivalence via Fourier sampling appears to be out of reach of current families of quantum algorithms. Code equivalence is directly related to the security of McEliece-type cryptosystems in the case where the private code is known to the adversary. However, for many codes the support splitting algorithm of Sendrier provides a classical attack in this case. We revisit the claims of our previous article in the light of these classical attacks, and discuss the particular case of the Sidelnikov cryptosystem, which is based on Reed-Muller codes.
112 - Hans Raj Tiwary 2016
In this article we undertake a study of extension complexity from the perspective of formal languages. We define a natural way to associate a family of polytopes with binary languages. This allows us to define the notion of extension complexity of fo rmal languages. We prove several closure properties of languages admitting compact extended formulations. Furthermore, we give a sufficient machine characterization of compact languages. We demonstrate the utility of this machine characterization by obtaining upper bounds for polytopes for problems in nondeterministic logspace; lower bounds in streaming models; and upper bounds on extension complexities of several polytopes.
Equality and disjointness are two of the most studied problems in communication complexity. They have been studied for both classical and also quantum communication and for various models and modes of communication. Buhrman et al. [Buh98] proved that the exact quantum communication complexity for a promise version of the equality problem is ${bf O}(log {n})$ while the classical deterministic communication complexity is $n+1$ for two-way communication, which was the first impressively large (exponential) gap between quantum and classical (deterministic and probabilistic) communication complexity. If an error is tolerated, both quantum and probabilistic communication complexities for equality are ${bf O}(log {n})$. However, even if an error is tolerated, the gaps between quantum (probabilistic) and deterministic complexity are not larger than quadratic for the disjointness problem. It is therefore interesting to ask whether there are some promis
The Probe Of Extreme Multi-Messenger Astrophysics (POEMMA) is designed to identify the sources of Ultra-High-Energy Cosmic Rays (UHECRs) and to observe cosmic neutrinos, both with full-sky coverage. Developed as a NASA Astrophysics Probe-class missio n, POEMMA consists of two spacecraft flying in a loose formation at 525 km altitude, 28.5 deg inclination orbits. Each spacecraft hosts a Schmidt telescope with a large collecting area and wide field of view. A novel focal plane is optimized to observe both the UV fluorescence signal from extensive air showers (EASs) and the beamed optical Cherenkov signals from EASs. In POEMMA-stereo fluorescence mode, POEMMA will measure the spectrum, composition, and full-sky distribution of the UHECRs above 20 EeV with high statistics along with remarkable sensitivity to UHE neutrinos. The spacecraft are designed to quickly re-orient to a POEMMA-limb mode to observe neutrino emission from Target-of-Opportunity (ToO) transient astrophysical sources viewed just below the Earths limb. In this mode, POEMMA will have unique sensitivity to cosmic neutrino tau events above 20 PeV by measuring the upward-moving EASs induced by the decay of the emerging tau leptons following the interactions of neutrino tau inside the Earth.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا