Abstract
We introduce a quantum-like classical computational concept, called affine computation, as a generalization of probabilistic computation. After giving the basics of affine computation, we define affine finite automata (AfA) and compare it with quantum and probabilistic finite automata (QFA and PFA, respectively) with respect to three basic language recognition modes. We show that, in the cases of bounded and unbounded error, AfAs are more powerful than QFAs and PFAs, and, in the case of nondeterministic computation, AfAs are more powerful than PFAs but equivalent to QFAs.
The arXiv number is 1602.04732 [4].
Díaz-Caro was partially supported by STIC-AmSud project 16STIC04 FoQCoSS.
Yakaryılmaz was partially supported by CAPES with grant 88881.030338/2013-01 and some parts of the work were done while Yakaryılmaz was visiting Buenos Aires in July 2015 to give a lecture at ECI2015 (Escuela de Ciencias Informáticas 2015, Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires), partially supported by CELFI, Ministerio de Ciencia, Tecnología e Innovación Productiva.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
A superoperator can also be obtained by applying a series of unitary and measurements operators where the next unitary operator is selected with respect to the last measurement outcome.
- 2.
A counter is blind if its status (whether its value is zero or not) cannot be accessible during the computation. A multi-blind-counter finite automaton is an automaton having \(k>0\) blind counter(s) such that in each transition it can update the value(s) of its counter(s) but never access the status of any counter. Moreover, an input can be accepted by such automaton only if the value of every counter is zero at the end of the computation.
References
Aaronson, S.: Quantum computing, postselection, and probabilistic polynomial-time. Proc. Roy. Soc. A 461(2063), 3473–3482 (2005)
Ambainis, A., Yakaryılmaz, A.: Automata and quantum computing. Technical report arXiv:1507.01988 (2015)
Belovs, A., Montoya, J.A., Yakaryılmaz, A.: Can one quantum bit separate any pair of words with zero-error? Technical report arXiv:1602.07967 (2016)
Díaz-Caro, A., Yakaryılmaz, A.: Affine computation and affine automaton. Technical report arXiv:1602.04732 (2016)
Greibach, S.A.: Remarks on blind and partially blind one-way multicounter machines. Theor. Comput. Sci. 7, 311–324 (1978)
Lapins, J.: On nonstochastic languages obtained as the union and intersection of stochastic languages. Avtom. Vychisl. Tekh. 4, 6–13 (1974). Russian
Li, L., Qiu, D., Zou, X., Li, L., Wu, L., Mateus, P.: Characterizations of one-way general quantum finite automata. Theoret. Comput. Sci. 419, 73–91 (2012)
Moore, C., Crutchfield, J.P.: Quantum automata and quantum grammars. Theoret. Comput. Sci. 237(1–2), 275–306 (2000)
Paz, A.: Introduction to Probabilistic Automata. Academic Press, New York (1971)
Rabin, M.O.: Probabilistic automata. Inf. Control 6, 230–243 (1963)
Rabin, M.O., Scott, D.: Finite automata and their decision problems. Scott. IBM J. Res. Dev. 3, 114–125 (1959)
Say, A.C.C., Yakaryılmaz, A.: Quantum finite automata: a modern introduction. In: Calude, C.S., Freivalds, R., Kazuo, I. (eds.) Computing with New Resources. LNCS, vol. 8808, pp. 208–222. Springer, Heidelberg (2014)
Villagra, M., Yakaryılmaz, A.: Language recognition power and succintness of affine automata. Technical report arXiv:1602.05432 (2016)
Watrous, J.: Quantum computational complexity. In: Encyclopedia of Complexity and System Science. Springer, Also available at (2009). arXiv:0804.3401
Yakaryılmaz, A., Say, A.C.C.: Languages recognized with unbounded error by quantum finite automata. In: Frid, A., Morozov, A., Rybalchenko, A., Wagner, K.W. (eds.) CSR 2009. LNCS, vol. 5675, pp. 356–367. Springer, Heidelberg (2009)
Yakaryılmaz, A., Say, A.C.C.: Languages recognized by nondeterministic quantum finite automata. Quantum Inf. Comput. 10(9&10), 747–770 (2010)
Yakaryılmaz, A., Say, A.C.C.: Unbounded-error quantum computation with small space bounds. Inf. Comput. 279(6), 873–892 (2011)
Acknowledgements
We thank Marcos Villagra for his very helpful comments. We also thank the anonymous reviewers for their very helpful comments.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Díaz-Caro, A., Yakaryılmaz, A. (2016). Affine Computation and Affine Automaton. In: Kulikov, A., Woeginger, G. (eds) Computer Science – Theory and Applications. CSR 2016. Lecture Notes in Computer Science(), vol 9691. Springer, Cham. https://doi.org/10.1007/978-3-319-34171-2_11
Download citation
DOI: https://doi.org/10.1007/978-3-319-34171-2_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-34170-5
Online ISBN: 978-3-319-34171-2
eBook Packages: Computer ScienceComputer Science (R0)