Dificuldade em entender o algoritmo quântico para o problema de subgrupos ocultos abelianos

Tenho dificuldade em entender os últimos passos do algoritmo AHSP. Deixe ser um grupo abeliano e ser a função que esconde o subgrupo . Deixe- representam o duplo grupo de .$G$$f$$H$$G^*$$G$

Aqui estão as etapas do algoritmo

1. Primeiro prepare o estado,

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

2. Em seguida, aplique o oráculo quântico que avalia em , obtemos$f$$I$

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

3. Agora meça o segundo qubit de , obtemos$I'$

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

   para alguns .$r \in G$

4. Agora aplicamos a transformada quântica de Fourier no primeiro qubit, obtemos

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

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

Agora, do estado como podemos obter geradores do grupo ?$I_m$$H$

Esse pós-processamento clássico explora várias propriedades teóricas de grupos não triviais de grupos abelianos. Eu escrevi uma explicação didática de como esse algoritmo clássico funciona aqui [1] ; outras boas fontes para se ler são [ 2 , 3 , 4 ].

Portanto, medir no final do algoritmo na base padrão fornecerá elementos de uniformemente aleatoriamente. Não é difícil verificar se o conjunto é um subgrupo (abeliano finito) do grupo de caracteres ; devido a, após a medição de , um conjunto gerador de é obtido com probabilidade exponencialmente próxima a um.$H^{*}$$H^{*}$$G^{*}$$O(\log{|G|})$$H^{*}$

A parte mais técnica é como reconstruir dado um conjunto gerador de . Vamos nos concentrar neste problema a partir de agora. Para isso, precisaremos de alguns rudimentos da teoria do caráter.$H$$H^{*}$

---

Teoria do Personagem

Antes de tudo, lembre-se de que, quando é um abeliano finito, os caracteres formam um grupo isomórfico para e que podem ser escritos como A etiqueta do carácter é um elemento de . O mapa define um isomorfismo entre e , para que possamos identificar os dois grupos.$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$

Agora, dado , o conjunto você descreve é calle o subgrupo ortogonal de ou, dependendo da fonte, o aniquilador de . Este subgrupo possui algumas propriedades matemáticas importantes:$H$$H^*$$H$$H$

1. Primeiro de tudo, também é subgrupo de ;$H^*$$G$

2. É duplo para , no sentido de que, se considerarmos o subgrupo de aniquilador duplo , esse subgrupo é isomórfico para : ou seja, . Isso garante que as soluções para o sistema de equações são precisamente os elementos do subgrupo que você deseja.H * * H H ≅ H * * χ g ( h ) = 1 $H$$H^{**}$$H$$H\cong H^{**}$

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

---

Equações lineares sobre grupos

Agora, uma observação chave que podemos usar é a seguinte (seguirei [1] para esta parte): os antigos sistemas de equações podem ser reescritos como um '' sistema de equações lineares sobre grupos abelianos finitos ''. Com isso, quero dizer um problema em que as entradas são para os grupos abelianos finitos , ; um elemento ; um homomorfismo de grupo e a tarefa é encontrar as soluções da equação Você pode mostrar que qualquer homomorfismo pode ser escrito como uma matriz , de maneira que o problema acima pode ser reexpresso como Y b ∈ Y α : X → Y α ( x ) = b $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}$$ em que assumimos .$Y=\mathbb{Z}_{d_{1}}\times\cdots\times \mathbb{Z}_{d_{m}}$

A observação final chave é que existem algoritmos clássicos eficientes para decidir se esses sistemas admitem soluções, as contam e as encontram (pesquisamos algumas em [1] ). O conjunto de soluções sempre tem a forma , onde é uma solução específica e é o kernel de (um subgrupo de ). Esses algoritmos clássicos podem encontrar uma solução específica do sistema e calcular um conjunto gerador de . Esses algoritmos clássicos fazem uso crucial das Formas Normais de Smith$x_0+\ker{\alpha}$$x_0$$\ker{\alpha}$$\alpha$$X$$\ker{\alpha}$ reescrever o sistema em uma forma quase diagonal (são necessárias outras etapas intermediárias, mas isso deve fornecer uma imagem intuitiva).

O sistema de equações que você obtenha em seu caso codifica o subgrupo escondido . Em particular, é da forma , para algum homomorfismo de grupo . O kernel do é precisamente o subgrupo oculto. Uma solução específica nesse caso é 0, a trivial.$H$$\Omega x = 0$$\Omega$$\Omega$

Após o passo 4, medir na base computacional nos dará aleatoriamente um . χ ∈ G $I_m$$\chi \in G^*$

Em seguida, repetir todos os passos que deram vezes para obter uma lista de caracteres no duplo grupo de . Essa lista de caracteres gera um subgrupo do grupo duplo .n G K G $n$$n$$G$$K$$G^*$

Em seguida, verifique a (classicamente) todas as possíveis subgrupos para encontrar uma onde é . H ∗$H$$H^*$$K$

Para fixo, essa nem sempre é uma correspondência única; portanto, quando houver degeneração, escolheríamos a maior correspondência (pois o subgrupo trivial corresponderá a todas as listas de caracteres).$n$