¿Cuál es la justificación matemática para la "universalidad" del conjunto universal de puertas cuánticas (CNOT, H, Z, X y π / 8)?

En esta respuesta, mencioné que las puertas CNOT, H, X, Z y forman un conjunto universal de puertas, que dado un número suficiente de puertas puede acercarse arbitrariamente a la replicación de cualquier puerta cuántica unitaria (llegué a conocer sobre este hecho de las conferencias EdX del profesor Umesh Vazirani). Pero, ¿hay alguna justificación matemática para esto? ¡Debería haber! Intenté buscar documentos relevantes pero no pude encontrar mucho. $\pi/8$

quantum-gate universal-gates gate-synthesis Sanchayan Dutta
fuente

Respuestas:

La respuesta que menciona hace referencia al libro de Michael Nielsen e Isaac Chuang, Computación cuántica e información cuántica (Cambridge University Press), que contiene una prueba de la universalidad de estas puertas. (En mi edición de 2000, esto se puede encontrar en la página 194.) La idea clave es que la puerta (o puerta ), junto con la puerta , genera dos rotaciones diferentes en la esfera Bloch con ángulos que son múltiplos irracionales de . Esto permite que las combinaciones de puertas y llenen densamente la superficie de la esfera Bloch y, por lo tanto, se aproximen a cualquier operador unitario de un qubit. $T$ $\pi/8$ $H$ $2\pi$ $T$ $H$

El teorema de Solovay-Kitaev muestra que esto se puede hacer de manera eficiente . Aquí, "eficientemente" significa polinomio en , donde es la precisión deseada. Esto también se demuestra en el libro de Nielsen y Chuang (Apéndice 3 en la edición de 2000). Se puede encontrar una construcción explícita en https://arxiv.org/abs/quant-ph/0505030 . $\log(1/\epsilon)$ $\epsilon$

La combinación de puertas CNOT le permite a uno aproximarse a unitarios arbitrarios de múltiples qubits, como lo muestran Barenco et al. en Phys. Rev. A 52 3457 (1995). (Una preimpresión de este documento se puede encontrar en https://arxiv.org/abs/quant-ph/9503016 .) Esto también se discute en Nielsen y Chuang (p. 191 en la edición de 2000).

Brian R. La Cour
fuente

Se puede obtener un resultado aún más fuerte con Kliuchnikov, Maslov y Mosca, probados en Giles Selinger .

AHusain

$Z$ $X$
$\rm{CNOT}$ $H$ $T=\pi/8$

$H$ $T$
$\rm{CNOT}$ $\epsilon>0$ $\mathcal{O}(\log^2(1/\epsilon))$

$\epsilon=0$ $\pi/2$ $\frac{a+ib}{2^n} + \frac{c+id}{2^{n+1/2}}$

$\{{\rm{CCNOT}},H\}$ ${D(\theta)}$

usuario1271772
fuente

Sin embargo, CCNOT + H es universal en un sentido diferente: es computacionalmente universal, pero no puede realizar ninguna puerta.

Norbert Schuch,

ϵ > 0

$\epsilon>0$

ϵ > 0

$\epsilon>0$

No No puede realizar ninguna puerta con coeficientes complejos (= no reales), por razones obvias. Es computacionalmente universal, es decir, puede ejecutar cualquier q. cálculo, pero no lo hace mediante la implementación individual de dichas puertas, sino una realización equivalente. Así que si quieres realizar unitarios (que parece ser el punto de la cuestión), es no un conjunto de puerta universal.

Norbert Schuch

@NorbertSchuch: Un ejemplo de cálculo cuántico es simular un unitario complejo. Entonces, si CCNOT + H puede hacer cualquier q. computación, ¿no puede acercarse arbitrariamente a la simulación de alguna unidad?

usuario1271772

Tanto CCNOT como H solo tienen entradas reales. NO HAY MANERA de que obtenga CUALQUIER puerta con entradas complejas. --- En términos más generales, existen (al menos) 3 nociones de "simulación": obtener cualquier unitario, obtener las estadísticas de medición de una computadora cuántica o resolver un problema de BQP. CCNOT + H es universal en el segundo (y tercer) sentido, pero no en el primero.

Norbert Schuch