Computación cuántica

La computación cuántica es un tipo de computación que aprovecha las propiedades colectivas de los estados cuánticos, como la superposición, la interferencia y el entrelazamiento, para realizar cálculos. Los dispositivos que realizan cálculos cuánticos se conocen como computadoras cuánticas. Aunque las computadoras cuánticas actuales son demasiado pequeñas para superar a las computadoras habituales (clásicas) para aplicaciones prácticas, se cree que son capaces de resolver ciertos problemas computacionales, como la factorización de enteros (que subyace en el cifrado RSA), sustancialmente más rápido que las computadoras clásicas. El estudio de la computación cuántica es un subcampo de la ciencia de la información cuántica.

Hay varios tipos de computadoras cuánticas (también conocidas como sistemas de computación cuántica), incluido el modelo de circuito cuántico, la máquina cuántica de Turing, la computadora cuántica adiabática, la computadora cuántica unidireccional y varios autómatas celulares cuánticos. El modelo más utilizado es el circuito cuántico, basado en el bit cuántico, o "qubit", que es algo análogo al bit en la computación clásica. Un qubit puede estar en un estado cuántico 1 o 0, o en una superposición de los estados 1 y 0. Sin embargo, cuando se mide, siempre es 0 o 1; la probabilidad de cualquiera de los resultados depende del estado cuántico del qubit inmediatamente antes de la medición.

Los esfuerzos para construir una computadora cuántica física se centran en tecnologías como transmons, trampas de iones y computadoras cuánticas topológicas, cuyo objetivo es crear qubits de alta calidad. Estos qubits pueden diseñarse de manera diferente, según el modelo de computación de la computadora cuántica completa, en cuanto a si se emplean puertas lógicas cuánticas, recocido cuántico o computación cuántica adiabática. Actualmente hay una serie de obstáculos significativos para construir computadoras cuánticas útiles. Es particularmente difícil mantener los estados cuánticos de los qubits, ya que sufren de decoherencia cuántica y fidelidad de estado. Por lo tanto, las computadoras cuánticas requieren corrección de errores.

Cualquier problema computacional que pueda ser resuelto por una computadora clásica también puede ser resuelto por una computadora cuántica. Por el contrario, cualquier problema que pueda ser resuelto por una computadora cuántica también puede ser resuelto por una computadora clásica, al menos en principio, con suficiente tiempo. En otras palabras, las computadoras cuánticas obedecen la tesis de Church-Turing. Esto significa que, si bien las computadoras cuánticas no brindan ventajas adicionales sobre las computadoras clásicas en términos de computabilidad, los algoritmos cuánticos para ciertos problemas tienen complejidades de tiempo significativamente menores que los correspondientes algoritmos clásicos conocidos. En particular, se cree que las computadoras cuánticas pueden resolver rápidamente ciertos problemas que ninguna computadora clásica podría resolver de manera factible.cantidad de tiempo, una hazaña conocida como "supremacía cuántica". El estudio de la complejidad computacional de los problemas con respecto a las computadoras cuánticas se conoce como teoría de la complejidad cuántica.

Historia

La computación cuántica comenzó en 1980 cuando el físico Paul Benioff propuso un modelo mecánico cuántico de la máquina de Turing. Richard Feynman y Yuri Manin sugirieron más tarde que una computadora cuántica tenía el potencial de simular cosas que una computadora clásica no podría hacer. En 1986, Feynman introdujo una versión temprana de la notación de circuito cuántico. En 1994, Peter Shor desarrolló un algoritmo cuántico para encontrar los factores primos de un número entero con el potencial de descifrar las comunicaciones cifradas con RSA. En 1998, Isaac Chuang, Neil Gershenfeld y Mark Kubinec crearon la primera computadora cuántica de dos qubits que podía realizar cálculos.A pesar del progreso experimental en curso desde finales de la década de 1990, la mayoría de los investigadores creen que "la computación cuántica tolerante a fallas [es] todavía un sueño bastante lejano". En los últimos años, la inversión en investigación en computación cuántica se ha incrementado en los sectores público y privado. El 23 de octubre de 2019, Google AI, en asociación con la Administración Nacional de Aeronáutica y del Espacio (NASA) de EE. UU., afirmó haber realizado un cálculo cuántico que no era factible en ninguna computadora clásica, pero si esta afirmación era o sigue siendo válida es un tema de debate. investigación activa.

Un análisis de McKinsey & Company de diciembre de 2021 afirma que "... los dólares de inversión están llegando a raudales y las nuevas empresas de computación cuántica están proliferando". Continúan señalando que "si bien la computación cuántica promete ayudar a las empresas a resolver problemas que están más allá del alcance y la velocidad de las computadoras convencionales de alto rendimiento, los casos de uso son en gran medida experimentales e hipotéticos en esta etapa inicial".

Cuanto da la vuelta

Definición

El modelo prevaleciente de computación cuántica describe la computación en términos de una red de puertas lógicas cuánticas. Este modelo es una generalización algebraica lineal compleja de circuitos booleanos.

Una memoria que consta de bits de información tiene estados posibles. Un vector que representa todos los estados de memoria tiene entradas (una para cada estado). Este vector se ve como un vector de probabilidad y representa el hecho de que la memoria se encuentra en un estado particular.

En la vista clásica, una entrada tendría un valor de 1 (es decir, una probabilidad del 100% de estar en este estado) y todas las demás entradas serían cero.

En mecánica cuántica, los vectores de probabilidad se pueden generalizar a operadores de densidad. El formalismo de vector de estado cuántico generalmente se presenta primero porque es conceptualmente más simple y porque puede usarse en lugar del formalismo de matriz de densidad para estados puros, donde se conoce todo el sistema cuántico.

Comenzamos considerando una memoria simple que consta de un solo bit. Esta memoria se puede encontrar en uno de dos estados: el estado cero o el estado uno. Podemos representar el estado de esta memoria usando la notación de Dirac de modo que

Entonces se puede encontrar una memoria cuántica en cualquier superposición cuántica de los dos estados clásicos y :

Los coeficientes y son números complejos. Se dice que un qubit de información está codificado en la memoria cuántica. El estado no es en sí mismo un vector de probabilidad, pero se puede conectar con un vector de probabilidad a través de una operación de medición. Si se mide la memoria cuántica para determinar si el estado es o (esto se conoce como una medida de base computacional), el estado cero se observaría con probabilidad y el estado uno con probabilidad . Los números y se denominan amplitudes de probabilidad.

El estado de esta memoria cuántica de un qubit se puede manipular aplicando puertas lógicas cuánticas, de forma análoga a cómo se puede manipular la memoria clásica con puertas lógicas clásicas. Una puerta importante tanto para la computación clásica como para la cuántica es la puerta NOT, que se puede representar mediante una matriz

Matemáticamente, la aplicación de una puerta lógica de este tipo a un vector de estado cuántico se modela con la multiplicación de matrices. Así y .

Las matemáticas de las puertas de un solo qubit se pueden extender para operar en memorias cuánticas de múltiples qubits de dos maneras importantes. Una forma es simplemente seleccionar un qubit y aplicar esa puerta al qubit de destino sin afectar el resto de la memoria. Otra forma es aplicar la puerta a su objetivo solo si otra parte de la memoria se encuentra en el estado deseado. Estas dos opciones se pueden ilustrar usando otro ejemplo. Los posibles estados de una memoria cuántica de dos qubits son

La puerta CNOT se puede representar usando la siguiente matriz:

Como consecuencia matemática de esta definición, , , y . En otras palabras, el CNOT aplica una puerta NOT (de antes) al segundo qubit si y solo si el primer qubit está en el estado . Si el primer qubit es , no se hace nada en ninguno de los qubit.

En resumen, una computación cuántica se puede describir como una red de puertas y medidas lógicas cuánticas. Sin embargo, cualquier medición puede posponerse hasta el final de la computación cuántica, aunque este aplazamiento puede tener un costo computacional, por lo que la mayoría de los circuitos cuánticos representan una red que consiste solo en puertas lógicas cuánticas y sin mediciones.

Cualquier computación cuántica (que es, en el formalismo anterior, cualquier matriz unitaria sobre qubits) se puede representar como una red de puertas lógicas cuánticas de una familia de puertas bastante pequeña. Una elección de familia de compuertas que permite esta construcción se conoce como conjunto de compuertas universales, ya que una computadora que puede ejecutar tales circuitos es una computadora cuántica universal. Un conjunto común de este tipo incluye todas las puertas de un solo qubit, así como la puerta CNOT de arriba. Esto significa que cualquier cálculo cuántico se puede realizar mediante la ejecución de una secuencia de puertas de un solo qubit junto con puertas CNOT. Aunque este conjunto de puertas es infinito, se puede reemplazar con un conjunto de puertas finito apelando al teorema de Solovay-Kitaev.

Algoritmos cuánticos

El progreso en la búsqueda de algoritmos cuánticos normalmente se centra en este modelo de circuito cuántico, aunque existen excepciones como el algoritmo adiabático cuántico. Los algoritmos cuánticos se pueden clasificar aproximadamente por el tipo de aceleración lograda sobre los algoritmos clásicos correspondientes.

Los algoritmos cuánticos que ofrecen más que una aceleración polinomial sobre el algoritmo clásico más conocido incluyen el algoritmo de Shor para la factorización y los algoritmos cuánticos relacionados para calcular logaritmos discretos, resolver la ecuación de Pell y, en general, resolver el problema del subgrupo oculto para grupos finitos abelianos. Estos algoritmos dependen de la primitiva de la transformada cuántica de Fourier. No se ha encontrado ninguna prueba matemática que demuestre que no se puede descubrir un algoritmo clásico igualmente rápido, aunque esto se considera poco probable.Ciertos problemas de Oracle como el problema de Simon y el problema de Bernstein-Vazirani dan aceleraciones demostrables, aunque esto está en el modelo de consulta cuántica, que es un modelo restringido donde los límites inferiores son mucho más fáciles de probar y no necesariamente se traducen en aceleraciones para problemas prácticos..

Otros problemas, incluida la simulación de procesos físicos cuánticos a partir de la química y la física del estado sólido, la aproximación de ciertos polinomios de Jones y el algoritmo cuántico para sistemas lineales de ecuaciones, tienen algoritmos cuánticos que parecen dar aceleraciones superpolinomiales y son BQP completos. Debido a que estos problemas son BQP-completos, un algoritmo clásico igualmente rápido para ellos implicaría que ningún algoritmo cuántico proporciona una aceleración superpolinomial, lo que se cree que es poco probable.

Algunos algoritmos cuánticos, como el algoritmo de Grover y la amplificación de amplitud, brindan aceleraciones polinómicas sobre los algoritmos clásicos correspondientes. Si bien estos algoritmos brindan una aceleración cuadrática comparativamente modesta, son ampliamente aplicables y, por lo tanto, brindan aceleraciones para una amplia gama de problemas. Muchos ejemplos de aceleraciones cuánticas comprobables para problemas de consulta están relacionados con el algoritmo de Grover, incluido el algoritmo de Brassard, Høyer y Tapp para encontrar colisiones en funciones de dos a uno, que utiliza el algoritmo de Grover y el algoritmo de Farhi, Goldstone y Gutmann para evaluar NAND árboles, que es una variante del problema de búsqueda.

Aplicaciones potenciales

Criptografía

Una aplicación notable de la computación cuántica es para ataques a sistemas criptográficos que están actualmente en uso. Se cree que la factorización de enteros, que sustenta la seguridad de los sistemas criptográficos de clave pública, es computacionalmente inviable con una computadora común para números enteros grandes si son el producto de pocos números primos (por ejemplo, productos de dos números primos de 300 dígitos).En comparación, una computadora cuántica podría resolver este problema de manera eficiente utilizando el algoritmo de Shor para encontrar sus factores. Esta capacidad permitiría a una computadora cuántica romper muchos de los sistemas criptográficos que se usan hoy en día, en el sentido de que habría un algoritmo de tiempo polinomial (en el número de dígitos del número entero) para resolver el problema. En particular, la mayoría de los cifrados de clave pública populares se basan en la dificultad de factorizar números enteros o el problema del logaritmo discreto, los cuales pueden resolverse mediante el algoritmo de Shor. En particular, los algoritmos RSA, Diffie-Hellman y Diffie-Hellman de curva elíptica podrían romperse. Estos se utilizan para proteger páginas web seguras, correo electrónico encriptado y muchos otros tipos de datos. Romperlos tendría ramificaciones significativas para la privacidad y la seguridad electrónicas.

La identificación de sistemas criptográficos que puedan ser seguros frente a los algoritmos cuánticos es un tema que se investiga activamente en el campo de la criptografía poscuántica. Algunos algoritmos de clave pública se basan en problemas distintos de la factorización de enteros y los problemas de logaritmos discretos a los que se aplica el algoritmo de Shor, como el criptosistema de McEliece basado en un problema de teoría de codificación. Tampoco se sabe que las computadoras cuánticas rompan los criptosistemas basados ​​en celosías, y encontrar un algoritmo de tiempo polinomial para resolver el problema del subgrupo oculto diédrico, que rompería muchos criptosistemas basados ​​en celosías, es un problema abierto bien estudiado. Se ha demostrado que aplicar el algoritmo de Grover para romper un algoritmo simétrico (clave secreta) por fuerza bruta requiere un tiempo de aproximadamente 2invocaciones del algoritmo criptográfico subyacente, en comparación con aproximadamente 2 en el caso clásico, lo que significa que las longitudes de clave simétricas se reducen a la mitad: AES-256 tendría la misma seguridad contra un ataque usando el algoritmo de Grover que AES-128 tiene contra la búsqueda clásica de fuerza bruta (ver Tamaño de clave).

La criptografía cuántica podría potencialmente cumplir algunas de las funciones de la criptografía de clave pública. Los sistemas criptográficos basados ​​en la tecnología cuántica podrían, por lo tanto, ser más seguros que los sistemas tradicionales contra la piratería cuántica.

Problemas de búsqueda

El ejemplo más conocido de un problema que admite una aceleración cuántica polinomial es la búsqueda no estructurada, encontrando un elemento marcado de una lista de elementos en una base de datos. Esto se puede resolver mediante el algoritmo de Grover utilizando consultas a la base de datos, cuadráticamente menos que las consultas requeridas por los algoritmos clásicos. En este caso, la ventaja no solo es comprobable sino también óptima: se ha demostrado que el algoritmo de Grover brinda la máxima probabilidad posible de encontrar el elemento deseado para cualquier número de búsquedas de Oracle.

Los problemas que se pueden abordar de manera eficiente con el algoritmo de Grover tienen las siguientes propiedades:

1. No hay una estructura de búsqueda en la colección de posibles respuestas,
2. El número de posibles respuestas a verificar es el mismo que el número de entradas al algoritmo, y
3. Existe una función booleana que evalúa cada entrada y determina si es la respuesta correcta

Para problemas con todas estas propiedades, el tiempo de ejecución del algoritmo de Grover en una computadora cuántica escala como la raíz cuadrada del número de entradas (o elementos en la base de datos), a diferencia de la escala lineal de los algoritmos clásicos. Una clase general de problemas a los que se puede aplicar el algoritmo de Grover es el problema de satisfacibilidad booleano, donde la base de datos a través de la cual itera el algoritmo es la de todas las respuestas posibles. Un ejemplo y una posible aplicación de esto es un descifrador de contraseñas que intenta adivinar una contraseña. Romper cifrados simétricos con este algoritmo es de interés para las agencias gubernamentales.

Simulación de sistemas cuánticos

Dado que la química y la nanotecnología se basan en la comprensión de los sistemas cuánticos, y tales sistemas son imposibles de simular de manera eficiente de manera clásica, muchos creen que la simulación cuántica será una de las aplicaciones más importantes de la computación cuántica. La simulación cuántica también podría usarse para simular el comportamiento de átomos y partículas en condiciones inusuales, como las reacciones dentro de un colisionador. Las simulaciones cuánticas podrían usarse para predecir las trayectorias futuras de partículas y protones bajo superposición en el experimento de doble rendija. Alrededor del 2% de la producción de energía global anual se utiliza para la fijación de nitrógeno para producir amoníaco para el proceso Haber en la industria de fertilizantes agrícolas, mientras que los organismos naturales también producen amoníaco. Las simulaciones cuánticas podrían usarse para comprender este proceso que aumenta la producción.

Recocido cuántico y optimización adiabática

El recocido cuántico o computación cuántica adiabática se basa en el teorema adiabático para realizar los cálculos. Un sistema se coloca en el estado fundamental para un hamiltoniano simple, que evoluciona lentamente a un hamiltoniano más complicado cuyo estado fundamental representa la solución al problema en cuestión. El teorema adiabático establece que si la evolución es lo suficientemente lenta, el sistema permanecerá en su estado fundamental en todo momento durante el proceso.

Aprendizaje automático

Dado que las computadoras cuánticas pueden producir resultados que las computadoras clásicas no pueden producir de manera eficiente, y dado que la computación cuántica es fundamentalmente algebraica lineal, algunos expresan su esperanza de desarrollar algoritmos cuánticos que puedan acelerar las tareas de aprendizaje automático. Por ejemplo, se cree que el algoritmo cuántico para sistemas lineales de ecuaciones, o "Algoritmo HHL", llamado así por sus descubridores Harrow, Hassidim y Lloyd, proporciona una mayor velocidad que sus contrapartes clásicas. Algunos grupos de investigación han explorado recientemente el uso de hardware de recocido cuántico para entrenar máquinas de Boltzmann y redes neuronales profundas.

Biología Computacional

En el campo de la biología computacional, la computación cuántica ha jugado un papel importante en la resolución de muchos problemas biológicos. Uno de los ejemplos más conocidos sería la genómica computacional y cómo la informática ha reducido drásticamente el tiempo para secuenciar un genoma humano. Dado que la biología computacional utiliza el modelado y el almacenamiento de datos genéricos, también se espera que surjan sus aplicaciones a la biología computacional.

Diseño de fármacos asistido por ordenador y química generativa

Los modelos de química generativa profunda emergen como herramientas poderosas para acelerar el descubrimiento de fármacos. Sin embargo, el inmenso tamaño y la complejidad del espacio estructural de todas las posibles moléculas similares a las drogas plantean obstáculos significativos que las computadoras cuánticas podrían superar en el futuro. Las computadoras cuánticas son naturalmente buenas para resolver problemas cuánticos complejos de muchos cuerpos y, por lo tanto, pueden ser fundamentales en aplicaciones relacionadas con la química cuántica. Por lo tanto, se puede esperar que los modelos generativos mejorados cuánticamente, incluidas las GAN cuánticaseventualmente se puede desarrollar en los últimos algoritmos de química generativa. Las arquitecturas híbridas que combinan computadoras cuánticas con redes clásicas profundas, como los codificadores automáticos variacionales cuánticos, ya pueden entrenarse en recocidos disponibles comercialmente y usarse para generar nuevas estructuras moleculares similares a las de las drogas.

Desarrollo de computadoras cuánticas físicas

Desafíos

Hay una serie de desafíos técnicos en la construcción de una computadora cuántica a gran escala. El físico David DiVincenzo ha enumerado estos requisitos para una computadora cuántica práctica:

• Físicamente escalable para aumentar el número de qubits
• Qubits que se pueden inicializar a valores arbitrarios
• Puertas cuánticas que son más rápidas que el tiempo de decoherencia
• Juego de puertas universales
• Qubits que se pueden leer fácilmente

El abastecimiento de piezas para computadoras cuánticas también es muy difícil. Muchas computadoras cuánticas, como las construidas por Google e IBM, necesitan helio-3, un subproducto de la investigación nuclear, y cables superconductores especiales fabricados únicamente por la empresa japonesa Coax Co.

El control de los sistemas multi-qubit requiere la generación y coordinación de una gran cantidad de señales eléctricas con una resolución de tiempo estricta y determinista. Esto ha llevado al desarrollo de controladores cuánticos que permiten interactuar con los qubits. Escalar estos sistemas para admitir un número creciente de qubits es un desafío adicional.

Decoherencia cuántica

Uno de los mayores desafíos relacionados con la construcción de computadoras cuánticas es controlar o eliminar la decoherencia cuántica. Esto generalmente significa aislar el sistema de su entorno, ya que las interacciones con el mundo externo hacen que el sistema se descoherente. Sin embargo, también existen otras fuentes de decoherencia. Los ejemplos incluyen las puertas cuánticas y las vibraciones de la red y el giro termonuclear de fondo del sistema físico utilizado para implementar los qubits. La decoherencia es irreversible, ya que es efectivamente no unitaria y, por lo general, es algo que debe controlarse en gran medida, si no evitarse. Los tiempos de decoherencia para los sistemas candidatos en particular, el tiempo de relajación transversal T ₂ (para la tecnología NMR y MRI, también llamado tiempo de desfase), normalmente oscilan entre nanosegundos y segundos a baja temperatura. Actualmente, algunas computadoras cuánticas requieren que sus qubits se enfríen a 20 milikelvin (generalmente usando un refrigerador de dilución) para evitar una decoherencia significativa. Un estudio de 2020 argumenta que la radiación ionizante, como los rayos cósmicos, puede, sin embargo, hacer que ciertos sistemas pierdan la coherencia en milisegundos.

Como resultado, las tareas que consumen mucho tiempo pueden hacer que algunos algoritmos cuánticos queden inoperables, ya que mantener el estado de los qubits durante un tiempo suficiente eventualmente corromperá las superposiciones.

Estos problemas son más difíciles para los enfoques ópticos, ya que las escalas de tiempo son órdenes de magnitud más cortas y un enfoque citado a menudo para superarlos es la formación de pulsos ópticos. Las tasas de error suelen ser proporcionales a la relación entre el tiempo de operación y el tiempo de decoherencia, por lo que cualquier operación debe completarse mucho más rápido que el tiempo de decoherencia.

Como se describe en el teorema del umbral cuántico, si la tasa de error es lo suficientemente pequeña, se cree que es posible utilizar la corrección de errores cuánticos para suprimir los errores y la decoherencia. Esto permite que el tiempo total de cálculo sea mayor que el tiempo de decoherencia si el esquema de corrección de errores puede corregir los errores más rápido de lo que los introduce la decoherencia. Una cifra citada a menudo para la tasa de error requerida en cada puerta para el cálculo tolerante a fallas es 10, suponiendo que el ruido se está despolarizando.

Cumplir esta condición de escalabilidad es posible para una amplia gama de sistemas. Sin embargo, el uso de la corrección de errores trae consigo el costo de un número mucho mayor de qubits requeridos. El número requerido para factorizar enteros utilizando el algoritmo de Shor sigue siendo polinomial y se cree que está entre L y L, donde L es el número de dígitos del número que se factorizará; los algoritmos de corrección de errores inflarían esta cifra por un factor adicional de L. Para un número de 1000 bits, esto implica la necesidad de unos 10 bits sin corrección de errores. Con la corrección de errores, la cifra se elevaría a unos 10 bits. El tiempo de cálculo es aproximadamente L o aproximadamente 10pasos y a 1 MHz, unos 10 segundos.

Un enfoque muy diferente al problema de estabilidad-decoherencia es crear una computadora cuántica topológica con anyons, cuasi-partículas que se usan como hilos y se basan en la teoría de la trenza para formar puertas lógicas estables.

Supremacía cuántica

La supremacía cuántica es un término acuñado por John Preskill que se refiere a la hazaña de ingeniería de demostrar que un dispositivo cuántico programable puede resolver un problema más allá de las capacidades de las computadoras clásicas de última generación. El problema no tiene por qué ser útil, por lo que algunos ven la prueba de supremacía cuántica solo como un posible punto de referencia futuro.

En octubre de 2019, Google AI Quantum, con la ayuda de la NASA, se convirtió en el primero en afirmar haber logrado la supremacía cuántica al realizar cálculos en la computadora cuántica Sycamore más de 3,000,000 de veces más rápido de lo que se podría hacer en Summit, generalmente considerado el más rápido del mundo. ordenador. Esta afirmación ha sido cuestionada posteriormente: IBM ha declarado que Summit puede realizar muestras mucho más rápido de lo que se afirma, y ​​desde entonces los investigadores han desarrollado mejores algoritmos para el problema de muestreo utilizado para reclamar la supremacía cuántica, lo que reduce sustancialmente la brecha entre Sycamore y las supercomputadoras clásicas.

En diciembre de 2020, un grupo de la USTC implementó un tipo de muestreo de bosones en 76 fotones con una computadora cuántica fotónica Jiuzhang para demostrar la supremacía cuántica. Los autores afirman que una supercomputadora contemporánea clásica requeriría un tiempo computacional de 600 millones de años para generar la cantidad de muestras que su procesador cuántico puede generar en 20 segundos. El 16 de noviembre de 2021, en la cumbre de computación cuántica, IBM presentó un microprocesador de 127 qubits llamado IBM Eagle.

Escepticismo

Algunos investigadores han expresado su escepticismo sobre la posibilidad de construir computadoras cuánticas escalables, generalmente debido a la cuestión de mantener la coherencia a gran escala.

Bill Unruh dudaba de la practicidad de las computadoras cuánticas en un artículo publicado en 1994. Paul Davies argumentó que una computadora de 400 qubits incluso entraría en conflicto con el límite de información cosmológica implícito en el principio holográfico. Los escépticos como Gil Kalai dudan de que alguna vez se logre la supremacía cuántica. El físico Mikhail Dyakonov ha expresado su escepticismo sobre la computación cuántica de la siguiente manera:"Entonces, la cantidad de parámetros continuos que describen el estado de una computadora cuántica tan útil en un momento dado debe ser... alrededor de 10... ¿Podríamos aprender a controlar los más de 10 parámetros continuamente variables que definen el estado cuántico de tal ? sistema? Mi respuesta es simple. No, nunca ".

Candidatos a realizaciones físicas

Para implementar físicamente una computadora cuántica, se están buscando muchos candidatos diferentes, entre ellos (distinguidos por el sistema físico utilizado para realizar los qubits):

• Computación cuántica superconductora (qubit implementado por el estado de pequeños circuitos superconductores [uniones de Josephson])
• Computadora cuántica de iones atrapados (qubit implementado por el estado interno de los iones atrapados)
• Átomos neutros en redes ópticas (qubit implementado por estados internos de átomos neutros atrapados en una red óptica)
• Computadora de puntos cuánticos, basada en espín (por ejemplo, la computadora cuántica Loss-DiVincenzo) (qubit dado por los estados de espín de los electrones atrapados)
• Computadora de puntos cuánticos, basada en el espacio (qubit dado por la posición del electrón en el punto cuántico doble)
• Computación cuántica utilizando pozos cuánticos diseñados, que en principio podrían permitir la construcción de computadoras cuánticas que operen a temperatura ambiente.
• Cable cuántico acoplado (qubit implementado por un par de cables cuánticos acoplados por un punto de contacto cuántico)
• Computadora cuántica de resonancia magnética nuclear (NMRQC) implementada con la resonancia magnética nuclear de moléculas en solución, donde los qubits son proporcionados por espines nucleares dentro de la molécula disuelta y sondeados con ondas de radio
• Computadoras cuánticas Kane de RMN de estado sólido (qubit realizado por el estado de espín nuclear de los donantes de fósforo en silicio)
• Computadora cuántica vibratoria (qubits realizados por superposiciones vibratorias en moléculas frías)
• Computadoras cuánticas de electrones en helio (qubit es el espín del electrón)
• Electrodinámica cuántica de cavidades (CQED) (qubit proporcionado por el estado interno de los átomos atrapados acoplados a cavidades de alta delicadeza)
• Imán molecular (qubit dado por estados de espín)
• Computadora cuántica ESR basada en fullereno (qubit basado en el espín electrónico de átomos o moléculas encerradas en fullerenos)
• Computadora cuántica óptica no lineal (qubits realizados mediante el procesamiento de estados de diferentes modos de luz a través de elementos lineales y no lineales)
• Computadora cuántica óptica lineal (qubits realizados mediante el procesamiento de estados de diferentes modos de luz a través de elementos lineales, por ejemplo, espejos, divisores de haz y cambiadores de fase)
• Computadora cuántica basada en diamantes (qubit realizado por el giro electrónico o nuclear de los centros de vacantes de nitrógeno en el diamante)
• Computadora cuántica basada en condensado Bose-Einstein
• Computadora cuántica basada en transistores: computadoras cuánticas de cadena con arrastre de agujeros positivos usando una trampa electrostática
• Computadoras cuánticas basadas en cristales inorgánicos dopados con iones de metales de tierras raras (qubit realizado por el estado electrónico interno de dopantes en fibras ópticas)
• Computadoras cuánticas basadas en nanoesferas de carbono de tipo metálico

La gran cantidad de candidatos demuestra que la computación cuántica, a pesar del rápido progreso, aún está en pañales.

Modelos de computación para computación cuántica

Hay una serie de modelos de computación para la computación cuántica, que se distinguen por los elementos básicos en los que se descompone la computación. Para implementaciones prácticas, los cuatro modelos de computación relevantes son:

• Matriz de puertas cuánticas: computación descompuesta en una secuencia de puertas cuánticas de pocos qubits.
• Computadora cuántica unidireccional: computación descompuesta en una secuencia de mediciones de estado de Bell y puertas cuánticas de un solo qubit aplicadas a un estado inicial altamente entrelazado (un estado de grupo), utilizando una técnica llamada teletransportación de puerta cuántica.
• Computadora cuántica adiabática, basada en recocido cuántico: computación descompuesta en una transformación continua lenta de un hamiltoniano inicial en un hamiltoniano final, cuyos estados fundamentales contienen la solución.
• Computadora cuántica topológica: computación descompuesta en el trenzado de anyons en una red 2D.

La máquina cuántica de Turing es teóricamente importante, pero la implementación física de este modelo no es factible. Se ha demostrado que todos estos modelos de computación (circuitos cuánticos, computación cuántica unidireccional, computación cuántica adiabática y computación cuántica topológica) son equivalentes a la máquina cuántica de Turing; dada una implementación perfecta de una de esas computadoras cuánticas, puede simular todas las demás con no más que una sobrecarga polinomial. Esta equivalencia no tiene por qué ser válida para las computadoras cuánticas prácticas, ya que la sobrecarga de la simulación puede ser demasiado grande para ser práctica.

Relación con la computabilidad y la teoría de la complejidad

Teoría de la computabilidad

Cualquier problema computacional que se pueda resolver con una computadora clásica también se puede resolver con una computadora cuántica. Intuitivamente, esto se debe a que se cree que todos los fenómenos físicos, incluido el funcionamiento de las computadoras clásicas, pueden describirse utilizando la mecánica cuántica, que subyace en el funcionamiento de las computadoras cuánticas.

Por el contrario, cualquier problema que pueda resolver una computadora cuántica también lo puede resolver una computadora clásica. Es posible simular computadoras tanto cuánticas como clásicas manualmente con solo un poco de papel y un bolígrafo, si se le da suficiente tiempo. Más formalmente, cualquier computadora cuántica puede ser simulada por una máquina de Turing. En otras palabras, las computadoras cuánticas no brindan poder adicional sobre las computadoras clásicas en términos de computabilidad. Esto significa que las computadoras cuánticas no pueden resolver problemas indecidibles como el problema de la detención y la existencia de computadoras cuánticas no refuta la tesis de Church-Turing.

Teoría de la complejidad cuántica

Si bien las computadoras cuánticas no pueden resolver ningún problema que las computadoras clásicas ya no puedan resolver, se sospecha que pueden resolver ciertos problemas más rápido que las computadoras clásicas. Por ejemplo, se sabe que las computadoras cuánticas pueden factorizar números enteros de manera eficiente, mientras que no se cree que este sea el caso de las computadoras clásicas.

La clase de problemas que puede resolver eficientemente una computadora cuántica con error acotado se llama BQP, por "error acotado, cuántico, tiempo polinomial". Más formalmente, BQP es la clase de problemas que puede resolver una máquina de Turing cuántica de tiempo polinomial con una probabilidad de error de 1/3 como máximo. Como clase de problemas probabilísticos, BQP es la contraparte cuántica de BPP ("error acotado, probabilístico, tiempo polinomial"), la clase de problemas que pueden resolverse mediante máquinas de Turing probabilísticas de tiempo polinomial con error acotado. Se sabe y se sospecha ampliamente que , lo que intuitivamente significaría que las computadoras cuánticas son más poderosas que las computadoras clásicas en términos de complejidad temporal.

Se desconoce la relación exacta de BQP con P, NP y PSPACE. Sin embargo, se sabe que; es decir, todos los problemas que pueden resolverse eficientemente con una computadora clásica determinista también pueden resolverse de manera eficiente con una computadora cuántica, y todos los problemas que pueden resolverse de manera eficiente con una computadora cuántica también pueden resolverse con una computadora clásica determinista con recursos de espacio polinomial. Además, se sospecha que BQP es un superconjunto estricto de P, lo que significa que hay problemas que las computadoras cuánticas pueden resolver de manera eficiente y que las computadoras clásicas deterministas no pueden resolver de manera eficiente. Por ejemplo, se sabe que la factorización de enteros y el problema del logaritmo discreto están en BQP y se sospecha que están fuera de P. Sobre la relación de BQP con NP, se sabe poco más allá del hecho de que algunos problemas de NP que se cree que no están en P también están en BQP (la factorización de enteros y el problema del logaritmo discreto están ambos en NP, por ejemplo). Se sospecha que; es decir, se cree que hay problemas verificables de manera eficiente que no son resueltos de manera eficiente por una computadora cuántica. Como consecuencia directa de esta creencia, también se sospecha que BQP es disjunto de la clase de problemas NP-completos (si un problema NP-completo estuviera en BQP, entonces se seguiría de la dureza NP que todos los problemas en NP están en BQP).

La relación de BQP con las clases de complejidad clásicas básicas se puede resumir de la siguiente manera:

También se sabe que BQP está contenido en la clase de complejidad (o más precisamente en la clase asociada de problemas de decisión ), que es una subclase de PSPACE.

Se ha especulado que nuevos avances en la física podrían conducir a computadoras aún más rápidas. Por ejemplo, se ha demostrado que una computadora cuántica variable oculta no local basada en Bohmian Mechanics podría implementar una búsqueda de una base de datos de N elementos en la mayoría de los pasos, una ligera aceleración sobre el algoritmo de Grover, que se ejecuta en pasos. Tenga en cuenta, sin embargo, que ningún método de búsqueda permitiría a las computadoras cuánticas resolver problemas NP-completos en tiempo polinomial.Las teorías de la gravedad cuántica, como la teoría M y la gravedad cuántica de bucles, pueden permitir la construcción de computadoras aún más rápidas. Sin embargo, definir la computación en estas teorías es un problema abierto por el problema del tiempo; es decir, dentro de estas teorías físicas actualmente no existe una forma obvia de describir lo que significa para un observador enviar una entrada a una computadora en un momento dado y luego recibir una salida en un momento posterior.