¿Cómo hacer un seguimiento de los enredos al emular la computación cuántica?

Estoy tratando de construir una biblioteca de computación cuántica como mi proyecto universitario. Todavía estoy aprendiendo todos los aspectos del campo de la computación cuántica. Sé que ya hay bibliotecas eficientes para la emulación cuántica. Solo quiero hacer el mío, lo que me ayudará a comprender algunos de los conceptos centrales de la computación cuántica.

Sé que qubits se pueden almacenar con una matriz compleja de elementos. Además, una puerta qubit es una matriz 2D. Entonces, las siguientes son mis dudas (principalmente relacionadas con enredos):$n$$2^n$$n$$2^n \times 2^n$

1. ¿Cuándo necesito encontrar el producto tensor de las puertas (como , para un sistema de qubits)? ¿Es siempre necesario calcular el producto tensorial de orden , incluso si los qubits no están enredados?$I \otimes H \otimes I$$3$$2^n \times 2^n$

2. Con solo una matriz de elementos de (que almaceno los coeficientes), ¿puedo calcular de alguna manera qué qubits están enredados? ¿O necesito hacer otra estructura de datos para almacenar la información de entrelazamiento de mis qubits (sobre qué qubits están enredados)?$2^n$$n$

3. ¿Es realmente relevante mi segunda pregunta? ¿Necesito hacer un seguimiento de la información del enredo? Quiero decir, no sé si multiplicar puertas con coeficientes es suficiente (incluso si el sistema está enredado). Tal vez sea relevante solo en el momento de la medición.

Ciertamente, es suficiente calcular siempre la matriz unitaria completa , y luego aplicarla al vector de estado de entrada 2 n . Si eso es lo que eliges hacer, eso es todo lo que tienes que hacer, ya que toda la información de enredos está contenida en ese vector. Una forma rápida y fácil de ver si un qubit en particular está enredado es tomar el rastro parcial de su vector de estado (puro) sobre todos los demás qubits. Si la matriz resultante es de rango 1, ese qubit está en un estado separable, de lo contrario está enredado.$2^n\times 2^n$$2^n$

Supongo que el punto de su pregunta es realmente "¿Cómo se puede evitar este enorme costo computacional?". En general, no puede: si está utilizando toda la potencia de la computadora cuántica, siempre necesitará el vector de estado de entradas. Sin embargo, hay varios trucos que reducen el costo computacional, como retrasar la necesidad de un vector de estado tan grande al realizar un seguimiento del enredo.$2^n$

Mejoras de eficiencia

El mayor ahorro que puede hacer en comparación con la implementación ingenua anterior es evitar las matrices unitarias . Por ejemplo, si solo está usando compuertas de 1 o 2 qubits, simplemente usando la escasez de matrices significa que solo necesita O ( 2 n ) de almacenamiento en lugar de O ( 2 2 n ) .$2^n\times 2^n$$O(2^n)$$O(2^{2n})$

Luego hay otras tácticas que puedes emplear. Por ejemplo, imagine que desea aplicar la puerta de dos qubits unitaria en qubits i y j . Usted puede tomar series de 4 elementos de su vector de estado ( | x ⟩ 1 , 2 , ... n ∖ i , j | y ⟩ i , j para fijo x ∈ { 0 , 1 } n - 2 , tomando todas diferentes y ∈ { 0 , 1 $U$$i$$j$$|x\rangle_{1,2,\ldots n\setminus i,j}|y\rangle_{i,j}$$x\in\{0,1\}^{n-2}$ ) y solo aplicando la U unitaria 4 × 4 en ese vector de 4 elementos. Repetir esto para cada x devolverá U promulgada en el vector de estado original.$y\in\{0,1\}^2$$4\times 4$$U$$x$$U$

Me imagino que hay otras estrategias que uno podría idear. El que se sugirió de la pregunta original fue el seguimiento de enredos. Esto proporciona mejoras en la memoria y la velocidad al comienzo de un cálculo, pero finalmente es equivalente porque (presumiblemente) todo en la computadora cuántica terminará enredado.

Seguimiento de enredos

Supongamos que su cálculo consiste solo en la evolución unitaria y la medición en el conjunto de qubits, es decir, no hay decoherencia, mapas probabilísticos, etc. Supongamos además que comienza desde un estado completamente separable como | 0 ⟩ ⊗ n . En este punto, cada qubit es separable, y es suficiente para mantener n registros diferentes, cada uno de los cuales transmite el estado de un qubit separable. Si su primera puerta es solo una operación de un solo qubit U en qubit i , entonces simplemente actualice el estado almacenado en qubit i como | ψ i ⟩ ↦ T $n$$|0\rangle^{\otimes n}$$n$$U$$i$$i$ , y usted no tiene que tocar nada más.$|\psi_i\rangle\mapsto U|\psi_i\rangle$

Si quieres hacer una de dos qubits puerta de entre qubits i y j , por ejemplo, entonces usted tiene que combinar los estados en ambos sitios. Por lo tanto, reemplaza dos registros de cada dimensión 2 con un registro de dimensión 4, que contiene el estado V | ψ i ⟩ | ψ j ⟩ . El problema es que ahora no puede dividir este estado nuevamente, por lo que debe mantener esos dos qubits en un registro para siempre. Por supuesto, si alguna vez tiene una puerta U de 1 qubit para aplicar en qubit i , ahora tendrá que aplicar | ψ i , j ⟩ ↦ U ⊗ $V$$i$$j$$V|\psi_i\rangle|\psi_j\rangle$$U$$i$ . Entonces, la próxima vez que desee una puerta 2-qubit entre, por ejemplo, j y k , que tendrá que combinar los espacios para ( i , j ) y k . Esos espacios seguirán creciendo, pero si una puerta se localiza en un solo espacio, solo tiene que aplicarla allí (usandooperadores I para rellenarla en el resto de los qubits), y no tiene que hacer nada al otros espacios$|\psi_{i,j}\rangle\mapsto U\otimes\mathbb{I}|\psi_{i,j}\rangle$$j$$k$$(i,j)$$k$$\mathbb{I}$

$2^n$

Aquí hay un pseudocódigo muy crudo que puede ayudar a transmitir mi significado:

#initialise variables
entangled_blocks={{1},{2},{3},...,{n}}
quantum_states={{1,0},{1,0},...,{1,0}}

#apply action of each gate
for each gate
   for each gate_target
       target_block=entangled_blocks entry containing gate_target
   next gate_target
   if all target_blocks equal then
      apply gate on target_block (pad with identity on other qubits)
   else
      new_entangled_block=union(target_blocks)
      new_state_vec=tensor_product(quantum_states for each target block)
      apply gate on new_state_vec (pad with identity on other qubits)
      replace all target_blocks in entangled_blocks with new_entangled_block
      replace all quantum_states(all target blocks) with new_state_vec
   end if
next gate

Otras opciones

(De ninguna manera exhaustiva)

Es posible que le interese leer acerca de los Estados de productos Matrix, que son una buena manera de encapsular la información sobre estados no demasiado enredados, y que pueden proporcionarle una ruta alternativa, dependiendo de exactamente qué es lo que está tratando de lograr.