Compilación automática de circuitos cuánticos.

12

Una pregunta reciente aquí preguntó cómo compilar la puerta de 4 qubits CCCZ (controlado-controlado-controlado-Z) en puertas simples de 1 qubit y 2 qubit, ¡y la única respuesta dada hasta ahora requiere 63 puertas !

El primer paso fue usar la construcción C n U dada por Nielsen & Chuang:n

Con n=3 esto significa 4 compuertas CCNOT y 3 compuertas simples (1 CNOT y 2 Hadamards es suficiente para hacer la CZ final en el qubit objetivo y el último qubit de trabajo).

El teorema 1 de este documento dice que, en general, el CCNOT requiere 9 compuertas de un qubit y 6 compuertas de dos qubit (15 en total):

ingrese la descripción de la imagen aquí


Esto significa:

(4 CCNOT) x (15 puertas por CCNOT) + (1 CNOT) + (2 Hadamards) = 63 puertas totales .

En un comentario , se ha sugerido que las 63 puertas pueden compilarse luego utilizando un "procedimiento automático", por ejemplo, a partir de la teoría de los grupos automáticos .

¿Cómo se puede hacer esta "compilación automática" y cuánto reduciría la cantidad de compuertas de 1 qubit y 2 qubit en este caso?

usuario1271772
fuente
1
Estoy en medio de algunas cosas, pero vi tu pregunta. Las compuertas globales de Mølmer-Sørensen son compuertas de 2 qubits, y el documento Uso de interacciones globales en construcciones de circuitos cuánticos eficientes describe: "Implementación optimizada de la compuerta CCCZ utilizando tres compuertas GMS", vea la figura 9. Puede escribir la respuesta si es así servicial.
Rob
La representación en la imagen requiere solo 4 CCNOT, y por lo tanto 63 puertas en lugar de 93.
Dyon J Don Kiwi van Vreumingen
@DonKiwi, señaló! 4 CCNOTs en lugar de 6. Lo estoy actualizando ahora.
user1271772
1
@Rob: Parece que estás sugiriendo conjugar la X en CCCX usando dos Hadamards. Entonces el CCCX puede descomponerse como en el circuito de Nielsen & Chaung anterior. ¿Es eso correcto? En mi segunda respuesta a la pregunta de DonKiwi, hice algo como esto. Parece que su comentario llegó justo cuando estaba escribiendo esa respuesta, ya que están separados por 5 minutos (y me tomó más de 5 minutos escribirlo). Sin embargo, esta pregunta sobre la "compilación automática" sigue en pie, ya que sería bueno poder construir un circuito de la "manera obvia" y luego compilar automáticamente en algo más eficiente.
user1271772
1
@ user1271772 - Cada bit (qu) ayuda.
Rob

Respuestas:

6

Deje que g1gM sean las puertas básicas que puede usar. A los fines de este CNOT12 y CNOT13 etc., se tratan por separado. Entonces, M es polinómicamente dependiente de n , el número de qubits. La dependencia precisa implica detalles de los tipos de puertas que usa y cuán k locales son. Por ejemplo, si hay x puertas de un solo qubit e y puertas de 2 qubit que no dependen de un orden como CZ entonces .M=xn+(n2)y

Un circuito es entonces un producto de esos generadores en algún orden. Pero hay múltiples circuitos que no hacen nada. Como . Entonces esos dan relaciones en el grupo. Es decir, es una presentación grupal donde hay muchas relaciones que no conocemos.CNOT12CNOT12=Id g1gMR1

El problema que deseamos resolver se le da una palabra en este grupo, ¿cuál es la palabra más corta que representa el mismo elemento? Para presentaciones grupales generales, esto es inútil. El tipo de presentación grupal donde este problema es accesible se llama automático.

Pero podemos considerar un problema más simple. Si algunas de las , entonces las palabras de antes tienen la forma donde cada una de las son palabras solo en las letras restantes. Si logramos acortarlos usando las relaciones que no involucran a , habremos todo el circuito. Esto es similar a la optimización de los CNOT por sí mismos realizados en la otra respuesta.giw1gi1w2gi2wkwigi

Por ejemplo, si hay tres generadores y la palabra es , pero no queremos tratar con , en su lugar y a y . Luego los volvemos a armar como y eso es un acortamiento de la palabra original.aababbacbbabacw1=aababbaw2=bbabaw^1w^2w^1cw^2

Entonces, WLOG (sin pérdida de generalidad), supongamos que ya estamos en ese problema donde ahora usamos todas las puertas especificadas. De nuevo, esto probablemente no sea un grupo automático. Pero, ¿y si descartamos algunas de las relaciones? Luego tendremos otro grupo que tiene un mapa de cocientes hasta el que realmente queremos.g1gMR1

El grupo sin relaciones es un grupo libre , pero si pone como relación, obtendrá el producto libre y hay un mapa de cocientes del primero al segundo que reduce el número de en cada segmento del módulo .g1g2g12=id Z2Zg12

Las relaciones que arrojemos serán tales que la de arriba (la fuente del mapa del cociente) será automática por diseño. Si solo usamos las relaciones que quedan y acortamos la palabra, entonces seguirá siendo una palabra más corta para el grupo del cociente. Simplemente no será óptimo para el grupo de cocientes (el objetivo del mapa de cocientes), pero tendrá la longitud a la longitud con la que comenzó.

Esa fue la idea general, ¿cómo podemos convertir esto en un algoritmo específico?

¿Cómo elegimos el y las relaciones que deseamos para obtener un grupo automático? Aquí es donde entra en juego el conocimiento de los tipos de puertas elementales que usamos habitualmente. Hay muchas involuciones, así que conserve solo esas. Preste especial atención al hecho de que estas son solo las involuciones elementales, por lo que si su hardware tiene dificultades para intercambiar qubits que están muy separados en su chip, esto los escribe solo en los que puede hacer fácilmente y reduce esa palabra a ser lo más corto posiblegi

Por ejemplo, suponga que tiene la configuración de IBM . Entonces son las puertas permitidas. Si desea hacer una permutación general, descomponga en factores . Esa es una palabra en el grupo que deseamos acortar .s01,s02,s12,s23,s24,s34si,i+1s01,s02,s12,s23,s24,s34R1

Tenga en cuenta que estas no tienen que ser las involuciones estándar. Puede agregar además de por ejemplo. Piense en el teorema de Gottesman-Knill , pero de manera abstracta eso significa que será más fácil generalizar. Tal como usar la propiedad que bajo secuencias exactas cortas, si tiene sistemas de reescritura finitos completos para los dos lados, entonces obtiene uno para el grupo medio. Ese comentario es innecesario para el resto de la respuesta, pero muestra cómo puede construir ejemplos más grandes y generales a partir de los de esta respuesta.R(θ)XR(θ)1X

Las relaciones que se mantienen son solo las de la forma . Esto le da un grupo Coxeter y es automático. De hecho, ni siquiera tenemos que comenzar desde cero para codificar el algoritmo para esta estructura automática. Ya está implementado en Sage (basado en Python) en un propósito general. Todo lo que tiene que hacer es especificar el y ya tiene la implementación restante. Podría hacer algunas aceleraciones además de eso.(gigj)mij=1mij

mij es realmente fácil de calcular debido a las propiedades de localidad de las puertas. Si las puertas son como máximo -local, entonces el cálculo de se puede hacer en un espacio de Hilbert de dimensiones. Esto se debe a que si los índices no se superponen, entonces sabe que . es para cuando y conmutan. También solo tiene que calcular menos de la mitad de las entradas. Esto se debe a que la matriz es simétrica, tiene 's en la diagonal ( ). Además, la mayoría de las entradas solo cambian el nombre de los qubits involucrados, por lo que si conoce el orden dekmij22k1mij=2mij=2gigjmij1(gigi)1=1(CNOT12H1) , conoce el orden de sin hacer el cálculo nuevamente.CNOT37H3

Eso se ocupó de todas las relaciones que solo involucraban a lo sumo dos puertas distintas (prueba: ejercicio). Las relaciones que involucraron a o más fueron descartadas. Ahora los volvemos a colocar. Digamos que tenemos eso, entonces uno puede realizar el codicioso algoritmo de Dehn usando nuevas relaciones. Si hubo un cambio, lo recuperamos para volver a atravesar el grupo Coxeter. Esto se repite hasta que no haya cambios.3

Cada vez que la palabra se acorta o se mantiene la misma longitud y solo usamos algoritmos que tienen un comportamiento lineal o cuadrático. Este es un procedimiento bastante barato, así que podría hacerlo y asegurarse de no hacer nada estúpido.

Si desea probarlo usted mismo, indique el número de generadores como , la longitud de la palabra aleatoria que está probando y la matriz Coxeter como .NKm

edge_list=[]
for i1 in range(N):
    for j1 in range(i):
        edge_list.append((j1+1,i1+1,m[i1,j1]))
G3 = Graph(edge_list)
W3 = CoxeterGroup(G3)
s3 = W3.simple_reflections()
word=[choice(list([1,..,N])) for k in range(K)]
print(word)
wTesting=s3[word[0]]
for o in word[1:]:
    wTesting=wTesting*s3[o]
word=wTesting.coset_representative([]).reduced_word()
print(word)

Un ejemplo con N=28y K=20, las dos primeras líneas son la palabra de entrada no reducida, las dos siguientes son la palabra reducida. Espero no haber cometido un error al ingresar a la matriz .m

[26, 10, 13, 16, 15, 16, 20, 22, 21, 25, 11, 22, 25, 13, 8, 20, 19, 19, 14, 28]

['CNOT_23', 'Y_1', 'Y_4', 'Z_2', 'Z_1', 'Z_2', 'H_1', 'H_3', 'H_2', 'CNOT_12', 'Y_2', 'H_3', 'CNOT_12', 'Y_4', 'X_4', 'H_1', 'Z_5', 'Z_5', 'Y_5', 'CNOT_45']

[14, 8, 28, 26, 21, 10, 15, 20, 25, 11, 25, 20]

['Y_5', 'X_4', 'CNOT_45', 'CNOT_23', 'H_2', 'Y_1', 'Z_1', 'H_1', 'CNOT_12', 'Y_2', 'CNOT_12', 'H_1']

Poniendo de vuelta esos generadores como solo volvemos a poner las relaciones como y que conmuta con puertas que no involucran qubit . Esto nos permite hacer que la descomposición de antes tenga la mayor tiempo posible. Queremos evitar situaciones como . (En Cliff + T, a menudo se busca minimizar el recuento de T). Para esta parte, el gráfico acíclico dirigido que muestra la dependencia es crucial. Este es un problema para encontrar un buen tipo topológico del DAG. Eso se hace cambiando la precedencia cuando uno tiene la opción de elegir qué vértice usar a continuación. (No perdería el tiempo optimizando esta parte demasiado).TiTin=1Tiiw1gi1w2gi2wkwiX1T2X1T2X1T2X1

Si la palabra ya está cerca de la longitud óptima, no hay mucho que hacer y este procedimiento no ayudará. Pero como el ejemplo más básico de lo que encuentra es que si tiene varias unidades y olvidó que había un al final de uno y un al comienzo del siguiente, se eliminará ese par. Esto significa que puede realizar rutinas comunes en el recuadro negro con mayor confianza de que cuando las reúne, todas las cancelaciones obvias se resolverán. Hace otros que no son tan obvios; esos usan cuando .HiHimij1,2

AHusain
fuente
+1 !!! ¡Muchos detalles! Lo estoy leyendo :)
user1271772
1
@AHussain, ¿es posible trabajar en un ejemplo en el que esto se aplica a la construcción "ingenua" de CCCZ en mi pregunta y terminar con un número menor de puertas? La pregunta original sobre CCCZ ahora tiene 6 respuestas, y muchas de ellas tienen recuentos de compuertas mucho más pequeños. Me pregunto qué daría tu enfoque para el recuento de puertas.
user1271772
4

Utilizando el procedimiento descrito en https://arxiv.org/abs/quant-ph/0303063 1 , cualquier compuerta diagonal, en particular la compuerta CCCZ, puede descomponerse en términos de, por ejemplo, CNOT y compuertas diagonales de un qubit, donde los CNOT se pueden optimizar por sí mismos siguiendo un procedimiento de optimización clásico.

La referencia proporciona un circuito que usa 16 CNOT para puertas diagonales arbitrarias de 4 qubits (Fig. 4).


Observación: Si bien en principio podría haber un circuito más simple (dicho circuito se ha optimizado con una arquitectura de circuito más restringida en mente), debería ser casi óptimo: el circuito necesita crear todos los estados de la forma para cualquier subconjunto no trivial , y hay 15 de esos para 4 qubits.iIxiI{1,2,3,4}

Tenga en cuenta también que esta construcción de ninguna manera debe ser óptima.


1 Nota: soy autor

Norbert Schuch
fuente
Interesante. Todavía tengo que leer el periódico para ver cuál es el procedimiento. También estoy esperando que @AHussain nos diga cómo hacerlo utilizando la teoría de los grupos automáticos.
usuario1271772