El algoritmo de Shor
HTML-код
- Опубликовано: 15 сен 2024
- En este video entenderemos como funciona realmente el algoritmo de Shor, el algoritmo más famoso en el mundo de la computación cuántica capaz de dividir un número en factores primos.
Comunidad Computación Cuántica: join.slack.com...
Twitter: @KetPuntoG
Gmail: canalket.g@gmail.com 
Наука
![Eminem - Fuel (Shady Edition) feat. Westside Boogie & GRIP [Official Audio]](http://i.ytimg.com/vi/k1OquBida9s/mqdefault.jpg)
Llevo algún tiempo buceando en el libro de Nielsen y Chuang y me perdía en los detalles sin conseguir entender la globalidad de algunos conceptos, como las ideas detrás de la transformada cuántica de Fourier o del algoritmo de Shor. En una tarde visualizando algunos de tus vídeos he empezado a ver la luz. Te felicito por el excelente trabajo, seguro que no es fácil explicar conceptos de esta complejidad de una forma tan amena.
Muchas gracias Ramon! Te aseguro que no es sencillo pero disfruto con ello 😊
Muchas gracias!!! Un abrazo a la distancia desde México.
Nada! Me alegra que te sea útil 😉
Ahora mismo estoy acabando un trabajo de 2ndo de bachiller sobre la programacion en un ordenador cuantico y te contenido me ha ayudando muchisimo a entenderlo todo bien. Muchisimas gracias!
Me alegra oír eso! Empiezas pronto en este mundo, animo con ello 😉
Buen video pero un par de apuntes. Primero que la segunda parte del video donde empiezas a hacer cálculos mentales, si bien se nota que es porque es una chapa escribir todo eso, ayudaría bastante plasmarlo en la pantalla, a pesar de ello, se puede seguir bien. Por otro lado, creo que te has dejado la parte más importante del algoritmo de Shor y es la implementación del circuito cuántico con el QPE.
A parte de eso, buen video.🌸
Buenas Carlos! Dato curioso, QPE apareció después del algoritmo de Shor 😉 Existen dos implementaciones distintas. Si quieres trabajar con la otra implementación aquí escribí un módulo que te puede ser interesante codebook.xanadu.ai/S.1
De nuevo enhorabuena por el video.
Creo q hiciste muy accesible un tema bastante complicado, al menos para mi.
Siento no tener ninguna red social para difundir su contenido.
Saludos desde Gijon.
No te preocupes Jorge, con saber que te ha servido me vale! 💪
Muy bueno. Muy bien explicado, gracias.
Como siempre, un gusto poder echar una mano!
Lo pones muy claro, gracias por tu vídeo.
Muchas gracias Cesar! 😄
Enhorabuena por tus contenidos Guillermo. Tratando de entender el algoritmo de Shor y basándome en el resultado de mis simulaciones veo que la condición no es solo que el periodo de la funcion f(y)=a^y(N) sea par para un "a" dado, también se debe cumplir que (a^(T/2))^2=1(N) y que a^(T/2)(N) esté entre 2 y N-2, siendo T el periodo. Si no se cumplen estas condiciones no podremos usar a^(T/2) o a^(T/2)(N) para factorizar mediante m.c.d(a^(T/2)-1,N) y m.c.d(a^(T/2)+1,N) o m.c.d(a^(T/2)(N)-1,N) y m.c.d(a^(T/2)(N)+1,N). Por ejemplo, para a=5 y N=21 sale periodo T=6, pero 5^3 mod 21=20 que no está entre 2 y 19, con lo que 5^3=125 no nos valdría para usarlo en m.c.d(124,21) y m.c.d(126,21). Y un contraejemplo de la otra condición que indico sería si tomamos a=9 y N=15 el periodo sería T=2, pero NO se cumple que 9^2=1(15). A ver si me pudieras confirmar lo que comento... Gracias.
Hola buenas!! Muy bien visto Alberto, efectivamente ese caso no valdría y habría que coger otro número, pero eso no es un problema. Si miras aquí en “explicación de algoritmo” , teorema 2 (es.m.wikipedia.org/wiki/Algoritmo_de_Shor) , lo que comenta es que con más de 50% de probabilidad vas a encontrar la raíz cuadrada, es decir, que se cumple la condición de que sea par y la otra que comentabas. Espero haber aclarado la duda, un saludo!
@@KetPuntoG Perfect. Muchas Gracias!
Gracias por los videos
🚀🚀🚀
Muy buenos vídeos!, ¿no hay enlace a la explicación matemática como con otros algoritmos?
Escribí este capitulo donde puedes entrar en detalle codebook.xanadu.ai/S.1
(Esta en inglés)
Videazo
🚀 Tema avanzado ya
yo e investigado acerca de la clase de complejidad postbqp(que es la clase de complejidad bqp pero añadiendole postseleccion)
de scott aaronson en donde el demuestra que esta clase de complejidad es igual a pp(probabibilistica polinomial) que se dice que esta clase contiene a np,
y segun por lo que e escuchado la postseleccion es capaz de resolver problemas np completos tambien investigue sobre las
cuvas cerradas de tiempo (ctc) que se dicen que tambien tienen el poder computacional suficiente para resolver problemas np-completos,
en el año 2010 seth lloyd simulando viajes en el tiempo demostro que añadiendo la postseleccion se podria hacer una
viajes en el tiempo libre de paradojas y en este mismo articulo el tambien confirma que la postseleccion le da el poder
computacional suficiente para resolver los problemas np, mi pregunta es si esto es cierto como podria aplicarlo para resolver
un problema np completo como por ejemplo el problema 3-sat o el problema de las n reinas? y si estos estudios son apartir de
modelos hipoteticos de computacion como es posible que confirmen algo tan dificil como que la postseleccion y las ctc son
capaces de resolver np completo? eso es lo que no acabo de entender
En este canal llegamos apropgramar el problema de las N reinas que conseguíamos que el algoritmo tardase la raíz cuadrada de lo que tardaría uno clásico. Para resolverlo utilizábamos Grover, en el que inicialmente marcábamos las soluciones con un uno y luego, aplicación cierto número de iteraciones a cierta puerta conseguíamos obtener los valores con ese uno. Pues si existiera la post selección nos ahorraríamos ese paso, ya que podríamos forzar que ese qubit sea un uno y por tanto el resto de estados se quedarían únicamente en los que son solución. No es fácil de explicar pero la idea es más o menos está. Espero haberte ayudado 😃
@@KetPuntoG muchas gracias, si la verdad es algo difícil de entender y estaba confundido con esto de la postseleccion, también e investigado que la simulación de sistemas cuánticos puede ser muy difícil tanto que según un articulo que leí (la verdad no me acuerdo bien de quien era pero por hay lo tengo descargado), dice que la simulación eficiente del modelo de Hubbard para los electrones en un sólido implicará la igualdad de las clases de complejidad P=NP=QMA, y al parecer este año Google pudo simular eficientemente una reacción química en un ordenador cuántico quien sabe ojala en un futuro quizás se pueda simular eficientemente la fisica cuantica en estos ordenadores
@@andresfelipemirandasilva6887 no estoy muy puesto en ese tema pero cuidado con una cosa, que un ordenador cuántico pueda resolver un problema NP no implica que P = NP. Ya vi que te metiste a la comunidad, puedes presentarte y comentar todo lo que se te pase por la cabeza :)
Lo puedes explicar todos los videos de la serie en un solo video?
Me gustaría ver el resultado.
Mi felicitación por el vídeo. La verdad es que intentas hacer fácil lo que desde mi punto de vista es difícil y lo consigues en un grado alto. Respecto a este vídeo de descomposición en números primos me surgen dos dudas:
1.- En el vídeo haces la demostración para el caso de que un número de descompone en dos números p y q, pero ¿cómo se hace cuando hay más de dos números primos?, o incluso cuando algún número primo hay que elevarlo a alguna potencia.
2. He intentado calcular M para el número N=21=7*3 pero no lo veo. He cogido algún número entre 2 y 19=21-2 pero no llego a localizar ese M. ¿Te importa darme alguna pista para este caso?.
Gracias por tu esfuerzo para difundir todo este conocimiento
Me alegra mucho que me hagas esa pregunta! 😊 Es algo que muy poquita gente se da cuenta pero el algoritmo de Shor solo factoriza producto de dos primos, no cualquier número! Sin embargo, esto no es un problema, ya que en criptografía, los únicos números que nos interesan factorizar para el sistema RSA cumplen esa propiedad
Respecto a la segunda pregunta no estoy seguro si estamos pensando en la misma M, te refieres a la raíz cuadrada?
@@KetPuntoG Ok. perfecto y aclarado, gracias.
Respecto de la segunda pregunta me puedes dar algún valor de esa M, si puedes claro porque supongo andas bastante liado. En todo caso gracias por tus aportaciones
@@franciscoredondo2781 aquí te dejo un pequeño script que acabo de hacer para sacar a fuerza bruta raices cuadradas modulo algo :)
def square_root_manual(mod):
for i in range(2, mod-2):
if i ** 2 % mod == 1:
return i
square_root_manual(21)
En este caso, 8 es el número que estás buscando
@@KetPuntoG Gracias de nuevo por tu amabilidad, pero en tu contestación no veo el enlace para ver ese script.
@@franciscoredondo2781
def square_root_manual(mod):
for i in range(2, mod-2):
if i ** 2 % mod == 1:
return i
square_root_manual(21)
Al parecer la matemática que se utiliza para cálculos en cca parece mucho más simple pero más lógica a la vez
El video muy interesante, pero no veo donde se aplica la cuántica.
Un saludo
El algoritmo de cálculo de periodo solo es eficiente en un computador cuántico 😊
@@KetPuntoG sí, sí eso me queda claro pero lo que veo es que el procedimiento se podría implementar en uno clásico, al fin y al cabo los qbits tienes que colapsarlos antes o si los pone en superposición debes tener fé en que caerán al ser colapsados en la combinación deseada, es decir, la que nos dé la solución. Por ejemplo, la puerta H nos pone el qbits en superposición de los estados 0 y 1, si entendí bien , con probabilidad al 50% cada uno de estos dos estados, al ser medido o colapsado dicho qbits, es decir , si este qbits se midiera 1000 veces , en 500 veces saldría 1 y las otras 500 saldría 0, ( o muy aproximada a eso, por los errores ) entonces tengo 3 preguntas
1. Si al inicio tengo qbits y los pasos a través de puertas H daría igual cual fuese el estado inicial de estos estados, pues la puerta H los coloca en estado de superposición del estado 0 y el estado 1 con igual probabilidad al ser medidos o colapsados, entonces ¿ por qué ciertos qbits iniciales en algunos circuitos deben comenzar en estado 1 y otros en estado 0 si luego se pasan por estás puertas? Tiene poca lógica ¿ no?
2. Si aún qbits se le ha hecho una serie de transformaciones y después se le aplica esta puerta H ¿ de que sirvieron estás transformaciones, si al final lo vas a colocar en un estado que tiene 50% de colapsar en 1 y el otro 50% de colapsar en 0? No sé si me explico.
3. En algunos casos se usa puertas H para varios qbits en alguna de sus partes y luego una medición y se dice ocurre tal o cual cosa si todas más mediciones dan 0 ó 1 o etc, ¿ no es confiar eso en el azar? Es decir, ¿ no es tener fe en que el azar nos hará descubrir la solución?
Gracias por el video y por contestar.
@@davidnunez1172 Efectivamente si solo aplicas Hadamard es jugar con el azar pero hay ciertos algoritmos que pueden ser deterministas. Esa es la gracia de la propiedad de interferencia :) Imaginate que creas una superposición de todas las posibles combinaciones pero consigues que de alguna manera, las soluciones malas interfieran, es decir, "se destruyan entre ellas". De esta forma puedes conseguir que siempre se te queden las buenas. Es un poco abstracto pero cuando profundizas en los algoritmos todo tiene sentido 😄 Probablemente el algoritmo de Deustch-Jozsa sea el más claro para ver que no es simplemente azar.
@@KetPuntoG pero entonces sigo sin entender , en el algoritmo que has mencionado si no recuerdo mal introduces todos los qbits en el estado 0 excepto el último en el estado 1, ¿ para luego pasarlos inmediatamente por una puerta H? No le veo sentido ninguno , es más no sé cómo eso no es acudir al azar. Para mí cuando se tiene algo determinado, sin azar, ya deja de ser cuántica porque entonces se deja de tener un qbit para tener un bit normal, y si se va operando sobre bits , quiero decir, sobre qbits ya definidos en su estado 0 o 1, eso ya es usar computación clásica y no cuántica.
A ver explicame si puedes y quieres como en el algoritmo de Dozja en el que al final los qbits son pasados por la puerta H ¿ qué sentido tiene la manipulación que le hayas hecho anteriormente a esos qbits si al final la probabilidad de medirlos , que es lo que nos da la solución al problema, tiene un 50% de dar 0 y otro de dar 1?
O al principio de ciertos algoritmo se dice , hay que meter todos en estado 0 menos uno en estado 1 y luego se pasan por La puerta H, de verdad que no le veo sentido ninguno por lo ya expuesto o quizás me estoy perdiendo algo de la puerta H, no sé.
A ver si me ayudas a comprender ese aspecto. Gracias
PD: excelentes videos
De que otra forma se encuentra el concepto de la raiz cuadrada no trivial modulo N? Busco en google y no aparece el concepto
En inglés es “modular square root” , lo de no trivial es para excluir el +1 y el -1
Hola, no sé si te equivocaste, pero 1/3 no tiene resto 1. Pero 10/3 sí.
1/3 es cociente 0 y resto 1, no?
no entendi NADA
Escribí aquí el módulo de Shor, tal ve te ayude más :)
codebook.xanadu.ai