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

Немає перевірених версій цієї сторінки; ймовірно, її ще не перевіряли на відповідність правилам проекту.

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

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

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

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

Мотивація

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

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

Алгоритми

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

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

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

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

Квантове перетворення Фур'є^[en] може бути означене в термінах $\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}$ має значення тільки тоді, коли $\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$ є експоненційним у розмірі.

Приклади

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


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

Див. також

Примітки

↑ Mark Ettinger; Peter Høyer (1999). A quantum observable for the graph isomorphism problem. arXiv:quant-ph/9901029.
↑ Oded Regev (2003). Quantum computation and lattice problems. arXiv:cs/0304005.
↑ Mark Ettinger; Peter Hoyer; Emanuel Knill (2004). The quantum query complexity of the hidden subgroup problem is polynomial. Information Processing Letters. 91: 43—48. arXiv:quant-ph/0401083. Bibcode:2004quant.ph..1083E. doi:10.1016/j.ipl.2004.01.024. S2CID 5520617.
↑ Kitaev, Alexei (20 листопада 1995). Quantum measurements and the Abelian Stabilizer Problem. arXiv:quant-ph/9511026.

Джерела

[1] Mark Ettinger; Peter Høyer (1999). A quantum observable for the graph isomorphism problem. arXiv:quant-ph/9901029.

[2] Oded Regev (2003). Quantum computation and lattice problems. arXiv:cs/0304005.

[3] Mark Ettinger; Peter Hoyer; Emanuel Knill (2004). The quantum query complexity of the hidden subgroup problem is polynomial. Information Processing Letters. 91: 43—48. arXiv:quant-ph/0401083. Bibcode:2004quant.ph..1083E. doi:10.1016/j.ipl.2004.01.024. S2CID 5520617.

[4] Kitaev, Alexei (20 листопада 1995). Quantum measurements and the Abelian Stabilizer Problem. arXiv:quant-ph/9511026.

[1]

[2]

[3]

[4]