¿Por qué no implementar circuitos cuánticos en ordenadores clásicos?

Question

De alguna manera he perdido de vista el panorama general en mi estudio de la computación cuántica. Entiendo que todavía no sabemos si los ordenadores cuánticos son más potentes que los clásicos, en el sentido de la complejidad computacional. Pero me pregunto:

Dado que toda puerta cuántica puede verse como una multiplicación matricial (unitaria), y que la multiplicación matricial puede hacerse clásicamente en tiempo polinómico, ¿de dónde viene la supuesta ventaja? ¿Qué me impide tomar un circuito cuántico de tamaño polinómico e implementarlo como un número polinómico de multiplicaciones matriciales (que requieren un tiempo polinómico)? ¿Cuál es la operación que clásicamente no está disponible?

Answer 1

La multiplicación de matrices es polinómica en el número de elementos de la matriz. En la computación cuántica, el número de elementos de la matriz es básicamente el número de elementos del vector de estado cuántico, que es exponencial en el tamaño de la entrada (el número de qubits).

Answer 2

El punto falso de la premisa es que una composición de puertas de un solo qubit y de dos qubits estará representada por algún tipo de composición de matrices de 2×2 y 4×4. De hecho, si una puerta de un solo qubit (para dos qubits es similar) actúa sobre el $i$ -ésimo qubit de $n$ la matriz debe ser convertida en $$(Id_2)^{\otimes (i-1)} \otimes A \otimes (Id_2)^{\otimes (n-i)},$$ donde $A$ es el original $2×2$ matriz, para describir su acción sobre la $n$ -Estado de los qubits. Se trata de una matriz de dimensiones $2^n × 2^n$ independientemente del tipo de puerta.

Aunque el producto tensorial con las identidades parece trivial, recordemos lo que significa para una aplicación sobre un vector de estado utilizando el algoritmo más sencillo:

for each index u, 0  u < 2^n:
  define u_i = bit value of i-th bit of u
  define v = u XOR 2^i
  if u_i = 0:
    new (psi[u], psi[v]) = a*psi[u] + b*psi[v]
  else:
    new (psi[u], psi[v]) = d*psi[u] + c*psi[v]

Sí, en el núcleo de este pseudo-algoritmo sólo hay una multiplicación bidimensional. Pero se hace $2^n$ tiempos.

Incluso antes de llegar a realizar la simulación clásica real, uno puede quedarse sin memoria disponible incluso en almacenar el estado en un instante determinado. Consulte $n = 100$ qubits, es decir $2^{100}$ amplitudes complejas de doble precisión (128 bits cada una). Se calcula que supera la capacidad de almacenamiento de datos de todos los ordenadores de la Tierra en unos 14 órdenes de magnitud, así que no lo veremos pronto. Mientras tanto, un ordenador cuántico de 100 bits empezaría a ser interesante para las aplicaciones, En teoría, no es raro que haya muchos más de los previstos.

Answer 3

Dicho de otra manera, el espacio de Hilbert (H) de su circuito cuántico crece exponencialmente ( $ \text{dim H} = 2^n$ ) donde n es el número de qubits. Existe una clase de circuitos cuánticos que pueden implementarse en tiempo polinómico, pero requieren que las puertas del circuito cuántico estén restringidas al grupo de Pauli y/o al normalizador del grupo de Pauli (Teorema de Gottesman Knill). Esto también restringe el tipo de modelos de error que se emplea en el circuito cuántico. La razón básica es que existe un isomorfismo que se puede definir entre el grupo de Pauli y el espacio vectorial sobre el campo finito con elementos. La multiplicación de los elementos del grupo de Pauli se convierte en un producto simpléctico de los elementos del espacio vectorial.

Answer 4

Porque las matrices son más grandes de lo que crees.

Considera un circuito sencillo de 8 qubits; quizás una transformada de Fourier. Utiliza ~40 puertas, y cada puerta multiplica el vector de estado del sistema de 8 qubits por alguna matriz. Para simular este sistema de forma clásica. se podría esperar que tuviéramos que invertir algo así como $40\cdot 8=320$ unidades arbitrarias de trabajo computacional (AUCW).

Pero el vector de estado del sistema tiene una amplitud para cada posible estado clásico del sistema. Se pueden asignar ocho bits $2^8 = 256$ valores posibles, por lo que nuestro vector de estado debe tener 256 entradas y no ocho o dieciséis. En consecuencia, una matriz que transforme este sistema debe tener un tamaño $256 \times 256$ , aunque sólo $256$ es realmente una estimación aproximada mucho mejor del "tamaño del trabajo", ya que la matriz de una sola puerta será escasa. Nuestra estimación de $40 \cdot 8 = 320$ La AUCW estaba muy equivocada. Una suposición mucho mejor es $40 \cdot 2^8 = 40 \cdot 256 = 10240$ . Así que $10$ kiloAUCW.

Este problema se hace muy camino peor a medida que aumenta el número de qubits. Con 50 qubits el vector de estado tiene $2^{50}$ entradas, las matrices son $2^{50} \times 2^{50}$ la transformada de Fourier utiliza ~1250 puertas, y tenemos que gastar un millón un millón de un millón de AUCWs para hacer la simulación clásica. Mientras que el ordenador cuántico hace apenas 1250 AUQW.