Задача прихованої підгрупи
Задача прихованої підгрупи (з англійської Hidden subgroup problem - HSP) є підходом до розв'язку задач в математиці та теоретичній інформатиці. В рамках підходу можна розглядати задачі факторизації, пошуку дискретного логарифму, ізоморфізму графів[en], та пошуку найкоротшого вектора. Це робить задачу дуже важливою в теорії квантових обчислень, оскільки факторизація за алгоритмом Шора в квантових обчисленнях є прикладом задачі про приховану підгрупу для скінченної абелевої групи, тоді як інші задачі відповідають неабелевим скінченним групам.
Нехай група має підгрупу . Також нехай маємо певну функцію , що відображає елементи групи в елементи деякої множини . Говориться, що функція приховує підгрупу , якщо для всіх тоді і тільки тоді, коли . Іншими словами, є константою на кожному класі суміжності, і водночас є різною для різних класів суміжності підгрупи .
Задача прихованої підгрупи. Нехай є групою, - скінченною множиною, а функція приховує підгрупу . Функція задається оракулом, який використовує бітів. Задача полягає в тому, щоб, використовуючи інформацію, отриману з обчислень через оракул, визначити множину генераторів для підгрупи .
Є також особливий випадок, коли множина також є групою (функція є груповим гомоморфізмом), а підгрупа є ядром функції .
Задача прихованої підгрупи є особливо важливою в теорії квантових комп'ютерів з нижче перерахованих причин.
- Алгоритм Шора факторизації чи пошуку дискретного логарифму (а також кілька його узагальнень) опирається на можливості квантових компютерів розв`язати HSP для скінченних абелевих груп.
- Існування ефективного квантового алгоритму для HSP для певних неабелевих груп означало б існування ефективного квантового алгоритму для розв`язку двох важливих задач: ізоморфності графів[en] і деяких задач про пошук найкоротшого вектора (SVP) на ґратках. Точніше кажучи, ефективний квантовий алгоритм для HSP для симетричних груп передбачав би існування квантового алгоритму для ізоморфізму графів[1]. Ефективний квантовий алгоритм для HSP для діедричної групи давав би можливість знайти єдиний найкоротший вектор (unique-SVP) за поліноміальний час від розмірності гратки [2].
Існує ефективний квантовий алгоритм для розв`язку HSP для скінченних абелевих груп за час поліноміальний від . Для довільної групи відомо, що задача прихованої підгрупи розв’язується з задіянням поліноміального числа обчислень оракула[3]. Однак складність схеми, яка реалізує цей алгоритм, може бути експоненційною за , що робить алгоритм неефективним в цілому, адже ефективний алгоритм мусить бути поліноміальним як за кількістю обчислень оракула ,так і за часом виконання. Існування такого алгоритму для довільних груп є відкритим питанням. Квантові алгоритми, поліноміальні в часі, існують для певних підкласів груп, таких як напівпрямі добутки деяких абелевих груп.
Алгоритм для абелевих груп використовує представлення, тобто гомоморфізми з на , які є загальними лінійними групами над кільцем комплексних чисел. Представлення групи є незвідним[en], якщо воно не може бути виражене як прямий добуток двох або більше представлень . Для абелевої групи всі незвідні представлення є характерами, які є представленнями порядку 1; іншими словами, для абелевих груп не існує незвідних представлень вищих порядків.
Квантове перетворення Фур'є[en] може бути означене в термінах , адитивної циклічої групи порядку . Введемо характер тоді квантове перетворення Фур'є має визначення Далі визначаємо стани . Будь-яка абелева група може бути записана як прямий добуток кількох циклічних груп . На квантовому комп’ютері це можна представити як тензорний добуток кількох регістрів розмірів відповідно, а квантове перетворення Фур'є загалом можна представити як .
Множина характерів групи в свою чергу також формують групу , що називається дуальною групою до . Також ми маємо підгрупу розміру , що визначається як На кожній ітерації алгоритму квантова схема видає елемент , що відповідає характеру , і оскільки для всіх , це допомагає визначити, якою є .
Алгоритм наступний:
- Почати з стану , де базові стани лівого реєстру є елементами , а базові стани правого реєстру є елементами .
- Створити суперпозицію базових станів в лівому реєстрі, що відповідає повному станові .
- Задіяти функцію . Після цього загальний стан буде .
- Зробити вимір на правому реєстрі, результатом якого буде для деякого , а стан колапсує до , оскільки має однакове значення для всіх елементів з класу суміжності . Надалі, відкидаючи правий реєстр, маємо стан .
- Застосовуючи квантове перетворення Фур`є, отримуємо стан .
- Цей стан є рівний (деталі нижче) станові , який в свою чергу може бути виміряний для того, щоб отримати інформацію про .
- Повторюємо, допоки не визначимо (або множини генераторів ).
Стани в кроках 5 і 6 є рівними, оскільки: Для встановлення останньої рівності ми використовуємо тотожнсть: яка може бути виведена з ортогональності характерів. Характери групи формують ортогональний базис: Ми вважаємо тривіальними представленнями, які відображають всі елементи в , щоб отримати наступну рівність:Так як сумування здійснюється по , тривіальність має значення тільки тоді, коли також тривіальна по ; тобто, якщо . Таким чином, ми знаємо, що в результаті сумування ми отримаємо , якщо , і отримаємо , якщо .
Кожне вимірювання остаточного стану дасть додаткову інформацію про , так як ми знаємо, що для всіх . , або множина генераторів для , буде знайдено після поліноміальної кількості вимірювань. Розмір множини генераторів буде логарифмічно малим, у порівнянні з розміром . Позначимо через множину генераторів для , тобто, . Розмір підгрупи, згенерованої , подвоюватиметься, коли до до неї додаватиметься новий елемент , тому що і є неперетинними і . Таким чином, розмір множини генераторів задовольняє наступне співвідношенняОтже, множину генераторів для можна отримати у поліноміальний час, навіть якщо є експоненційним у розмірі.
Багато алгоритмів, для яких можна отримати квантове пришвидшення, є прикладами задачі прихованої підгрупи. У таблиці внизу подано важливі прикладі задачі прихованої підгрупи, та зазначено їхню розв'язність.
Задача | Квантовий алгоритм | Абелева? | Поліноміальний час розв'язання? |
---|---|---|---|
Задача Дойча | Алгоритм Дойча; алгоритм Дойча — Йожи | Так | Так |
Задача Саймона[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.
- 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
|