Abstract
Ultrametric algorithms are similar to probabilistic algorithms but they describe the degree of indeterminism by p-adic numbers instead of real numbers. This paper introduces the notion of ultrametric query algorithms and shows an example of advantages of ultrametric query algorithms over deterministic, probabilistic and quantum query algorithms.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ablayev, F.M., Freivalds, R.: Why sometimes probabilistic algorithms can be more effective. In: Wiedermann, J., Gruska, J., Rovan, B. (eds.) MFCS 1986. LNCS, vol. 233, pp. 1–14. Springer, Heidelberg (1986)
Ambainis, A.: Polynomial degree vs. quantum query complexity. Journal of Computer and System Sciences 72(2), 220–238 (2006)
Ambainis, A., Freivalds, R.: 1-way quantum finite automata: strengths, weaknesses and generalizations. In: Proc. IEEE FOCS 1998, pp. 332–341 (1998)
Balodis, K., Beriņa, A., Cīpola, K., Dimitrijevs, M., Iraids, J., Jēriņš, K., Kacs, V., Kalājs, J., Krišlauks, R., Lukstiņš, K., Raumanis, R., Scegulnaja, I., Somova, N., Vanaga, A., Freivalds, R.: On the state complexity of ultrametric finite automata. In: Proceedings of SOFSEM, vol. 2, pp. 1–9 (2013)
Bērziņa, A., Freivalds, R.: On quantum query complexity of kushilevitz function. In: Proceedings of Baltic DB&IS 2004, vol. 2, pp. 57–65 (2004)
Buhrman, H., Wolf, R.D.: Complexity measures and decision tree complexity: a survey. Theoretical Computer Science 288(1), 21–43 (2002)
Moore, C., Quantum, J.C.: automata and quantum grammars. Theoretical Computer Science 237(1-2), 275–306 (2000)
Dragovich, B., Dragovich, A.: A p-adic model of dna sequence and genetic code. p-Adic Numbers, Ultrametric Analysis, and Applications 1(1), 34–41 (2009)
Freivalds, R.: Recognition of languages with high probability on different classes of automata. Doklady Akademii Nauk SSSR 239(1), 60–62 (1978)
Freivalds, R.: Projections of languages recognizable by probabilistic and alternating finite multi-tape automata. Information Processing Letters 13(4-5), 195–198 (1981)
Freivalds, R.: On the growth of the number of states in result of the determinization of probabilistic finite automata. Avtomatika i Vichislitel’naya Tekhnika (3), 39–42 (1982)
Freivalds, R.: Complexity of probabilistic versus deterministic automata. In: Barzdins, J., Bjorner, D. (eds.) Baltic Computer Science. LNCS, vol. 502, pp. 565–613. Springer, Heidelberg (1991)
Freivalds, R.: Languages recognizable by quantum finite automata. In: Farré, J., Litovsky, I., Schmitz, S. (eds.) CIAA 2005. LNCS, vol. 3845, pp. 1–14. Springer, Heidelberg (2006)
Freivalds, R.: Non-constructive methods for finite probabilistic automata. International Journal of Foundations of Computer Science 19, 565–580 (2008)
Freivalds, R.: Ultrametric finite automata and turing machines. In: Béal, M.-P., Carton, O. (eds.) DLT 2013. LNCS, vol. 7907, pp. 1–11. Springer, Heidelberg (2013)
Freivalds, R., Zeugmann, T.: Active learning of recursive functions by ultrametric algorithms. In: Geffert, V., Preneel, B., Rovan, B., Štuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 246–257. Springer, Heidelberg (2014)
Gouvea, F.Q.: p-adic numbers: An introduction, universitext (1983)
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th ACM Symposium on Theory of Computing, pp. 212–219 (1996)
Khrennikov, A.Y.: Non-Archimedean Analysis: Quantum Paradoxes, Dynamical Systems and Biological Models. Kluwer Academic Publishers (1997)
Koblitz, N.: P-adic Numbers, p-adic Analysis, and Zeta-Functions, 2nd edn. Graduate Texts in Mathematics, vol. 58. Springer (1984)
Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: Proc. IEEE FOCS 1997, pp. 66–75 (1997)
Kozyrev, S.V.: Ultrametric analysis and interbasin kinetics. In: Proc. of the 2nd International Conference on p-Adic Mathematical Physics, vol. 826, pp. 121–128. American Institute Conference Proceedings (2006)
Krišlauks, R., Rukšāne, I., Balodis, K., Kucevalovs, I., Freivalds, R., Agele, I.N.: Ultrametric turing machines with limited reversal complexity. In: Proceedings of SOFSEM, vol. 2, pp. 87–94 (2013)
Nielsen, M.A., Chuang, I.L.: Quantum computation and quantum information. Cambridge University Press (2000)
Nisan, N., Wigderson, A.: On rank vs. communication complexity. Combinatorica 15(4), 557–565 (1995)
Ostrowski, A.: Über einige Lösungen der Funktionalgleichung ϕ(x)ϕ(y) = ϕ(xy). Acta Mathematica 41(1), 271–284 (1916)
Papadimitriou, C.H.: Computational complexity. John Wiley and Sons Ltd, Chichester (2003)
Vladimirov, V.S., Volovich, I.V., Zelenov, E.I.: p-Adic Analysis and Mathematical Physics. World Scientific, Singapore (1995)
Zariņa, S., Freivalds, R.: Visualisation and and ultrametric analysis of koch fractals. In: Proc. 16th Japan Conference on Discrete and Computational Geometry and Graphs, pp. 84–85. Tokyo (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Freivalds, R. (2014). Ultrametric Vs. Quantum Query Algorithms. In: Dediu, AH., Lozano, M., Martín-Vide, C. (eds) Theory and Practice of Natural Computing. TPNC 2014. Lecture Notes in Computer Science, vol 8890. Springer, Cham. https://doi.org/10.1007/978-3-319-13749-0_1
Download citation
DOI: https://doi.org/10.1007/978-3-319-13749-0_1
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13748-3
Online ISBN: 978-3-319-13749-0
eBook Packages: Computer ScienceComputer Science (R0)