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

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

ред.

Нехай група   має підгрупу  . Також нехай маємо певну функцію  , що відображає елементи групи   в елементи деякої множини  . Говориться, що функція   приховує підгрупу  , якщо для всіх   тоді і тільки тоді, коли  . Іншими словами,   є константою на кожному класі суміжності, і водночас є різною для різних класів суміжності підгрупи  .

Задача прихованої підгрупи. Нехай   є групою,   - скінченною множиною, а функція   приховує підгрупу  . Функція   задається оракулом, який використовує   бітів. Задача полягає в тому, щоб, використовуючи інформацію, отриману з обчислень   через оракул, визначити множину генераторів для підгрупи  .

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

Мотивація

ред.

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

Алгоритми

ред.

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

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

ред.

Алгоритм для абелевих груп використовує представлення, тобто гомоморфізми з   на  , які є загальними лінійними групами над кільцем комплексних чисел. Представлення групи   є незвідним[en], якщо воно не може бути виражене як прямий добуток двох або більше представлень  . Для абелевої групи всі незвідні представлення є характерами, які є представленнями порядку 1; іншими словами, для абелевих груп не існує незвідних представлень вищих порядків.

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

ред.

Квантове перетворення Фур'є[en] може бути означене в термінах  , адитивної циклічої групи порядку  . Введемо характер  тоді квантове перетворення Фур'є має визначення   Далі визначаємо стани  . Будь-яка абелева група може бути записана як прямий добуток кількох циклічних груп  . На квантовому комп’ютері це можна представити як тензорний добуток кількох регістрів розмірів   відповідно, а квантове перетворення Фур'є загалом можна представити як  .

Процедура

ред.

Множина характерів групи   в свою чергу також формують групу  , що називається дуальною групою до  . Також ми маємо підгрупу   розміру   , що визначається як   На кожній ітерації алгоритму квантова схема видає елемент  , що відповідає характеру  , і оскільки   для всіх  , це допомагає визначити, якою є  .

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

  1. Почати з стану  , де базові стани лівого реєстру є елементами  , а базові стани правого реєстру є елементами  .
  2. Створити суперпозицію базових станів   в лівому реєстрі, що відповідає повному станові  .
  3. Задіяти функцію  . Після цього загальний стан буде  .
  4. Зробити вимір на правому реєстрі, результатом якого буде   для деякого  , а стан колапсує до   , оскільки   має однакове значення для всіх елементів з класу суміжності  . Надалі, відкидаючи правий реєстр, маємо стан  .
  5. Застосовуючи квантове перетворення Фур`є, отримуємо стан  .
  6. Цей стан є рівний (деталі нижче) станові  , який в свою чергу може бути виміряний для того, щоб отримати інформацію про  .
  7. Повторюємо, допоки не визначимо   (або множини генераторів  ).

Стани в кроках 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 Ні Ні

Див. також

ред.

Посилання

ред.
  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.

Зовнішні джерела

ред.

Шаблон:Quantum Computing