Трудность в понимании квантового алгоритма для задачи об абелевой скрытой подгруппе

У меня есть трудности в понимании последних шагов алгоритма AHSP. Пусть абелева группа и е функция , которая скрывает подгруппу H . Пусть G * представляет двойную группу G .$G$$f$$H$$G^*$$G$

Вот шаги алгоритма

1. Сначала подготовь государство,

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

2. Затем примените квантовый оракул, который оценивает на I , мы получаем$f$$I$

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

3. Теперь измерим второй кубит , получим$I'$

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

   для некоторого .$r \in G$

4. Теперь мы применяем квантовое преобразование Фурье на первом кубите, получим

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

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

Теперь из состояния как мы можем получить генераторы группы H ?$I_m$$H$

Эта классическая постобработка использует несколько нетривиальных групповых теоретических свойств абелевых групп. Я написал дидактическое объяснение того, как этот классический алгоритм работает здесь [1] ; другие хорошие источники для чтения [ 2 , 3 , 4 ].

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

$H$$H^{*}$

---

Теория персонажей

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

---

Линейные уравнения над группами

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

Последнее ключевое наблюдение состоит в том, что существуют эффективные классические алгоритмы, позволяющие решить, допускают ли эти системы решения, подсчитать их и найти их (некоторые из них мы рассмотрели в [1] ). Множество решений всегда имеет вид , где - это конкретное решение, а - ядро (подгруппа ). Эти классические алгоритмы могут найти конкретное решение системы и вычислить порождающий набор . Эти классические алгоритмы решающим образом используют нормальные формы Смита.$x_0+\ker{\alpha}$$x_0$$\ker{\alpha}$$\alpha$$X$$\ker{\alpha}$ переписать систему в почти диагональной форме (необходимы некоторые другие промежуточные шаги, но это должно дать вам интуитивную картину).

Система уравнений , что вы получите в вашем случае кодирует скрытую подгруппу . В частности, имеет вид для некоторого группового гомоморфизма . Ядро - это именно скрытая подгруппа. Конкретным решением в этом случае является 0, тривиальное.$H$$\Omega x = 0$$\Omega$$\Omega$

После вашего шага 4 измерение в вычислительном базисе случайным образом даст нам один . χ ∈ G $I_m$$\chi \in G^*$

Затем повторите все шаги , которые вы дали раз , чтобы получить список символов в двойственной группе . Этот список символов порождает подгруппу двойственной группы .n G K G $n$$n$$G$$K$$G^*$

Затем мы проверяем через (классический) все возможные подгруппы , чтобы найти тот , где является . H ∗$H$$H^*$$K$

Для фиксированного это не всегда уникальное совпадение, поэтому при вырождении мы просто выбираем наибольшее совпадение (так как тривиальная подгруппа будет соответствовать всем спискам символов).$n$