Decidabilidad / algoritmo para verificar la universalidad de un conjunto de puertas cuánticas

Dado un conjunto finito de puertas cuánticas , ¿es decidible (en sentido teórico de la computación) si es un conjunto de puerta universal? Por un lado, "casi todos" los conjuntos de compuertas son universales, por otro lado, los conjuntos de compuertas no universales aún no se comprenden bien (en particular, por supuesto, no se sabe si cada conjunto de compuertas no universales es clásicamente simulable), así que imagino que dar un algoritmo explícito para verificar la universalidad podría no ser trivial. $\mathcal{G} = \{G_1, \dots, G_n\}$ $\mathcal{G}$

quantum-computing Marcin Kotowski
fuente

¿Puedes aclarar la pregunta? La respuesta de Joe supone que tiene un número fijo de qubits y que todas las puertas actúan sobre ellas, pero por universalidad, a menudo asumimos que las puertas pueden actuar sobre cualquier subconjunto de qubits. Por ejemplo, CNOT + todas las puertas de un qubit no son universales si las puertas de un qubit solo pueden actuar en el primer qubit, y CNOT solo es del qubit 1 al qubit 2. En el último caso, es posible que queramos extrapolar a muchos qubits para conseguir la universalidad En ese caso, creo que la respuesta puede ser desconocida.

@DanielGottesman: estoy de acuerdo con las limitaciones de mi respuesta. De hecho, creo que es indecidible en el último caso de la siguiente manera: tome un autómata celular en una red infinita de qubits y para codificar el problema de detención (llame a esta actualización unitaria ). Luego tome una segunda red con un QCA universal (con actualización unitaria ). Podemos definir un nuevo , donde el subíndice denota un qubit que se establece en iff el primer celular autómatas se detiene.

U_{1}

$U_1$

U_{2}

$U_2$

C U_{2} = | 0 ⟩ ⟨ 0 |_{H} \otimes I + | 1 ⟩ ⟨ 1 | \otimes U_{2}

$CU_2 = |0\rangle\langle0|_H\otimes I + |1\rangle\langle1|\otimes U_2$

H

$H$

| 1 ⟩

$|1\rangle$

Joe Fitzsimons

Por lo tanto, la puerta es universal si y solo si la primera máquina de Turing se detiene, y por lo tanto es indecidible.

C U_{2} \times U_{1}

$CU_2 \times U_1$

Joe Fitzsimons

Respuestas:

Para el caso de los hamiltonianos, en lugar de puertas, la respuesta es trivialmente sí: simplemente enumera los elementos independientes del álgebra de Lie. Dado que el álgebra de Lie es un espacio vectorial con la adición del operador de soporte de Lie. Como el espacio es finito, tiene una base finita, y se puede verificar fácilmente si está cerrado o abierto bajo la operación de soporte de Lie. Simplemente verificando el corchete de Lie de todos los pares de operadores ortogonales se puede hacer en el tiempo polinomial en la dimensionalidad del espacio, y se puede encontrar una base de operador adecuada por el método de Gram-Schmidt.

Para las compuertas, realmente no tiene la misma opción para recurrir a infinitesimales directamente, y necesita construir compuertas con valores propios irracionales para que pueda aproximarse arbitrariamente a los generadores infinitesimales requeridos. Supongo que hay una forma relativamente simple de hacer esto, pero no me resulta obvio de inmediato.

En cualquier caso, tomar el registro de las puertas para obtener un conjunto de operadores que los generan cuando se expongan y verificar si estos generaron el álgebra de Lie completo proporcionaría un criterio simple pero no suficiente para la universalidad.

Joe Fitzsimons
fuente

¿Por qué deberíamos comprobar solo pares?

Alex 'qubeat' el

@AlexV: Debido a que el soporte de Lie toma funciona con 2 entradas. Cada vez que produce un nuevo operador linealmente independiente, produce uno ortogonal y repite hasta obtener el cierre.

Joe Fitzsimons

decir que deberías considerar , pero no solo pares, por ejemplo, ver mi propio documento arxiv.org/abs/quant-ph/0010071

[\dots [H_{k}, H_{j}], H_{l}], \dots]

$[\ldots[H_k,H_j],H_l],\ldots]$

Alex 'qubeat'

@ AlexV: No es necesario. Es un espacio vectorial, por lo que un vector es ortogonal a un subespacio dado si y solo si es ortogonal a cualquier base para ese subespacio.

Joe Fitzsimons

Probablemente estamos hablando de cosas diferentes, ¿de qué espacio vectorial estás hablando? Desde el principio, no conoce el subálgebra generado por sus puertas; debe construirlo a partir de Hamiltonianos dados para verificar si todo es álgebra de mentiras.

Alex 'qubeat' el