Jak faktycznie działa próbkowanie Fouriera (i rozwiązuje problem parzystości)?

Piszę w odniesieniu do części I i części II wykładów wideo na temat próbkowania Fouriera prowadzonych przez profesora Umesh Vazirani.

W części I zaczynają się od:

W transformacji Hadamarda:

| U⟩=| U1. . . Un⟩→Ď{0,1}n(-1),u.

$$|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$)}$$

W próbkowaniu Fouriera:

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

Kiedy mierzy widzimy X z prawdopodobieństwem | ^ α x | 2 .$|\hat{\psi}\rangle$$x$$|\hat{\alpha_x}|^2$

W części II:

Problem parzystości:

Otrzymujemy funkcję jako czarną skrzynkę. Wiemy, że f ( x ) = u . x (to znaczy u 1 x 1 + U 2 x 2 + . . . + U n x n ( mod 2 ) ) dla ukrytego u ∈ { 0 , 1 } $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}$. Jak wymyślimy z jak najmniejszą liczbą zapytań do f ?$u$$f$

Mówią, że musimy postępować zgodnie z dwuetapową procedurą, aby ustalić minimalną możliwą liczbę kroków.$u$

• Ustaw superpozycję $\frac{1}{2^{n/2}}\sum_{x}(-1)^{f(x)}|x\rangle$

• Fouriera próbki w celu uzyskania .$u$

Tu się zgubiłem. Nie rozumiem, co dokładnie rozumieją przez „skonfigurowanie superpozycji…”. Dlaczego powinniśmy to zrobić? I w jaki sposób próbkowanie Fouriera (jak opisano) pomaga określić ?$u$

Budują dalej bramę kwantową w ten sposób:

$|0\rangle$$|-\rangle$$- \oplus f(0...0)$$\oplus$

$\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.$$

$\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)$

$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.$$

This gives the property

$$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.$$

This gives the final state as

$$\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.$$

We know that $f\left(x\right) = u.x = x.u$, giving $\left(-1\right)^{f\left(x\right) \oplus x.y} = \left(-1\right)^{x.\left(u\oplus y\right)}$. Summing over the $x$ terms gives that $\sum_x\left(-1\right)^{x.\left(u\oplus y\right)} = 0,\, \forall\, u\oplus y \neq 0$. This means that we're left with the term for $u\oplus y = 0$, which means that $u=y$, giving the output as $\left|u\right\rangle\left|-\right\rangle$, which is measured to obtain $u$.

Jeśli chodzi o to, dlaczego chcemy ustawić superpozycję : tutaj pojawia się moc obliczeń kwantowych - w mniej matematycznych kategoriach zastosowanie transformacji Hadamarda powoduje obrót stanów kubitów, aby dostać się do stanu$\left|+\right\rangle^{\otimes n}$. Następnie obracasz każdy kubit w tym stanie superpozycji za pomocą operacji równoważnej XOR (w tej nowej podstawie), dzięki czemu przy ponownym przeprowadzaniu transformacji Hadamarda teraz po prostu wracasz do stanu$\left|u\right\rangle$. Innym sposobem patrzenia na to jest uznanie go za odbicie lub odwrócenie, które pozwala osiągnąć ten sam rezultat.

Chodzi o to, że za pomocą superpozycji możemy to zrobić dla wszystkich kubitów jednocześnie, zamiast konieczności indywidualnego sprawdzania każdego kubitów, jak w przypadku klasycznym.