Kesulitan dalam memahami algoritma kuantum untuk masalah subkelompok tersembunyi abelian

Saya mengalami kesulitan dalam memahami langkah-langkah terakhir dari algoritma AHSP. Mari menjadi grup abelian dan f menjadi fungsi yang menyembunyikan subkelompok H . Mari G * mewakili kelompok ganda G .$G$$f$$H$$G^*$$G$

Berikut langkah-langkah algoritma

1. Pertama-tama persiapkan negara,

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

2. Kemudian menerapkan oracle kuantum yang mengevaluasi pada I , kita dapatkan$f$$I$

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

3. Sekarang ukur qubit kedua , kita dapatkan$I'$

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

   untuk beberapa .$r \in G$

4. Sekarang kita menerapkan transformasi quantum fourier pada qubit pertama, kita dapatkan

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

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

Sekarang dari negara bagaimana kita bisa mendapatkan generator dari grup H ?$I_m$$H$

Post-processing klasik ini mengeksploitasi beberapa properti teoretis kelompok non-sepele dari grup Abelian. Saya menulis penjelasan didaktik tentang bagaimana algoritma klasik ini bekerja di sini [1] ; Sumber lain yang baik untuk dibaca adalah [ 2 , 3 , 4 ].

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

$H$$H^{*}$

---

Teori Karakter

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

---

Persamaan Linear atas Grup

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

$$\alpha(x)=b$$ $A$ $$\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}}$

$x_0+\ker{\alpha}$$x_0$$\ker{\alpha}$$\alpha$$X$$\ker{\alpha}$ untuk menulis ulang sistem dalam bentuk yang hampir diagonal (beberapa langkah menengah lainnya diperlukan, tetapi itu akan memberi Anda gambaran intuitif).

$H$$\Omega x = 0$$\Omega$$\Omega$

$I_m$$\chi \in G^*$

$n$$n$$G$$K$$G^*$

$H$$H^*$$K$

$n$