Encontrar el llamado orden es uno de los pasos esenciales en diversos algoritmos cuánticos.
Aquí, por analogía con los demás casos, se tratará el problema de la búsqueda del orden enfocado al algoritmo de Shor, lo cual proporciona un marco claro donde puede verse una motivación para este parámetro.
Por ello, se citarán algunos razonamientos o conclusiones extraídos de dicho algoritmo o alguna de sus subrutinas.
enteros positivos sin divisores comunes, se define el orden
como el menor número entero tal que
No existe un algoritmo clásico que resuelva el problema de encontrar el orden fijados
Por este motivo se hace necesaria la implementación de un algoritmo cuántico eficiente tal como el que va a explicarse haciendo uso de lo que se conoce como estimación de fase.
x y ( m o d
Fácilmente se comprueba que efectivamente al actuar el operador
Para recuperar el autoestado hemos necesitado que el sumando correspondiente a
sea igual al correspondiente a
, lo cual se cumple por la definición de orden que hemos dado.
La estimación de fase proporcionará estos autovalores del cual obtendremos el orden.
Para llevar a cabo este procedimiento, hay dos requerimientos:
qubits del primer registro e
corresponde al segundo registro, tal y como se explica en el algoritmo cuántico de estimación de fase.
Por lo visto anteriormente, es conocido que dicha transformación puede darse por medio de la aplicación del operador
(el contenido del primer registro) en notación binaria.
Así, el circuito cuántico del algoritmo para encontrar el orden se resume en lo anterior donde los
y el estado del segundo registro es precisamente el autovector definido como
Por tanto, ya solo queda ser capaces de hallar el valor de r, para lo cual se va a explicar a continuación la subrutina que habría que implementar:[2] La fracción continua constituye una transformación sencilla y original de una fracción que tiene gran utilidad a la hora de estudiar números irracionales, y que en el contexto dentro del algoritmo de Shor no será más que una subrutina puramente clásica que no introducirá una mayor dificultad teórica.
Esta idea se entiende muy bien explicándolo con un ejemplo sencillo:
con el previo conocimiento del correspondiente conjunto de enteros.
Puesto que no es conocido dicho conjunto de enteros, básicamente se tiene que ir probando aleatoriamente combinaciones de enteros hasta que se obtiene el valor del cociente.
Cuando se llega a esta situación basta con realizar marcha atrás el desarrollo y obtendremos unos
Como se puede entender, este algoritmo conlleva un tiempo de cómputo increíblemente alto en general, por lo que no constituye un método muy eficiente para obtener el orden.
que no coincida con el orden por dos motivos: Para estar seguros de que no se da este segundo motivo de error, se puede repetir el proceso un número alto de veces concreto que ahora razonaremos.
Para ello, vamos a dar dos resultados útiles: Por lo contado hasta ahora, también se conoce que
es un número primo (y por tanto coprimo con
), pudiendo afirmar definitivamente que este es el orden.