GRUSKA, Jozef, Daowen QIU and Shenggen ZHENG. Potential of Quantum Finite Automata with Exact Acceptance. International Journal of Foundations of Computer Science. 2015, vol. 26, No 3, p. 381-398. ISSN 0129-0541. Available from: https://dx.doi.org/10.1142/S0129054115500215.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Potential of Quantum Finite Automata with Exact Acceptance
Authors GRUSKA, Jozef (703 Slovakia, guarantor, belonging to the institution), Daowen QIU (156 China) and Shenggen ZHENG (156 China, belonging to the institution).
Edition International Journal of Foundations of Computer Science, 2015, 0129-0541.
Other information
Original language English
Type of outcome Article in a journal
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Singapore
Confidentiality degree is not subject to a state or trade secret
WWW URL
Impact factor Impact factor: 0.467
RIV identification code RIV/00216224:14330/15:00084457
Organization unit Faculty of Informatics
Doi http://dx.doi.org/10.1142/S0129054115500215
UT WoS 000370870100005
Keywords in English Exact quantum computing; quantum finite automata; promise problems; state succinctness Read More: http://www.worldscientific.com/doi/abs/10.1142/S0129054115500215
Tags International impact, Reviewed
Changed by Changed by: prof. RNDr. Jozef Gruska, DrSc., učo 3026. Changed: 28/11/2017 10:32.
Abstract
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
Links
EE2.3.30.0009, research and development projectName: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci
PrintDisplayed: 22/5/2024 01:55