Задача прихованої підгрупи
![]() | Цю статтю перекладають з іншої мови. Будь ласка, не редагуйте її, бо Ваші зміни можуть бути втрачені. Якщо ця стаття не редагувалася кілька днів, будь ласка, приберіть цей шаблон. Це повідомлення призначене для уникнення конфліктів редагування. Останнє редагування зробив користувач 2A02:2378:1064:19A:C9C5:80FD:658A:BD06 (внесок, журнали) о 09:14 UTC (6837 хвилин тому). |
Задача прихованої підгрупи (з англійської Hidden subgroup problem - HSP) є підходом до розв'язку задач в математиці та теоретичній інформатиці. В рамках підходу можна розглядати задачі факторизації, пошуку дискретного логарифму, ізоморфізму графів[en], та пошуку найкоротшого вектора. Це робить задачу дуже важливою в теорії квантових обчислень, оскільки факторизація за алгоритмом Шора в квантових обчисленнях є прикладом задачі про приховану підгрупу для скінченної абелевої групи, тоді як інші задачі відповідають неабелевим скінченним групам.
Нехай група має підгрупу . Також нехай маємо певну функцію , що відображає елементи групи в елементи деякої множини . Говориться, що функція приховує підгрупу , якщо для всіх тоді і тільки тоді, коли . Іншими словами, є константою на кожному класі суміжності, і водночас є різною для різних класів суміжності підгрупи .
Задача прихованої підгрупи. Нехай є групою, - скінченною множиною, а функція приховує підгрупу . Функція задається оракулом, який використовує бітів. Задача полягає в тому, щоб, використовуючи інформацію, отриману з обчислень через оракул, визначити множину генераторів для підгрупи .
Є також особливий випадок, коли множина також є групою (функція є груповим гомоморфізмом), а підгрупа є ядром функції .
Задача прихованої підгрупи є особливо важливою в теорії квантових комп'ютерів з нижче перерахованих причин.
- Алгоритм Шора факторизації чи пошуку дискретного логарифму (а також кілька його узагальнень) опирається на можливості квантових компютерів розв`язати HSP для скінченних абелевих груп.
- Існування ефективного квантового алгоритму[en] для HSP для певних неабелевих груп означало б існування ефективного квантового алгоритму для розв`язку двох важливих задач: ізоморфності графів[en] і деяких задач про пошук найкоротшого вектора (SVP) на ґратках. Точніше кажучи, ефективний квантовий алгоритм для HSP для симетричних груп передбачав би існування квантового алгоритму для ізоморфізму графів[1]. Ефективний квантовий алгоритм для HSP для діедричної групи давав би можливість знайти єдиний найкоротший вектор (unique-SVP) за поліноміальний час від розмірності гратки [2].
Існує ефективний квантовий алгоритм[en] для розв`язку HSP для скінченних абелевих груп за час поліноміальний від . Для довільної групи відомо, що задача прихованої підгрупи розв’язується з задіянням поліноміального числа обчислень оракула[3]. Однак складність схеми, яка реалізує цей алгоритм, може бути експоненційною за , що робить алгоритм неефективним в цілому, адже ефективний алгоритм мусить бути поліноміальним як за кількістю обчислень оракула ,так і за часом виконання. Існування такого алгоритму для довільних груп є відкритим питанням. Квантові алгоритми, поліноміальні в часі, існують для певних підкласів груп, таких як напівпрямі добутки деяких абелевих груп.
Алгоритм для абелевих груп використовує представлення, тобто гомоморфізми з на , які є загальними лінійними групами над кільцем комплексних чисел. Представлення групи є незвідним[en], якщо воно не може бути виражене як прямий добуток двох або більше представлень . Для абелевої групи всі незвідні представлення є характерами, які є представленнями порядку 1; іншими словами, для абелевих груп не існує незвідних представлень вищих порядків.
Квантове перетворення Фур'є[en] може бути означене в термінах , адитивної циклічої групи порядку . Введемо характер тоді квантове перетворення Фур'є має визначення Далі визначаємо стани . Будь-яка абелева група може бути записана як прямий добуток кількох циклічних груп . На квантовому комп’ютері це можна представити як тензорний добуток кількох регістрів розмірів відповідно, а квантове перетворення Фур'є загалом можна представити як .
Множина характерів групи в свою чергу також формують групу , що називається дуальною групою до . Також ми маємо підгрупу розміру , що визначається як На кожній ітерації алгоритму квантова схема видає елемент , що відповідає характеру , і оскільки для всіх , це допомагає визначити, якою є .
Алгоритм наступний:
- Почати з стану , де базові стани лівого реєстру є елементами , а базові стани правого реєстру є елементами .
- Створити суперпозицію базових станів в лівому реєстрі, що відповідає повному станові .
- Задіяти функцію . Після цього загальний стан буде .
- Зробити вимір на правому реєстрі, результатом якого буде для деякого , а стан колапсує до , оскільки має однакове значення для всіх елементів з класу суміжності . Надалі, відкидаючи правий реєстр, маємо стан .
- Застосовуючи квантове перетворення Фур`є, отримуємо стан .
- Цей стан є рівний (деталі нижче) станові , який в свою чергу може бути виміряний для того, щоб отримати інформацію про .
- Повторюємо, допоки не визначимо (або множини генераторів ).
Стани в кроках 5 і 6 є рівними, оскільки: Для встановлення останньої рівності ми використовуємо тотожнсть: яка може бути виведена з ортогональності характерів. Характери групи формують ортогональний базис: Ми вважаємо тривіальними представленнями, які відображають всі елементи в , щоб отримати наступну рівність:Так як сумування здійснюється по , тривіальність має значення тільки тоді, коли також тривіальна по ; тобто, якщо . Таким чином, ми знаємо, що в результаті сумування ми отримаємо , якщо , і отримаємо , якщо .
Кожне вимірювання остаточного стану дасть додаткову інформацію про , так як ми знаємо, що для всіх . , або множина генераторів для , буде знайдено після поліноміальної кількості вимірювань. Розмір множини генераторів буде логарифмічно малим, у порівнянні з розміром . Позначимо через множину генераторів для , тобто, . Розмір підгрупи, згенерованої , подвоюватиметься, коли до до неї додаватиметься новий елемент , тому що і є неперетинними і . Таким чином, розмір множини генераторів задовольняє наступне співвідношенняОтже, множину генераторів для можна отримати у поліноміальний час, навіть якщо є експоненційним у розмірі.
Багато алгоритмів, для яких можна отримати квантове пришвидшення, є прикладами задачі прихованої підгрупи. У таблиці внизу подано важливі прикладі задачі прихованої підгрупи, та зазначено їхню розв'язність.
Задача | Квантовий алгоритм | Абелева? | Поліноміальний час розв'язку? |
---|---|---|---|
Deutsch's problem | Deutsch's algorithm; Deutsch-Jozsa algorithm | Так | Так |
Simon's problem | Simon's algorithm | Так | Так |
Order finding | Shor's order finding algorithm | Так | Так |
Discrete logarithm | Shor's algorithm § Discrete logarithms | Так | Так |
Period finding | Shor's algorithm | Так | Так |
Abelian stabilizer | Kitaev's algorithm[4] | Так | Так |
Graph Isomorphism | None | Ні | Ні |
Shortest vector problem | None | Ні | Ні |
- ↑ 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.