Publication: Hipercomputación desde la computación cuántica.
Loading...
Date
2003
Authors
Sicard Ramírez, Andrés
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
El problema de investigación propuesto consiste en generalizar el modelo de Kieu a diferentes referentes físicos, sin perder (en lo posible) la generalidad del algoritmo de Kieu, diseñado para resolver el décimo problema de Hilbert. Es decir, el problema de investigación consiste en construir nuevos modelos y algoritmos de hipercomputación sustentados en la computación cuántica.
En particular, se desea ampliar el modelo y el algoritmo de Kieu a los siguientes referentes físicos: la caja de potencial, el oscilador de Laguerre, el oscilador de Laguerre generalizado y el rotor cuántico. Para estos referentes se presentan las siguientes hipótesis respecto al problema no Turing-computable que es posible resolver, donde $P(x_1,\dots,x_p)$ es una ecuación diofántica y $n_i \in \mbb{N}$.
Referente físico propuesto: Caja de potencial
Problema no Turing computable: Ecuaciones $P(x_1, \dots, x_p)$ con soluciones de la forma $\{x_i = n_i^2\}$.
Referente físico propuesto: Oscilador de Laguerre
Problema no Turing computable: Ecuaciones $P(x_1, \dots, x_p)$ con soluciones de la forma $\{x_i = K + n_i\}$, donde $K \in \mbb{N}$.
Referente físico propuesto: Oscilador de Laguerre generalizado
Problema no Turing computable: Ecuaciones $P(x_1, \dots, x_p)$ con soluciones de la forma $\{x_i = n_i(n_i + \alpha) \}$, donde $\alpha \in \mbb{N}$.
Referente físico propuesto: Rotor cuántico
Problema no Turing computable: Ecuaciones $P(x_1, \dots, x_p)$ con soluciones de la forma $\{x_i = -J+n_i\}$, donde $J \in \mbb{N}$ y $ 0 \leq n \leq 2J$.
2. Marco teórico:
El primer modelo de computación cuántica que directamente atacó el problema de la hipercomputación, fue el modelo propuesto por Tien D. Kieu, en octubre del año 2001, en el cual presentó un algoritmo dise\~nado para solucionar el décimo problema de Hilbert \cite{Kieu-2003a,Kieu-2002a,Kieu-2003}. La estrategia de Kieu consistió en una estrategia similar a la seguida por Farhi \cite{Farhi-2000,Farhi-2001} para encontrar una solución polinómica a problemas $NP$-completos, pero en lugar de manipular hamiltonianos $finito$-dimensionales, Kieu seleccionó un hamilnoniano $\infty$-dimensional en el espacio de Hilbert $H$ cuya base $\{\ket{n}\mid n \in \mbb{N} \}$ es el conjunto de autovectores del operador número $N$. Además Kieu utilizó una versión del teorema adiabático para un cierto hamiltoniano total $H_P + H_I$ asociado al oscilador armónico, el cual es la suma de un hamiltoniano $H_P$ que codifica la ecuación diofántica $P(x_1, \dots, x_p)$ a resolver y un hamiltoniano $H_I$ de interacción universal construido a partir de los estados coherentes $\ket{z}$ correspondientes al álgebra de Wely-Heissenberg. La idea entonces es que la ecuación $P(x_1, \dots, x_p)$ tiene al menos una solución entera si y sólo si el valor propio asociado al estado fundamental de $H_P$ es igual a cero.
3. Objetivos
3.1 Objetivo general:
Construir nuevos modelos de hipercomputación sustentados en la computación cuántica.
3.2 Objetivos específicos:
Para cada uno de los referentes físicos propuestos, se espera:
A. Construir un nuevo modelo de hipercomputación, con base en la adaptación del modelo de hipercomputación de Kieu al nuevo referente físico.
B. Adaptar el algoritmo de Kieu para el décimo problema de Hilbert, al nuevo modelo de hipercomputación obtenido.
C. Simular numéricamente el comportamiento del algoritmo obtenido.
D. Determinar las similitudes y diferencias con los otros modelos de hipercomputación propuestos (incluyendo el modelo de Kieu).
4. Metodología propuesta:
Los tres primeros objetivos se desarrollarán para cada uno de los referentes físicos propuestos. El cuarto objetivo se desarrollará para los cuatro modelos propuestos. Cada una de las siguientes etapas está relacionada con el cumplimiento de cada uno de estos objetivos.