Trudności ze zrozumieniem algorytmu kwantowego dla problemu ukrytej podgrupy abelowej

Mam trudności ze zrozumieniem ostatnich kroków algorytmu AHSP. Niech $G$ była grupą abelowa i $f$ jest funkcją, która ukrywa podgrupy $H$ . Niech $G^*$ reprezentują podwójną grupę $G$ .

Oto kroki algorytmu

1. Najpierw przygotuj państwo,

   $\qquad \displaystyle I=\frac{1}{|G|} \sum_{g \in G} |g\rangle|0\rangle$.

2. Następnie zastosuj kwantową wyrocznię, która ocenia $f$ na $I$ , otrzymujemy

   $\qquad \displaystyle I'=\sum_{g \in G} |g\rangle|f(g)\rangle$ .

3. Teraz zmierzmy drugi kubit $I'$ , rozumiemy

   $\qquad\displaystyle I'= \left(\frac{1}{|H|}\Sigma_{g \in H} |rh\rangle\right) \otimes |f(rh)\rangle$

   jakiegoś $r \in G$ .

4. Teraz stosujemy kwantową transformatę Fouriera na pierwszym kubicie

   $\qquad \displaystyle I_m = \frac{1}{|H^*|}\sum_{\chi \in H^*} |\chi\rangle$,

   gdzie .$H^*= \{\chi \in G^*: \chi(h)=1 ,\forall h \in H\}$

Teraz od państwowego jaki sposób możemy uzyskać generatorów w grupie H ?$I_m$$H$

Ta klasyczna obróbka końcowa wykorzystuje kilka nietrywialnych grupowych właściwości teoretycznych grup abelowych. Napisałem dydaktyczne wyjaśnienie, w jaki sposób działa ten klasyczny algorytm [1] ; inne dobre źródła do przeczytania to [ 2 , 3 , 4 ].

$H^{*}$$H^{*}$$G^{*}$$O(\log{|G|})$$H^{*}$

$H$$H^{*}$

---

Teoria postaci

$G$$G$

$$\begin{equation} \chi_g(h)=\exp{\left(2\pi i \sum_{i=1}^{m} \frac{g(i)h(i)}{d_i}\right)}. \end{equation}$$ $g$$\chi_g$$G$$g\rightarrow \chi_g$$G^*$$G$

$H$$H^*$$H$$H$

1. $H^*$$G$

2. $H$$H^{**}$$H$$H\cong H^{**}$

   $$\chi_g(h)=1,\quad \textrm{ for every } g\in H^*$$ $H$

---

Równania liniowe nad grupami

$X$$Y$$b\in Y$$\alpha:X\rightarrow Y$

$$\alpha(x)=b$$ $A$, w taki sposób, że powyższy problem może zostać ponownie wyrażony jako gdzie przyjmujemy . $$\begin{equation} A x= \begin{pmatrix} a_1(1) & a_2(1) & \cdots & a_n(1)\\ a_1(2) & a_2(2) & \cdots & a_n(2)\\ \vdots & \vdots & \cdots & \vdots\\ a_1(m) & a_2(m) & \cdots & a_n(m) \end{pmatrix} \begin{pmatrix} x(1)\\ x(2)\\ \vdots\\ x(n) \end{pmatrix} = \begin{pmatrix} b(1) \\ b(2) \\ \vdots\\ b(m) \end{pmatrix} \begin{matrix} \mod d_1\\ \mod d_2\\ \vdots\\ \mod d_m \end{matrix} = b \end{equation}$$ $Y=\mathbb{Z}_{d_{1}}\times\cdots\times \mathbb{Z}_{d_{m}}$

Ostatnią kluczową obserwacją jest to, że istnieją wydajne klasyczne algorytmy do decydowania, czy systemy te dopuszczają rozwiązania, liczą je i je znajdują (badamy niektóre w [1] ). Zbiór rozwiązań ma zawsze postać , gdzie jest konkretnym rozwiązaniem, a jest jądrem (podgrupy ). Te klasyczne algorytmy mogą znaleźć określone rozwiązanie systemu i obliczyć zestaw generatora . Te klasyczne algorytmy wykorzystują kluczowe formy Smitha$x_0+\ker{\alpha}$$x_0$$\ker{\alpha}$$\alpha$$X$$\ker{\alpha}$ przepisać system w niemal przekątnej formie (konieczne są inne pośrednie kroki, ale powinno to dać intuicyjny obraz).

Układ równań, które można uzyskać w przypadku koduje ukrytej podgrupy . W szczególności ma postać , dla niektórych homomorfizmów grupowych . Jądro jest właśnie ukrytą podgrupą. Szczególnym rozwiązaniem w tym przypadku jest 0, trywialne.$H$$\Omega x = 0$$\Omega$$\Omega$

Po kroku 4, pomiar w podstawie obliczeniowej losowo da nam jeden . χ ∈ G $I_m$$\chi \in G^*$

Następnie powtórz wszystkie kroki zostały podane razy, aby uzyskać listę znaków w podwójnej grupy . Ta lista znaków generuje podgrupę podwójnej grupy .n G K G $n$$n$$G$$K$$G^*$

Następnie sprawdzamy poprzez (klasycznie) wszystkie możliwe podgrupy , aby znaleźć taki, gdzie jest . H ∗$H$$H^*$$K$

Dla ustalonego nie zawsze jest to unikalne dopasowanie, więc gdy występuje degeneracja, wybieramy po prostu największe dopasowanie (ponieważ trywialna podgrupa dopasuje wszystkie listy znaków).$n$