Cómo funcionan las computadoras cuánticas. Armando el rompecabezas
Computadoras cuánticas y computación cuántica - nuevo palabra pegadiza, que se agregó a nuestro espacio de información junto con inteligencia artificial, aprendizaje automático y otros términos de alta tecnología. Al mismo tiempo, nunca pude encontrar en Internet material que pudiera armar el rompecabezas en mi cabeza llamado "Cómo funcionan las computadoras cuánticas". Sí, hay muchos trabajos excelentes, incluso sobre Habr (ver. Lista de recursos), comentarios que, como suele ser el caso, son aún más informativos y útiles, pero la imagen en mi cabeza, como suele decirse, no cuadraba.
Y recientemente mis colegas se me acercaron y me preguntaron: “¿Entiendes cómo funciona una computadora cuántica? ¿Puedes decirnos?" Y luego me di cuenta de que no soy el único que tiene problemas para armar una imagen coherente en mi cabeza.
Como resultado, se intentó compilar información sobre computadoras cuánticas en un circuito lógico consistente en el que Nivel básico, sin una inmersión profunda en las matemáticas y la estructura del mundo cuántico.Se explicó qué es un ordenador cuántico, con qué principios funciona y a qué problemas se enfrentan los científicos a la hora de crearlo y utilizarlo.
El autor no es un experto en computación cuántica y El público objetivo del artículo son los mismos informáticos, no los especialistas cuánticos., quienes también quieren armar en sus cabezas una imagen llamada “Cómo funcionan las computadoras cuánticas”. Debido a esto, muchos conceptos en el artículo se simplifican deliberadamente para comprender mejor las tecnologías cuánticas en un nivel "básico", pero sin una simplificación muy fuerte con pérdida de contenido y adecuación de la información.
El artículo en algunos lugares utiliza materiales de otras fuentes, una lista de los cuales se proporciona al final del artículo. Siempre que sea posible, se insertan enlaces directos e indicaciones al texto, tabla o figura original. Si olvidé algo (o alguien) en algún lado, escribe y lo corrijo.
En este capítulo, veremos brevemente cómo comenzó la era cuántica, cuál fue la razón que motivó la idea de una computadora cuántica, quiénes (qué países y corporaciones) son actualmente los principales actores en este campo, y también hablaremos brevemente sobre las principales direcciones del desarrollo de la computación cuántica.
Se considera que el punto de partida de la era cuántica es 1900, cuando M. Planck propuso por primera vez hipótesis esa energía se emite y absorbe no continuamente, sino en cuantos (porciones) separados. La idea fue recogida y desarrollada por muchos científicos destacados de la época: Bohr, Einstein, Heisenberg, Schrödinger, lo que finalmente condujo a la creación y desarrollo de una ciencia como la física cuántica. Hay muchos buenos materiales en Internet sobre la formación de la física cuántica como ciencia, en este artículo no nos detendremos en esto en detalle, pero era necesario indicar la fecha en que ingresamos a la nueva era cuántica.
La física cuántica ha introducido muchos inventos y tecnologías en nuestra vida cotidiana, sin los cuales ahora es difícil imaginar el mundo que nos rodea. Por ejemplo, un láser, que ahora se utiliza en todas partes, desde electrodomésticos (niveles láser, etc.) hasta sistemas de alta tecnología (láseres para corregir la visión, hola meklón ). Sería lógico suponer que tarde o temprano a alguien se le ocurrirá la idea de por qué no utilizar sistemas cuánticos para la informática. Y luego, en 1980, sucedió.
Wikipedia indica que la primera idea de la computación cuántica fue expresada en 1980 por nuestro científico Yuri Manin. Pero realmente no se empezó a hablar de ello hasta 1981, cuando el conocido R. Feynman charla en la primera Conferencia de Física Computacional celebrada en el MIT, señaló que es imposible simular de manera eficiente la evolución de un sistema cuántico en una computadora clásica. Propuso un modelo elemental. computadora cuántica, que podrá realizar dicho modelado.
Como ves, han pasado 17 años (de 1981 a 1998) desde el momento de la idea hasta su primera implementación en un ordenador de 2 qubits, y 21 años (de 1998 a 2019) hasta que el número de qubits aumentó hasta 53. Fueron necesarios 11 años (de 2001 a 2012) para mejorar el resultado del algoritmo de Shor (lo veremos con más detalle más adelante) del número 15 al 21. Además, hace sólo tres años llegamos al punto de implementar lo que habló Feynman y aprender a modelar los sistemas físicos más simples.
El desarrollo de la computación cuántica es lento. Los científicos e ingenieros se enfrentan a tareas muy difíciles, los estados cuánticos son de vida muy corta y frágiles, y para conservarlos el tiempo suficiente para realizar los cálculos, tienen que construir sarcófagos por valor de decenas de millones de dólares, en los que se mantiene la temperatura. justo por encima del cero absoluto y que están máximamente protegidos de influencias externas. A continuación hablaremos de estas tareas y problemas con más detalle.
Todos los países tecnológicamente exitosos están actualmente desarrollando activamente tecnologías cuánticas. En esta investigación se invierte una enorme cantidad de dinero y se crean programas especiales para apoyar las tecnologías cuánticas.
En la carrera cuántica participan no sólo los estados, sino también las empresas privadas. En total, Google, IBM, Intel y Microsoft han invertido recientemente alrededor de 0,5 millones de dólares en el desarrollo de ordenadores cuánticos y han creado grandes laboratorios y centros de investigación.
Hay muchos artículos sobre Habré y en Internet, por ejemplo, aquí, aquí и aquí, en el que se examina con más detalle la situación actual del desarrollo de las tecnologías cuánticas en diferentes países. Lo principal para nosotros ahora es que todos los países y actores líderes tecnológicamente desarrollados están invirtiendo enormes cantidades de dinero en investigación en esta dirección, lo que da esperanzas de una salida al actual estancamiento tecnológico.
Por el momento (puede que me equivoque, corríjanme), los principales esfuerzos (y resultados más o menos significativos) de todos los actores destacados se concentran en dos áreas:
Computadoras cuánticas especializadas, que tienen como objetivo resolver un problema específico específico, por ejemplo, un problema de optimización. Un ejemplo de producto son las computadoras cuánticas D-Wave.
Computadoras cuánticas universales — que son capaces de implementar algoritmos cuánticos arbitrarios (Shor, Grover, etc.). Implementaciones de IBM, Google.
Otros vectores de desarrollo que nos brinda la física cuántica, como por ejemplo:
Lo más importante que hay que entender en esta sección es que
Computadora cuántica (a diferencia de lo habitual) usos como soportes de información objetos cuánticos, y para realizar cálculos, los objetos cuánticos deben estar conectados en sistema cuántico.
¿Qué es un objeto cuántico?
Objeto cuántico - un objeto del micromundo (mundo cuántico) que exhibe propiedades cuánticas:
Tiene un estado definido con dos niveles límite.
Está en una superposición de su estado hasta el momento de la medición.
Se entrelaza con otros objetos para crear sistemas cuánticos.
Satisface el teorema de no clonación (el estado de un objeto no se puede copiar)
Veamos cada propiedad con más detalle:
Tiene un estado definido con dos niveles límite (estado final)
Un ejemplo clásico del mundo real es una moneda. Tiene un estado "lateral", que adopta dos niveles límite: "cara" y "cruz".
Está en una superposición de su estado hasta el momento de la medición.
Lanzaron una moneda, ésta vuela y gira. Mientras gira, es imposible decir en cuál de los niveles límite se encuentra su estado "lateral". Pero tan pronto como lo cerramos y miramos el resultado, la superposición de estados inmediatamente colapsa en uno de los dos estados fronterizos: "cara" y "cruz". Dar una palmada a una moneda en nuestro caso es una medida.
Se entrelaza con otros objetos para crear sistemas cuánticos.
Es difícil con una moneda, pero intentémoslo. Imagina que lanzamos tres monedas para que giren pegadas una a la otra, esto es hacer malabarismos con monedas. En cada momento del tiempo, no sólo cada uno de ellos está en una superposición de estados, sino que estos estados se influyen mutuamente (las monedas chocan).
Satisface el teorema de no clonación (el estado de un objeto no se puede copiar)
Mientras las monedas vuelan y giran, no hay manera de que podamos crear una copia del estado de giro de cualquiera de las monedas, separada del sistema. El sistema vive dentro de sí mismo y es muy celoso de liberar cualquier información al mundo exterior.
Algunas palabras más sobre el concepto en sí. “superposiciones”, en casi todos los artículos la superposición se explica como “está en todos los estados al mismo tiempo”, lo cual es cierto, por supuesto, pero a veces innecesariamente confuso. Una superposición de estados también se puede imaginar como el hecho de que en cada momento un objeto cuántico tiene Hay ciertas probabilidades de colapsar en cada uno de sus niveles límite y, en suma, estas probabilidades son naturalmente iguales a 1.. Más adelante, al considerar el qubit, nos detendremos en esto con más detalle.
En el caso de las monedas, esto se puede visualizar: dependiendo de la velocidad inicial, el ángulo de lanzamiento, el estado del entorno en el que vuela la moneda, en cada momento la probabilidad de obtener “cara” o “cruz” es diferente. Y, como se mencionó anteriormente, el estado de dicha moneda voladora puede imaginarse como “estar en todos sus estados fronterizos al mismo tiempo, pero con diferentes probabilidades de su implementación”.
Cualquier objeto que cumpla las propiedades anteriores y que podamos crear y controlar puede utilizarse como portador de información en una computadora cuántica.
Un poco más adelante hablaremos sobre la situación actual con la implementación física de los qubits como objetos cuánticos y lo que los científicos están utilizando ahora en esta capacidad.
Entonces, la tercera propiedad establece que los objetos cuánticos pueden entrelazarse para crear sistemas cuánticos. ¿Qué es un sistema cuántico?
sistema cuántico — un sistema de objetos cuánticos entrelazados con las siguientes propiedades:
Un sistema cuántico se encuentra en una superposición de todos los estados posibles de los objetos que lo componen.
Es imposible conocer el estado del sistema hasta el momento de la medición.
En el momento de la medición, el sistema implementa una de las posibles variantes de sus estados límite.
(y, mirando un poco hacia adelante)
Corolario de los programas cuánticos:
Un programa cuántico tiene un estado dado del sistema en la entrada, una superposición en el interior, una superposición en la salida.
A la salida del programa después de la medición tenemos una implementación probabilística de uno de los posibles estados finales del sistema (más posibles errores)
Cualquier programa cuántico tiene una arquitectura de chimenea (entrada -> salida. No hay bucles, no se puede ver el estado del sistema en medio del proceso).
Comparación de una computadora cuántica y una convencional
Comparemos ahora una computadora convencional y una cuántica.
computadora normal
Computadora cuántica
Lógica
0 / 1
`a|0> + b|1>, a^2+b^2=1`
La física
Transistor semiconductor
Objeto cuántico
Portador de información
Niveles de voltaje
Polarización, giro,…
operaciones
NO, Y, O, XOR sobre bits
Válvulas: CNOT, Hadamard,…
Interconexión
chip semiconductor
Confusión entre sí
Algoritmos
Estándar (ver Látigo)
Especiales (costa, Grover)
principio
Digital, determinista
Analógico, probabilístico
nivel lógico
En una computadora normal esto es un poco. Bien conocido por nosotros de principio a fin. bit determinista. Puede tomar valores de 0 o 1. Se adapta perfectamente al papel. unidad lógica para una computadora normal, pero es completamente inadecuado para describir el estado objeto cuántico, que, como ya hemos dicho, en estado salvaje se encuentra ensuperposiciones de sus estados fronterizos.
Esto es lo que se les ocurrió cúbit. En sus estados límite realiza estados similares a 0 y 1 |0> y |1>, y en superposición representa distribución de probabilidad sobre sus estados límite|0> и |1>:
a|0> + b|1>, такое, что a^2+b^2=1
a y b representan amplitudes de probabilidad, y los cuadrados de sus módulos son las probabilidades reales de obtener exactamente esos valores de los estados límite |0> и |1>, si colapsas el qubit con una medición ahora mismo.
Nivel fisico
En el nivel actual de desarrollo tecnológico, la implementación física de un bit para una computadora convencional es transistor semiconductor, para cuántico, como ya hemos dicho, cualquier objeto cuántico. En la siguiente sección hablaremos de lo que se utiliza actualmente como medio físico para los qubits.
Medio de almacenamiento
Para una computadora normal esto es electricidad - niveles de voltaje, presencia o ausencia de corriente, etc., para cuantos - lo mismo estado de un objeto cuántico (dirección de polarización, espín, etc.), que pueden estar en estado de superposición.
operaciones
Para implementar circuitos lógicos en una computadora normal, utilizamos conocidos operaciones lógicas, para las operaciones en qubits fue necesario idear un sistema de operaciones completamente diferente, llamado puertas cuánticas. Las puertas pueden ser de un solo qubit o de dos qubits, dependiendo de cuántos qubits se estén convirtiendo.
Ejemplos de puertas cuánticas:
Hay un concepto juego de válvulas universales, que son suficientes para realizar cualquier cálculo cuántico. Por ejemplo, un conjunto universal incluye una puerta de Hadamard, una puerta de cambio de fase, una puerta CNOT y una puerta π⁄8. Con su ayuda, es posible realizar cualquier cálculo cuántico en un conjunto arbitrario de qubits.
En este artículo no nos detendremos en detalle en el sistema de puertas cuánticas; puede leer más sobre ellas y las operaciones lógicas en qubits, por ejemplo, aquí. Lo principal para recordar:
Las operaciones sobre objetos cuánticos requieren la creación de nuevos operadores lógicos (puertas cuánticas)
Las puertas cuánticas vienen en tipos de qubit simple y de qubit doble.
Existen conjuntos universales de puertas que se pueden utilizar para realizar cualquier cálculo cuántico.
Interconexión
Un transistor es completamente inútil para nosotros; para realizar cálculos necesitamos conectar muchos transistores entre sí, es decir, crear un chip semiconductor a partir de millones de transistores sobre el cual construir circuitos lógicos. ALU y, en definitiva, conseguir un procesador moderno en su forma clásica.
Un qubit también es completamente inútil para nosotros (bueno, aunque solo sea en términos académicos),
para realizar cálculos necesitamos un sistema de qubits (objetos cuánticos)
que, como ya hemos dicho, se crea entrelazando qubits entre sí para que los cambios en sus estados se produzcan de forma coordinada.
Algoritmos
Los algoritmos estándar que la humanidad ha acumulado hasta la fecha son completamente inadecuados para implementarse en una computadora cuántica. Sí, en general no es necesario. Las computadoras cuánticas basadas en lógica de puerta sobre qubits requieren la creación de algoritmos completamente diferentes: algoritmos cuánticos. De los algoritmos cuánticos más conocidos se pueden distinguir tres:
Y la diferencia más importante es el principio de funcionamiento. Para una computadora estándar esto es Principio digital, estrictamente determinista., basado en el hecho de que si establecemos algún estado inicial del sistema y lo pasamos a través de un algoritmo determinado, entonces el resultado de los cálculos será el mismo, sin importar cuántas veces ejecutemos este cálculo. En realidad, este comportamiento es exactamente lo que esperamos de una computadora.
La computadora cuántica funciona principio analógico, probabilístico. El resultado de un algoritmo dado en un estado inicial dado es muestra de una distribución de probabilidad implementaciones finales del algoritmo más posibles errores.
Esta naturaleza probabilística de la computación cuántica se debe a la esencia misma probabilística del mundo cuántico. "Dios no juega a los dados con el universo"., decía el viejo Einstein, pero todos los experimentos y observaciones hasta ahora (en el paradigma científico actual) confirman lo contrario.
Como ya hemos dicho, un qubit puede representarse mediante un objeto cuántico, es decir, un objeto físico que implementa las propiedades cuánticas descritas anteriormente. Es decir, en términos generales, cualquier objeto físico en el que haya dos estados y estos dos estados estén en estado de superposición puede usarse para construir una computadora cuántica.
“Si podemos colocar un átomo en dos niveles diferentes y controlarlos, entonces tenemos un qubit. Si podemos hacer esto con un ion, es un qubit. Lo mismo ocurre con la corriente. Si lo hacemos funcionar en sentido horario y antihorario al mismo tiempo, tenemos un qubit”.(C)
Hay gran comentario к статье, en el que se analiza con más detalle la variedad actual de implementaciones físicas del qubit, simplemente enumeraremos las más conocidas y comunes:
De toda esta diversidad, el más desarrollado es el primer método de obtención de qubits, basado en superconductores. Google, IBM, Intel y otros actores líderes lo utilizan para construir sus sistemas.
Entonces, imaginemos que tenemos la siguiente tarea:
Hay un grupo de tres personas: (A)ndrey, (B)olodya y (C)erezha. Hay dos taxis (0 y 1).
También se sabe que:
(A)ndrey, (B)olodya son amigos
(A)ndrey, (C)erezha son enemigos
(B)olodya y (C)erezha son enemigos
Tarea: Colocar personas en taxis para que max(amigos) и Mín (enemigos)
Оценка: L = (número de amigos) - (número de enemigos) para cada opción de alojamiento
IMPORTANTE: Suponiendo que no existen heurísticas, no existe una solución óptima. En este caso, el problema sólo puede solucionarse mediante una búsqueda completa de opciones.
Solución en una computadora normal.
Cómo resolver este problema en una (súper) computadora (o clúster) normal: está claro que necesitas recorrer todas las opciones posibles. Si tenemos un sistema multiprocesador, podemos paralelizar el cálculo de soluciones en varios procesadores y luego recopilar los resultados.
Disponemos de 2 posibles opciones de alojamiento (taxi 0 y taxi 1) y 3 personas. Espacio de solución ^ = 2 3 8. Incluso puedes pasar por 8 opciones usando una calculadora, esto no es un problema. Ahora compliquemos el problema: tenemos 20 personas y dos autobuses, la solución es espacial. 2^20 = 1. Nada complicado tampoco. Aumentemos el número de personas 2.5 veces: tomemos 50 personas y dos trenes, el espacio de la solución ahora es 2^50 = 1.12 x 10^15. Una (super)computadora común y corriente ya está empezando a tener serios problemas. Aumentemos el número de personas 2 veces, ya nos darán 100 personas. 1.2 x 10 ^ 30 opciones posibles.
Eso es todo, esta tarea no se puede calcular en un tiempo razonable.
Conexión de una supercomputadora
El ordenador más potente actualmente es el número 1 de Top500es Summit, productividad 122 Pflops. Supongamos que necesitamos 100 operaciones para calcular una opción, luego, para resolver el problema para 100 personas, necesitaremos:
(1.2x10^30 100) / 122×10^15 / (606024365) = 3 x 10^37 años.
Como vemos A medida que aumenta la dimensión de los datos iniciales, el espacio de solución crece según una ley de potencia., en el caso general, para N bits tenemos 2^N posibles opciones de solución, que para N relativamente pequeño (100) nos dan un espacio de solución no calculado (al nivel tecnológico actual).
¿Hay alguna alternativa? Como habrás adivinado, sí, lo hay.
Pero antes de analizar cómo y por qué las computadoras cuánticas pueden resolver eficazmente problemas como estos, tomemos un momento para recapitular en qué consisten. Distribución de probabilidad. No te alarmes, este es un artículo de revisión, aquí no habrá matemáticas difíciles, nos conformaremos con el ejemplo clásico con una bolsa y pelotas.
Sólo un poco de combinatoria, teoría de la probabilidad y un extraño experimentador.
Tomemos una bolsa y pongámosla en ella. 1000 bolas blancas y 1000 negras. Realizaremos un experimento: sacaremos la pelota, anotaremos el color, devolveremos la pelota a la bolsa y mezclaremos las bolas en la bolsa.
El experimento se realizó 10 veces, sacó 10 bolas negras. ¿Tal vez? Bastante. ¿Nos da esta muestra alguna idea razonable de la verdadera distribución en la bolsa? Obviamente no. Qué hay que hacer - correcto, pRepite el experimento un millón de veces y calcula las frecuencias de las bolas blancas y negras. Obtenemos, por ejemplo 49.95% negro y 50.05% blanco. En este caso, la estructura de la distribución de la que tomamos el muestreo (sacamos una bola) ya está más o menos clara.
Lo principal es entender que el experimento en sí tiene una naturaleza probabilística, con una muestra (bola) no sabremos la verdadera estructura de la distribución, Necesitamos repetir el experimento muchas veces. y promediar los resultados.
Agreguémoslo a nuestra bolsa. 10 bolas rojas y 10 verdes (errores). Repitamos el experimento 10 veces. ENsacó 5 rojos y 5 verdes. ¿Tal vez? Sí. Podemos decir algo sobre la verdadera distribución: no. Lo que hay que hacer, bueno, ya lo entiendes.
Para comprender la estructura de una distribución de probabilidad, es necesario muestrear repetidamente los resultados individuales de esta distribución y promediar los resultados.
Conectando la teoría con la práctica
Ahora, en lugar de bolas blancas y negras, tomemos bolas de billar y pongámoslas en una bolsa. 1000 bolas con el número 2, 1000 con el número 7 y 10 bolas con otros números. Imaginemos a un experimentador que está entrenado en las acciones más simples (sacar una pelota, anotar el número, volver a poner la pelota en la bolsa, mezclar las bolas en la bolsa) y lo hace en 150 microsegundos. Bueno, un experimentador de velocidad (¡¡¡no un anuncio de drogas !!!). Luego, en 150 segundos podrá realizar nuestro experimento 1 millón de veces. y proporcionarnos los resultados promedio.
Sentaron al experimentador, le dieron una bolsa, se dieron la vuelta, esperaron 150 segundos y recibieron:
número 2 - 49.5%, número 7 - 49.5%, los números restantes en total - 1%.
Sí, es cierto. nuestro bolso es una computadora cuántica con un algoritmo que resuelve nuestro problema, y las bolas son posibles soluciones. Como hay dos soluciones correctas, entonces una computadora cuántica nos dará cualquiera de estas posibles soluciones con igual probabilidad y 0.5% (10/2000) de error, del que hablaremos más adelante.
Para obtener el resultado de una computadora cuántica, es necesario ejecutar el algoritmo cuántico varias veces en el mismo conjunto de datos de entrada y promediar el resultado.
Escalabilidad de una computadora cuántica
Ahora imagina que para una tarea que involucra a 100 personas (espacio solución 2^100 recordamos esto), también hay sólo dos decisiones correctas. Luego, si tomamos 100 qubits y escribimos un algoritmo que calcula nuestra función objetivo (L, ver arriba) sobre estos qubits, obtendremos una bolsa en la que habrá 1000 bolas con el número de la primera respuesta correcta, 1000 con el número de la segunda respuesta correcta y 10 bolas con otros números. Y dentro de los mismos 150 segundos nuestro experimentador nos dará una estimación de la distribución de probabilidad de respuestas correctas..
El tiempo de ejecución de un algoritmo cuántico (con algunas suposiciones) puede considerarse constante O(1) con respecto a la dimensión del espacio de solución (2^N).
Y esta es precisamente la propiedad de una computadora cuántica: constancia del tiempo de ejecución En relación con la creciente ley de potencia, la complejidad del espacio de solución es la clave.
Qubit y mundos paralelos
¿Como sucedió esto? ¿Qué permite que una computadora cuántica realice cálculos tan rápido? Se trata de la naturaleza cuántica del qubit.
Mira, dijimos que un qubit es como un objeto cuántico. realiza uno de sus dos estados cuando se observa, pero en la “naturaleza salvaje” es en superposiciones de estados, es decir, se encuentra en ambos estados límite simultáneamente (con cierta probabilidad).
Tomar (A)ndreya e imagine su estado (en qué vehículo se encuentra: 0 o 1) como un qubit. Entonces tenemos (en el espacio cuántico) dos mundos paralelos, en uno (A) se sienta en el taxi 0, en otro mundo, en el taxi 1. En dos taxis al mismo tiempo, pero con cierta probabilidad de encontrarlo en cada uno de ellos durante la observación.
Tomar (B) joven e imaginemos también su estado como un qubit. Surgen otros dos mundos paralelos. Pero por ahora estos pares de mundos (A) и (B) no interactúes en absoluto. ¿Qué hay que hacer para crear? relacionados ¿sistema? Así es, necesitamos estos qubits atar (confundir). Lo tomamos y lo confundimos. (A) con (B) — obtenemos un sistema cuántico de dos qubits (A, B), realizando dentro de sí cuatro interdependiente mundos paralelos. Agregar (S)ergey y obtenemos un sistema de tres qubits (A B C), implementando ocho interdependiente mundos paralelos.
La esencia de la computación cuántica (la implementación de una cadena de puertas cuánticas sobre un sistema de qubits conectados) es el hecho de que el cálculo ocurre en todos los mundos paralelos simultáneamente.
Y no importa cuántos de ellos tengamos, 2^3 o 2^100, El algoritmo cuántico se ejecutará en un tiempo finito en todos estos mundos paralelos. y nos dará un resultado, que es una muestra de la distribución de probabilidad de las respuestas del algoritmo.
Para una mejor comprensión, uno puede imaginar que una computadora cuántica a nivel cuántico ejecuta 2 ^ N procesos de solución paralelos, cada uno de los cuales trabaja en una posible opción, luego recopila los resultados del trabajo y nos da la respuesta en forma de superposición de la solución (distribución de probabilidad de respuestas), de la cual tomamos muestras una cada vez (para cada experimento).
Recuerda el tiempo requerido por nuestro experimentador. (150 µs) Para realizar el experimento, esto nos será útil un poco más, cuando hablemos de los principales problemas de los ordenadores cuánticos y del tiempo de decoherencia.
Como ya se mencionó, los algoritmos convencionales basados en lógica binaria no son aplicables a una computadora cuántica que utiliza lógica cuántica (puertas cuánticas). Para él, era necesario idear otros nuevos que aprovecharan al máximo el potencial inherente a la naturaleza cuántica de la informática.
Los algoritmos más conocidos en la actualidad son:
A diferencia de los clásicos, los ordenadores cuánticos no son universales. Hasta ahora sólo se ha encontrado un pequeño número de algoritmos cuánticos.(C)
En este artículo no analizaremos en detalle los algoritmos cuánticos; en Internet hay muchos materiales excelentes para cualquier nivel de complejidad, pero aún necesitamos repasar brevemente los tres más famosos.
El algoritmo cuántico más famoso es algoritmo de shor (inventado en 1994 por el matemático inglés Peter Orilla), que tiene como objetivo resolver el problema de factorizar números en factores primos (problema de factorización, logaritmo discreto).
Es este algoritmo el que se cita como ejemplo cuando escriben que sus sistemas bancarios y sus contraseñas pronto serán pirateados. Teniendo en cuenta que la longitud de las claves utilizadas hoy en día es de nada menos que 2048 bits, aún no ha llegado el momento de poner un límite.
hoy resultados más que modesto. Mejores resultados de factorización con el algoritmo de Shor: números 15 и 21, que es mucho menos que 2048 bits. Para los resultados restantes de la tabla, una diferente el algoritmo cálculos, pero incluso el mejor resultado según este algoritmo (291311) está muy lejos de ser una aplicación real.
Puede leer más sobre el algoritmo de Shor, por ejemplo, aquí. Sobre la implementación práctica - aquí.
El algoritmo de Grover se puede utilizar para encontrar medianas и significado aritmetico serie numérica. Además, se puede utilizar para resolver NP-completo problemas mediante una búsqueda exhaustiva entre muchas soluciones posibles. Esto puede suponer un importante aumento de velocidad respecto a los algoritmos clásicos, aunque sin proporcionar "solución polinómica" en general.(C)
Puedes leer más aquíO aquí. Más aquí Hay una buena explicación del algoritmo usando el ejemplo de cajas y una pelota, pero, desafortunadamente, por razones que escapan a nuestro control, este sitio no se abre para mí desde Rusia. Si usted tiene este sitio también está bloqueado, así que aquí hay un breve resumen:
Algoritmo de Grover. Imagina que tienes N piezas de cajas cerradas numeradas. Todos están vacíos excepto uno, que contiene una pelota. Tu tarea: averiguar el número de la caja en la que se encuentra la bola (este número desconocido a menudo se denota con la letra w).
¿Cómo resolver este problema? La forma más estúpida es turnarse para abrir las cajas y, tarde o temprano, te encontrarás con una caja con una pelota. En promedio, ¿cuántas casillas deben marcarse antes de encontrar una casilla con una pelota? En promedio, necesitas abrir aproximadamente la mitad de N/2 cajas. Lo principal aquí es que si aumentamos el número de cajas 100 veces, entonces el número promedio de cajas que deben abrirse antes de encontrar la caja con la pelota también aumentará 100 veces.
Ahora hagamos una aclaración más. No abramos nosotros mismos las cajas con las manos y comprobemos la presencia de una bola en cada una, sino que hay un cierto intermediario, llamémosle Oráculo. Le decimos al Oráculo: "marque la casilla número 732", y el Oráculo honestamente verifica y responde: "no hay ninguna bola en la casilla número 732". Ahora, en lugar de decir cuántas cajas necesitamos abrir en promedio, decimos “cuántas veces en promedio debemos ir al Oráculo para encontrar el número de la caja con la pelota”
Resulta que si traducimos este problema con las cajas, la bola y el Oráculo al lenguaje cuántico, obtenemos un resultado notable: para encontrar el número de una caja con una bola entre N cajas, necesitamos perturbar al Oráculo sólo sobre SQRT. (N) veces!
Es decir, la complejidad de la tarea de búsqueda utilizando el algoritmo de Grover se reduce en la raíz cuadrada de los tiempos.
El problema de Deutsch-Jozsi consiste en determinar si una función de varias variables binarias F(x1, x2, ... xn) es constante (toma el valor 0 o 1 para cualquier argumento) o equilibrada (para la mitad del dominio se necesita el valor 0, para la otra mitad 1). En este caso, se considera conocido a priori que la función es constante o equilibrada.(C)
Aún puedes leer aquí. Una explicación más sencilla:
El algoritmo Deutsch (Deutsch-Jozsi) se basa en la fuerza bruta, pero permite hacerlo más rápido de lo habitual. Imagina que hay una moneda sobre la mesa y necesitas saber si es falsa o no. Para hacer esto, debe mirar la moneda dos veces y determinar: "cara" y "cruz" son reales, dos "cara", dos "cruces" son falsas. Entonces, si se utiliza el algoritmo cuántico de Deutsch, esta determinación se puede hacer de un vistazo: la medición.(C)
Al diseñar y operar ordenadores cuánticos, los científicos e ingenieros se enfrentan a una gran cantidad de problemas que hasta la fecha se han resuelto con distintos grados de éxito. De acuerdo a investigacion (y también aquí) se pueden identificar la siguiente serie de problemas:
Sensibilidad al medio ambiente e interacción con el medio ambiente.
Acumulación de errores durante los cálculos.
Dificultades con la inicialización inicial de los estados de qubit
Estado cuántico cosa muy frágilLos qubits en estado entrelazado son extremadamente inestables, cualquier influencia externa puede (y destruye) esta conexión. Un cambio de temperatura de la más mínima fracción de grado, la presión, un fotón aleatorio volando cerca: todo esto desestabiliza nuestro sistema.
Para solucionar este problema, se construyen sarcófagos de baja temperatura, en los que la temperatura (-273.14 grados Celsius) es ligeramente superior al cero absoluto, con el máximo aislamiento de la cámara interna con el procesador de todas (posibles) influencias del entorno externo.
La vida máxima de un sistema cuántico de varios qubits entrelazados, durante la cual conserva sus propiedades cuánticas y puede usarse para cálculos, se llama tiempo de decoherencia.
Actualmente, el tiempo de decoherencia en las mejores soluciones cuánticas es del orden de decenas y cientos de microsegundos.
Hay un maravilloso sitio webdonde puedes mirar tablas comparativas de parámetros de todos los sistemas cuánticos creados. Este artículo incluye solo dos procesadores superiores como ejemplos: de IBM IBM Q Sistema Uno y desde sicomoro de google. Como podemos observar, el tiempo de decoherencia (T2) no supera los 200 μs.
No encontré datos exactos sobre Sycamore, pero en la mayoría artículo sobre supremacía cuántica se dan dos números - 1 millón de cálculos en 200 segundos, en otro lugar - para 130 segundos sin pérdida de señales de control, etc.. En cualquier caso, esto nos da El tiempo de decoherencia es de aproximadamente 150 μs.. Recuerda nuestro experimentador con una bolsa? Bueno, aquí está.
Nombre del ordenador
N qubits
máximo emparejado
T2 (μs)
IBM Q Sistema Uno
20
6
70
sicomoro de google
53
4
~ 150-200
¿Con qué nos amenaza la decoherencia?
El principal problema es que después de 150 μs, nuestro sistema informático de N qubits entrelazados comenzará a generar ruido blanco probabilístico en lugar de una distribución probabilística de soluciones correctas.
Es decir, necesitamos:
Inicializar el sistema qubit
Realizar un cálculo (cadena de operaciones de puerta)
Leer resultado
Y haz todo esto en 150 microsegundos. No tuve tiempo, el resultado fue una calabaza.
Como dijimos, Los procesos cuánticos y la computación cuántica son de naturaleza probabilística., no podemos estar 100% seguros de nada, sólo con cierta probabilidad. La situación se agrava aún más por el hecho de que La computación cuántica es propensa a errores.. Los principales tipos de errores en la computación cuántica son:
Los errores de decoherencia son causados por la complejidad del sistema y la interacción con el entorno externo.
Errores computacionales de puerta (debido a la naturaleza cuántica del cálculo)
Errores en la lectura del estado final (resultado)
Errores asociados a la decoherencia., aparecen tan pronto como entrelazamos nuestros qubits y comenzamos a hacer cálculos. Cuantos más qubits entrelacemos, más complejo será el sistema, y más fácil será destruirlo. Sarcófagos de baja temperatura, cámaras protegidas, todos estos trucos tecnológicos tienen como objetivo precisamente reducir el número de errores y alargar el tiempo de decoherencia.
Errores computacionales de la puerta - cualquier operación (puerta) en qubits puede, con cierta probabilidad, terminar con un error, y para implementar el algoritmo necesitamos realizar cientos de puertas, así que imagina lo que obtenemos al final de la ejecución de nuestro algoritmo. La respuesta clásica a la pregunta es "¿Cuál es la probabilidad de encontrarnos con un dinosaurio en un ascensor?" - 50x50, o os encontraréis o no.
Para empeorar el problema, los métodos estándar de corrección de errores (duplicación de cálculos y promediación) no funcionan en el mundo cuántico debido al teorema de no clonación. Para error de corrección en la computación cuántica hubo que inventar métodos de corrección cuántica. En términos generales, tomamos N qubits ordinarios y creamos 1 de ellos. cúbit lógico con una menor tasa de error.
Pero aquí surge otro problema: número total de qubits. Mira, digamos que tenemos un procesador con 100 qubits, de los cuales 80 qubits se usan para corrección de errores, entonces solo nos quedan 20 para cálculos.
Errores al leer el resultado final — como recordamos, el resultado de los cálculos cuánticos se nos presenta en la forma distribución de probabilidad de respuestas. Pero la lectura del estado final también puede generar un error.
En el mismo sitio web Existen tablas comparativas de procesadores por niveles de error. A modo de comparación, tomemos los mismos procesadores que en el ejemplo anterior: IBM IBM Q Sistema Uno и sicomoro de google:
Módulo
Fidelidad de puerta de 1 Qubit
2-Fidelidad de la puerta Qubit
Fidelidad de lectura
IBM Q Sistema Uno
99.96%
98.31%
-
sicomoro de google
99.84%
99.38%
96.2%
es fidelidad es una medida de la similitud de dos estados cuánticos. La magnitud del error se puede expresar aproximadamente como 1-Fidelidad. Como podemos ver, los errores en las puertas de 2 qubits y los errores de lectura son el principal obstáculo para ejecutar algoritmos complejos y largos en las computadoras cuánticas existentes.
En teoría construimos y operamos circuitos de docenas de qubits entrelazados, en realidad todo es más complicado. Todos los chips (procesadores) cuánticos existentes están construidos de tal manera que proporcionan sin dolor entrelazamiento de un qubit solo con sus vecinos, de los cuales no hay más de seis.
Si necesitamos entrelazar el primer qubit, digamos, con el duodécimo, entonces tendremos que construir una cadena de operaciones cuánticas adicionales, implican qubits adicionales, etc., lo que aumenta el nivel de error general. Sí, y no te olvides de tiempo de decoherencia, tal vez cuando termines de conectar los qubits al circuito que necesitas, el tiempo terminará y todo el circuito se convertirá en bonito generador de ruido blanco.
Además, no olvides eso La arquitectura de todos los procesadores cuánticos es diferente, y el programa escrito en el emulador en el modo "conectividad total" deberá "recompilarse" en la arquitectura de un chip específico. incluso hay programas optimizadores especiales para realizar esta operación.
Conectividad máxima y número máximo de qubits para los mismos chips superiores:
Nombre del ordenador
N qubits
máximo emparejado
T2 (μs)
IBM Q Sistema Uno
20
6
70
sicomoro de google
53
4
~ 150-200
Y, a modo de comparación, tabla con datos de la generación anterior de procesadores. Compare la cantidad de qubits, el tiempo de decoherencia y la tasa de error con lo que tenemos ahora con la nueva generación. Aún así, el progreso es lento, pero avanza.
Por lo tanto:
Actualmente no existen arquitecturas completamente conectadas con > 6 qubits
Para entrelazar el qubit 0 en un procesador real, por ejemplo, el qubit 15 puede requerir varias docenas de operaciones adicionales
Más operaciones -> más errores -> mayor influencia de la decoherencia
La decoherencia es el lecho de Procusto de la computación cuántica moderna. Debemos encajar todo en 150 μs:
Inicialización del estado inicial de qubits.
Calcular un problema utilizando puertas cuánticas
Corregir errores para obtener resultados significativos
leer el resultado
Aunque hasta ahora los resultados son decepcionantes aquí afirman lograr un tiempo de retención de coherencia de 0.5 s en una computadora cuántica basada en trampas de iones:
Medimos un tiempo de coherencia de qubit superior a 0.5 s, y con el blindaje magnético esperamos que mejore hasta ser superior a 1000 s.
También puedes leer sobre esta tecnología. aquí o por ejemplo aquí.
La situación se complica aún más por el hecho de que al realizar cálculos complejos es necesario utilizar circuitos de corrección de errores cuánticos, lo que también consume tiempo y qubits disponibles.
Y finalmente, las arquitecturas modernas no permiten implementar esquemas de entrelazamiento mejores que 1 en 4 o 1 en 6 a un costo mínimo.
Para resolver los problemas anteriores, actualmente se utilizan los siguientes enfoques y métodos:
Uso de criocámaras con bajas temperaturas (10 mK (–273,14°C))
Usar unidades de procesador que estén máximamente protegidas contra influencias externas.
Uso de sistemas de corrección de errores cuánticos (Logic Qubit)
Uso de optimizadores al programar circuitos para un procesador específico
También se están realizando investigaciones encaminadas a aumentar el tiempo de decoherencia, buscar nuevas (y mejorar las conocidas) implementaciones físicas de objetos cuánticos, optimizar circuitos de corrección, etc., etc. Hay avances (mira arriba las características de los chips de gama alta anteriores y actuales), pero hasta ahora es lento, muy, muy lento.
Computadora D-Wave 2000Q de 2000 qubits. Fuente: D-Wave Systems
En medio del anuncio de Google de lograr la supremacía cuántica utilizando un procesador de 53 qubit, ordenadores и anuncios de la empresa D-Wave, en el que el número de qubits es de miles, resulta algo confuso. Bueno, realmente, si 53 qubits fueron capaces de alcanzar la supremacía cuántica, entonces ¿de qué es capaz una computadora con 2048 qubits? Pero no todo es tan bueno...
En resumen (tomado de la wiki):
Компьютеры D-Wave trabajar según el principio relajación cuántica (recocido cuántico), pueden resolver una subclase muy limitada de problemas de optimización y no son adecuados para implementar algoritmos cuánticos y puertas cuánticas tradicionales.
Para más detalles puedes leer, por ejemplo, aquí, aquí (cuidado, es posible que no se abra desde Rusia), o De Scott Aaronson в статье de su Blog. Por cierto, recomiendo mucho leer su blog en general, hay mucho material bueno allí.
En general, desde el comienzo de los anuncios, la comunidad científica tuvo dudas sobre las computadoras D-Wave. Por ejemplo, en 2014, IBM cuestionó el hecho de que D-Wave Utiliza efectos cuánticos. Llegó al punto que en 2015 Google, junto con la NASA, compró una de estas computadoras cuánticas y después de una investigación confirmadoEso sí, el ordenador funciona y calcula el problema más rápido que uno normal. Puedes leer más sobre el comunicado de Google aquí y por ejemplo aquí.
Lo principal es que las computadoras D-Wave, con sus cientos y miles de qubits, no pueden usarse para calcular y ejecutar algoritmos cuánticos. No puedes ejecutar el algoritmo de Shor en ellos, por ejemplo. Lo único que pueden hacer es utilizar ciertos mecanismos cuánticos para resolver un determinado problema de optimización. Podemos considerar que D-Wave es un ASIC cuántico para una tarea específica.
Un poco sobre la emulación de computadoras cuánticas
La computación cuántica se puede emular en una computadora normal. En efecto, Ver:
El estado del qubit puede ser представитьNúmero complejo, ocupando de 2x32 a 2x64 bits (8-16 bytes) dependiendo de la arquitectura del procesador
El estado de N qubits conectados se puede representar como 2^N números complejos, es decir 2^(3+N) para arquitectura de 32 bits y 2^(4+N) para 64 bits.
Una operación cuántica en N qubits se puede representar mediante una matriz de 2^N x 2^N
Entonces:
Para almacenar los estados emulados de 10 qubits se necesitan 8 KB
Para almacenar los estados de 20 qubits necesitas 8 MB
Para almacenar los estados de 30 qubits se necesitan 8 GB
Se necesitan 40 Terabytes para almacenar los estados de 8 qubits
Para almacenar los estados de 50 qubits se necesitan 8 Petabytes, etc.
El límite de la simulación de una computadora cuántica en sistemas clásicos está determinado por la cantidad de RAM necesaria para almacenar el estado de los qubits.
Por operación: para una emulación precisa de un circuito de 49 qubits que consta de unos 39 "ciclos" (capas independientes de puertas) Tomó 2^63 multiplicaciones complejas: 4 Pflops de una supercomputadora durante 4 horas
Emular una computadora cuántica de más de 50 qubits en sistemas clásicos se considera imposible en un tiempo razonable. Esta es también la razón por la que Google utilizó un procesador de 53 qubits para su experimento de supremacía cuántica.
Wikipedia nos da la siguiente definición de supremacía de la computación cuántica:
Supremacía cuántica - habilidad computación cuántica dispositivos para resolver problemas que las computadoras clásicas prácticamente no pueden resolver.
De hecho, lograr la supremacía cuántica significa que, por ejemplo, la factorización de grandes números utilizando el algoritmo de Shor se puede resolver en el tiempo adecuado, o se pueden emular moléculas químicas complejas a nivel cuántico, etc. Es decir, ha llegado una nueva era.
Pero hay una laguna en la redacción de la definición: “que los ordenadores clásicos prácticamente no pueden resolver" De hecho, esto significa que si crea una computadora cuántica de más de 50 qubits y ejecuta algún circuito cuántico en ella, entonces, como comentamos anteriormente, el resultado de este circuito no se puede emular en una computadora normal. Eso es una computadora clásica no podrá recrear el resultado de tal circuito.
Así, en octubre de 2019, los desarrolladores de Google publicaron un artículo en la publicación científica Nature “Supremacía cuántica utilizando un procesador superconductor programable" Los autores anunciaron el logro de la supremacía cuántica por primera vez en la historia utilizando el procesador Sycamore de 54 qubits.
Los artículos de Sycamore en línea a menudo se refieren a un procesador de 54 qubit o a un procesador de 53 qubit. La verdad es que según artículo original, el procesador consta físicamente de 54 qubits, pero uno de ellos no funciona y ha sido puesto fuera de servicio. Así, en realidad tenemos un procesador de 53 qubit.
El equipo de computación cuántica de IBM declaró más tarde que Google informó falsamente haber logrado la supremacía cuántica. La empresa afirma que un ordenador convencional podrá realizar esta tarea en el peor de los casos en dos días y medio y la respuesta resultante será más precisa que la de un ordenador cuántico. Esta conclusión se llegó a partir de los resultados de un análisis teórico de varios métodos de optimización.
¿Qué hizo realmente Google? Para una comprensión detallada, lea Aaronson, pero brevemente aquí:
Por supuesto que puedo decírtelo, pero me siento bastante estúpido. El cálculo es el siguiente: el experimentador genera un circuito cuántico aleatorio C (es decir, una secuencia aleatoria de puertas de 1 qubit y 2 qubit entre vecinos más cercanos, con una profundidad de, por ejemplo, 20, que actúa sobre una red 2D de n = 50-60 cúbits). Luego, el experimentador envía C a la computadora cuántica y le pide que aplique C a un estado inicial de 0, mida el resultado en la base {0,1}, envíe de vuelta una secuencia observada de n bits (cadena) y repita varias miles o millones de veces. Finalmente, utilizando su conocimiento de C, el experimentador realiza una prueba estadística para ver si el resultado coincide con la salida esperada de la computadora cuántica.
Muy corto:
Se crea un circuito aleatorio de longitud 20 de 53 qubits utilizando puertas.
El circuito comienza con el estado inicial [0…0] para su ejecución.
La salida del circuito es una cadena de bits aleatoria (muestra)
La distribución del resultado no es aleatoria (interferencia)
La distribución de las muestras obtenidas se compara con la esperada.
Concluye la supremacía cuántica
Es decir, Google implementó un problema sintético en un procesador de 53 qubits y basa su afirmación de lograr la supremacía cuántica en el hecho de que es imposible emular dicho procesador en sistemas estándar en un tiempo razonable.
Para entender - Esta sección no disminuye de ninguna manera los logros de Google., los ingenieros son realmente geniales, y la cuestión de si esto puede considerarse una superioridad cuántica real o no, como se mencionó anteriormente, es más filosófica que de ingeniería. Pero debemos entender que habiendo logrado tal superioridad computacional, no hemos avanzado ni un paso hacia la capacidad de ejecutar el algoritmo de Shor en números de 2048 bits.
Las computadoras cuánticas y la computación cuántica son un área de tecnología de la información muy prometedora, muy joven y hasta ahora poco aplicable industrialmente.
El desarrollo de la computación cuántica (algún día) nos permitirá resolver problemas:
Modelado de sistemas físicos complejos a nivel cuántico.
No se puede resolver en una computadora normal debido a la complejidad computacional
Los principales problemas en la creación y operación de computadoras cuánticas:
Decoherencia
Errores (decoherencia y puerta)
Arquitectura del procesador (circuitos qubit completamente conectados)
Aún no existe una explotación comercial REAL (y no está claro cuándo la habrá)
Qué puede ayudar:
Algún tipo de descubrimiento físico que reduzca el coste de cableado y funcionamiento de los procesadores.
Descubrir algo que aumentará el tiempo de decoherencia en un orden de magnitud y/o reducirá los errores.
En mi opinión (opinión puramente personal), En el actual paradigma científico del conocimiento, no lograremos un éxito significativo en el desarrollo de tecnologías cuánticas., aquí necesitamos un avance cualitativo en algún área de la ciencia fundamental o aplicada, que dará impulso a nuevas ideas y métodos.
Mientras tanto, estamos adquiriendo experiencia en programación cuántica, recopilando y creando algoritmos cuánticos, probando ideas, etc., etc. Estamos esperando un gran avance.
En este artículo, repasamos los principales hitos en el desarrollo de la computación cuántica y las computadoras cuánticas, examinamos el principio de su funcionamiento, examinamos los principales problemas que enfrentan los ingenieros en el desarrollo y operación de procesadores cuánticos y también analizamos qué son los multiqubit. Las computadoras D en realidad lo son. Wave y el reciente anuncio de Google de lograr la supremacía cuántica.
Detrás de escena quedan cuestiones de programación de computadoras cuánticas (lenguajes, enfoques, métodos, etc.) y cuestiones relacionadas con la implementación física específica de los procesadores, cómo se gestionan, vinculan, leen los qubits, etc. Quizás este sea el tema del próximo artículo o artículos.
Gracias por su atención, espero que este artículo sea útil para alguien.