Construyendo una computadora cuántica en simulación

Si uno quiere comenzar a construir una computadora cuántica desde cero dentro de las simulaciones (como la gente puede construir una computadora clásica desde cero en el curso Nand2Tetris ), ¿es posible?

En caso afirmativo, ¿cuáles serían algunos enfoques posibles?

Además, ¿cuáles serán los límites de una máquina tan simulada, dada una cantidad específica de potencia informática clásica? Por ejemplo, si tuviéramos que elegir su computadora de escritorio / portátil promedio, ¿cuál sería el límite? Si tomamos una supercomputadora (como Titán), ¿cuál sería el límite?

La primera parte de su pregunta parece un duplicado de una publicación existente de QC SE: ¿Hay emuladores para computadoras cuánticas? .

No estoy completamente seguro de lo que quieres decir con construir una computadora cuántica desde cero dentro de las simulaciones . Sin embargo, sí, puede hacer simulaciones de software de una computadora cuántica usando su computadora portátil / computadora de escritorio promedio. El "límite" exacto dependerá de las especificaciones de la computadora.

Dado que una computadora cuántica no viola la tesis de Church-Turing , en teoría es definitivamente posible simular una computadora cuántica usando una máquina Turing ideal . El enfoque obvio para simular un sistema de este tipo requiere un tiempo exponencial en una computadora clásica y la complejidad del espacio es una función exponencial del número de bits cuánticos simulados. Por ejemplo, que simulan un equipo bit cuántico, que había necesidad de almacenar alrededor de 2 n bits de información en su ordenador clásico en cada instante. Además, la implementación de puertas cuánticas volverá a requerir una gran cantidad de recursos en términos de complejidad de tiempo y espacio. Una implementación de una puerta cuántica que opera en n -bits debería almacenar aproximadamente$n$$2^{n}$$n$ (porque puede representar todas las operaciones de puerta cuántica como una matriz de tamaño 2 n × 2 n ) bits de información.$4^{n}$$2^{n}\times2^{n}$

Puede estimar el "límite" según las especificaciones de la computadora clásica. Por ejemplo, si el tamaño de memoria (accesible) de su computadora clásica es de alrededor de TB, esperaría que pueda simular una computadora cuántica log 4 ( 8 × 10 12 ) ≈ 21 bits (para estar seguro, digamos 20 ). Sin embargo, tenga en cuenta que las computadoras clásicas tardarían mucho más tiempo en acceder a todos los bits individuales de información, en comparación con una computadora cuántica real (dependiendo del hardware de la computadora cuántica). Entonces va a ser más lento$1$$\log_4(8\times 10^{12})\approx 21$$20$que una computadora cuántica real! Algunas otras limitaciones son que, después de cada acción de una puerta de bits, debe realizar un seguimiento de qué qubits de salida están enredados, lo cual es un problema NP-difícil . Además, la medición no se puede simular con precisión en una computadora clásica, porque no existe un generador de números verdaderamente aleatorio .$n$

Bueno, actualmente estoy trabajando en un simulador de una computadora cuántica. La idea básica de la computación cuántica, por supuesto, es puertas representadas por matrices aplicadas a qubits representados por vectores. Usando el paquete numpy de Python, esto no es tan difícil de programar en el sentido más básico.

A partir de ahí, uno podría ampliar, por supuesto, la interfaz. También se podría considerar intentar convertirlo en un simulador de una computadora cuántica no ideal, es decir, teniendo en cuenta los tiempos de decoherencia y la corrección de errores.

Luego, entras en un territorio muy desconocido. ¿Cómo se construye el conjunto de instrucciones para una computadora cuántica? Quién sabe. Tendrás que averiguarlo. También tendrá que averiguar su versión de ensamblaje, e incluso su versión de lenguajes de programación de nivel superior.

Entonces, ¿las limitaciones de una computadora clásica en esto? Bueno, esta es una pregunta realmente complicada (y vale la pena preguntar por separado, en mi humilde opinión), pero aquí hay un resumen rápido:

• no sabemos si las computadoras cuánticas son realmente mejores que las computadoras clásicas; los algoritmos para computadoras clásicas podrían no ser lo suficientemente buenos todavía (supremacía cuántica)
• digamos, como parece decentemente probable, que las computadoras cuánticas son mejores que las computadoras clásicas. esa mejora dependerá en gran medida del problema: las computadoras cuánticas podrían ver, por ejemplo, una mejora de velocidad mucho mayor en la búsqueda de factorizaciones principales que en la verificación del correo electrónico. (vea también este P.SE q / a.)
• $O\Big(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}}\Big)$$O((\log N)^2(\log \log N)(\log \log \log N))$
• $|0\rangle$$|1\rangle$

Siento que esta respuesta se basa principalmente en un malentendido subyacente de lo que significa "simular" algo.

En términos generales, "simular" un sistema complejo significa reproducir ciertas características de dicho sistema con una plataforma que es más fácil de controlar (a menudo, pero no siempre, una computadora clásica).

Por lo tanto, la cuestión de si "se puede simular una computadora cuántica en una computadora clásica" es algo mal planteada. Si quiere decir que desea replicar todos los aspectos posibles de una "computadora cuántica", eso nunca va a suceder, al igual que nunca podrá simular todos los aspectos de cualquier sistema clásico (a menos que use el mismo sistema idéntico sistema, por supuesto).

Por otro lado, ciertamente puede simular muchos aspectos de un dispositivo complejo como una "computadora cuántica". Por ejemplo, uno puede querer simular la evolución de un estado dentro de un circuito cuántico. De hecho, ¡esto puede ser extremadamente fácil de hacer! Por ejemplo, si tiene Python en su computadora, simplemente ejecute lo siguiente

import numpy as np
identity_2d = np.diag([1, 1])
pauliX_gate = np.array([[0, 1], [1, 0]])
hadamard_gate = np.array([[1, 1], [1, -1]]) / np.sqrt(2)

cnot_gate = np.kron(identity_2d, pauliX_gate)
H1_gate = np.kron(hadamard_gate, identity_2d)

awesome_entangling_gate = np.dot(cnot_gate, H1_gate)

initial_state = np.array([1, 0, 0, 0])
final_state = np.dot(awesome_entangling_gate, initial_state)
print(final_state)

¡Felicitaciones, usted simplemente "simuló" la evolución de un estado separable de dos qubits a un estado Bell!

$n$$2^n$$^{(1)}$$^{(2)}$

Otras respuestas ya tocaron varios aspectos de esta dureza, y las respuestas a esta otra pregunta ya mencionan muchas plataformas disponibles para simular / emular varios aspectos de algoritmos cuánticos, por lo que no iré allí.

(1) Un ejemplo interesante de esto es el problema de simular un dispositivo de muestreo de bosones (este no es un algoritmo cuántico en el sentido de un estado que evoluciona a través de una serie de compuertas, pero no obstante es un ejemplo de un dispositivo cuántico no trivial). BosonSampling es un problema de muestreo , en el que uno tiene la tarea del problema del muestreode una distribución de probabilidad específica, y esto se ha demostrado (bajo supuestos probables) que es imposible hacerlo de manera eficiente con un dispositivo clásico. Aunque nunca se demostró que fuera un aspecto fundamental de esta dureza, un problema ciertamente no trivial asociado con la simulación de un dispositivo de muestreo de bosones era tener que calcular un número exponencialmente grande de probabilidades a partir de las cuales tomar muestras. Sin embargo, recientemente se demostró que, de hecho, no es necesario calcular todo el conjunto de probabilidades para tomar muestras de ellos ( 1705.00686 y 1706.01260) En principio, esto no está lejos de simular la evolución de muchos qubits en un circuito cuántico sin tener que almacenar todo el estado del sistema en un punto dado. Con respecto a los circuitos cuánticos más directos, los ejemplos de avances recientes en las capacidades de simulación son 1704.01127 y 1710.05867 (también uno súper reciente, aún no publicado, es 1802.06952 ).

(2) De hecho, se ha demostrado (o más bien, se ha proporcionado una fuerte evidencia del hecho) que no es posible simular eficientemente la mayoría de los circuitos cuánticos, ver 1504.07999 .