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

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

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

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

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

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

Мотивація

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

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

Алгоритми

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

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

Алгоритм для абелевих груп використовує представлення, тобто гомоморфізми з ${\displaystyle G}$ на ${\displaystyle \mathrm {GL} _{k}(\mathbb {C} )}$, які є загальними лінійними групами над кільцем комплексних чисел. Представлення групи ${\displaystyle G}$ є незвідним^[en], якщо воно не може бути виражене як прямий добуток двох або більше представлень ${\displaystyle G}$. Для абелевої групи всі незвідні представлення є характерами, які є представленнями порядку 1; іншими словами, для абелевих груп не існує незвідних представлень вищих порядків.

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

Квантове перетворення Фур'є^[en] може бути означене в термінах ${\displaystyle \mathrm {Z} _{N}}$, адитивної циклічої групи порядку ${\displaystyle N}$. Введемо характер$${\displaystyle \chi _{j}(k)=\omega _{N}^{jk}=e^{2\pi i{\frac {jk}{N}}},}$$ тоді квантове перетворення Фур'є має визначення $${\displaystyle F_{N}|j\rangle ={\frac {1}{\sqrt {N}}}\sum _{k=0}^{N}\chi _{j}(k)|k\rangle .}$$ Далі визначаємо стани ${\displaystyle |\chi _{j}\rangle =F_{N}|j\rangle }$. Будь-яка абелева група може бути записана як прямий добуток кількох циклічних груп ${\displaystyle \mathrm {Z} _{N_{1}}\times \mathrm {Z} _{N_{2}}\times \ldots \times \mathrm {Z} _{N_{m}}}$. На квантовому комп’ютері це можна представити як тензорний добуток кількох регістрів розмірів ${\displaystyle N_{1},N_{2},\ldots ,N_{m}}$ відповідно, а квантове перетворення Фур'є загалом можна представити як ${\displaystyle F_{N_{1}}\otimes F_{N_{2}}\otimes \ldots \otimes F_{N_{m}}}$.

Процедура

Множина характерів групи ${\displaystyle G}$ в свою чергу також формують групу ${\displaystyle {\widehat {G}}}$, що називається дуальною групою до ${\displaystyle G}$. Також ми маємо підгрупу ${\displaystyle H^{\perp }\leq {\widehat {G}}}$ розміру ${\displaystyle |G|/|H|}$ , що визначається як $${\displaystyle H^{\perp }=\{\chi _{g}:\chi _{g}(h)=1{\text{ for all }}h\in H\}}$$ На кожній ітерації алгоритму квантова схема видає елемент ${\displaystyle g\in G}$, що відповідає характеру ${\displaystyle \chi _{g}\in H^{\perp }}$, і оскільки ${\displaystyle \chi _{g}(h)={1}}$ для всіх ${\displaystyle h\in H}$, це допомагає визначити, якою є ${\displaystyle H}$.

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

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

Стани в кроках 5 і 6 є рівними, оскільки: $${\displaystyle {\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}}}$$ Для встановлення останньої рівності ми використовуємо тотожнсть: $${\displaystyle \sum _{h\in H}\chi _{g}(h)={\begin{cases}|H|&\chi _{g}\in H^{\perp }\\0&\chi _{g}\notin H^{\perp }\end{cases}}}$$ яка може бути виведена з ортогональності характерів. Характери групи ${\displaystyle G}$ формують ортогональний базис: $${\displaystyle {\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}}}$$ Ми вважаємо ${\displaystyle \chi _{g'}}$ тривіальними представленнями, які відображають всі елементи в ${\displaystyle 1}$, щоб отримати наступну рівність:$${\displaystyle \sum _{h\in H}\chi _{g}(h)={\begin{cases}\vert H\vert &g{\text{ is trivial}}\\0&g{\text{ is not trivial}}\end{cases}}}$$Так як сумування здійснюється по ${\displaystyle H}$, тривіальність ${\displaystyle \chi _{g}}$ має значення тільки тоді, коли ${\displaystyle \chi _{g}}$ також тривіальна по ${\displaystyle H}$; тобто, якщо ${\displaystyle \chi _{g}\in H^{\perp }}$. Таким чином, ми знаємо, що в результаті сумування ми отримаємо ${\displaystyle \vert H\vert }$, якщо ${\displaystyle \chi _{g}\in H^{\perp }}$, і отримаємо ${\displaystyle 0}$ , якщо ${\displaystyle \chi _{g}\notin H^{\perp }}$.

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

Приклади

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

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

Див. також

• Задача прихованого зсуву^[en]
• Дуальність Понтрягіна