Notes on quantum computing
DOI:
https://doi.org/10.59471/raia202610e5Keywords:
Quantum Computing, Algorithm, ComplexityAbstract
This article includes a series of notes intended to provide the reader with an initial aproximation to quantum computing. It covers the reasons for studying the field, the necessary physics and mathematics, the theoretical foundations, the key computational models, characteristics of the algorithms and computational complexity, and a brief overview of the origins and evolution of the paradigm. Particular attention is paid to the similarities and differences between probabilistic computing, which is the standard classical model in the context of computational complexity, and quantum computing. Due to space constraints, representative quantum algorithms are not described, which will be presented in a subsequent article.
Downloads
References
Aaronson, S. (2013). Quantum computing since Democritus. Cambridge University Press.
Arora, S. y Barak, B. (2009). Computational complexity: a modern approach. Cambridge University Press.
Barenco, A., Bennett, C., Cleve, R., DiVincenzo, D., Margolus, N., Shor, P., Sleator, T., Smolin, J. y Weinfurter, H. (1995). Elementary gates for quantum computation. Physical Review, A, 52, 5, 3457–3467.
Benioff, P. (1980). The computer as a physical system: a microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines. Journal of Statistical Physics, 22, 5, 563-591.
Bennett, C. y Brassard, G. (1984). Quantum cryptography: Public key distribution and coin tossing. Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing, Bangalore, India, 175–179.
Bennett, C., Brassard, G., Crépeau, C., Jozsa, R., Peres A. y Wootters, W. (1993). Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. Physical Review Letters, 70, 1895–1899.
Bennett, C. y Wiesner, S. (1992). Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states. Physical Review Letters, 69, 2881–2884.
Bernstein, E. y Vazirani, U. (1993). Quantum complexity theory. Proceedings of the 25th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, 11–20. ACM Press.
Bernstein, E. y Vazirani, U. (1997). Quantum complexity theory. SIAM Journal on Computing, 26, 5, 1411–1473.
Clauser, J., Horne, M., Shimony, A. y Holt, R. (1969). Proposed experiment to test local hidden-variable theories. Physical Review Letters, 23, 880–884.
Cleve, R., Ekert, A., Macchiavello, C. y Mosca, M. (1998). Quantum algorithms revisited. Proceedings of the Royal Society of London. A, 454, 1969, 339–354.
Deutsch, D. (1985). Quantum theory, the Church–Turing principle and the universal quantum computer. Proceedings of the Royal Society of London. Mathematical and Physical Sciences. A, 400, 1818, 97–117.
Deutsch, D. (1989). Quantum computational networks. Proceedings of the Royal Society of London. Mathematical and Physical Sciences, A, 425, 1868, 73–90.
Deutsch, D. y Jozsa, R. (1992). Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London. A, 439, 553–558.
Feynman, R. (1982). Simulating physics with computers. International Journal of Theoretical Physics, 21, 467–488.
Grover, L. (1996). A fast quantum mechanical algorithm for database search. Proceedings of the 28th Annual ACM Symposium on Theory of Computing, Philadelphia, Pennsylvania, USA, 212–219. ACM Press.
Hughes, C. (2021). Quantum computing for the quantum curious. Springer.
Kitaev, A. (1997). Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52, 6, 1191–1249.
Kitaev, A., Shen, A. y Vyalyi, M. (2002). Classical and quantum computation. American Mathematical Society.
Kumar, M. (2011). Quantum: Einstein, Bohr y el gran debate sobre la naturaleza de la realidad. Editorial Kairós.
Matuschak, A. y Nielsen, M. (2019). Quantum computing for the very curious. Quantum Country.
Nielsen, M. y Chuang, I. (2010). Quantum computation and quantum information. Cambridge University Press, 10th Anniversary Edition.
Quantum Soar (2025). Introduction to quantum computing: complete course. Quantum Soar.
Rosenfeld, R. (2026). Computabilidad y complejidad computacional. EDULP.
Shi, A. (2002). Both Toffoli and Controlled-NOT need little help to do universal quantum computation. Quantum Information and Computation, 2, 1, 41–59.
Shor, P. (1994). Algorithms for quantum computation: discrete logarithms and factoring. Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 124–134. IEEE Computer Society Press.
Simon, D. (1994). On the power of quantum computation. Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 116–123. IEEE Computer Society Press.
Tomatis, F. y Miglierini, F. (2025). Dos hojas de ruta para aprender computación cuántica. Tesis de grado, Facultad de Informática, Universidad Nacional de La Plata.
Watrous, J. (2025). Understanding quantum information and computation. IBM Quantum Learning.
Wong, T. (2022). Introduction to classical and quantum computing. Rooted Grove.
Yao, A. (1993). Quantum circuit complexity. Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, Palo Alto, CA, USA, 352-361. IEEE Computer Society Press.
Downloads
Published
Issue
Section
License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
