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

11

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

Aqui estão as etapas do algoritmo

  1. Primeiro prepare o estado,

    I=1|G|gG|g|0 .

  2. Em seguida, aplique o oráculo quântico que avalia em , obtemosfI

    I=gG|g|f(g) .

  3. Agora meça o segundo qubit de , obtemosI

    I=(1|H|ΣgH|rh)|f(rh)

    para alguns .rG

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

    Im=1|H|χH|χ ,

    onde .H={χG:χ(h)=1,hH}

Agora, do estado como podemos obter geradores do grupo ? HImH

user774025
fonte
Eu recomendo fortemente a leitura das notas da aula de Andrew Childs sobre AHSP. Eles estão disponíveis em math.uwaterloo.ca/~amchilds/teaching/w13/qic823.html
Robin Kothari

Respostas:

4

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.HHGO(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.HH


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

χg(h)=exp(2πii=1mg(i)h(i)di).
gχgGgχgGG

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:HHHH

  1. Primeiro de tudo, também é subgrupo de ;HG

  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 ,HHHHH H

    χg(h)=1, for every gH
    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 AXYbYα:XY

α(x)=b
A
Ax=(a1(1)a2(1)an(1)a1(2)a2(2)an(2)a1(m)a2(m)an(m))(x(1)x(2)x(n))=(b(1)b(2)b(m))modd1modd2moddm=b
em que assumimos .Y=Zd1××Zdm

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 Smithx0+kerαx0kerααXkerα 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Ωx=0ΩΩ

Juan Bermejo Vega
fonte
2

Após o passo 4, medir na base computacional nos dará aleatoriamente um . χ G Imχ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 nnGKG

Em seguida, verifique a (classicamente) todas as possíveis subgrupos para encontrar uma onde é . H KHHK

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

WJ Zeng
fonte