Restricción de entradas de operadores unitarios a números reales y conjuntos de puertas universales

10

En el artículo seminal de Bernstein y Vazirani, "Teoría de la complejidad cuántica", muestran que una transformación unitaria dimensional puede ser aproximada eficientemente por un producto de lo que llaman "rotaciones casi triviales" y "cambios de fase casi triviales".re

Las "rotaciones casi triviales" son matrices unitarias dimensionales que actúan como identidad en todas las dimensiones menos 2, pero actúan como una rotación en el plano atravesado por esas dos dimensiones (es decir, tiene una submatriz de 2x2 de la forma:re

(cosθ-pecadoθpecadoθcosθ)

para algunos ).θ

Los "cambios de fase casi triviales" son matrices unitarias dimensionales que actúan como identidad en todas las dimensiones menos 1, pero aplican un factor de para alguna a esa dimensión.e i θ θremiyoθθ

Además, muestran que solo se necesita un ángulo de rotación (tanto para las unidades de rotación como de desplazamiento de fase), dado que el ángulo es un múltiplo irracional de (BV establece el ángulo en .2 π j = 1 2 - 2 j2π2πj=12-2j

Documentos posteriores sobre la teoría de la complejidad cuántica (como la de Adleman et al o Fortnow y Rogers) afirman que el resultado BV implica que el cálculo cuántico universal se puede lograr con operadores unitarios cuyas entradas están en .R

¿Cómo sigue esto? Puedo entender que un producto de matrices de rotación casi triviales le dará una matriz unitaria con entradas reales, pero ¿qué pasa con las matrices de cambio de fase?

Es decir: si solo puede realizar rotaciones casi triviales y matrices de desplazamiento de fase donde las entradas de la matriz son , ¿podemos aproximar eficientemente todas las demás matrices de desplazamiento de fase?0 0,±1

Sospecho que esta implicación no es inmediatamente obvia, y la prueba adecuada para ello se parecería a la prueba de que la puerta tipo Toffoli de Deutsch es universal, ¿o me estoy perdiendo algo muy obvio?

Henry Yuen
fuente

Respuestas:

13

Hay una prueba simple de que Toffoli y Hadamard son Quantum Universal de Dorit Aharonov, que muestra primero cómo se pueden simular amplitudes complejas mediante amplitudes reales sobre un espacio Hilbert más grande con un qubit más.

"Esto se hace agregando un qubit adicional al circuito, cuyo estado indica si el estado del sistema está en la parte real o imaginaria del espacio de Hilbert, y reemplazando cada puerta compleja opera en k qubits por su versión real , indicada ˜ U , que opera en los mismos k qubits más el qubit extra. ˜ U se define por:UkU~kU~

U~El |yoEl |0 0=[Rmi(U)El |yo]El |0 0+[yometro(U)El |yo]El |1
U~El |yoEl |1=-[yometro(U)El |yo]El |0 0+[Rmi(U)El |yo]El |1

{0 0,1,±12}

Martin Schwarz
fuente
Gracias Martin! Sin embargo, me parece que la técnica de Aharonov para reemplazar unidades unitarias complejas por unidades unitarias reales no es la misma que Adleman / BV consideró (porque no puedo encontrar evidencia de que pensaran de esta manera). Pero el resultado de Aharanov es interesante y muy agradable.
Henry Yuen
1
Estoy bastante seguro de que Adleman / BV utilizó una construcción que duplicó el número de qubits en lugar de solo agregar uno, pero que funcionó de manera similar.
Peter Shor
@Peter: la construcción de Rudolph y Grover funciona de esa manera, usando dos rebits para codificar un solo qubit: quant-ph / 0210187.
Joe Fitzsimons
9

Además del documento que Martin le señaló, hubo un documento anterior de Terry Rudolph y Lov Grover que mostraba que una puerta de 2 reinicios es universal para la computación cuántica (ver quant-ph / 0210187 ). La puerta tiene todas las entradas reales, y en caso de que no se dé cuenta, los reinicios son qubits donde las amplitudes están restringidas a números reales. Esta puede ser la fuente del reclamo. La puerta en cuestión descrita en el documento es una rotación Y controlada.

G(θ)=Y2(θ2)CZ12Y2(θ2)CZ12

Joe Fitzsimons
fuente