Задача прихованої підгрупи

Задача прихованої підгрупи (з англійської Hidden subgroup problem - HSP) є підходом до розв'язку задач в математиці та теоретичній інформатиці. В рамках підходу можна розглядати задачі факторизації, пошуку дискретного логарифму, Шаблон:Нп, та пошуку найкоротшого вектора. Це робить задачу дуже важливою в теорії квантових обчислень, оскільки факторизація за алгоритмом Шора в квантових обчисленнях є прикладом задачі про приховану підгрупу для скінченної абелевої групи, тоді як інші задачі відповідають неабелевим скінченним групам.

Постановка задачі

Нехай група $G$ має підгрупу $H\le G$. Також нехай маємо певну функцію $f:G\to X$, що відображає елементи групи $G$ в елементи деякої множини $X$. Говориться, що функція $f$ приховує підгрупу $H$, якщо для всіх $g_1,g_2\in G,f(g_1)=f(g_2)$ тоді і тільки тоді, коли $g_{1}H=g_{2}H$. Іншими словами, $f$ є константою на кожному класі суміжності, і водночас є різною для різних класів суміжності підгрупи $H$.

Задача прихованої підгрупи. Нехай $G$ є групою, $X$ - скінченною множиною, а функція $f:G\to X$ приховує підгрупу $H\le G$. Функція $f$ задається оракулом, який використовує $O(\log |G|+\log |X|)$ бітів. Задача полягає в тому, щоб, використовуючи інформацію, отриману з обчислень $f$ через оракул, визначити множину генераторів для підгрупи $H$.

Є також особливий випадок, коли множина $X$ також є групою (функція $f$ є груповим гомоморфізмом), а підгрупа $H$ є ядром функції $f$.

Мотивація

Задача прихованої підгрупи є особливо важливою в теорії квантових комп'ютерів з нижче перерахованих причин.

• Алгоритм Шора факторизації чи пошуку дискретного логарифму (а також кілька його узагальнень) опирається на можливості квантових компютерів розв`язати HSP для скінченних абелевих груп.
• Існування ефективного квантового алгоритму для HSP для певних неабелевих груп означало б існування ефективного квантового алгоритму для розв`язку двох важливих задач: Шаблон:Нп і деяких задач про пошук найкоротшого вектора (SVP) на ґратках. Точніше кажучи, ефективний квантовий алгоритм для HSP для симетричних груп передбачав би існування квантового алгоритму для ізоморфізму графів. Ефективний квантовий алгоритм для HSP для діедричної групи давав би можливість знайти єдиний найкоротший вектор (unique-SVP) за поліноміальний час від розмірності ґратки $n$.

Алгоритми

Існує ефективний квантовий алгоритм для розв`язку HSP для скінченних абелевих груп за час поліноміальний від $\log |G|$. Для довільної групи відомо, що задача прихованої підгрупи розв’язується з задіянням поліноміального числа обчислень оракула. Однак складність схеми, яка реалізує цей алгоритм, може бути експоненційною за $\log |G|$, що робить алгоритм неефективним в цілому, адже ефективний алгоритм мусить бути поліноміальним як за кількістю обчислень оракула, так і за часом виконання. Існування такого алгоритму для довільних груп є відкритим питанням. Квантові алгоритми, поліноміальні в часі, існують для певних підкласів груп, таких як напівпрямі добутки деяких абелевих груп.

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

Алгоритм для абелевих груп використовує представлення, тобто гомоморфізми з $G$ на ${\mathrm{G}\mathrm{L}}_k(ℂ)$, які є загальними лінійними групами над кільцем комплексних чисел. Представлення групи $G$ є Шаблон:Нп, якщо воно не може бути виражене як прямий добуток двох або більше представлень $G$. Для абелевої групи всі незвідні представлення є характерами, які є представленнями порядку 1; іншими словами, для абелевих груп не існує незвідних представлень вищих порядків.

Означення квантового перетворення Фур'є

Шаблон:Нп може бути означене в термінах ${\mathrm{Z}}_N$, адитивної циклічої групи порядку $N$. Введемо характер$${\chi }_j(k)={\omega }_N^{jk}=e^{2\pi i\frac{jk}{N}},$$ тоді квантове перетворення Фур'є має визначення $$F_N|j⟩=\frac{1}{\sqrt{N}}\sum _{k=0}^N{\chi }_j(k)|k⟩.$$ Далі визначаємо стани $|{\chi }_j⟩=F_N|j⟩$. Будь-яка абелева група може бути записана як прямий добуток кількох циклічних груп ${\mathrm{Z}}_{N_1}\times {\mathrm{Z}}_{N_2}\times \dots \times {\mathrm{Z}}_{N_m}$. На квантовому комп’ютері це можна представити як тензорний добуток кількох регістрів розмірів $N_1,N_2,\dots ,N_m$ відповідно, а квантове перетворення Фур'є загалом можна представити як $F_{N_1}\otimes F_{N_2}\otimes \dots \otimes F_{N_m}$.

Процедура

Множина характерів групи $G$ в свою чергу також формують групу $\hat{G}$, що називається дуальною групою до $G$. Також ми маємо підгрупу $H^{\perp }\le \hat{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$.

Алгоритм наступний:

1. Почати з стану $|0⟩|0⟩$, де базові стани лівого реєстру є елементами $G$, а базові стани правого реєстру є елементами $X$.
2. Створити суперпозицію базових станів $G$ в лівому реєстрі, що відповідає повному станові $\frac{1}{\sqrt{|G|}}\sum _{g\in G}|g⟩|0⟩$.
3. Задіяти функцію $f$. Після цього загальний стан буде $\frac{1}{\sqrt{|G|}}\sum _{g\in G}|g⟩|f(g)⟩$.
4. Зробити вимір на правому реєстрі, результатом якого буде $f(s)$ для деякого $s\in G$, а стан колапсує до $\frac{1}{\sqrt{|H|}}\sum _{h\in H}|s+h⟩|f(s)⟩$ , оскільки $f$ має однакове значення для всіх елементів з класу суміжності $s+H$. Надалі, відкидаючи правий реєстр, маємо стан $\frac{1}{\sqrt{|H|}}\sum _{h\in H}|s+h⟩$.
5. Застосовуючи квантове перетворення Фур`є, отримуємо стан $\frac{1}{\sqrt{|H|}}\sum _{h\in H}|{\chi }_{s+h}⟩$.
6. Цей стан є рівний (деталі нижче) станові $\sqrt{\frac{|H|}{|G|}}\sum _{{\chi }_g\in H^{\perp }}{\chi }_g(s)|g⟩$, який в свою чергу може бути виміряний для того, щоб отримати інформацію про $H$.
7. Повторюємо, допоки не визначимо $H$ (або множини генераторів $H$).

Стани в кроках 5 і 6 є рівними, оскільки: $$\begin{array}{cc}\frac{1}{\sqrt{|H|}}\sum _{h\in H}|{\chi }_{s+h}⟩& =\frac{1}{\sqrt{|H||G|}}\sum _{h\in H}\sum _{g\in G}{\chi }_{s+h}(g)|g⟩\\ & =\frac{1}{\sqrt{|H||G|}}\sum _{g\in G}{\chi }_s(g)\sum _{h\in H}{\chi }_h(g)|g⟩\\ & =\frac{1}{\sqrt{|H||G|}}\sum _{g\in G}{\chi }_g(s)(\sum _{h\in H}{\chi }_g(h))|g⟩\\ & =\sqrt{\frac{|H|}{|G|}}\sum _{{\chi }_g\in H^{\perp }}{\chi }_g(s)|g⟩\end{array}$$ Для встановлення останньої рівності ми використовуємо тотожнсть: $$\sum _{h\in H}{\chi }_g(h)=\{\begin{array}{cc}|H|& {\chi }_g\in H^{\perp }\\ 0& {\chi }_g\notin H^{\perp }\end{array}$$ яка може бути виведена з ортогональності характерів. Характери групи $G$ формують ортогональний базис: $$\frac{1}{|H|}\sum _{h\in H}{\chi }_g(h){\chi }_{g^{\prime }}(h)=\{\begin{array}{cc}1& g=g^{\prime }\\ 0& g\ne g^{\prime }\end{array}$$ Ми вважаємо ${\chi }_{g^{\prime }}$ тривіальними представленнями, які відображають всі елементи в $1$, щоб отримати наступну рівність:$$\sum _{h\in H}{\chi }_g(h)=\{\begin{array}{cc}|H|& g\text{ is trivial}\\ 0& g\text{ is not trivial}\end{array}$$Так як сумування здійснюється по $H$, тривіальність ${\chi }_g$ має значення тільки тоді, коли ${\chi }_g$ також тривіальна по $H$; тобто, якщо ${\chi }_g\in H^{\perp }$. Таким чином, ми знаємо, що в результаті сумування ми отримаємо $|H|$, якщо ${\chi }_g\in H^{\perp }$, і отримаємо $0$ , якщо ${\chi }_g\notin H^{\perp }$.

Кожне вимірювання остаточного стану дасть додаткову інформацію про $H$, так як ми знаємо, що ${\chi }_g(h)=1$ для всіх $h\in H$. $H$, або множина генераторів для $H$, буде знайдено після поліноміальної кількості вимірювань. Розмір множини генераторів буде логарифмічно малим, у порівнянні з розміром $G$. Позначимо через $T$ множину генераторів для $H$, тобто, $⟨T⟩=H$. Розмір підгрупи, згенерованої $T$, подвоюватиметься, коли до неї додаватиметься новий елемент $t\notin T$, тому що $H$ і $t+H$ є неперетинними і $H,t+H\subseteq ⟨\{t\}\cup T⟩$. Таким чином, розмір множини генераторів $|T|$ задовольняє наступне співвідношення$$|T|\le \log |H|\le \log |G|$$Отже, множину генераторів для $H$ можна отримати у поліноміальний час, навіть якщо $G$ є експоненційним у розмірі.

Приклади

Багато алгоритмів, для яких можна отримати квантове пришвидшення, є прикладами задачі прихованої підгрупи. У таблиці внизу подано важливі прикладі задачі прихованої підгрупи, та зазначено їхню розв'язність.

Задача	Квантовий алгоритм	Абелева?	Поліноміальний час розв'язання?
Задача Дойча	Алгоритм Дойча; алгоритм Дойча — Йожи	Так	Так
Шаблон:Нп	Алгоритм Саймона	Так	Так
Знаходження порядку	Алгоритм знаходження порядку Шора	Так	Так
Дискретне логарифмування	Шаблон:Section link	Так	Так
Знаходження періоду	Алгоритм Шора	Так	Так
Абелів стабілізатор	Алгоритм Китаєва	Так	Так
Ізоморфізм графів	Немає	Ні	Ні
Задача про найкоротший вектор	Немає	Ні	Ні

Див. також

• Шаблон:Нп
• Дуальність Понтрягіна

Джерела

• Richard Jozsa: Quantum factoring, discrete logarithms and the hidden subgroup problem
• Chris Lomont: The Hidden Subgroup Problem - Review and Open Problems
• Hidden subgroup problem on arxiv.org