Determining the equivalence for one-way quantum finite automata

DOI10.1016/J.TCS.2008.03.021MaRDI QIDQ2518375zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Lvzhou Li, Daowen Qiu

Publication date 15 January 2009

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0703087

zbMATH Keywords

quantum computing regular languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Quantum computation (81P68)

Abstract: In this paper, we focus on determining the equivalence for {it 1-way quantum finite automata with control language} (CL-1QFAs) defined by Bertoni et al and {it measure-many 1-way quantum finite automata} (MM-1QFAs) introduced by Kondacs and Watrous. More specifically, we obtain that: �egin{enumerate} item[(i)] Two CL-1QFAs

{c a l A}_{1}

and

{c a l A}_{2}

with control languages (regular languages)

{c a l L}_{1}

and

{c a l L}_{2}

, respectively, are equivalent if and only if they are

(c_{1} n_{1}^{2} + c_{2} n_{2}^{2} - 1)

-equivalent. Furthermore, if

{c a l L}_{1}

and

{c a l L}_{2}

are given in the form of DFAs, with

m_{1}

and

m_{2}

states, respectively, then there exists a polynomial-time algorithm running in time

O ((m_{1} n_{1}^{2} + m_{2} n_{2}^{2})^{4})

that takes as input

{c a l A}_{1}

and

{c a l A}_{2}

and determines whether they are equivalent. item[(ii)] Two MM-1QFAs

{c a l A}_{1}

and

{c a l A}_{2}

with

n_{1}

and

n_{2}

states, respectively, are equivalent if and only if they are

(3 n_{1}^{2} + 3 n_{2}^{2} - 1)

-equivalent. Furthermore, there is a polynomial-time algorithm running in time

O ((3 n_{1}^{2} + 3 n_{2}^{2})^{4})

that takes as input

{c a l A}_{1}

and

{c a l A}_{2}

and determines whether

{c a l A}_{1}

and

{c a l A}_{2}

are equivalent.

Recommendations

Cites work

Cited in

(25)

This page was built for publication: Determining the equivalence for one-way quantum finite automata

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