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

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

Задача прихованої підгрупи (з англійської 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 для симетричних груп передбачав би існування квантового алгоритму для ізоморфізму графів. Ефективний квантовий алгоритм для HSP для діедричної групи давав би можливість знайти єдиний найкоротший вектор (unique-SVP) за поліноміальний час від розмірності ґратки ${\displaystyle n}$.

Алгоритми

Існує ефективний квантовий алгоритм для розв`язку HSP для (скінченних абелевих груп) за час поліноміальний від ${\displaystyle \log |G|}$. Для довільної групи відомо, що задача прихованої підгрупи розв’язується з задіянням поліноміального числа обчислень оракула. Однак складність схеми, яка реалізує цей алгоритм, може бути експоненційною за ${\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]	Алгоритм Саймона	Так	Так
Знаходження порядку	Алгоритм знаходження порядку Шора	Так	Так
Дискретне логарифмування	(Алгоритм Шора § Дискретні логарифми)	Так	Так
Знаходження періоду	Алгоритм Шора	Так	Так
Абелів стабілізатор	Алгоритм Китаєва	Так	Так
Ізоморфізм графів	Немає	Ні	Ні
Задача про найкоротший вектор	Немає	Ні	Ні

Див. також

• ^[en]
• Дуальність Понтрягіна

Примітки

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.

Джерела

• 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