Implementación de una puerta CCCNOT usando solo puertas Toffoli

10

Una puerta CCCNOT es una puerta reversible de cuatro bits que voltea su cuarto bit si y solo si los primeros tres bits están todos en el estado 1 .

¿Cómo implementaría una puerta CCCNOT usando puertas Toffoli? Suponga que los bits en el espacio de trabajo comienzan con un valor particular, 0 o 1, siempre que los devuelva a ese valor.

chuster
fuente
¿Usando solo puertas Toffoli, o Toffoli y CNOT son juegos justos?
user1271772
Solo se permiten puertas Toffoli.
chuster
1
¿Qué parte de esta pregunta es cuántica? Parece que desea descomponer una compuerta reversible clásica (CCCNOT) en compuertas reversibles clásicas más pequeñas (CCNOT).
usuario1271772
1
La pregunta en sí no se refiere a la computación cuántica, pero las puertas son importantes para los circuitos cuánticos.
chuster

Respuestas:

8

Supongo que lo que estás buscando es el siguiente circuito. Aquí, b1,b2,b3,b4{0,1} , y es el módulo de suma 2 .

ingrese la descripción de la imagen aquí

|0|0

|143|1|0 después de que se aplica el circuito.


En la sección de comentarios, surgió la pregunta de si es posible implementar dicho circuito usando solo compuertas Toffoli, sin usar qubits auxiliares. Esta pregunta se puede responder en forma negativa, como mostraré aquí.

CCCNOTX

X=[0110]
NINCCCNOT16×16
CCCNOT=[I1400X]
det(CCCNOT)=1
4
ToffoliI2=[I600X]I2=[I1200XI2]=[I120000I20I20]
det(ToffoliI2)=1
Las puertas Toffoli también pueden actuar en diferentes qubits, por supuesto. Supongamos que dejamos que la puerta Toffoli actúe en el primer, segundo y cuarto qubit, donde el cuarto qubit es el qubit objetivo. Luego obtenemos la nueva representación matricial de la que se muestra arriba intercambiando las columnas correspondientes a los estados que difieren solo en el tercer y cuarto qubit, es decir, con , con , etc. Lo importante a tener en cuenta aquí es que el número de intercambios de columnas es par y, por lo tanto, el determinante permanece sin cambios. Como podemos escribir cada permutación de qubits como una secuencia de permutaciones consecutivas de solo qubits (es decir,|0001|0010|0101|01102S4es generado por las transposiciones en ), encontramos que para todas las puertas Toffoli, aplicadas a cualquier combinación de qubits de control y objetivo, su representación matricial tiene determinante .S41

Lo último a tener en cuenta es que el determinante conmuta con la multiplicación de matrices, es decir, , para cualesquiera dos matrices y compatibles con la multiplicación de matrices. Por lo tanto, ahora resulta evidente que la aplicación de múltiples compuertas Toffoli en secuencia nunca crea un circuito cuya representación matricial tenga un determinante diferente de , lo que en particular implica que la no se puede implementar utilizando solo compuertas Toffoli en qubits .det(AB)=det(A)det(B)AB1CCCNOT4

La pregunta obvia, ahora, es qué cambia cuando permitimos un qubit auxiliar. Encontramos la respuesta cuando escribimos la acción de la en un sistema de bits: Si calculamos este determinante, encontramos : Por lo tanto, el determinante del -gate que actúa en qubits es , en lugar de . Es por eso que el argumento anterior no es válido paraCCCNOT5

CCCNOTI2=[I1400X]I2=[I280000I20I20]
det(CCCNOTI2)=1
CCCNOT5115 qubits, como ya sabíamos debido al circuito construido explícitamente que solicitó el OP.

arriópolis
fuente
1
¡Una fuente, o método utilizado para derivar el circuito, sería útil!
glS
1
No conozco fuentes que expliquen cómo diseñar tales circuitos de manera integral. Las fuentes que utilicé cuando aprendí sobre computación cuántica fueron el libro de Nielsen y Chuang, y las notas de la conferencia que se pueden encontrar aquí: homepages.cwi.nl/~rdewolf/qcnotes.pdf , pero estas fuentes no se centran específicamente en el diseño de circuitos cuánticos.
arriópolis
2
Intenté explicar un poco más cómo funciona el circuito. ¡Espero que esto ayude a diseñar circuitos similares a este! :)
arriópolis
¿Es posible sin auxiliares?
user1271772
1
Pregunta interesante, pero no lo creo. Cada vez que se escribe la representación matricial de una puerta Toffoli que actúa en un sistema de cuatro qubits, el determinante de esta matriz es . Sin embargo, el determinante de la representación matricial de la puerta actúa sobre qubits es , por lo que no puede construirse mediante aplicaciones consecutivas de la puerta Toffoli. Con este qubit auxiliar, la diferencia es que la representación matricial de la puerta convierte en . +1CCCNOT41CCCNOT+1
arriópolis