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".
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:
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 θ θ
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 j
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 .
¿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?
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?
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.
fuente