Проблема скрытой подгруппы

Проблема скрытой подгруппы ( HSP ) является темой исследований в области математики и теоретической информатики . Структура охватывает такие проблемы, как факторизация , дискретный логарифм , изоморфизм графов и задача о кратчайшем векторе . Это делает это особенно важным в теории квантовых вычислений , поскольку алгоритм Шора для факторизации в квантовых вычислениях является примером проблемы скрытой подгруппы для конечных абелевых групп , в то время как другие проблемы соответствуют конечным группам, которые не являются абелевыми.

Постановка задачи [ править ]

Учитывая группу $G$ , подгруппа $H\leq G$ , и набор $X$ , мы говорим, что функция $f:G\to X$ скрывает подгруппу $H$ если для всех $g_{1},g_{2}\in G,f(g_{1})=f(g_{2})$ тогда и только тогда, когда $g_{1}H=g_{2}H$ . Эквивалентно, $f$ является постоянным в смежных классах H , он различен в то время как в разных смежных классах H .

Проблема скрытой подгруппы : пусть $G$ быть группой, $X$ конечное множество, и $f:G\to X$ функция, которая скрывает подгруппу $H\leq G$ . Функция $f$ передается через оракул , который использует $O(\log |G|+\log |X|)$ биты. Используя информацию, полученную в результате оценок $f$ через свой оракул определить генераторную установку для $H$ .

Особый случай – это когда $X$ это группа и $f$ является групповым гомоморфизмом, и в этом случае $H$ соответствует ядру $f$ .

Мотивация [ править ]

Проблема скрытых подгрупп особенно важна в теории квантовых вычислений по следующим причинам.

Алгоритм Шора для факторизации и нахождения дискретных логарифмов (а также некоторые его расширения) основан на способности квантовых компьютеров решать HSP для конечных абелевых групп .
Существование эффективных квантовых алгоритмов для HSP для некоторых неабелевых групп подразумевало бы эффективные квантовые алгоритмы для решения двух основных проблем: проблемы изоморфизма графов и некоторых задач о кратчайших векторах (SVP) в решетках. Точнее, эффективный квантовый алгоритм HSP для симметричной группы даст квантовый алгоритм изоморфизма графов. ^[1] Эффективный квантовый алгоритм для HSP для группы диэдра дал бы квантовый алгоритм для $\operatorname {poly} (n)$ уникальный СВП. ^[2]

Алгоритмы [ править ]

Существует эффективный квантовый алгоритм решения HSP над конечными абелевыми группами за полиномиальное по времени время. $\log |G|$ . Для произвольных групп известно, что проблема скрытой подгруппы разрешима с использованием полиномиального числа оценок оракула. ^[3] Однако схемы, реализующие это, могут быть экспоненциальными по $\log |G|$ , что делает алгоритм в целом неэффективным; эффективные алгоритмы должны быть полиномиальными по количеству вычислений оракула и времени работы. Существование такого алгоритма для произвольных групп открыто. Алгоритмы квантового полиномиального времени существуют для определенных подклассов групп, таких как полупрямые произведения некоторых абелевых групп .

Алгоритм для абелевых групп [ править ]

Алгоритм для абелевых групп использует представления , т.е. гомоморфизмы из $G$ к $\mathrm {GL} _{k}(\mathbb {C} )$ , общая линейная группа над комплексными числами . Представление является неприводимым, если оно не может быть выражено как прямой продукт двух или более представлений. $G$ . Для абелевой группы все неприводимые представления являются характерами , которые являются представлениями размерности один; неприводимых представлений большей размерности для абелевых групп не существует.

квантового Определение преобразования Фурье

Квантовое преобразование Фурье можно определить в терминах $\mathrm {Z} _{N}$ , аддитивная циклическая группа порядка $N$ . Представляем персонажа

\chi _{j}(k)=\omega _{N}^{jk}=e^{2\pi i{\frac {jk}{N}}},

квантовое преобразование Фурье имеет определение

F_{N}|j\rangle ={\frac {1}{\sqrt {N}}}\sum _{k=0}^{N}\chi _{j}(k)|k\rangle .

Кроме того, мы определяем

|\chi _{j}\rangle =F_{N}|j\rangle

. Любую абелеву группу можно записать как прямое произведение нескольких циклических групп.

\mathrm {Z} _{N_{1}}\times \mathrm {Z} _{N_{2}}\times \ldots \times \mathrm {Z} _{N_{m}}

. На квантовом компьютере это представляется как тензорное произведение нескольких регистров измерений.

N_{1},N_{2},\ldots ,N_{m}

соответственно, а общее квантовое преобразование Фурье равно

F_{N_{1}}\otimes F_{N_{2}}\otimes \ldots \otimes F_{N_{m}}

.

Процедура [ править ]

Набор персонажей $G$ формирует группу ${\widehat {G}}$ называемая группой двойственной $G$ . Еще у нас есть подгруппа $H^{\perp }\leq {\widehat {G}}$ размера $|G|/|H|$ определяется

H^{\perp }=\{\chi _{g}:\chi _{g}(h)=1{\text{ for all }}h\in H\}

Для каждой итерации алгоритма квантовая схема выводит элемент

g\in G

соответствующий персонажу

\chi _{g}\in H^{\perp }

, и поскольку

\chi _{g}(h)={1}

для всех

h\in H

, это помогает определить, что

H

является.

Алгоритм следующий:

Начни с государства $|0\rangle |0\rangle$ , где базисные состояния левого регистра — это каждый элемент $G$ , а базовые состояния правого регистра являются каждым элементом $X$ .
Создайте суперпозицию между базисными состояниями $G$ в левом регистре, оставляя состояние ${\textstyle {\frac {1}{\sqrt {|G|}}}\sum _{g\in G}|g\rangle |0\rangle }$ .
Запросить функцию $f$ . Состояние после этого ${\textstyle {\frac {1}{\sqrt {|G|}}}\sum _{g\in G}|g\rangle |f(g)\rangle }$ .
Измерьте выходной регистр. Это дает некоторую $f(s)$ для некоторых $s\in G$ , и схлопывает состояние до ${\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|s+h\rangle |f(s)\rangle }$ потому что $f$ имеет одинаковое значение для каждого элемента смежного класса $s+{H}$ . Мы отбрасываем выходной регистр, чтобы получить ${\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|s+h\rangle }$ .
Выполните квантовое преобразование Фурье, получив состояние ${\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|\chi _{s+h}\rangle }$ .
Это состояние равно ${\textstyle {\sqrt {\frac {|H|}{|G|}}}\sum _{\chi _{g}\in H^{\perp }}\chi _{g}(s)|g\rangle }$ , который можно измерить, чтобы узнать информацию о $H$ .
Повторяйте до $H$ (или генераторная установка для $H$ ) определяется.

Состояние на шаге 5 равно состоянию на шаге 6 по следующим причинам:

{\begin{aligned}{\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|\chi _{s+h}\rangle &={\frac {1}{\sqrt {|H||G|}}}\sum _{h\in H}\sum _{g\in G}\chi _{s+h}(g)|g\rangle \\&={\frac {1}{\sqrt {|H||G|}}}\sum _{g\in G}\chi _{s}(g)\sum _{h\in H}\chi _{h}(g)|g\rangle \\&={\frac {1}{\sqrt {|H||G|}}}\sum _{g\in G}\chi _{g}(s)\left(\sum _{h\in H}\chi _{g}(h)\right)|g\rangle \\&={\sqrt {\frac {|H|}{|G|}}}\sum _{\chi _{g}\in H^{\perp }}\chi _{g}(s)|g\rangle \end{aligned}}

Для последнего равенства мы используем следующее тождество:

Теорема —

\sum _{h\in H}\chi _{g}(h)={\begin{cases}|H|&\chi _{g}\in H^{\perp }\\0&\chi _{g}\notin H^{\perp }\end{cases}}

Доказательство

Это можно вывести из ортогональности символов. Персонажи $G$ образуют ортонормированный базис:

{\frac {1}{\vert H\vert }}\sum _{h\in H}\chi _{g}(h)\chi _{g'}(h)={\begin{cases}1&g=g'\\0&g\neq g'\end{cases}}

Мы позволяем

\chi _{g'}

быть тривиальным представлением, которое отображает все входные данные в

1

, получить

\sum _{h\in H}\chi _{g}(h)={\begin{cases}\vert H\vert &g{\text{ is trivial}}\\0&g{\text{ is not trivial}}\end{cases}}

Поскольку суммирование производится

H

,

\chi _{g}

также тривиальность имеет значение только в том случае, если она тривиальна над

H

; то есть, если

\chi _{g}\in H^{\perp }

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

\vert H\vert

если

\chi _{g}\in H^{\perp }

и приведет к

0

если

\chi _{g}\notin H^{\perp }

.

Каждое измерение конечного состояния приведет к получению некоторой информации о $H$ поскольку мы знаем это $\chi _{g}(h)=1$ для всех $h\in H$ . $H$ , или генераторная установка для $H$ , будет найден после полиномиального числа измерений. Размер генераторной установки будет логарифмически мал по сравнению с размером $G$ . Позволять $T$ обозначим порождающий набор для $H$ , значение $\langle T\rangle =H$ . Размер подгруппы, созданной $T$ будет удвоено, когда новый элемент $t\notin T$ к нему добавляется, потому что $H$ и $t+H$ непересекающиеся и потому $H,t+H\subseteq \langle \{t\}\cup T\rangle$ . Таким образом, размер генераторной установки $|T|$ удовлетворяет

|T|\leq \log |H|\leq \log |G|

Таким образом, генераторная установка для

H

можно будет получить за полиномиальное время, даже если

G

имеет экспоненциальный размер.

Экземпляры [ править ]

Многие алгоритмы, в которых происходит квантовое ускорение квантовых вычислений, являются примерами проблемы скрытой подгруппы. В следующем списке описаны важные случаи HSP и указано, разрешимы ли они.


Проблема	Квантовый алгоритм	Абелев?	Полиномиальное решение по времени?
проблема немца	алгоритм Германа; Алгоритм Германа-Йожсы	Да	Да
Проблема Саймона	Алгоритм Саймона	Да	Да
Поиск заказа	Алгоритм поиска порядка Шора	Да	Да
Дискретный логарифм	Алгоритм Шора § Дискретные логарифмы	Да	Да
Нахождение периода	Алгоритм Шора	Да	Да
Абелев стабилизатор	Алгоритм Китаева ^[4]	Да	Да
Изоморфизм графа	Никто	Нет	Нет
Задача о кратчайшем векторе	Никто	Нет	Нет

См. также [ править ]

Ссылки [ править ]

^ Марк Эттингер; Питер Хойер (1999). «Квантовая наблюдаемая для проблемы изоморфизма графов». arXiv : Quant-ph/9901029 .
^ Одед Регев (2003). «Квантовые вычисления и проблемы решетки». arXiv : cs/0304005 .
^ Марк Эттингер; Питер Хойер; Эмануэль Нилл (2004). «Сложность квантового запроса проблемы скрытой подгруппы полиномиальна». Письма об обработке информации . 91 : 43–48. arXiv : Quant-ph/0401083 . Бибкод : 2004quant.ph..1083E . дои : 10.1016/j.ipl.2004.01.024 . S2CID 5520617 .
^ Китаев, Алексей (20 ноября 1995 г.). «Квантовые измерения и проблема абелева стабилизатора». arXiv : Quant-ph/9511026 .

Внешние ссылки [ править ]

[1] Марк Эттингер; Питер Хойер (1999). «Квантовая наблюдаемая для проблемы изоморфизма графов». arXiv : Quant-ph/9901029 .

[2] Одед Регев (2003). «Квантовые вычисления и проблемы решетки». arXiv : cs/0304005 .

[3] Марк Эттингер; Питер Хойер; Эмануэль Нилл (2004). «Сложность квантового запроса проблемы скрытой подгруппы полиномиальна». Письма об обработке информации . 91 : 43–48. arXiv : Quant-ph/0401083 . Бибкод : 2004quant.ph..1083E . дои : 10.1016/j.ipl.2004.01.024 . S2CID 5520617 .

[4] Китаев, Алексей (20 ноября 1995 г.). «Квантовые измерения и проблема абелева стабилизатора». arXiv : Quant-ph/9511026 .

[1]

[2]

[3]

[4]