La Singularidad Desnuda

Un universo impredecible de pensamientos y cavilaciones sobre ciencia, tecnología y otros conundros

Lo que la computación cuántica (no) puede hacer por nosotros

Posted by Carlos en febrero 13, 2007

Computador cuánticoHoy es el día en el que los muchachos de D-Wave planean hacer la presentación de su sistema cuántico Orión, tal como Alvy nos acaba de recordar en Microsiervos. Creo que puede ser entonces interesante analizar someramente qué es lo que la computación cuántica nos puede ofrecer, ya que se trata de un campo cuyas posibilidades en el ámbito de la computación están casi tan sobredimensionadas como las de Guti en el ámbito del mediocampo del Real Madrid. Para ponernos en situación, es necesario empezar por algunos preliminares que nos ayuden entender el nicho en el que los computadores cuánticos pueden ser útiles.

En primer lugar, vamos a comenzar por definir un marco computacional (puede hacerse una discusión en términos más abstractos, pero es más simple centrar las cosas en un modelo concreto). Hay diferentes posibilidades, pero vamos a ser clásicos e inclinarnos por las máquinas de Turing (MT). Una MT es un modelo formal del concepto de algoritmo que podemos imaginar como un dispositivo capaz de leer/escribir símbolos de/en una cinta, y de desplazarse por la misma (o hacer que la cinta se desplace, que tanto da una cosa como la otra). La cinta la podemos imaginar como de longitud ilimitada, y dividida en casillas, en cada una de las cuales puede haber un símbolo. La MT se halla en todo momento en un cierto estado interno (de entre un cierto conjunto de estados posibles) y dispone de una función de transición interna que le dice qué debe escribir, cómo debe moverse, y cómo debe cambiar el estado interno en función del estado actual y de lo que esté leyendo en cada momento de la cinta. La definición de la MT es completa si indicamos el alfabeto A que contiene a todos los símbolos que se pueden leer/escribir, el conjunto de estados posibles Q, el estado inicial q0, y la función de transición d. El funcionamiento de la MT termina en el momento que se alcanza un cierto estado de parada. Los contenidos iniciales de la cinta corresponden a la entrada del algoritmo, y los contenidos finales a su salida.

Esta definición de MT es suficiente para abarcar cualquier algoritmo (de hecho un algoritmo se define como una MT). En particular, un algoritmo cuántico es simulable en una MT, por lo que un supuesto ordenador cuántico no nos va a permitir nada que no podamos hacer con nuestro PC, Mac, o -ya puestos- ZX-81. Por supuesto, es posible que -aunque no pueda hacer nada nuevo- un algoritmo cuántico sí pueda ser más eficiente que un algoritmo clásico. Nos adentramos entonces en los vericuetos de la complejidad computacional, y necesitamos definir algunos conceptos adicionales, empezando por el de MT no determinista (nMT).

Una nMT es una MT en la que la función de transición puede estar sobre- o sub-especificada, es decir, se puede indicar más de un comportamiento en una determinada situación o ninguno en absoluto. Lógicamente, lo primero es más interesante. Podemos imaginarnos que cuando se produce una de estas situaciones en la que la función de transición indica más de una posibilidad, la nMT se ramifica, produciendo copias de la máquina que exploran estas posibilidades en paralelo. Contrariamente a lo que una primera impresión pudiera hacer pensar, este paralelismo masivo no nos permite nuevamente hacer nada que no pueda hacer una MT determinista, pero sí que permite realizar una tarea mucho más deprisa (exponencialmente más rápido). Podemos emplear esta posibilidad para realizar una clasificación de los problemas computacionales de decisión (problemas para los que tenemos que encontrar una respuesta SÍ o NO) en dos clases: P y NP. La primera comprende aquellos problemas para los que una MT determinista puede encontrar la respuesta en un número polinomial (en el tamaño del problema) de pasos, es decir, en algo del orden de nc, donde n es dicho tamaño y c es una constante que no depende de n. Análogamente, NP es el conjunto de problemas de decisión para los que una nMT puede encontrar la respuesta en un número polinomial de pasos (es decir, basta con que una de las ramas encuentre la solución en tiempo polinomial). Hay numerosos problemas prácticos de optimización cuya versión decisional (e.g., la que tiene por respuesta SÍ o NO) está en la clase NP. Por ejemplo, el problema del viajante de comercio (TSP): dado un conjunto de ciudades, encontrar una ruta de longitud mínima que pase por todas las ciudades, sin repetir ninguna, y vuelva a la ciudad de partida. La versión decisional de este problema sería plantear: ¿existe un camino de las características requeridas cuya longitud sea inferior a K?

En relación al ejemplo anterior, no consta que el TSP (entre otros muchos problemas) esté en P, lo que hace plantearse la cuestión de si es que no se conoce aún un algoritmo polinomial para él, o es que realmente el problema es intrínsecamente no-polinomial. En otras palabras, dado que P está claramente contenida en NP (porque toda MT determinista es una nMT también), se ignora si la inclusión es estricta o no, esto es, si hay problemas en NP que no estén en P. Se cree que sí los hay, pero no hay demostración en un sentido o en otro (hay un premio de 1,000,000$ para quien lo consiga demostrar). Lo que sí se sabe es que o bien P = NP (en cuyo caso la necesidad de computadores cuánticos pasa a ser muy cuestionable), o bien hay tres tipos de problemas en NP: los problemas en P, y otros dos tipos que veremos a continuación, una vez se defina el concepto de completitud para una clase.

Se dice que un problema X es completo para la clase C, si X es un problema que pertenece a la clase C, y cualquier otro problema en C es reducible a X. A grandes rasgos, esto último quiere decir que dada una instancia de un problema Y perteneciente a C, podemos usar un cierto procedimiento R para convertirlo en una instancia del problema X. Si esto es así, X representa el mayor grado de dificultad dentro de la clase (cualquier otro problema es a lo sumo tan complejo de resolver como X). En el caso particular de NP requerimos que la transformación anterior se haga con un algoritmo polinomial. El problema de la satisfacibilidad es un problema completo para NP. Hay otros muchos que pueden consultarse aquí.

Bajo la suposición de que P no es igual a NP, los problemas NP-completos están lógicamente fuera de P, pero también hay problemas que ni están en P, ni son NP-completos. No consta que un algoritmo cuántico, gracias a la aceleración que el uso de estados superpuestos permita, pueda resolver en tiempo polinomial un problema NP-completo, y de hecho se piensa que no podrá. La utilidad de los computadores cuánticos será entonces para problemas no NP-completos como la factorización de enteros (una utilidad mucho más reducida de lo que los optimistas de D-Wave afirman). En otro artículo ya trataremos esto con más detalle, y lo cuantificaremos más formalmente. Vamos a esperar mientras tanto a ver en qué queda la presentación de Orión.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

About these ads

31 comentarios to “Lo que la computación cuántica (no) puede hacer por nosotros”

  1. Panta said

    Encuentro muy interesante este post, además al enlazar a wikipedia me has ejemplificado por fin qué diablos era el problema ‘P vs NP’ entre los problemas del milenio.(¿Se ha llevado Perelman un millón de dólares por su solución?)
    Tu texto ¿puedo entenderlo como una razonada versión de por qué más potencia de cálculo no implica necesariamente que se resuelvan nuevos problemas?
    Gracias.

  2. Interesante artìculo pero no estoy de acuerdo en el punto que mencionas al principio:
    ” se trata de un campo cuyas posibilidades en el ámbito de la computación están casi tan sobredimensionadas…”
    Aùn en el caso de que realmente no sirva para resolver màs y mejores problemas dentro de las matemàticas…¿te imaginas el potencial que tal potencia de càlculo tendrìa en otros campos?Yo trabajo todos los dìas en ordenadores relativamente potentes pero que se quedan cortos dentro del campo en que trabajo con ellos (los gràficos 3D).No es lo mismo renderizar en 19 horas que en apenas unos minutos.Te recuerdo ademàs que hace apenas unas dècadas se consideraba una tonterìa el poseer un ordenador en casa (para què iba a necesitar alguien un ordenador en casa…)y ahora mira…Las aplicaciones de este campo tecnològico quizàs tarden muchos años en llegar al consumo masivo pero cuando lleguen…

  3. iXen said

    Aunque redujéramos a los problemas NP-completos el avance de un ordenador cuántico con el suficiente numero de qubit interesantes cambiaría el mundo en el mismo momento que existiera.

    ¿podría un ordenador cuántico calcular todos los movimientos de una partida de ajedrez y decidir cual es el mas favorable?

    Hablamos de una cantidad de posibilidades asombrosas pero ni mucho menos hablamos del infinito. Recuerdo mis practicas de lenguajes de programación declarativo y de lo realmente simple que es desbordar la memoria de un pc realizando programas simples puramente recursivos.

    Si Guti fuera para el Madrid lo que un ordenador cuántico a computación, no tendría clausula de rescisión.

  4. Carlos said

    Panta, para dar respuesta a tu pregunta es preciso hacer una precisión en relación a la noción de resolver. La idea clave en esta discusión es la resolución eficiente de problemas que carecen de solución de este tipo. Cualquier problema NP-completo tiene un conjunto inmenso pero finito de posibles soluciones. Esto quiere decir que dichos problemas son por definición resolubles: basta explorar todas las posibles soluciones y ver si alguna de ellas es satisfactoria. El desafío es conseguir lo mismo de manera mucho más eficiente, y lo que la conjetura “P distinto de NP” afirma es que no hay algorimos clásicos eficientes (de complejidad polinómica) para ello.

    Sobre la potencia de cálculo, piensa lo siguiente. Un problema como SAT tiene 2^n soluciones posibles, donde n es el número de variables. Con un enfoque de fuerza bruta, duplicar la potencia de cómputo permite abordar en el mismo tiempo un problema con sólo una variable más. Cualquier aumento fijo en la potencia de cálculo permitirá aumentar entonces un poco el límite de lo que podemos resolver en un cierto tiempo, pero no permitirá romper la barrera inherente de complejidad que tienen ciertos problemas.

    La computación cuántica parece que permitirá dar un salto cualitativo, pero este salto no alcanzará el nivel que permita la resolución eficiente de problemas NP-completos. Se quedará en un escalón inferior (problemas como la factorización de enteros), que sigue siendo muy interesante, pero no es la panacea que en algunos ámbitos intentan vender.

  5. Carlos said

    Rhasalgheti, en línea con lo que le comentaba a Panta, la utilidad de la computación cuántica está en romper la barrera de la clase P. Los problemas en P pueden explotar de manera mucho más directa los aumentos en la potencia del hardware, y por ahí y por la computación en grid van los tiros en las áreas en las que hay que hacer cálculos numéricos intensivos.

    La computación cuántica tiene muchos problemas prácticos como plataforma de cómputo básica. Se puede pensar de manera razonable en dispositivos cuánticos que actuaran como co-procesadores especializados para resolver ciertos problemas al servicio de un procesador no cuántico, pero soy muy escéptico acerca de las posibilidades más allá de esto.

  6. Carlos said

    IXen, es que precisamente son pocos los que piensan que un computador cuántico pueda llegar siquiera a problemas NP-completos.

    El ajedrez estándar 8×8 tiene un número de partidas posibles de 10^123 según la wikipedia, más que protones hay en el Universo (10^80). La exploración exhaustiva de todas las mismas parece irreal. Más aún, el ajedrez generalizado a tableros más grandes tiene una complejidad muchos niveles superior a la de los problemas NP-completos: es un problema EXPTIME-completo.

    En mi opinión, si lo que a veces se afirma de la computación cuántica fuera cierto, Guti sería mejor que Di Stéfano, Zidane y Cruyff juntos. ;-)

  7. Francisco said

    Me encanta “escucharos discutir”, auqnue no pueda aportar mucho.

    Sólo plantear dudas.

    Si la computación cuántica no es el salto cualitativo sufiiente para resolver todos los problemas ¿se ha teorizado otra computación que sí lo sea?

    Mil gracias

  8. iabal said

    Quería hacer un apunte, una MT no es un algoritmo. Una MT representa un lenguaje recursivamente enumerable, y un algoritmo es equivalente a un lenguaje recursivo. Estos últimos están contenidos en los primeros, pero es un contenido estricto (está demostrado). Es decir, con una MT puedes hacer cosas que no son algoritmos, eso es fácil de ver utilizando cualquier lenguaje de programación (que son equivalentes a las MT):

    “while (true) do begin … end;”

    Esto no es un algoritmo, porque un algoritmo siempre termina y el programa anterior es un bucle infinito que por lo tanto nunca termina.

    Otro apunte es que decir que lo que haces con una MT lo haces con tu PC y viceversa es algo que se debería decir con cuidado. La tesis de Turing (y la tesis de Church) vienen a decir que sí, que un ordenador es equivalente a una MT, pero no está demostrado, simplemente no se ha encontrado un contraejemplo (eso no es suficiente para demostrar nada, sólo para hacer conjeturas y suposiciones).

    No es por corregirte ni con mala intención, pero tengo fresca la asignatura de autómatas y lenguajes formales y quería comentar esos detalles ;)

    Por el resto es un artículo interesante, felicidades. Creía que los ordenadores cuánticos iban a ser una revolución e iban a poder solucionar cualquier problema NP-completo.

  9. Carlos said

    Hola Iabal. Gracias por las precisiones, que por supuestísimo son bienvenidas :-) . En relación a la identificación de MT y algoritmo, el matiz que comentas es por supuesto correcto. Al hilo de Gödel, tengo pendiente escribir algo sobre calculabilidad, y abundar sobre R, RE y problemas no computables, pero no quería liar más la madeja ;-) .

    Sobre la tesis de Church-Turing, no creo que afecte a la identificación MT = PC, ya que en el fondo la arquitectura de von Neumann es la implementación física de una una MT universal (con la evidente limitación de que la cinta no es infinita, claro). La cuestión sería más peliaguda si nos refiriéramos a cualquier dispositivo de cómputo que pudiera inventarse en el futuro. Es una cuestión muy interesante, aunque sólo sea filosóficamente hablando: ¿es el Universo computable? Quien sabe…

    Un saludo

  10. Carlos said

    Francisco, que yo sepa hay algunas ideas exóticas no ya para romper la barrera de la NP-completitud, sino incluso la de la propia Turing-computabilidad (resolver problemas que una MT no puede). Sin embargo, no parecen tener muchos visos de ser físicamente posibles.

  11. elmitsui said

    Sinceramente no entiendo nada de lo que aparece en el post, a pesar de que el tema me interesa bastante. lo siento no soy matemático.

    lo que sí creo es que no se puede comparar la etapa final en la evolución del procesador de silicio con el principio de la computación cuantica

  12. [...] La Singularidad Desnuda [...]

  13. iXen said

    Admito que me deje llevar por la ilusión que me hizo el mero echo de pensar en un pc que todo lo puede. Aquí la gente tiene frescas las asignaturas y yo las tengo ya un poco olvidadas.

    Yo solo recuerdo lo realmente inútil que es un pc cuando se pone a hacer problemas que bifurcan en arboles, y no me refiero realizando por ejemplo un algoritmo que tenga en cuenta la recursividad por la cola, o que no tome caminos que ya ha tomado, hablo de lo que a mi me vendieron que era la computación cuántica.

    Seria tan increíblemente productivo para el ser humano disponer de herramientas que hiciera infinitos cálculos en paralelos.

    En mi cabeza el salto a la informática cuántica era un salto al universo de star trek. Si realmente un electrón cuando se mueve físicamente pasa por todos los posibles caminos para llegar a su destino, y esto se puede llevar a eficiencia de calculo, entonce solo puedo decir que sigo creyendo que sera increíble un futuro no tan lejano.

  14. Carlos said

    No pasa nada, IXen, quien más quien menos tenemos ya también TALF en los talones. ;-) Fíjate que en relación con lo que comentas, conseguir por ejemplo una superposición de infinitos estados podría permitir no sólo resolver inmediatamente problemas NP-completos, sino que podría incluso abrir la puerta a funciones no computables. No está nada claro que eso sea físicamente factible.

    Hay que tener en cuenta también que el sistema Orión es un proyecto privado con fines comerciales, por lo que es lógico que inflen las expectativas de lo que pueden conseguir. Se trata de encontrar inversores, y empezar a colocar las máquinas (cosa que no me parece mal, ya que como comentaba antes, un sistema de computación cuántica que funcione será útil e interesante).

  15. Carlos said

    Elmitsui, no te disculpes, este tema no es nada trivial de entender. Sobre lo que comentas, creo que todavía le queda recorrido a la tecnología actual, pero hay que tener en cuenta que el razonamiento anterior no está ligado a una tecnología en particular, sino a un modelo general de cómputo.

  16. [...] Es muy completo.Tambien recomiendo la lactura de este excelente articulo relacionado con el tema: Lo que la computación cuántica (no) puede hacer por nosotros.Esta entrevista a David Deutsch, de la Universidad de Oxford, uno de los padres de la [...]

  17. Arturo said

    Hola, ps todo esto me parece la verdad muy interesante y tienen una platicas muy profundas acerca de la computación cuantica, soy un estudiante de una universidad y tengo que dar redactar un articulo de un tema cientifico de mi interés y pues la “Computación Cuantica” me gusta.
    Ojala que alguno de ustedes pudiera proporcionarme links en internet confiables para encontrar información suficiente para mi trabajo y darlo lo mejor posible.

    Ojala me respondan lo antes posible,

  18. Villa said

    Hola, permitidme unos comentarios sobre computación cuántica. Podría estar escribiendo sobre el tema durante horas, pero me contendré, no os preocupéis. Primero, ¿ puede un ordenador cuántico resolver problemas NP-completos en tiempo polinomial? No, en el marco de la mecánica cuántica “lineal” que “todos” conocemos. Pero sí en el caso de que una teoría cuántica no lineal sea desarrollada (la teoría de cuerdas y otras “barbaridades” de los físicos teóricos apuntan en esta dirección), como demostró Seth LLoyd hace muchos años: “Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems”, http://arxiv.org/abs/quant-ph/9801041. Los ordenadores cuánticos de propósito general no están aún en el mercado, pero la computación cuántica de propósito específico, en concreto, el cifrado cuántico es una realidad, que podéis comprar (ahora mismo es un poco caro). Sobre “la utilidad de los computadores cuánticos”. Es muy bonito vender que los ordenadores cuánticos harán cosas “maravillosas”, como descifrar códigos secretos gracias al algoritmo de Peter Shor, pero la realidad es más prosaica, la utilidad “de verdad” de los computadores cuánticos será algo muy sencillo y a la vez extremadamente complicado con los computadores clásicos: “simular” problemas o sistemas cuánticos. Por ejemplo, simular cómo dos proteínas interactúan en una reacción enzimática. Os puede parecer fácil, pero es extremadamente difícil. Efectos intrínsicamente cuánticos, como el efecto túnel o el colapso (no local) de la función de onda son extremedamente difíciles de implementar en un algoritmo clásico (con los conocimientos actuales). Sin embargo, serían “casi” directos en un ordenador cuántico “adecuado”. No es una idea mía, es del propio Peter Shor y, de hecho, ya la tuvo el “abuelo” de la computación cuántica, si consideramos a Deutsch como el “padre” (lo es de la máquina de Turing cuántica), el Nobel Richard Feynman. El propuso la necesidad de ordenadores cuánticos para simular sistemas cuánticos. Y ahí los ordenadores clásicos tienen poco que hacer. Podríamos entrar en cuestiones metafísicas como las de Roger Penrose en “La Nueva Mente del Emperador” en relación a que nuestro cerebro es un ordenador cuántico, etc. En contestación a Arturo, hay tal cantidad de información sobre computación cuántica en la web que seguramente necesitarás un buen guía. Mi recomendación es que escojas algún buen libro (hay muchos, basta ojear en Amazon). Si no puedes comprarlo o conseguirlo en alguna biblioteca, te recomiendo el artículo “From Cbits to Qbits: Teaching computer scientists quantum mechanics” de N. David Mermin, American Journal of Physics — January 2003 — Volume 71, Issue 1, pp. 23-30. Si no tienes acceso a la revista, tienes copia en
    hubcap.clemson.edu/~daw/D_PHYS456/AJP00023.pdf.gz

    Si vas a escribir un trabajo sobre computación cuántica no puedes olvidar comentar “en detalle” el algoritmo de Peter Shor. Quizás el artículo original (que puedes conseguir en la web) te resulte difícil de entender. Hay varios digest, quizás el siguiente te sea útil: Shor’s Factoring Algorithm and Modern Cryptography. An Illustration of the Capabilities Inherent in Quantum Computers, Edward Gerjuoy: http://arxiv.org/abs/quant-ph/0411184

    Tampoco debes olvidar mencionar el artículo de Grover sobre búsqueda de números con complejidad sqrt(N). La versión en “From Schrödinger’s Equation to the Quantum Search Algorithm” del propio Grover, es fácil de entender y la tienes en

    http://arxiv.org/abs/quant-ph/0109116.

    Peter Shor tiene un curso corto que también puede ser de tu interés: “Introduction to Quantum Algorithms” http://arxiv.org/abs/quant-ph/0005003.

    Y para acabar, si sabes un poquito de física, te gustará el artículo de Lloyd “Ultimate physical limits to computation” http://arxiv.org/abs/quant-ph/9908043.

    Saludos

  19. Villa said

    Arturo,

    ¿quieres sitios en castellano o en inglés? En este último caso, busca “quantum computing” “quantum computer” o “quantum computation” en http://arxiv.org/

  20. Pablo said

    En el artículo dice: “un algoritmo cuántico es simulable en una MT”

    Me gustaría saber de un artículo que lo explique, es decir, que muestre cómo se reduce el modelo de cálculo cuántico a MT, ¿o sólamente es simulable?.

    Quiero ver cómo un algoritmo cuántico puede escribirse en una MT, y no por simulación, sino por correspondencia entre modelos.

    Gracias.

  21. Carlos said

    Pablo, “simulación” no debe entenderse aquí como “aproximación” sino como “inclusión”. Las barreras de la computabilidad son las mismas para los algoritmos cuánticos y para los clásicos (salvo que se descubriera algún nuevo principio físico que permitiera superarlas). En relación a lo que buscas, el siguiente artículo te puede interesar:

    L. Fortnow, “One complexity theorist’s view of quantum computing“, Theoretical Computer Science 292(3):597-610, 2003

  22. Pablo said

    Sí, me interesa el paper :)

    Muchas gracias!

  23. Lanjarote said

    Jamás se podrá simular el Universo completo en ninguna máquina de computación, puesto que la propia máquina de computación deberá tener una implementación física, es decir, debemos reservar una parcela del Universo para alojar el Hw de la misma.
    Realizar una simulación es construir un sistema físico (computador) que se comporte de forma equivalente (a través de una correspondencia semiótica) a como lo hace otro sistema físco (el sistema problema)
    Si la parte de Universo que reservamos para construir la máquina se dedica a modelar el comportamiento del resto del universo, no puede dedicarse también simultaneamente a modelar su propio comportamiento. Es decir, no podrá hacer introspectivo su propio comportamiento físico, y por tanto habrá una parte del Universo que quedará oculta oculta a su conocimiento (la fenomenología física de su comportamiento propio)

    Quizá ni siquiera Dios sabe exactamente quien es

  24. Lanjarote said

    Un BEC (Condensado de Bose Einstein) es ‘de facto’ un computador cuántico bestial.
    Un BEC pequeño de unos 100.000 átomos en estado de coherencia cuántica viene a tener del orden de 2^2^100.000 estados interfiriendo y procesando. Es decir sería (tan solo en memoria análogo a un ordenador convencional de 2^100.000 bits), pero con todos los bits operando simultaneamente y no de 64 en 64 como en un procesador convencional.
    En comparación un computador corriente tiene del orden de 2^30 bits, y un cerebro humano del orden de 2^70 bits

    Lo único que le falta a un BEC para ser un computador cuántico ‘decente’ es ser además útil para nosotros (los humanos). No hay forma (al menos por el momento) de introducirle un programa ni de extraer datos del mismo. Por su puesto el BEC está computando. Pero computa ‘su programa’, no ‘el nuestro’. Como mínimo, hay que reconocerles un comportamiento fascinante que no cesa de estimular su estudio y en consecuencia un innegable éxito reproductivo: el número de BECs crece de forma exponencial y por el momento nos necesitan como parte de su ‘ciclo biológico’.

    ….pero a mí no dejan de producirme cierta aprensíón:

    ¿En qué demonios estarán pensando?

  25. [...] el ácido úrico? Toma caféLa mente más maravillosa del siglo XXIncendios y calentamiento globalLo que la computación cuántica (no) puede hacer por nosotros46 vídeos de Richard FeynmanSobrevivir el máximo tiempo en un agujero negro (o ¿y si los gemelos [...]

  26. Eyvar Diaz said

    ya se demostró que el orion no es un computador cuantico si no una maquina de proposito general que usa algo de mecanica cuantica.
    Un computador cuantico, creo que no es imposible lograrlo pero si bastante dificil ya que en el se debe tener en cuenta varios factores; uno de ellos puede ser el problema de la decoherencia ya que al realizar procesos tan rapidos los subsistemas del sistema al estar entrelazados entre si, podrian presentar fenomenos como la decoherencia antes nombrada que consiste en que al depender un subsistema de otro subsistema por el hecho de hacer procesos a una velocidad extrema estos subsistemas podrian colapsar, y lo mismo pasaria con el sistema al convertirse en subsistema, por ejemplo al estar conectado a una red para esto se puede decir que el tiempo que se estima por numero de procesos en un computador cuantico seria demasiado bajo por ejemplo si el numero de procesos en un compuatdor actual es la mitad de este en un computador cuantico seria la raiz cuadrada del mismo o sea del numero de procesos (No proc/2(t))(√No proc)ya que estos trabajan en qubits en paralelo.

  27. LIZARDO BENAVIDES said

    COMPUTADORES CUANTIC0S

    En el momento desconociendo mucho del tema en mención daré una opinión corta de lo comprendido sobre la computación cuantica, como el texto lo señala existen personas interesadas en el desarrollo de este sistema cuantico llamado Orión. Siendo este un terreno muy avanzado de la computación por lo cual debemos hacer una introducción con la cual podamos entender en que nos pueden ser útiles o no los computadores cuanticos.
    Para comenzar se nos señala la presencia de un modelo concreto con la maquina de Turín (MT), el cual es un modelo formal de un algoritmo muy avanzado capaz de leer, escribir cantidad de símbolos en una extensión ilimitada, los cuales internamente son procesados enviando resultados y cálculos matemáticos a gran velocidad, sabiendo que un algoritmo cuantico es mucho mas eficiente que un algoritmo clásico.
    Así se convierte la computación cuántica es un modelo de computación distinto al de la computación clásica. Se basa en el uso de qubits en lugar de bits, y da lugar a nuevas puertas lógicas que hacen posibles nuevos algoritmos. Una misma tarea puede tener diferente complejidad en computación clásica y en computación cuántica.
    Realizando consultas complementaria al texto encontramos que hoy en día existe empresa canadiense D-Wave System había supuestamente en el 2007 en Silicón Valley, crea una primera computadora cuántica comercial de 16-qubits de propósito general; luego la misma compañía admitió que tal máquina llamada Orión no es realmente una Computadora Cuántica, sino una clase de máquina de propósito general que usa algo de mecánica cuántica para resolver problemas. La que costa de un hardware para computación cuántica qué sería el ideal. Cuántica para realizar cada uno de los procesos que el sistema requiere el cual debe cumplir con unas condiciones de poder inicializarse en un estado de partida conocido y controlado.
    Ha de ser posible hacer manipulaciones a los qubits de forma controlada, con un conjunto de operaciones que forme un conjunto universal de puertas lógicas para poder reproducir a cualquier otra puerta lógica posible.
    El sistema ha de mantener su coherencia cuántica a lo largo del experimento.
    Ha de poder leerse el estado final del sistema, tras el cálculo.
    El sistema ha de ser escalable: tiene que haber una forma definida de aumentar el número de qubits, para tratar con problemas de mayor coste computacional.
    En cuanto a procesadores científicos del Instituto de Física aplicada de la Universidad de Bonn publicaron resultados sobre un registro cuántico experimental. Para ello utilizaron átomos neutros que almacenan información cuántica, por lo que son llamados qubits por analogía con los bits. Su objetivo actual es construir una puerta cuántica, con lo cual se tendrían los elementos básicos que constituyen los procesadores, que son el corazón de los computadores actuales. Cabe destacar que un chip de tecnología VLSI contiene actualmente más de 100.000 puertas, de manera que su uso práctico todavía se presenta en un horizonte lejano.
    El Software serán Los algoritmos cuánticos se basan en un margen de error conocido en las operaciones de base y trabajan reduciendo el margen de error a niveles exponencialmente pequeños, comparables al nivel de error de las máquinas actuales.
    • Algoritmo de Shor
    • Algoritmo de Grover
    • Algoritmo de Deutsch-Jozsa

  28. cristina argenis said

    COMPUTADORES CUANTICOS
    (Ensayo)

    Para dar opiniones sobre tecnología, lo primero que debemos hacer es fundamentarnos bien sobre el tema del cual se va a exponer, en este caso el tema el cual se relaciona en estas paginas y como lo dice el titulo es Computadores cuánticos.
    Teoría cuántica es la teoría física basada en la utilización del concepto de unidad cuántica para describir las propiedades dinámicas de las partículas subatómicas y las interacciones entre la materia y la radiación.
    La computación cuántica es un modelo de computación distinto al de la computación clásica. Se basa en el uso de qubits en lugar de bits, y da lugar a nuevas puertas lógicas que hacen posibles nuevas notaciones.
    Como ya se sabe una puerta lógica es un circuito que sustituyen a la caja negra estableciendo una relación lógica determinada entre las entregas que reciben y las salidas que emiten.
    Un gubit al igual que un bit puede estar en dos estados 0 y 1, y se diferencia del bit debido a las propiedades de la mecánica cuantica.
    Un qubit que contiene los valores cero y uno a la vez se dice que está en superposición de los estados cero y uno. Este estado de superposición es persistente hasta que el qubit es externamente medido.
    Al medir un qubit, su estado se ve forzado a tomar un solo valor. Porque la medición determina el valor del qubit, los posibles estados que existen deben describirse antes de realizar la medición en términos de su probabilidad de ocurrencia.

    Una misma tarea puede tener diferente complejidad en computación clásica y en computación cuántica, lo que ha dado lugar a un gran interés, ya que algunos problemas que no se pueden tratar pasan a ser tratados. Mientras un computador clásico equivale a una máquina de turing, un computador cuántico equivale a una máquina de turing in determinista.
    Orión como se llama la computadora que fue presentada por la empresa canadiense D wave System el 17 de febrero de 2007, se dice que no es realmente una Computadora Cuántica, sino una clase de máquina de propósito general que usa algo de mecánica cuántica para resolver problemas.
    Un computador quántico hace referencia a una maquina de Turíng in determinista, lo que quiere decir es que independiente.
    Los computadores cuánticos usarán los estados cuánticos del átomo para representar la información. Diseño y Construcción de Coprocesadores de cálculo Complejo.
    Retos de la Computación Cuántica: Controlar los Estados Cuánticos deseados
    Mantener superposición de estados, Lectura de los resultados
    Los Computadores Cuánticos poseen una Capacidad de cálculos Paralelos Naturales y Masivo en espacio y tiempo.
    Los computadores cuánticos, proponen un nuevo enfoque para encriptación. Control absoluto de seguridad a nivel de comunicación
    Las dificultades de la computación cuántica quedan en las mismas leyes de la mecánica cuántica que harían que un computador cuántico sea realizable. La computación cuántica es un campo rico y poco explorado en el que aún estamos descubriendo como hacer las cosas.
    Al rebasar cierta escala de miniaturización, el tamaño de los componentes electrónicos se convierte en un problema: los conductores atascados y los transistores apenas funcionan. Por fortuna, nuevos diseños circuitales ultra pequeños, basados en efectos de la Mecánica Cuántica, manejan los datos con mayor fiabilidad.
    Por muy pequeños que sean los circuitos que se logran por las distintas técnicas de miniaturización dentro de los chips, todavía son enormes agregados de átomos. Nuevas tecnologías de Computación (Computación Cuántica) podrían operar a escalas menores, posiblemente a nivel molecular e incluso atómico. La Computación Cuántica, presenta una alternativa al problema de la miniaturización, mostrando la manera de implementar Compuertas Lógico-Cuánticas, componentes esenciales para el diseño de una Computadora del Futuro. También proporciona otro paradigma con diferentes rasgos mucho más poderosos (Superposición Coherente – Enlazamiento) que los establecidos en la Teoría Computacional Clásica. Transistores apenas funcionan. Por fortuna, nuevos diseños circuitales ultra pequeños, basados en efectos de la Mecánica Cuántica, manejan los datos con mayor fiabilidad.
    Por muy pequeños que sean los circuitos que se logran por las distintas técnicas de miniaturización dentro de los chips, todavía son enormes agregados de átomos. Nuevas tecnologías de Computación (Computación Cuántica) podrían operar a escalas menores, posiblemente a nivel molecular e incluso atómico.
    La Computación Cuántica, presenta una alternativa al problema de la miniaturización, mostrando la manera de implementar Compuertas Lógico-Cuánticas, componentes esenciales para el diseño de una Computadora del Futuro. También proporciona otro paradigma con diferentes rasgos mucho más poderosos (Superposición Coherente – Enlazamiento) que los establecidos en la Teoría Computacional Clásica.

  29. SILVIA CORAL ZAMBRANO said

    COMPUTACION CUÁNTICA
    Hoy en día muchas empresas planean construir un sistema mas avanzado para el manejo de la información computacional de allí se nace la computación cuántica en un sistema llamado Orión. Por lo cual creo que puede ser entonces interesante analizar detenidamente qué es la computación cuántica que beneficios y desventajas nos pueden dejar, es necesario empezar hacer una preámbulo que nos ayude a entender el hecho en el que los computadores cuánticos pueden ser útiles en nuestro trabajo, estudio y en general en nuestra vida cotidiana.
    Basándose en forma general de lo que se conoce a cerca de la computación cuántica, con las máquinas de Turín (MT). Una MT es un modelo formal del concepto de algoritmo, que podemos imaginar como un dispositivo capaz de leer y escribir símbolos en unos procesos lógico-matemáticos a grandes velocidades.
    La computación cuántica es un modelo de computación distinto al de la computación clásica. Se basa en el uso de qubits en lugar de bits, y da lugar a nuevas puertas lógicas que hacen posibles nuevos algoritmos. Una misma tarea puede tener diferente complejidad en computación clásica y en computación cuántica.
    La empresa canadiense D-Wave System crea la primera computadora cuántica comercial de 16-qubits de propósito general; luego la misma compañía admitió que tal máquina llamada Orión no es realmente una Computadora Cuántica, sino una clase de máquina de propósito general que usa algo de mecánica cuántica para resolver problemas. De lo cual se puede decir que este sistema no se encuentra totalmente desarrollado.
    Aún no se ha resuelto el problema de qué hardware sería el ideal para la computación cuántica, se ha definido una serie de condiciones que debe cumplir. Ha de ser posible hacer manipulaciones a los qubits de forma controlada, con un conjunto de operaciones que forme un conjunto universal de puertas lógicas para poder reproducir a cualquier otra puerta lógica posible.
    El sistema ha de mantener su coherencia cuántica a lo largo del experimento.
    Ha de poder leerse el estado final del sistema, tras el cálculo.
    El sistema ha de ser escalable: tiene que haber una forma definida de aumentar el número de qubits, para tratar con problemas de mayor coste computacional.
    Los procesadores, que son el corazón de los computadores actuales. Cabe destacar que un chip de tecnología VLSI contiene actualmente más de 100.000 puertas, de manera que su uso práctico todavía se presenta en un horizonte lejano.
    En cuanto al software Los algoritmos cuánticos se basan en un margen de error conocido en las operaciones de base y trabajan reduciendo el margen de error a niveles exponencialmente pequeños, comparables al nivel de error de las máquinas actuales.
    Las computadoras han ido duplicando su velocidad cada dos años, al tiempo que el tamaño de sus componentes se reducía a la mitad. Los circuitos actuales contienen transistores y líneas de conducción cuya anchura es sólo una centésima parte de la de un cabello humano. Las máquinas de nuestros días son millones de veces más potentes que sus rudimentarias antepasados a causa de tan explosivo progreso.
    El incremento del poder de las computadoras se debe esencialmente a la miniaturización incesante del componente más elemental de la computadora, el transistor. Cuando los transistores se reducen de tamaño y se logran integrar en un solo microchip se incrementa el poder computacional. Sin embargo, las técnicas de integración de microcircuitos están empezando a tropezar con sus límites.

  30. Laura said

    Hola a todos, nos parecieron muy interesantes muchas de las cosas que leimos. Sobre todo una aclaración de Iabal, donde citaba el ejemplo del while true … Lo que si tenemos es una gran duda con respecto a la noción de computable.
    En un paper de Gandy (“Church’s thesis and principles for mechanisms”) enuncia la tesis de Church así: “lo que es efectivamente calculable es computable” y aclara que la palabra efectivo en la tesis sirve para enfatizar que el proceso de cálculo es determinístico y debe terminar después de cierto tiempo. Sumarizando, el while true es un procedimiento que es programable en una maquina de Turing pero no es un procedimiento efectivo (algoritmo) porque no para, entonces la pregunta es :¿no es computable?
    Por otro lado, otra de las interpretaciones de la tesis de church-turing se refiere a su relación con las funciones parciales: “Todas las funciones recursivas parciales son computables por una MT”.
    Pero si la función es recursiva parcial, en la parte divergente de la función (o en la que no está definida la función) no retorna ningún valor..entonces la parcialidad no sería computable..
    La idea entonces de la tesis de church es que no se ha encontrado una función recursiva parcial que no pueda ser computada por una máquina de turing, pero aquí se centra en la parte total de la función, sin considerar la divergencia…

    Como verán, tenemos semejante embrollo en la cabeza.

  31. [...] Artículo de Interés: Lo que la computación cuántica no puede hacer por nosotros [...]

Lo siento, el formulario de comentarios está cerrado en este momento.

 
%d personas les gusta esto: