DOI:
https://doi.org/10.14483/22484728.18414Publicado:
2019-03-13Número:
Vol. 2 Núm. 1 (2019): Edición especialSección:
Visión InvestigadoraClassic simulation of quantum algorithm
Simulación clásica de un algoritmo cuántico
Palabras clave:
Algoritmo, Grover, Computación cuántica, Compuerta cuántica, Hadamard, Simulación (es).Palabras clave:
Algorithm, Grover, Quantum Computing, Quantum gate, Hadamard, Simulation (en).Descargas
Resumen (en)
Classical computing there are multiple algorithms to efficiently locate a certain element within a disorganized database; however, quantum computing can be applied more assertively in the face of problems in which it is complicated to verify a solution and at the same time to test multiple and possible solutions. Therefore, this article presents an introduction to Quantum Computing, developing some concepts of quantum formalism, and then approach Grover's algorithm which exploits the principle of superposition to the maximum. Finally, a classic simulation of this algorithm is performed, and the results obtained are compared with classical algorithms such as sequential search and binary search method. A 95% is obtained as a result of greater effectiveness in times -when solving the same search-, revealing the potential advantages of quantum computing.
Resumen (es)
En la computación clásica existen múltiples algoritmos para localizar de manera eficiente un determinado elemento dentro de una base de datos desorganizada; sin embargo, la computación cuántica puede aplicarse de manera más asertiva frente a tales problemas cuando es complejo verificar una solución y a la vez probar múltiples y posibles soluciones. Por lo anterior, en este artículo se presenta una introducción a la Computación Cuántica -desarrollando algunos conceptos del formalismo cuántico-, y luego se aborda el algoritmo de Grover el cual explota al máximo el principio de superposición. Finalmente se realiza una simulación clásica de dicho algoritmo, y los resultados obtenidos se comparan con otros algoritmos clásicos como el método de búsqueda lineal y búsqueda binaria. Se obtiene como resultado un %95 de mayor efectividad en tiempos -a la hora de resolver la misma búsqueda- logrando poner de manifiesto las ventajas potenciales de la computación cuántica.
Referencias
P. Benioff, “The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines”, J. Stat. Phys., vol. 22, pp. 563—591, 1980. https://doi.org/10.1007/BF01011339
P. Benioff. “Quantum mechanical Hamiltonian models of Turing machines”, J. Stat. Phys., vol. 29, pp. 515—546, 1982. https://doi.org/10.1007/BF01342185
P. Benioff. Quantum mechanical models of Turing machines that dissipate no energy. Phys. Rev. Lett. vol. 48, pp. 1581—1585, 1982. https://doi.org/10.1103/PhysRevLett.48.1581
R. P. Feynman. Simulating physics with computers. Int. J. Theor. Phys. 21, pp. 467—488, 1982. https://doi.org/10.1007/BF02650179
R. P. Feynman. Quantum mechanical computers. Opt. News, 1985. https://doi.org/10.1364/ON.11.2.000011
V. Moret-Bonillo. Principios fundamentales de computación cuántica, 2013, Universidad de La Coruña.
R. P. Feynman, International Journal of Theoretical Physics, 1982. https://doi.org/10.1007/BF02650179
P. Benioff, Physical Review Letters, 1982. https://doi.org/10.1103/PhysRevLett.48.1581
D. Deutsch, Proceedings of the Royal Society of London Series A., 1985.
D. Deutsch, Proceedings of the Royal Society of London, 1989. https://doi.org/10.1098/rspa.1989.0099
A. Barenco, Charles H. Bennett, Richard Cleve David P. DiVincenzo, Norman Margolus Peter Shor Tycho Sleator, John Smolin y Harald Weinfurter, “Elementary gates for quantum computation”, Phys. Rev. A, vol. 52, no. 5, pp. 3457-3467, 1995. https://doi.org/10.1103/PhysRevA.52.3457
Serway, R. A., Jewett, J. W., Hernández, A. E. G., & López, E. F. “Física para ciencias e ingeniería”, vol. 6, Thomson, 2006.
E. Arikan. “An information-theoretic analysis of Grover's algorithm”, 2003. [En línea]. https://doi.org/10.1109/ISIT.2003.1228418
J. Richard, W. Kenneth. “Grover's Algorithm”, 2014. [En línea]. Disponible en: https://ieeexplore.ieee.org/xpl/ebooks/bookPdfWithBanner.jsp?fileName=7010444.pdf&bkn=7008157&pdfType=chapter
D. Deutsch. Quantum theory, the Church-Turing principle and the universal Quantum computer. Proc. Roy. Soc. Lond, pp. 97-117, 1985. https://doi.org/10.1098/rspa.1985.0070
S. Aarón; Viviana; S. Esteban, “Un análisis profundo del fenómeno dualidad onda partícula para la comprensión del mundo cuántico”, Latin-American Journal of Physics Education, 2012, vol. 6, no 1.
B. José Enrique. G. Pablo. S José Javier. Introducción al formalismo de la mecánica cuántica. Editorial UNED, 2010.
M. A. Nielsen and I. L. Chuang, “Quantum Computation and Quantum Information”, Cambridge University Press, 2000.
Meglicki, Z., “Quantum Computing without Magic: Devices”, The MIT Press, 2008. https://doi.org/10.7551/mitpress/7724.001.0001
Gisin, N., “Nonlocality Criteria for Quantum Teleportation”, Phys. Rev. Lett. A, vol. 210, pp. 151-156, 1996. https://doi.org/10.1016/S0375-9601 96)80001-6
Grupo de Computación Cuántica, Departamento de Matemática Aplicada, E.U. Informática, U. Politécnica Madrid, “Introducción al Modelo Cuántico de Computación”, TECHNICAL REPORT Nº 19, 2003.
R. P. Feynman, “Conferencias Sobre Computación”, Crítica eds., 2003.
R. P. Feynman, “Simulating Physics with Computers”, International Journal of Theoretical Physics, vol. 21, pp. 467-488, 1982. https://doi.org/10.1007/BF02650179
E. Desurvire, “Classical and Quantum Information Theory”, Cambridge University Press. 2009. https://doi.org/10.1017/CBO9780511803758
J. Laverde, H. Cárdenas, “Estado del arte en computación cuántica”, Visión Electrónica, 2018.
N. S. Yanofsky, and M. A. Mannucci, “Quantum Computing for Computer Scientists”, Cambridge University Press, 2008. https://doi.org/10.1017/CBO9780511813887
S. Andrés. Algunos elementos introductorios acerca de la computación cuántica. Memorias VII Encuentro ERM, Universidad de Antioquia, Medellín, 1999, vol. 23.
S. Andrés; V. Mario; G. Fredy; G. Cathalina; O. Luis; P. Carlos. et al. Introduction to Quantum Computing through Shor's Factorization Algorithm and Grover's Search Algorithm. 1999.
S. Andrés; V. Mario; P. Carlos. Paralelismo cuántico: el problema de Deutsch.
L. K. Grover, “A fast quantum mechanical algorithm for database search”, Proceeding of the 28th Annual ACM Symposium on Theory of Computing, 1996. https://doi.org/10.1145/237814.237866
X. Xue, H. Chen, K. Chen, Z. Li. “On the Research of BDD Based Simulation of Grover's Algorithm”, 2008. [En línea]. https://doi.org/10.1109/WGEC.2008.87
X. Li, K. Song, N. Sun, C. Zhao. “Phase matching in grover's algorithm”, 2013. [En línea]. Disponible en: https://ieeexplore.ieee.org/document/6640838/
I. Hamouda, M. Bahaa-Eldin, H. Said. “A generalized Grover's algorithm with access control to quantum databases”, 2016. https://doi.org/10.1109/ICCES.2016.7822015
N. Benchasattabuse, P. Chongstitvatana, Ch. Apomtewan. “Quantum Rough Counting and Its Application to Grover's Search Algorithm”, 2018. https://doi.org/10.1109/CCOMS.2018.8463331
L. Panchi, L. Shiyong. “Grover quantum searching algorithm based on weighted targets”, 2008. https://doi.org/10.1016/S1004-4132 , 08)60093-6
M. Li, Q. Yang, H. Zhang. “Microwave Simulation of Grover's Quantum Search Algorithm”, 2018. https://doi.org/10.1109/MAP.2006.277153
M. Li-min, S. Xin-yu, Z. Kai. “Research on routing algorithm for MANET based on Grover searching theory”, 2010. https://doi.org/10.1109/ICWITS.2010.5611812
X. Li, K. Song, N. Sun, Ch. Zhao. “Quantum searching algorithm based on the weighting marked items”, 2013. [En línea]. Disponible en: https://ieeexplore.ieee.org/document/6640837/
K. Arima, N. Shigei, H. Miyajima. “A Proposal of a Quantum Search Algorithm”, 2009. https://doi.org/10.1109/ICCIT.2009.126
A. Mandviwalla, K. Ohshiro, B. Ji. “Implementing Grover’s Algorithm on the IBM Quantum Computers”, 2018. https://doi.org/10.1109/BigData.2018.8622457
A. Giovanni, F. Luongo, A. Vitiello. “Quantum Implementation of Fuzzy Systems through Grover’s Algorithm”, 2018. https://doi.org/10.1109/FUZZ-IEEE.2018.8491579
A. Avila, R. Reiser, A. Yamin, M. Pilla. “Efficient In-Situ Quantum Computing Simulation of Shor's and Grover's Algorithms”, 2017. https://doi.org/10.1109/SBAC-PADW.2017.19
F. Li, Li. Zhou, L. Liu, H. Li. “A quantum search based signal detection for MIMO-OFDM systems”, 2011. https://doi.org/10.1109/CTS.2011.5898934
P. Zuliani. “A Formal Derivation of Grover's Quantum Search Algorithm”, 2007. https://doi.org/10.1109/TASE.2007.3
L. Li, M. Thornton, M. Perkowski. “A Quantum CAD Accelerator Based on Grover's Algorithm for Finding the Minimum Fixed Polarity Reed-Muller Form”, 2006.
K. Kang, “Two improvements in Grover's algorithm”, 2015. https://doi.org/10.1109/CCDC.2015.7162096
A. Bushnag, A. Alessa, M. Li, K. Elleithy. “Directed diffusion based on weighted Grover's quantum algorithm DWGQ”, 2015. https://doi.org/10.1109/LISAT.2015.7160216
A. Avila, R. Reiser, A. Yamin, M. Pilla. “Parallel simulation of Shor's and Grover's algorithms in the distributed geometric machine”, 2017. https://doi.org/10.1109/FSKD.2017.8393304
S. Dhawan, M. Perkowski. “Comparison of Influence of Two Data-Encoding Methods for Grover Algorithm on Quantum Costs”, 2011. https://doi.org/10.1109/ISMVL.2011.29
M. Li, Q. Yang, H. Zhang. “A Numerical Quantum Optimal Control with Grover Iteration”, 2018. https://doi.org/10.23919/ChiCC.2018.8483175
S. Jordan, Y. Liu. “Quantum Cryptanalysis: Shor, Grover, and Beyond”, 2018. https://doi.org/10.1109/MSP.2018.3761719
F. P. Zen, A. N. Atmaja, and S. Sigit, “Pencarian data dengan indeks tak-terurut menggunakan algoritma kuantum “, Indonesian Journal of Physics, no.4, October 2003.
Z. Sakhi, R. Kabil, A. Tragha, M. Bennai. “Quantum cryptography based on Grover's algorithm”, 2012. https://doi.org/10.1109/INTECH.2012.6457788
A. Saha, A. Chongder, S. Mandal, A. Chakrabarti. “Multiuser detection based on Grover's algorithm”, 2015. https://doi.org/10.1109/ISCAS.2006.1693688
Z. Qu, Z. Li, G. Xu, S. Wu, X. Wang. “Quantum Image Steganography Protocol Based on Quantum Image Expansion and Grover Search Algorithm”, 2019. https://doi.org/10.1109/ACCESS.2019.2909906
Y. Tang, S. Su. “Application of Grover's Quantum Search Algorithm to Solve the Transcendental Logarithm Problem”, 2014. https://doi.org/10.1109/CIS.2014.166
A. Saha, A. Chongder, S. Mandal, A. Chakrabarti. “Synthesis of Vertex Coloring Problem Using Grover's Algorithm”, 2015. https://doi.org/10.1109/iNIS.2015.55
P. Roger; S. Javier García. Las sombras de la mente. Ed. Crítica, 1996.
H. T. Schmid et al., “Evidence of wave-particule duality for single fast hidrogen atom. Phys. Rev. Lett.https://doi.org/10.1103/PhysRevLett.101.083201
P. A. M. Dirac. The principles of quantum Mechanics. 1958 No. 27. Oxford University Press
DK Lee, D. Derek. 2016. Grover_Algorithm, San José CA. Recuperado de https://github.com/dqdang/Grover-Algorithm/blob/5f6cb123ef5aad6585c392487a472e59dbdc71e0/src/Driver.java#L1-L76
J. A. Olarte, M. C. Cifuentes, “Espintrónica: principios básicos y aplicaciones”. Visión Electrónica, algo más que un estado sólido, vol. 8, No. 2, 155-161, julio-diciembre de 2014.
Cómo citar
APA
ACM
ACS
ABNT
Chicago
Harvard
IEEE
MLA
Turabian
Vancouver
Descargar cita
Licencia
Derechos de autor 2019 Visión electrónica
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial 4.0.
.png)
atribución- no comercial 4.0 International
.jpg)
