Potential of Quantum Finite Automata with Exact Acceptance

J 2015

Potential of Quantum Finite Automata with Exact Acceptance

GRUSKA, Jozef, Daowen QIU a Shenggen ZHENG

Základní údaje

Originální název

Potential of Quantum Finite Automata with Exact Acceptance

Autoři

GRUSKA, Jozef (703 Slovensko, garant, domácí), Daowen QIU (156 Čína) a Shenggen ZHENG (156 Čína, domácí)

Vydání

International Journal of Foundations of Computer Science, 2015, 0129-0541

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Singapur

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 0.467

Kód RIV

RIV/00216224:14330/15:00084457

Organizační jednotka

Fakulta informatiky

DOI

http://dx.doi.org/10.1142/S0129054115500215

UT WoS

000370870100005

Klíčová slova anglicky

Exact quantum computing; quantum finite automata; promise problems; state succinctness Read More: http://www.worldscientific.com/doi/abs/10.1142/S0129054115500215

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 28. 11. 2017 10:32, prof. RNDr. Jozef Gruska, DrSc.

Anotace

V originále

The potential of the exact quantum information processing is an interesting, important and intriguing issue. For examples, it has been believed that quantum tools can provide significant, that is larger than polynomial, advantages in the case of exact quantum computation only, or mainly, for problems with very special structures. We will show that this is not the case. In this paper the potential of quantum finite automata producing outcomes not only with a (high) probability, but with certainty (so called exactly) is explored in the context of their uses for solving promise problems and with respect to the size of automata. It is shown that for solving particular classes {An}n in N of promise problems, even those without some very special structure, that succinctness of the exact quantum finite automata under consideration, with respect to the number of (basis) states, can be very small (and constant) though it grows proportional to n in the case deterministic finite automata (DFAs) of the same power are used. This is here demonstrated also for the case that the component languages of the promise problems solvable by DFAs are non-regular. The method used can be applied in finding more exact quantum finite automata or quantum algorithms for other promise problems. Read More: http://www.worldscientific.com/doi/abs/10.1142/S0129054115500215

Návaznosti

EE2.3.30.0009, projekt VaV

Název: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci

Citovat

GRUSKA, Jozef, Daowen QIU a Shenggen ZHENG. Potential of Quantum Finite Automata with Exact Acceptance. International Journal of Foundations of Computer Science. 2015, roč. 26, č. 3, s. 381-398. ISSN 0129-0541. Dostupné z: https://dx.doi.org/10.1142/S0129054115500215.

@article{1315560,
   author = {Gruska, Jozef and QIU, Daowen and Zheng, Shenggen},
   article_number = {3},
   doi = {http://dx.doi.org/10.1142/S0129054115500215},
   keywords = {Exact quantum computing; quantum finite automata; promise problems; state succinctness Read More: http://www.worldscientific.com/doi/abs/10.1142/S0129054115500215},
   language = {eng},
   issn = {0129-0541},
   journal = {International Journal of Foundations of Computer Science},
   title = {Potential of Quantum Finite Automata with Exact Acceptance},
   url = {http://www.worldscientific.com/doi/abs/10.1142/S0129054115500215},
   volume = {26},
   year = {2015}
}

TY  - JOUR
ID  - 1315560
AU  - Gruska, Jozef - QIU, Daowen - Zheng, Shenggen
PY  - 2015
TI  - Potential of Quantum Finite Automata with Exact Acceptance
JF  - International Journal of Foundations of Computer Science
VL  - 26
IS  - 3
SP  - 381-398
EP  - 381-398
SN  - 01290541
KW  - Exact quantum computing
KW  - quantum finite automata
KW  - promise problems
KW  - state succinctness Read More: http://www.worldscientific.com/doi/abs/10.1142/S0129054115500215
UR  - http://www.worldscientific.com/doi/abs/10.1142/S0129054115500215
L2  - http://www.worldscientific.com/doi/abs/10.1142/S0129054115500215
N2  - The potential of the exact quantum information processing is an interesting, important and intriguing issue. For examples, it has been believed that quantum tools can provide significant, that is larger than polynomial, advantages in the case of exact quantum computation only, or mainly, for problems with very special structures. We will show that this is not the case. In this paper the potential of quantum finite automata producing outcomes not only with a (high) probability, but with certainty (so called exactly) is explored in the context of their uses for solving promise problems and with respect to the size of automata. It is shown that for solving particular classes {An}n in N of promise problems, even those without some very special structure, that succinctness of the exact quantum finite automata under consideration, with respect to the number of (basis) states, can be very small (and constant) though it grows proportional to n in the case deterministic finite automata (DFAs) of the same power are used. This is here demonstrated also for the case that the component languages of the promise problems solvable by DFAs are non-regular. The method used can be applied in finding more exact quantum finite automata or quantum algorithms for other promise problems. Read More: http://www.worldscientific.com/doi/abs/10.1142/S0129054115500215
ER  -

GRUSKA, Jozef, Daowen QIU a Shenggen ZHENG. Potential of Quantum Finite Automata with Exact Acceptance. \textit{International Journal of Foundations of Computer Science}. 2015, roč.~26, č.~3, s.~381-398. ISSN~0129-0541. Dostupné z: https://dx.doi.org/10.1142/S0129054115500215.

Podrobný výpis o publikaci