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

11

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

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

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

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

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

    .I=gG|g|f(g)

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

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

    для некоторого .rG

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

    ,Im=1|H|χH|χ

    где .H={χG:χ(h)=1,hH}

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

user774025
источник
Я настоятельно рекомендую прочитать конспект лекций Эндрю Чайлдса по AHSP. Они доступны по адресу math.uwaterloo.ca/~amchilds/teaching/w13/qic823.html
Робин Котари

Ответы:

4

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

HHGO(log|G|)H

HH


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

GG

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

HHHH

  1. HG

  2. HHHHH

    χg(h)=1, for every gH
    H

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

XYbYα: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
Y=Zd1××Zdm

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

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

Хуан Бермехо Вега
источник
2

После вашего шага 4 измерение в вычислительном базисе случайным образом даст нам один . χ G ImχG

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

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

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

WJ Zeng
источник