¿Qué es el modelo computacional cuántico?

32

Ocasionalmente he escuchado a personas hablar sobre algoritmos cuánticos y sobre estados y la capacidad de considerar múltiples posibilidades a la vez, pero nunca he logrado que alguien explique el modelo computacional detrás de esto. Para ser claros, no estoy preguntando cómo se construyen físicamente las computadoras cuánticas, sino cómo verlas desde un punto de vista computacional.

Casebash
fuente
8
Corrija la ortografía en el título de la pregunta.
Shane
Algunas historias y referencias están aquí en.wikipedia.org/wiki/Universal_quantum_simulator
Radu GRIGore
Nota de modificación: fusionó una pregunta duplicada exacta cerrada con esta pregunta y eliminó los comentarios del duplicado que ya no eran relevantes.
Kaveh

Respuestas:

24

Me haré eco de la recomendación de Martin Schwartz de Nielsen & Chaung como referencia estándar; Hay muchos otros también.

La investigación en el campo prefiere considerar familias uniformes de circuitos cuánticos, que (irónicamente) son redes acíclicas dirigidas que describen cómo el estado de uno o más registros se transforma con el tiempo, de manera similar a los circuitos booleanos clásicos. Si desea obtener más información, le recomiendo aprender en términos de este modelo.

Me gustaría dar algunas respuestas cualitativas para complementar la respuesta de Martin.

  1. La computación cuántica en realidad no considera "múltiples posibilidades a la vez" --- o más precisamente, si usted considera que considera múltiples posibilidades a la vez, depende de su elección de interpretación de la mecánica cuántica , es decir, una elección filosófica que no tiene teniendo en cuenta la capacidad o las predicciones del modelo computacional. ("Tener en cuenta múltiples posibilidades a la vez" corresponde a la "interpretación de muchos mundos" de QM).

    Como mínimo, se puede decir que una computadora cuántica considera múltiples posibilidades al mismo tiempo solo en la medida en que un cálculo aleatorio utilizando monedas- Flip considera múltiples posibilidades al mismo tiempo. Esto es porque:

  2. Los estados cuánticos son generalizaciones de las distribuciones de probabilidad "habituales", con algunas diferencias simples pero importantes. Una distribución de probabilidad se puede representar como un vector real no negativo cuyas entradas suman 1: es decir, un vector unitario en la norma ℓ 1 . Los cálculos probabilísticos deben mapear los vectores de la unidad ℓ 1 a otros vectores, por lo que se describen mediante mapas estocásticos. Se puede describir el cálculo cuántico de una manera similar, excepto que se usan vectores de vectors 2 unidades sobre ℂ (no restringido a ser real o no negativo); las transformaciones son por esos mapas que preservan la forma ℓ 2 , es decir, operaciones unitarias

    Esta diferencia no es trivial, por supuesto, ni aún a explicar lo que los coeficientes de los vectores de estado cuántico significan . Pero puede ser útil explicar lo que está sucediendo con los espacios de Hilbert y los productos tensoriales en la computación cuántica: a saber, exactamente las mismas cosas que suceden en la computación probabilística. El espacio de configuración de un bit aleatorio es un vector en ℝ + 2 (donde ℝ + son los reales no negativos); pero debido a que los bits aleatorios pueden correlacionarse, combinamos los espacios de configuración de uno o más bits aleatorios tomando el producto tensorial. Entonces el espacio de configuración de dos bits aleatorios es ℝ + 2  ⊗ ℝ + 2  ≅ ℝ + 4 , o el espacio totalmente general de distribuciones de probabilidad sobre las cuatro cadenas de dos bits distintas. Una operación A en el primero de estos bits aleatorios que no actúa en el segundo está representada por el operador A  ⊗  I 2  . Y así. Las mismas construcciones se aplican a los bits cuánticos; y podemos considerar los registros cuánticos sobre conjuntos de elementos distinguibles de la misma manera que consideramos las distribuciones de probabilidad sobre tales conjuntos, nuevamente usando ℓ 2 vectores de forma normal sobre ℂ.

    Esta descripción en realidad describe los estados cuánticos "puros", aquellos para los cuales, en principio, puede transformarse de una manera que preserva la información en una distribución delta sobre la cadena de bits 00 ... 0 (o más precisamente, estado arbitrariamente cercano a esto en la norma ℓ 2 ). Además de la aleatoriedad cuántica (de la cual aún no he mencionado nada explícito), puede considerar la aleatoriedad de convexidad de vainilla correspondiente a mezclas probabilísticas de estados cuánticos: estos están representados por operadores de densidad , que pueden representarse por matrices definidas positivas con la traza 1 (nuevamente generalizando las distribuciones de probabilidad "clásicas", que pueden estar representadas por el caso especial de matrices diagonales positivas con la traza 1).

    Lo importante de esto es que, si bien los estados cuánticos a menudo se describen como "exponencialmente grandes", esto se debe a que generalmente se describen utilizando las mismas estructuras matemáticas que las distribuciones de probabilidad; por qué las distribuciones de probabilidad no se describen como "exponencialmente grandes" de la misma manera no está claro (pero en última instancia no es importante). La dificultad de simular estados cuánticos proviene de este hecho, junto con el hecho de que los coeficientes complejos de estas distribuciones ℓ 2 (o los términos complejos fuera de la diagonal de los operadores de densidad, si lo prefiere) pueden cancelarse de una manera que las probabilidades no pueden , haciendo que la estimación de ellos sea más difícil.

  3. El enredo es solo otra forma de correlación. Para el cálculo probabilístico en, por ejemplo, cadenas booleanas, los únicos estados "puros" (que pueden mapearse mediante transformaciones que preservan la información a una distribución con pico delta en 000 ... 0) son la "base estándar" de las distribuciones con pico delta en el diferentes cadenas booleanas. Por lo tanto, esta base de ℝ + 2 nes distinguido Pero no hay una base tan distinguida en la mecánica cuántica, por lo que podemos decir, esto es más claro para los bits cuánticos (busque spin 1/2 partículas, si desea saber por qué). Como consecuencia, hay más transformaciones que preservan la información que solo las permutaciones: un grupo continuo de ellas, de hecho. Esto permite que las computadoras cuánticas potenciales transformen estados de maneras que no son posibles para las computadoras probabilísticas, posiblemente obteniendo una ventaja asintótica sobre ellas.

    Pero, ¿qué pasa con el enredo, que muchas personas encuentran misterioso, y afirman ser la causa de la aceleración de las computadoras cuánticas sobre la clásica? El "enredo" aquí es realmente solo una forma de correlación: así como dos variables aleatorias están correlacionadas si su distribución es una combinación convexa de más de una distribución de productos (con diferentes márgenes en cada variable), dos "variables cuánticas" están enredadas si su la distribución es una combinación lineal (con la unidad ℓ 2-norm) de dos distribuciones de producto válidas; Es el mismo concepto bajo una norma diferente, y juega un papel similar en las tareas de comunicación. (Por ejemplo: la "teletransportación cuántica" en la comunicación cuántica corresponde a la codificación y decodificación de un mensaje usando una libreta de un solo uso clásico). Esta es una forma de correlación que es más general que solo bits correlacionados de forma clásica; pero la única forma de mostrar esto es que las correlaciones codificadas en el estado entrelazado se aplican a más de una base privilegiada . En cierto modo, el enredo es una consecuencia de la ausencia de una base privilegiada.

    A la gente le gusta invocar el enredo como el elemento clave de la computación cuántica, pero esto simplemente no parece aguantar: ha habido resultados que demuestran queel enredo no es cuantitativamente importante para el algoritmo de Shor para factorizar enteros grandes, y de hecho, un sistema cuántico puede tener demasiado enredo para ser útil para un cálculo. De hecho, en todas partes que conozco que el enredo juega un papel importante en un protocolo cuántico es esencialmente uno de comunicación (donde se esperaría que las correlaciones desempeñen un papel importante para un protocolo clásico).

En este punto, empiezo a meterme en el dominio de la opinión personal, así que me detendré aquí. Pero con suerte, estos comentarios podrían desmitificar algo de lo que es oscuro sobre la computación cuántica y cómo se describe.

Niel de Beaudrap
fuente
1
Debo admitir que no estoy de acuerdo contigo en la cuestión del enredo. Las operaciones en estados de producto puro son eficientemente simulables. El papel "demasiado enredado para calcular" es un poco engañoso. Este documento trata realmente sobre los recursos para el cálculo basado en mediciones, y MBQC trata sobre el rango schmidt, no el enredo en sí mismo.
Joe Fitzsimons
1
Por supuesto, tiene razón en que si un cálculo permanece dentro de la variedad de estados de producto puro, es (eficientemente) clásicamente simulable; ¿pero eso significa que el enredo hace que las computadoras cuánticas sean "más rápidas" (admitiendo trayectorias computacionales más cortas), en lugar de simplemente "difíciles de seguir" (teniendo trayectorias computacionales 'ofuscadas')? Mi posición es que si hay una aceleración cuántica, entonces el enredo es el penacho de escape, no el combustible del cohete.
Niel de Beaudrap
Bueno, el enredo es divertido, ya que depende de la dimensión de sus sistemas locales. Creo que el poder real simplemente proviene de la existencia de superposiciones y, por lo tanto, de amplitudes complejas. El enredo parece ser una consecuencia de esto. Hay una buena codificación que hace posible el cómputo cuántico universal con amplitudes puramente reales, lo que creo que contribuye a caracterizar esto. Los algoritmos actuales están explotando alguna forma de efecto de interferencia.
Joe Fitzsimons
Estoy parcialmente de acuerdo con Joe en el punto de interferencia, pero un tema para hablar rigurosamente sobre este punto es ¿qué medidas de interferencia (razonablemente probadas) existen en el mercado ? ¿Conocen ustedes trabajos en esta dirección? El único ejemplo que se me ocurre es este (sin embargo, no lo he leído con mucho detalle).
Juan Bermejo Vega
@JuanBermejoVega: la interferencia parece ser solo un corolario del hecho de que hay transformaciones que preservan la información que no preservan los estados básicos estándar. La única alternativa aparente a la interferencia es la pérdida de información, como en la probabilidad clásica. Entonces, lo que tenemos son transformaciones simplemente reversibles que no conservan la base estándar; La narrativa de la interferencia, tan productiva como es cuando se habla de propagación en el espacio, es solo una forma de describir cómo se ve si continúas tratando de analizar esta no preservación en términos de la base estándar.
Niel de Beaudrap
12

Lance Fortnow escribió un artículo que explica la computación cuántica sin usar la mecánica cuántica. Lo presenta esencialmente de la misma manera que uno presentaría la computación probabilística. Sospecho que este puede ser un punto de partida más rápido que algo como Nielson y Chuang (aunque estoy de acuerdo en que si realmente quieres profundizar en esto, entonces Nielson y Chung definitivamente deberían estar en tu lista de lectura).

L. Fortnow. La visión de un teórico de la complejidad de la computación cuántica. Theoretical Computer Science, 292 (3): 597-610, 2003. Número especial de documentos presentados en el segundo taller sobre Algoritmos en el procesamiento de información cuántica.

Joshua Grochow
fuente
11

Bueno, el texto estándar utilizado es Computación Cuántica e Información Cuántica de Nielsen y Chuang. Cubre una amplia gama de aspectos diferentes a un nivel razonable. Casi todos los que trabajan en el campo tienen una copia de esto en su estante. El libro de Kaye, Laflamme y Mosca también es bueno, pero cubre menos (aunque hay un poco más de enfoque en los algoritmos).

Si bien es bastante posible explicar la computación cuántica sin entrar en mucha mecánica cuántica, no creo que esta sea necesariamente una buena manera de abordar el aprendizaje de la computación cuántica. Hay una gran intuición que se obtiene al tener una idea de la teoría física, ya que muchos de los modelos más recientes de computación cuántica (es decir, modelos adiabáticos, topológicos y basados ​​en mediciones) están más motivados físicamente que la máquina cuántica de Turing o El modelo del circuito.

Dicho esto, la mecánica cuántica requerida para comprender la computación cuántica es bastante simple y está bastante bien cubierta en Nielsen y Chuang. Realmente, puede tener una buena idea al leer el capítulo correspondiente y probar los ejercicios. Es el tipo de cosas que puede obtener una comprensión justa con un par de días de trabajo. Sin embargo, mi consejo es que no busques un texto de introducción estándar para la mecánica cuántica. El enfoque adoptado para modelar átomos, moléculas y materiales utiliza sistemas de dimensiones infinitas, y requiere mucho más esfuerzo para lograrlo. Para la información cuántica, es mucho mejor comenzar a mirar sistemas de dimensiones finitas. Además, tradicionalmente, los problemas estudiados por los físicos tienden a girar en torno a encontrar estados fundamentales y comportamientos de estado estacionario, y esto es lo que la mayoría de los textos introductorios cubrirán (comenzando con la ecuación de onda de Schroedinger independiente del tiempo). Para la computación cuántica, tendemos a estar más interesados ​​en la evolución temporal de los sistemas, y esto se trata de manera mucho más sucinta en los textos de computación cuántica que en los textos generales de introducción a la mecánica cuántica (que son, por definición, más generales).

Joe Fitzsimons
fuente
8

BQP

|ϕH2H2...H2|ψUsquare

Para una introducción más detallada, consulte el libro de texto estándar Nielsen y Chuang.

Martin Schwarz
fuente
Además de los modelos que Martin mencionó, hay algunos otros: computación cuántica adiabática y topológica basada en mediciones.
Joe Fitzsimons
5

Puede tener una buena introducción en el artículo "Una introducción a la computación cuántica para no físicos" de Eleanor Rieffel y Wolfgang Polak. Tal vez sea un poco viejo, sin embargo, sigue siendo una buena introducción breve y autónoma al tema: http://arxiv.org/abs/quant-ph/9809016

Otro artículo, mucho más resumido es la "Computación cuántica de Pablo Arrighi explicada a mi madre" en http://arxiv.org/abs/quant-ph/0305045

Alejandro DC
fuente
1
Rieffel y Polak también parecen haber publicado un libro: Quantum Computing: A Gentle Introduction
Logan Mayfield
4

Probablemente ya esté al tanto de esto, pero en su blog , Scott Aaronson tiene enlaces a varias de sus conferencias sobre computación cuántica, así como enlaces a primers de control de calidad por otros (solo desplácese hacia abajo en la barra lateral derecha para encontrarlos) .

Si desea una introducción de un libro, pero algo más suave que un texto como Nielsen y Chuang, recomendaría Quantum Computing for Computer Scientists por Yanofsky y Mannucci. Pasan una buena cantidad de tiempo revisando los requisitos matemáticos previos antes de sumergirse en el control de calidad. Si tiene una sólida formación matemática, este libro puede parecer demasiado básico, pero lo encuentro bastante útil.

Kurt
fuente
4

En general, apoyaría el consejo de Joe. Pero para una introducción rápida, pondría los textos de Lance Fortnow y Stephen Fenner en la lista de lectura de científicos informáticos que se están volviendo cuánticos.

Martin Schwarz
fuente
3

Si está bastante avanzado, puede comenzar con la encuesta de Wolf-Drucker sobre métodos cuánticos para problemas clásicos. Es una buena manera de comprender las técnicas cuánticas antes de llegar a los problemas cuánticos .

Suresh Venkat
fuente
2

No creo que necesites aprender mecánica cuántica. Sin embargo, depende de en qué área le gustaría trabajar. Hay áreas del campo que realmente necesitan un conocimiento sobre mecánica cuántica, sin embargo, como el área en la que trabajo, la teoría de tipos y el cálculo lambda, no lo necesito, puedo hacerlo solo conociendo algunos de los modelos computacionales para ello.

Alejandro DC
fuente
2

Además de su texto estándar con Chuang, Michael Nielsen tiene una serie de video conferencias en Youtube llamada Quantum Computing for the Determined que hasta ahora ofrece una visión general del modelo computacional. Los videos son muy fáciles de ver para cualquier persona con un poco de comprensión de la informática y el álgebra lineal.

Max
fuente