¿Por qué se requiere la transformación cuántica de Fourier en el algoritmo de Shor?

8

Actualmente estoy estudiando el algoritmo de Shor y estoy confundido sobre el tema de la complejidad. Por lo que he leído, el algoritmo de Shor reduce el problema de factorización al problema de búsqueda de orden o período de secuencia de exponenciación modular de alguna $x$ aleatoria tal que $1 < x < N$ .

No tengo ningún problema con respecto a la idea del algoritmo. Pero me pregunto si el algoritmo de Shor crea una secuencia de este tipo mediante la cuadratura repetida (que es una forma eficiente clásicamente). Según tengo entendido, el término "eficiente" significa que la complejidad del algoritmo es polinómica en el tiempo.

Dado que existe una manera eficiente de crear la secuencia de manera clásica, ¿no podemos simplemente agregar una pequeña verificación para ver si hemos encontrado $x^{r} = 1 \ \text{mod} N$ ? Durante el proceso de creación, no debería aumentar la complejidad al tiempo exponencial, ¿verdad?

¿Por qué molestarse con la transformación cuántica de Fourier? ¿Lo entendí mal de alguna manera?

algorithm complexity-theory shors-algorithm quantum-fourier-transform Poramet Pathumsoot
fuente

1

Hola poramet ¡Bienvenido a Quantum Computing SE! Por favor, solo haga una pregunta por publicación; solo pregunte a varias si están tan estrechamente relacionadas que no tendría sentido dividirlas, ya que no se pueden responder razonablemente por separado. De esa manera, los que responden que podrían responder una pregunta pero no las demás, pueden proporcionar respuestas completas y útiles a una pregunta. Repaso ¿Cómo escribir una buena pregunta? .

Sanchayan Dutta

1

He edición ed su puesto para eliminar la segunda pregunta (v5 es aún visible aquí ). Por favor pregunte eso como una pregunta separada si es necesario.

Sanchayan Dutta

7

La característica esencial de este problema es que, si bien los algoritmos cuántico y clásico pueden hacer uso de la función clásica eficiente de calcular $a^k\text{ mod }N$ , el problema es cuántas veces cada uno tiene que evaluar la función.

Para el algoritmo clásico que está sugiriendo, calcularía $a\text{ mod }N$ , $a^2\text{ mod }N$ y $a^3\text{ mod }N$ , y así sucesivamente, hasta que alcance un valor repetido. Tienes que realizar $r$ evaluaciones, y $r$ podría ser bastante grande. De hecho, podría ser $O(N)$ . Es esta gran cantidad de repeticiones lo que mata esta idea para el algoritmo clásico.

En comparación, el algoritmo cuántico solo evalúa el orden una vez . Luego necesita la Transformación Cuántica de Fourier para poder comparar todos los valores calculados simultáneamente porque no puede acceder a todos estos valores a la vez. El QFT es lo que hace toda la magia.

DaftWullie
fuente

O (N)

$O(N)$

N

$N$

x^{a} mod N

$x^{a} \text{mod} N$

a

$a$

O (N)

$O(N)$

1

n = \log_{2} (N)

$n=\log_2(N)$

N

$N$

n

$n$

3

$x^{r} = 1 \ \text{mod} N$

¿Por qué molestarse con la transformación cuántica de Fourier? ¿Lo entendí mal de alguna manera?

$x = 2^r_{1} \ \text{mod} N$ . Eso no quiere decir que tal algoritmo clásico no exista, solo que nadie conoce un algoritmo tan clásico.

La transformada de Fourier discreta clásica tiene una complejidad exponencial; sin embargo, la versión cuántica de esa transformada de Fourier tiene una complejidad polinómica. Por lo tanto, debemos molestarnos con la transformación cuántica de Fourier.

Aprendiz
fuente

x^{r} = 1 m o d N

$x^r = 1 mod N$

Hola aprendiz. ¡Bienvenido a Quantum Computing ! He edición ed su respuesta un poco para que coincida con la versión actual (v8) de la pregunta.

Sanchayan Dutta

¿Por qué se requiere la transformación cuántica de Fourier en el algoritmo de Shor?

Respuestas: