¿Por qué consideramos vectores de longitud N=2nN=2nN = 2^n para la Transformada Cuántica de Fourier?

Question

¿Por qué consideramos vectores de longitud N=2nN=2nN = 2^n para la Transformada Cuántica de Fourier?

brzepkowski

Transformada de Fourier discreta

La transformada de Fourier discreta clásica actúa sobre un vector $(x_0, x_1, ..., x_{N-1}) \in C^N$ y lo asigna a vector $(y_0, y_1, ..., y_{N-1}) \in C^N$ según la fórmula

y_{k} = \frac{1}{\sqrt{norte}} \sum_{j = 0}^{norte - 1} {mi}^{\frac{2 π i j k}{norte}} X_{j},

$y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} e^{\frac{2\pi ijk}{N}} x_j,$ dónde

k = 0, 1, 2, . . ., N - 1

$k = 0, 1, 2, ..., N-1$ .

Mi entendimiento de esto es que estamos expresando el mismo vector en una nueva base (que tiene la misma cantidad de dimensiones que el original). Además, cada coeficiente que se encuentra junto al vector de la nueva base depende de cada coeficiente de la base original.

Transformada cuántica de Fourier

En Quantum Fourier Transform consideramos vectores de longitud $N = 2^n$ . Entonces cada coeficiente se calcula de la siguiente manera

y_{k} = \frac{1}{2^{norte / 2}} \sum_{j = 0}^{2^{norte} - 1} {mi}^{\frac{2 π i j k}{2^{norte}}} X_{j}

$y_k = \frac{1}{2^{n/2}} \sum_{j=0}^{2^n - 1} e^{\frac{2 \pi ijk}{2^n}} x_j$

La página Wiki ( https://en.wikipedia.org/wiki/Quantum_Fourier_transform ) da el siguiente ejemplo:

Considere la transformada cuántica de Fourier en 3 qubits. Es la siguiente transformación:

$q F T : | X ⟩ \to \frac{1}{\sqrt{2^{3}}} \sum_{j = 0}^{2^{3} - 1} {mi}^{\frac{2 π i X k}{2^{3}}} | k ⟩$ $QFT:|x\rangle \ \rightarrow \frac{1}{\sqrt{2^3}} \sum_{j=0}^{2^3 - 1} e^{\frac{2 \pi ixk}{2^3}} |k\rangle$

No puedo entender la correspondencia entre el número de qubits $n$ necesario para expresar el estado cuántico y esto $N = 2^n$ . Nielsen y Chuang en su libro "Quantum Computation and Quantum Information" también escriben que "debido a que tomamos $N = 2^n$ tenemos la base $|0\rangle, |1\rangle, ..., |2^n-1\rangle$ que es la base de cálculo para $n$ computadora cuántica qubit".

¿Puedes explicarme por qué cambiamos la base de $|0\rangle, |1\rangle, ..., |N-1\rangle$ a $|0\rangle, |1\rangle, ..., |2^n - 1\rangle$ ? Mi intuición me dice que ahora operamos en tales vectores $(x_0, x_1, ..., x_{2^n - 1}) \in C^{2^n - 1}$ , pero sé que esto está mal.

Emilio Pisanty

Esto no es particularmente exclusivo de la versión cuántica: la transformada rápida de Fourier (clásica) también tiene esta restricción y, con frecuencia, es mucho más rápida que la DFT estándar, por lo que es más económico rellenar su vector con ceros y usar la FFT en un entrada más larga que ejecutar la DFT directamente. También hay variaciones de la FFT que pueden reducir eso y mantener el

O (n \log (n))

$O(n\log(n))$ tiempo de ejecución, que potencialmente podría replicarse en el lado cuántico si ejecuta cosas en qudits (aunque no es que tenga mucho sentido explorarlos).

Norberto Schuch

@EmilioPisanty Padding no da como resultado un FT sobre Z_N.

glS

@EmilioPisanty no es que tenga mucho sentido explorarlos, aunque tal vez no en el contexto de la computación cuántica con qubits, pero hay aplicaciones interesantes de QFT (rápido) sobre qudits, consulte, por ejemplo, arxiv.org/abs/1508.00782

Emilio Pisanty

@Norbert de hecho no lo hace; en algunas aplicaciones la diferencia importa y en otras no. Si te importa la diferencia y realmente quieres una DFT sobre

Z_{p}

$\mathbb Z_p$ para

p

$p$ un primo grande, entonces estás atascado con un algoritmo lento que ya está en el lado clásico.

Respuestas (1)

¿Por qué consideramos vectores de longitud N=2nN=2nN = 2^n para la Transformada Cuántica de Fourier?

Esto no es particularmente exclusivo de la versión cuántica: la transformada rápida de Fourier (clásica) también tiene esta restricción y, con frecuencia, es mucho más rápida que la DFT estándar, por lo que es más económico rellenar su vector con ceros y usar la FFT en un entrada más larga que ejecutar la DFT directamente. También hay variaciones de la FFT que pueden reducir eso y mantener el $O(n\log(n))$ tiempo de ejecución, que potencialmente podría replicarse en el lado cuántico si ejecuta cosas en qudits (aunque no es que tenga mucho sentido explorarlos).
@EmilioPisanty Padding no da como resultado un FT sobre Z_N.
@EmilioPisanty no es que tenga mucho sentido explorarlos, aunque tal vez no en el contexto de la computación cuántica con qubits, pero hay aplicaciones interesantes de QFT (rápido) sobre qudits, consulte, por ejemplo, arxiv.org/abs/1508.00782
@Norbert de hecho no lo hace; en algunas aplicaciones la diferencia importa y en otras no. Si te importa la diferencia y realmente quieres una DFT sobre $\mathbb Z_p$ para $p$ un primo grande, entonces estás atascado con un algoritmo lento que ya está en el lado clásico.

punk_físico · Answer 1

Esta es simplemente la diferencia entre preguntar cuál es la dimensionalidad de tu espacio $N$ (o equivalentemente el número de estados base), y cuántos bits (o qubits) $n$ tienes. Para cada (qu) bit, duplica el número de estados básicos distintos, por lo que la relación entre $N$ y $n$ es

norte = 2^{norte} .

$N = 2^n.$ contando desde

0

$0$ esto es

j \in [0, N - 1] = [0, 2^{n} - 1]

$j\in[0,N-1]=[0,2^n-1]$ .

Como ejemplo, 3 qubits abarcan un espacio de dimensión $2^3 = 8$ porque cada qubit en el estado base se puede representar mediante un binario $0$ o $1$ . Entonces los estados base son

| b_{1} ⟩ \otimes | b_{2} ⟩ \otimes | b_{3} ⟩,

$|b_1\rangle\otimes|b_2\rangle\otimes|b_3\rangle,$ dónde

b_{m}

$b_m$ es el

m^{th}

$m^\text{th}$ qubit, y se puede etiquetar como

0

$0$ o

1

$1$ en una base dada. En forma condensada podría escribir

| 0 ⟩ \otimes | 1 ⟩ \otimes | 0 ⟩

$|0\rangle\otimes|1\rangle\otimes|0\rangle$ como

| 010 ⟩

$|010\rangle$ , o podría numerar los estados para que este estado pueda escribirse como

| 2 ⟩

$|2\rangle$ .

Todavía no lo entiendo bien. Pienso en los qubits de manera similar a los bits. por ej. podemos tener el número decimal j = 10 = (1010)_bin = 1*2^3 + 0*2^2 + 1*2^1 + 0*2^0 (donde está la notación binaria) _bin. Entonces, por analogía, ¿no sería la base para una computadora cuántica con n quibts como |2^0>, |2^1>, |2^2>, |2^3>?
Creo que lo estás consiguiendo. $N$ contra $n$ es solo el número de estados totales en una base frente al número de qubits. Esto es lo mismo clásicamente cuando se habla de la cantidad de bits frente a la cantidad de opciones posibles. He ampliado mi respuesta con un ejemplo para (con suerte) aclarar esto. Avíseme si todavía está confundido y ampliaré esto más.
Entonces, cuando decimos que tenemos una base en la forma |0>, |1>, ..., |2^n - 1> es como una lista de todos los estados cuánticos posibles, que se pueden representar en $n$ qubits? Entonces no es como la base ortonormal (que en nuestro caso está hecha de qubits), donde expresamos un vector en forma $\alpha |j_1> + \beta |j_2> + ... + \omega |j_n>$ ? ¿Quizás mi problema es sobre el mal uso de la palabra "base" en estos dos contextos?
Sin embargo, es una pregunta interesante si se puede hacer una QFT sobre Z_N para cualquier N.
@Ozaru Hay una cantidad infinita de estados posibles, pero una base (completa) se establece en estados linealmente independientes que se pueden usar para representar cualquier estado. Entonces, para un solo qubit, necesita dos estados para ser la base, por ejemplo $|0\rangle$ y $|1\rangle$ son una base que puede representar cualquier estado (puro) $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$ . Para $n$ qubits que necesitas $2^n$ estados independientes para formar una base.
@NorbertSchuch Si tiene el control total de un sistema cuántico con $N$ o más grados de libertad, entonces puede hacer la QFT para cualquier $N$ . Si su dispositivo es una computadora cuántica universal que utiliza $n$ qubits tales que $2^n > N$ , simplemente no usa todos los estados. Esto no es diferente a las computadoras clásicas. El hecho de que tenga 4 Gb de RAM no significa que no pueda hacer cálculos con números mucho más pequeños. No tengo que usar todos mis recursos disponibles en todo momento.
@Punk_Physicist Así que comenzamos eligiendo $n$ qubits, en los que queremos trabajar, y para representarlos necesitamos $2^n$ estados base? Como |0>, |1> para $1st$ qubit, |2>, |3> para $2nd$ qubit y así sucesivamente?
Si agrega un tercer qubit, necesita agregar 4 estados más, pero los estados $|4\rangle$ , $|5\rangle$ , $|6\rangle$ , y $|7\rangle$ no están asociados solo con qubit 3, por lo que tiene más sentido hablar sobre la cantidad de qubits (y la cantidad de estados es $2^n$ ), en lugar de hablar de un número exponencial de estados posibles.
Creo que por fin lo entiendo, muchas gracias por todas las explicaciones :)
@Punk_Physicist Obviamente, la pregunta es si puedes hacer el QFT sobre $\mathbb Z_N$ para cualquier $N$ eficientemente _ ¿Es obvio? ¿Cuál sería el circuito?
@Punk_Physicist Capítulo 3 de arxiv.org/abs/quant-ph/0212002 analiza preguntas de este tipo. La respuesta general parece que esto no se puede hacer de manera eficiente en general (o, al menos, no está claro). Parece que hay versiones aproximadas, consulte el Capítulo 5.
@NorbertSchuch estuvo de acuerdo en que preguntar si esto es computable de manera eficiente es sin duda la pregunta más interesante/sutil. Como señalan la referencia que proporciona (y el comentario anterior de Emilio Pisanty), esto también es un poco complicado en los algoritmos FT clásicos. Sin embargo, en la práctica, esto generalmente no es demasiado molesto (por ejemplo, uno puede rellenar el vector con ceros para hacer que el tamaño $N=2^n$ )
@punk_physicist Padding no da como resultado un FT sobre Z_N.

¿Por qué consideramos vectores de longitud N=2nN=2nN = 2^n para la Transformada Cuántica de Fourier?

brzepkowski

Transformada de Fourier discreta

Transformada cuántica de Fourier

Emilio Pisanty

Norberto Schuch

glS

Emilio Pisanty

Respuestas (1)

punk_físico

brzepkowski

punk_físico

brzepkowski

Norberto Schuch

punk_físico

punk_físico

brzepkowski

punk_físico

brzepkowski

Norberto Schuch

Norberto Schuch

punk_físico

Norberto Schuch

Mecánica cuántica: ¿cómo funciona exactamente la "normalización de la función delta" para funciones propias en el caso de espacio libre 1-d?

Normalización de la función propia a la función Dirac-delta

Tratando de entender primero las bases de posición y momento en Mecánica Cuántica

¿Qué significa la notación Ψk/(Ψk,Ψk)1/2Ψk/(Ψk,Ψk)1/2\Psi_k/(\Psi_k,\Psi_k)^{1/2}?

Equivalencia de un ket a un vector y equivalencia de estados hasta una fase global, duda sobre notación

¿Cómo es posible tomar el producto interno de estados que pertenecen a dos espacios de Hilbert diferentes?

¿Se puede derivar la ecuación de Schrödinger a partir de la teoría de la información cuántica?

Unidades de una función delta de dirac en mecánica cuántica

Enredo cuántico para partículas indistinguibles

Norma de estado cuántico en tres dimensiones