¿Cómo funciona realmente el muestreo de Fourier (y resuelve el problema de paridad)?

Escribo con respecto a la parte I y la parte II de las conferencias de video de muestreo de Fourier del profesor Umesh Vazirani.

En parte, comienzan con:

En la transformación de Hadamard:

$$|0...0\rangle \to \sum_{\{0,1\}^n}\frac{1}{2^{n/2}}|x\rangle$$ $$|u\rangle =|u_1...u_n\rangle \to \sum_{\{0,1\}^n}\frac{(-1)^{u.x}}{2^{n/2}}|x\rangle \quad \text{(where $u.x=u_1x_1+u_2x_2+...+u_nx_n$)}$$

En muestreo de Fourier:

$$|\psi\rangle=\sum_{\{0,1\}}^{n}\alpha_x|x\rangle \to \sum_{x}\hat{\alpha_x}|x\rangle=|\hat{\psi}\rangle$$

Cuando se mide , vemos con probabilidad .$|\hat{\psi}\rangle$$x$$|\hat{\alpha_x}|^2$

En la parte II:

El problema de la paridad:

Se nos da una función como un cuadro negro. Sabemos que (es decir, ) para algunos ocultos . ¿Cómo podemos averiguar con el menor número de consultas a como sea posible?$f:\{0,1\}^n\to\{0,1\}$$f(x)=u.x$$u_1x_1+u_2x_2+...+u_nx_n (\text{mod 2})$$u\in\{0,1\}^{n}$$u$$f$

Dicen que hay que seguir un procedimiento en dos etapas para averiguar en el menor número posible de pasos.$u$

• Configure una superposición$\frac{1}{2^{n/2}}\sum_{x}(-1)^{f(x)}|x\rangle$

• Muestra de Fourier para obtener .$u$

Aquí es donde me perdí. No entiendo qué quieren decir exactamente con "establecer una superposición ...". ¿Por qué deberíamos hacerlo? Y cómo Fourier de muestreo (como se describe) ayuda a determinar ?$u$

Además construyen una puerta cuántica como esta:

Incluso esto no tiene sentido para mí. Están realizando transformaciones de Hadamard en un conjunto de n-qubits que tienen estado y luego bit flip y nuevamente Hadamard transform. Entonces volvemos a donde estábamos inicialmente. ¿Cómo ayuda una entrada de estado extra al generar ? Ni siquiera estoy seguro de qué operación representan, aquí.$|0\rangle$$|-\rangle$$- \oplus f(0...0)$$\oplus$

Comenzando desde el principio (un muy buen lugar para comenzar, después de todo), el estado se ingresa en (aquí, llamado 'muestra de Fourier'). Esto genera el estadoAhora, aplicamos la operación (en este caso, el oráculo de bits ) para dar$\left| 0\right\rangle^{\otimes n}\left| -\right\rangle$$H^{\otimes n}\otimes I$

$$\left(\sum_{x=\{0,1\}^n}\frac{1}{2^{n/2}}|x\rangle\right)\left|-\right\rangle = \frac{1}{2^{n/2}}\left(\left|0\right\rangle + \left|1\right\rangle\right)^{\otimes n}\left|-\right\rangle.$$ $U_f$ $$U_f\left(\sum_{x=\{0,1\}^n}\frac{1}{2^{n/2}}|x\rangle\right)\left|-\right\rangle = \sum_{x=\{0,1\}^n}\frac{1}{2^{n/2}}|x\rangle\left|-\oplus f\left(x\right)\right\rangle.$$

El primer punto a tener en cuenta es que es la operación clásica de XOR . Lo que esto proporciona es en realidad el oráculo de fase , de modo que obtenemosEsto se debe a que . Este es el punto de "configurar una superposición ...": todo lo que esto significa es$\oplus$

$$\left(\sum_{x=\{0,1\}^n}\frac{1}{2^{n/2}}\left(-1\right)^{f\left(x\right)}\left|x\right\rangle\right)\left|-\right\rangle.$$ $U_f\left|x\right\rangle\left(\left|0\right\rangle - \left|1\right\rangle\right) = \left|x\right\rangle\left|f\left(x\right)\right\rangle - \left|1\oplus f\left(x\right)\right\rangle = \left(-1\right)^{f\left(x\right)}\left|x\right\rangle\left(\left|0\right\rangle - \left|1\right\rangle\right)$realice las operaciones necesarias para establecer los qubits en el estado anterior, que es una superposición de todos los estados posibles (con factores de fase, en este caso) . En este caso, esto es solo Hadamard, seguido de un oráculo de fase.

Ahora, es solo una cadena de bits clásica: , entonces$x$$x = \prod_ix_i$

$$H\left|x_i\right\rangle = \frac{1}{\sqrt{2}}\left(\left|0\right\rangle + \left(-1\right)^{x_i}\left|1\right\rangle\right) = \frac{1}{\sqrt{2}}\sum_{y=\left\lbrace0, 1\right\rbrace}\left(-1\right)^{x_i.y}\left|y\right\rangle.$$

Esto le da a la propiedad

$$H^{\otimes n}\left| x\right\rangle = \frac{1}{2^{n/2}}\sum_{y\in\left\lbrace0, 1\right\rbrace^n}\left(-1\right)^{x.y}\left|y\right\rangle.$$

Esto proporciona el estado final como

$$\frac{1}{2^n}\left(\sum_{x, y=\{0,1\}^n}\left(-1\right)^{f\left(x\right) \oplus x.y}\left|y\right\rangle\right)\left|-\right\rangle.$$

Sabemos que , dando . Sumar los términos da que . Esto significa que nos queda el término para , lo que significa que , dando la salida como , que se mide como obtener .$f\left(x\right) = u.x = x.u$$\left(-1\right)^{f\left(x\right) \oplus x.y} = \left(-1\right)^{x.\left(u\oplus y\right)}$$x$$\sum_x\left(-1\right)^{x.\left(u\oplus y\right)} = 0,\, \forall\, u\oplus y \neq 0$$u\oplus y = 0$$u=y$$\left|u\right\rangle\left|-\right\rangle$$u$

En cuanto a por qué queremos establecer una superposición : aquí es donde entra en juego el poder de la computación cuántica: en términos menos matemáticos, aplicar la transformación de Hadamard es realizar una rotación en los estados qubit para ingresar al estado . Luego, gira cada qubit en este estado de superposición utilizando una operación equivalente a XOR (en esta nueva base), de modo que al realizar la transformación de Hadamard nuevamente, ahora está girando nuevamente sobre el estado . Otra forma de ver esto es considerarlo como un reflejo o inversión que logra el mismo resultado.$\left|+\right\rangle^{\otimes n}$$\left|u\right\rangle$

El punto es que, usando la superposición, podemos hacer esto a todos los qubits al mismo tiempo, en lugar de tener que verificar individualmente cada qubit como en el caso clásico.