Trabajo Fin de Grado
Estudio sobre computación cuántica con aplicación a particionado de grafos
Autor/es | Sanz Pérez, Miguel Antonio |
Director | Maestre Torreblanca, José María
Zafra Cabeza, Ascensión |
Departamento | Universidad de Sevilla. Departamento de Ingeniería de Sistemas y Automática |
Fecha de publicación | 2019 |
Fecha de depósito | 2020-03-16 |
Titulación | Universidad de Sevilla. Grado en Ingeniería de las Tecnologías Industriales |
Resumen | En los últimos años se ha aumentado el interés de conceptos cuán
ticos como la superposición o el
entrelazamiento cuántico, así como el fenómeno de la teleportación cuántica. Esto se debe principalmente a un
nuevo ... En los últimos años se ha aumentado el interés de conceptos cuán ticos como la superposición o el entrelazamiento cuántico, así como el fenómeno de la teleportación cuántica. Esto se debe principalmente a un nuevo concepto que ha surgido de la aplicación de estas propiedades cuánticas al mundo de la computación, cuyo no mbre es computación cuántica. En este trabajo se va a realizar una breve descripción de estos conceptos cuánticos así como de los conceptos que surgen de la aplicación de la mecánica cuántica a la computación, como el qubit, las puertas lógicas cuánticas o el teorema de no clonación. T odo esto será de gran ayuda para poder abordar el verdadero objetivo del trabajo, aplicar estos conceptos revolucionarios a un problema combinatorio que en la actualidad, debido a su dificultad computacional, es imposible resolver para aplicaciones real . E ste es el caso del problema de máximo corte, un problema combinatorio cuya solución no puede ser obtenida en tiempo polinomial por un ordenador clásico, pero en cambio, las propiedades cuánticas permiten realizar cálculos simultáneos de múltiples estados m ediante la superposición y el entrelazamiento cuántico de los qubits. Por ello, se ha elegido un algoritmo cuántico que se aproveche de estas propiedades y consiga obtener resultados prometedores. Este es el caso de QAOA (Quantum Approximate Optimization A lgorithm), un algoritmo que permite resolver varios problemas combinatorios de tipo NP (no polinomiales) de forma aproximada. Además, este algoritmo tiene múltiples beneficios frente a otros algoritmos cuánticos utilizados para resolver problemas de este t ipo, entre los que destaca la posibilidad de utilizar este algoritmo para poder demostrar la tan ansiada por muchos expertos supremacía cuántica, la cual se alcanzará cuando se consiga obtener resultados mejores en un ordenador cuántico real que en uno clá sico. Al final del trabajo, se realizarán simulaciones de este algoritmo en un ordenador clásico con un software que permite simular algoritmos cuánticos, y de donde se obtendrán resultados de casos sencillos, pero que pueden ser extrapolados para casos má s complejos. Last years, interest in quantum con cepts such as superposition or quantum entanglement has increased, as well as the quantum teleportation. This is mainly due to a new idea that has appeared from the application of ... Last years, interest in quantum con cepts such as superposition or quantum entanglement has increased, as well as the quantum teleportation. This is mainly due to a new idea that has appeared from the application of these quantum properties to computing, whose name is quantum computing In this dissertation we will make a short description of these quantum ideas and the concepts that appear from the application of quantum mechanics to c omputing, such as qubit, quantum logic gates or the non cloning theorem. All this will help to achieve the objective of this dissertation; apply these revolutionary concepts to a combinatorial problem that nowadays, due to its computational difficulty, is impossible to solve for complex cases. For example, max cut problem is a combinatorial problem whose solution cannot be obtained in polinomial time (NP problem), but quantum properties allow to simultaneous calculations of many states due to superposition and quantum entanglement of qubits. Therefore, a quantum algorithm has been chosen for this problem. QAOA (Quantum Approximate Optimization Algorithm) is an algorithm that allows to solve some combinatorial problems of type NP (not polynomial time) approxi mately. In addition, this algorithm has multiple benefits when it is compared to other quantum algorithms that have been used to solve problems like the max cut. One of those benefits is the possibility of using this algorithm to demonstrate the expected q uantum supremacy, which will be achieved when a real quantum computer improves the results of a supercomputer. |
Cita | Sanz Pérez, M.A. (2019). Estudio sobre computación cuántica con aplicación a particionado de grafos. (Trabajo Fin de Grado Inédito). Universidad de Sevilla, Sevilla. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
TFG-2556-SANZ PEREZ.pdf | 2.047Mb | [PDF] | Ver/ | |