En la lógica no cuántica, muestra que el conjunto en cuestión puede simular otro conjunto de operadores booleanos que se sabe que es universal. No sé si es lo mismo en el mundo cuántico, pero creo que sí.
Raphael
8
En lógica cuántica, la puerta de Toffoli no es universal, porque solo puedes hacer cálculos clásicos con ella. También necesita alguna puerta cuántica que, si la entrada está en un estado base, coloca la salida en una superposición de estados base.
Peter Shor
Me doy cuenta de que la pregunta puede ser confusa, tal vez debería editarse para preguntar la diferencia entre la universalidad en el mundo cuántico / clásico.
Ran G.
Edité mi respuesta para cubrir el caso cuántico. ¿Que piensas ahora?
Victor Stafusa
1
@Sonó. Se supone que debemos mostrar el camino para futuras preguntas, esta pregunta está etiquetada como tarea, pero parece que no explica por qué no pudo resolverla usted mismo (y dónde radica el problema). Creo que no es una buena pregunta para la versión beta privada (vea la meta discusión ). Voto para cerrar esta pregunta.
Gopi
Respuestas:
13
Toffoli es universal para la computación clásica (como lo muestra @Victor). Sin embargo, Toffoli NO es universal para el cálculo cuántico (a menos que tengamos algo loco como ).P=BQP
Para ser universal para el cálculo cuántico (según la definición habitual), el grupo generado por sus puertas debe ser denso en las unidades unitarias. En otras palabras, dado un arbitrario y una U unitaria objetivo, hay alguna forma de aplicar un número finito de puertas cuánticas para obtener un unitarioϵUtal que | El | U - U ′ | El | < ϵ .U′||U−U′||<ϵ
Toffoli en sí mismo claramente no es universal bajo esta definición, ya que siempre toma estados base a estados base, y por lo tanto no puede implementar algo que tome por ejemplo. En otras palabras, no puede crear superposición.|0⟩→12√(|0⟩+|1⟩)
La puerta de Toffoli es universal; Esto significa que para cualquier función booleana f (x1, x2, ..., xm), hay un circuito que consta de compuertas Toffoli que toma x1, x2, ..., xm y algunos bits adicionales establecidos en 0 o 1 y salidas x1, x2, ..., xm, f (x1, x2, ..., xm) y algunos bits adicionales (llamados basura). Esencialmente, esto significa que uno puede usar puertas Toffoli para construir sistemas que realizarán cualquier cálculo de la función booleana deseada de manera reversible.
Lo que significa en términos simples que cualquier función booleana puede construirse solo con puertas Toffoli.
Las funciones booleanas se construyen típicamente a partir de compuertas OR, AND y NOT, que se pueden combinar para formar cualquier función booleana. Es ampliamente conocido que lo mismo es posible solo con puertas NOR o solo con puertas NAND.
La puerta de Toffoli se puede resumir como:
T o fFo l i (a,b,c)= { ( a , b , ¬ c )( a , b , c )cuando a=b=1de otra manera.
Como la primera y la segunda salida son siempre iguales a la primera y segunda entrada, podemos desconsiderarlas. Entonces tenemos:
To ofFo l i′( a , b , c ) = { ¬ cCcuando a=b=1de otra manera.
Con eso, es posible definir la puerta NAND como:
NAND( a , b ) = T o fFo l i′( a , b , 1 )
Como la puerta NAND es universal y la puerta NAND puede definirse como una puerta Toffoli, entonces la puerta Toffoli es universal.
Hay otra forma de demostrar que Toffoli es universal, mediante la construcción directa de las puertas AND y NOT:
O( a , b ) = NO( Y( NO(a),NOT(b))=Toffoli′(1,1,Toffoli′(Toffoli′(1,1,a),Toffoli′( 1 ,1,b),0))
EDITAR, ya que la pregunta fue editada y su alcance cambió:
Primero, no entiendo la computación cuántica, así que si hay algo mal, agregue un comentario. Investigué un poco para tratar de completar esta respuesta y terminé con esto:
La puerta Toffoli es reversible (pero el Toffoli 'usado anteriormente no lo es). Esto significa que cualquier cálculo realizado con él se puede deshacer. Esto es:
( a , b , c ) = T ofFo l i ( T ofFo l i (a,b,c))
Lo que significa que para cualquier triple (a, b, c) si el Toffoli se aplica dos veces, la entrada original se obtiene como salida.
La reversibilidad es importante porque las puertas cuánticas deben ser reversibles, por lo que la puerta Toffoli (clásica) puede usarse como una puerta cuántica debido a esto.
Como se demostró aquí , la puerta Deutsch se define de manera similar a la puerta Toffoli, pero en lugar de una puerta clásica, es cuántica:
Alemán( a , b , c ) = | un , b , c ⟩ ↦ { i cos( θ ) | un , b , c ⟩ + pecado( θ ) | un , b , 1 - c ⟩El | un,b,c⟩para a=b=1de otra manera.
De esta manera, la puerta Toffoli es un caso particular de la puerta Deutsch donde:
T o fFo l i (a,b,c)=Deutsch( π2) ( a , b , c )
π2 ) cambios de fase (y combinando múltiples puertas, para obtener múltiplos de 90 grados). Pero esto también significa que no se puede usar para crear sobreposiciones de estado porque esto requeriría cambios de fase en ángulos que no son múltiples de 90 grados, por lo tanto, la puerta Toffoli no es una puerta cuántica universal.
Se puede obtener un conjunto de Tgate cuántico universal, si combinamos la puerta Toffoli con la puerta Hadamard. Esto es exactamente lo que hace la puerta de Deutsch.
Se pueden encontrar referencias interesantes aquí , aquí y aquí . Una posible referencia valiosa, que muestra los fundamentos de la transformación Deutsch debería estar aquí , sin embargo, el enlace está protegido con contraseña.
Toffolli no es universal para el cálculo cuántico, tampoco lo es CNOT por sí mismo. Esto es fácil de ver ya que no pueden crear superposición.
Artem Kaznatcheev
{}
Su referencia en EDIT 2 es incorrecta. Ese artículo establece claramente que Toffoli + Hadamard es universal, no Toffoli en sí mismo
Artem Kaznatcheev
@ArtemKaznatcheev: El artículo dice "Toffoli y Hadamard". Entonces pensé que esto significaba "Toffoli es un ejemplo y Hadamart es otro". De todos modos, está claro ahora.
Respuestas:
Toffoli es universal para la computación clásica (como lo muestra @Victor). Sin embargo, Toffoli NO es universal para el cálculo cuántico (a menos que tengamos algo loco como ).P=BQP
Para ser universal para el cálculo cuántico (según la definición habitual), el grupo generado por sus puertas debe ser denso en las unidades unitarias. En otras palabras, dado un arbitrario y una U unitaria objetivo, hay alguna forma de aplicar un número finito de puertas cuánticas para obtener un unitarioϵ U tal que | El | U - U ′ | El | < ϵ .U′ ||U−U′||<ϵ
Toffoli en sí mismo claramente no es universal bajo esta definición, ya que siempre toma estados base a estados base, y por lo tanto no puede implementar algo que tome por ejemplo. En otras palabras, no puede crear superposición.|0⟩→12√(|0⟩+|1⟩)
fuente
Del artículo de Wikipedia que citó :
Lo que significa en términos simples que cualquier función booleana puede construirse solo con puertas Toffoli.
Las funciones booleanas se construyen típicamente a partir de compuertas OR, AND y NOT, que se pueden combinar para formar cualquier función booleana. Es ampliamente conocido que lo mismo es posible solo con puertas NOR o solo con puertas NAND.
La puerta de Toffoli se puede resumir como:
Como la primera y la segunda salida son siempre iguales a la primera y segunda entrada, podemos desconsiderarlas. Entonces tenemos:
Con eso, es posible definir la puerta NAND como:
Como la puerta NAND es universal y la puerta NAND puede definirse como una puerta Toffoli, entonces la puerta Toffoli es universal.
Hay otra forma de demostrar que Toffoli es universal, mediante la construcción directa de las puertas AND y NOT:
Luego, podemos construir la puerta OR utilizando las leyes de De Morgan :
EDITAR, ya que la pregunta fue editada y su alcance cambió:
Primero, no entiendo la computación cuántica, así que si hay algo mal, agregue un comentario. Investigué un poco para tratar de completar esta respuesta y terminé con esto:
La puerta Toffoli es reversible (pero el Toffoli 'usado anteriormente no lo es). Esto significa que cualquier cálculo realizado con él se puede deshacer. Esto es:
Lo que significa que para cualquier triple (a, b, c) si el Toffoli se aplica dos veces, la entrada original se obtiene como salida.
La reversibilidad es importante porque las puertas cuánticas deben ser reversibles, por lo que la puerta Toffoli (clásica) puede usarse como una puerta cuántica debido a esto.
Como se demostró aquí , la puerta Deutsch se define de manera similar a la puerta Toffoli, pero en lugar de una puerta clásica, es cuántica:
De esta manera, la puerta Toffoli es un caso particular de la puerta Deutsch donde:
Se puede obtener un conjunto de Tgate cuántico universal, si combinamos la puerta Toffoli con la puerta Hadamard. Esto es exactamente lo que hace la puerta de Deutsch.
Se pueden encontrar referencias interesantes aquí , aquí y aquí . Una posible referencia valiosa, que muestra los fundamentos de la transformación Deutsch debería estar aquí , sin embargo, el enlace está protegido con contraseña.
fuente