Квантовий пошук за допомогою алгоритму Гровера

    Сьогодні слідом за першими квантовими алгоритмами, які ми вже розглянули (див. алгоритм Дойча і алгоритм Дойча-Йожі — якщо хтось ще не читав ці статті, то пропоную попередньо з ними ознайомитися, оскільки без цього виклад може здатися кілька туманним), пропоную вивчити алгоритм Гровера для неструктуріруемого квантового пошуку. Цей алгоритм був розроблений американським математиком ловом Гровером в 1996 році (вже набагато пізніше того, як модель квантових обчислень стала в моді). Цей алгоритм використовує властивість квантової інтерференції для того, щоб вирішувати вкрай нагальну задачу з пошуку значення деякого параметра, на якому задана функція видає певний результат.
 
Даний алгоритм не вказує експоненціального виграшу для завдання порівняно з класичною обчислювальної моделлю, але для більших значень виграш (квадратичний) є суттєвим. Однак це загальний алгоритм для вирішення досить узагальненої задачі, і доведено, що кращого результату в рамках моделі квантових обчислень добитися не можна. У більш приватних алгоритмах це можливо.
 
Ця стаття є продовженням в циклі статей за моделлю квантових обчислень, тому якщо почати читати її без ознайомлення з попередніми статтями циклу, щось може здатися незрозумілим. Так що читача, який вперше набрів на ці мої замітки, я відправляю до перших статтями: 1 , 2 , 3 , 4 .
 
Отже, якщо хтось зацікавився, то як звичайно ласкаво просимо під кат.
 
  напівформального опис алгоритму Завдання формулюється таким чином. Нехай є бінарна функція від n бінарних же аргументів, яка приймає значення 1 тільки на одному з них (а на інших 2 n — 1 значеннях, стало бути, приймає 0). Необхідно знайти це значення вхідних аргументів, маючи тільки функцію (для квантових обчислень дану у вигляді оракула, як це годиться).
 
Природно, що в класичному варіанті в середньому необхідно переглянути 2 n / 2 варіантів вхідних значень, оскільки в кращому випадку вдасться знайти «щасливий номер» з першої спроби, а в гіршому буде потрібно перебрати всі 2 n варіантів. А ось алгоритм Гровера дозволяє зробити це за π / 4 √ (2 n ) звернень до оракула. Зрозуміло, що при збільшенні числа вхідних кубітів n різниця в продуктивності стає кардинальної. Однак, як вже написано вище, суперполіноміального збільшення продуктивності тут немає і не передбачається.
 
За своєю суттю це завдання неструктурованого пошуку. Якщо є невпорядкований набір даних («стіг сіна») і потрібно знайти в ньому якийсь один елемент, що задовольняє специфічному вимогу (цей елемент один такий — «голка»), алгоритм Гровера допоможе, оскільки альтернативою є класичний перебір варіантів. Наприклад, якщо розглянути аналогію з базою даних автомобілістів з іменами, впорядкованими за алфавітом (і нехай у ній буде взаємно однозначна відповідність між прізвищем і номером автомобіля), то впорядкованим пошуком є ​​пошук номера автомобіля на прізвище (робиться, наприклад, методом дихотомії, якщо немає індексу). А неврегульованим пошуком є ​​зворотна завдання — пошук прізвища за номером автомобіля. У даній аналогії оракулом є функція (перетворена відповідним чином), яка за прізвищем повертає номер автомобіля. Тоді ця задача зводиться до задачі Гровера за допомогою кодування прізвищ у бінарне представлення, а сама функція повертає відповідь на питання «Чи володіє даний автомобіліст N автомобілем X ?», Де N — вхідний параметр функції, а X — параметр алгоритму, як би «зашивали» всередину оракула при його побудові. Відповідно, цей оракул повертає значення 1 ("так") тільки єдино для тієї прізвища, навпроти якої в базі даних коштує шуканий номер автомобіля.
 
Алгоритм Гровера складається з наступних кроків:
 
 
     
Ініціалізація початкового стану . Необхідно підготувати равновероятностних суперпозицію станів всіх вхідних кубітів. Це робиться за допомогою застосування відповідного гейта Адамара, який дорівнює тензорному твору n унарних гейтов Адамара один на одного.
 Застосування ітерації Гровера . Дана ітерація складається з послідовного застосування двох гейтов — оракула і так званого гейта дифузії Гровера (обидва будуть детально розглянуті нижче). Ця ітерація здійснюється √ (2 n ) разів.
 Вимірювання . Після застосування ітерації Гровера достатню кількість разів необхідно виміряти вхідний регістр кубітів. З дуже високою ймовірністю виміряне значення дасть вказівку на шуканий параметр. Якщо необхідно збільшити достовірність відповіді, то алгоритм прогоняется кілька разів і обчислюється сукупна ймовірність правильної відповіді.
 
Квантова схема цього алгоритму, само собою зрозуміло, залежить від розміру вхідних даних, оскільки від цього безпосередньо залежить кількість застосувань ітерації Гровера. У загальному вигляді така схема може бути зображена за допомогою діаграми, показаної на наступному малюнку.
  
 
Тепер звернемо свою увагу на оракул і гейт дифузії, оскільки вони є серцем алгоритму. Оракул в даному випадку повинен бути побудований не зовсім стандартним способом. Якщо згадати процес перетворення класичної бінарної функції в оракул, то можна зрозуміти, що приймаючи на вхід два квантових реєстру (x , y ) , він повинен видавати на виході пару (x , y f (x )) . Однак у випадку алгоритму Гровера оракул повинен інвертувати фазу у того квантового стану, який відповідає згаданої значенням x (нагадаємо, що ми за заданим значенням f (x ) шукаємо x , тобто вирішуємо зворотну задачу). Це означає, що оракул повинен на виході видавати значення (-1) f (x )
|x>
. Фазовий коефіцієнт (-1) f (x ) встановлений саме таким, оскільки f (x ) = 1 тоді і тільки тоді, коли функція отримує на вхід шукане значення x , і саме в цьому випадку фазовий коефіцієнт стає дорівнює -1. Іншими словами, оракул U w діє таким чином:
 
 
     
U w
|w>
= —
|w>

 U w
|x>
=
|x>
, x w
 
Гейт дифузії, в свою чергу, являє собою поєднання трьох гейтов, два з яких стандартні — це многокубітовие гейти Адамара. А от між ними знаходиться спеціальний гейт, який, по суті, здійснює переворот кубітів щодо середнього значення. Його представлення у вигляді аналітичної формули (2
|0
n
><0
n
|
— I n )
кілька затуманює суть, оскільки його матричне уявлення просто — у верхньому лівому кутку матриці стоїть значення 1, в інших позиціях головної діагоналі стоїть значення -1, а в інших місцях стоять 0:
 
 
Але того ж самого можна досягти, якщо в вищенаведеної формулою замінити
|0
n
>
на
|+
n
>
, і тоді не треба застосовувати гейти Адамара до і після застосування цього спеціального гейта. Так що оператор дифузії Гровера буде виглядати як:
 
 (2
|+
n
><+
n
|
— I n )

 
Іншими словами, з такою формою оператора дифузії квантова схема алгоритму Гровера стає наступною:
 
 
 Програмна реалізація Щоб не бути голослівним, можна розглянути цей алгоритм у його реалізації на мові програмування Haskell. Для цього продовжимо користуватися тим набором функцій, які вже тягнуться в цій серії публікацій зі статті в статтю. Цей набір дозволить «заглянути» в надра алгоритму (чого не дозволив би, наприклад, мова Quipper, оскільки надає дуже високорівневі засоби генерації квантових схем).
 
Але перед написанням коду нам знову треба трохи зайнятися квантової схемотехнікою , оскільки треба спроектувати оракул у вигляді гейта. Для різноманітності (і зміцнення навичок квантової системотехніки) можна розглянути функцію від трьох змінних, тобто оракул отримуватиме на вхід 3 кубіта (і, природно, на виході теж буде 3 кубіта). Розглянемо таку задачу:
 
 f (x 1 , x 2 , x 3 ) = x 1 & x 2 & x 3
 
Ця функція приймає значення 1 тільки на одному з восьми варіантів вхідних значень, що і потрібно для алгоритму Гровера. Немає ніякої різниці, яку саме з восьми можливих функцій такого виду на трьох змінних розглядати, але ця функція більш проста з технічної точки зору. Як зазвичай для побудови оракула можна скористатися таблицею.
 
                                                                 
X 1 X 2 X 3 f (X) (-1) f (X)
0 0 0 0 1
0 0 1 0 1
0 1 0 0 1
0 1 1 0 1
1 0 0 0 1
1 0 1 0 1
1 1 0 0 1
1 1 1 1 -1
Цій таблиці відповідає наступна матриця 8 × 8:
 
 
Оскільки ми зараз починаємо реалізацію більш серйозних речей, ніж розглядалися в попередніх статтях, нам треба додати деяку кількість корисних для конструювання оракулів, гейтов та іншого, службових функцій. Зокрема, необхідно додати функцію, яка вже іспользоваласть в операторі тензорного твори:
 
 
groups :: Int -> [a] -> [[a]]
groups i s | null s = []
           | otherwise  = let (h, t) = splitAt i s
                          in   h : groups i t

Тепер перейдемо до визначення нових гейтов та операторів над ними. У відповідності з описом алгоритму Гровера, нам буде потрібно оператор віднімання матриць один з одного, а також функція для створення гейтов для декількох кубітів на основі гейта для одного кубіта. Принаймні, ця функція буде потрібно для тензорного твори гейтов I і H, щоб мати можливість застосовувати їх до квантових регістрів, що складається з декількох кубітів.
 
Для початку визначимо простий оператор для отримання різниці матриць:
 
 
(<->) :: Num a => Matrix a -> Matrix a -> Matrix a
m1 <-> m2 = zipWith (zipWith (-)) m1 m2

Ну і для порядку визначимо такий же оператор для складання матриць:
 
 
(<+>) :: Num a => Matrix a -> Matrix a -> Matrix a
m1 <+> m2 = zipWith (zipWith (+)) m1 m2

Тут знову необхідно прийняти до уваги те, що розробник сам повинен стежити за розмірністю своїх векторів і матриць.
 
Тепер перейдемо до функцій для генерації гейтов. Поки були реалізовані лише функції для представлення гейтов, обробних один або максимум два кубіта. Проте за допомогою оператора тензорного твори та функції
entangle
можна створювати функції для представлення гейтов, обробних довільну кількість кубітів. Наприклад, ось так виглядає узагальнена функція, яка перетворює заданий однокубітовий гейт в той же гейт, що обробляє задану кількість кубітів:
 
 
gateN :: Matrix (Complex Double)
      -> Int -> Matrix (Complex Double)
gateN g n = foldl1 (<++>) $ replicate n g

Дуже просто і витончено. За допомогою стандартної функції
replicate
створюється список з заданої кількості однокубітових гейтов (при цьому розробник сам повинен стежити за тим, що сюди передаються саме однокубітовие гейти, хоча функція цілком буде працювати і з многокубітовимі). Далі цей список згортається за допомогою оператора тензорного твори (
<++>
). А ось так ця функція використовується:
 
 
gateIn :: Int -> Matrix (Complex Double)
gateIn = gateN gateI

gateHn :: Int -> Matrix (Complex Double)
gateHn = gateN gateH

Як видно, перша функція формує тотожне перетворення для заданої кількості кубітів, а другий — перетворення Адамара знову ж для заданої кількості кубітів. Ці два многокубітових гейта дуже важливі в моделі квантових обчислень і часто використовуються у всіляких квантових схемах.
 
Нарешті можна звернутися до реалізації самого алгоритму Гровера. Почнемо з оракула:
 
 
oracle :: Matrix (Complex Double)
oracle = matrixToComplex [[1, 0, 0, 0, 0, 0, 0,  0],
                          [0, 1, 0, 0, 0, 0, 0,  0],
                          [0, 0, 1, 0, 0, 0, 0,  0],
                          [0, 0, 0, 1, 0, 0, 0,  0],
                          [0, 0, 0, 0, 1, 0, 0,  0],
                          [0, 0, 0, 0, 0, 1, 0,  0],
                          [0, 0, 0, 0, 0, 0, 1,  0],
                          [0, 0, 0, 0, 0, 0, 0, -1]]

Тут ніякої складності немає, необхідно просто закодувати матрицю. Звичайно, вдумливий читач вже давно самостійно розширив представлений набір функцій і визначив функцію вищого порядку для генерації подібних оракулів (і багатьох інших). Але ми поки будемо діяти по-старому.
 
Тепер реалізуємо функцію для представлення оператора дифузії Гровера. З урахуванням тих міркувань щодо зміни базису (використовувати кубіт в квантовому стані
|+>
замість
|0>
), її визначення буде вкрай простим:
 
 
diffusion :: Matrix (Complex Double)
diffusion = 2 <*> (qubitPlus3 |><| qubitPlus3)
              <-> gateIn 3
  where
    qubitPlus3 = toVector $
                   foldl1 entangle $
                   replicate 3 qubitPlus

Беремо три кубіта в стані
|+>
(
qubitPlus
), робимо з них список кубітів і звертаємо його за допомогою функції
entangle
. Далі переводимо отриманий квантовий регістр в векторне подання. Так виходить локальне визначення
qubitPlus3
.
 
Потім цей квантовий регістр
qubitPlus3
векторно множимо сам на себе, в результаті чого виходить матриця
|+><+|
, яка далі множиться на 2. Ну і з результату віднімається одинична матриця, підготовлена ​​для трьох кубітів (тобто розміру 8 × 8). За допомогою реалізованих раніше операторів написання таких функцій стає справою дуже приємним.
 
Що ж, тепер залишилося реалізувати сам алгоритм Гровера. Ось визначення функції для трьох кубітів:
 
 
grover :: Matrix (Complex Double) -> IO String
grover f = initial |> gateHn 3
                   |> f |> diffusion
                   |> f |> diffusion
                   >>> (measure . fromVector 3)
  where
    initial = toVector $
                foldr entangle qubitZero $
                replicate 2 qubitZero

У локальному зразку
initial
знову готується початковий стан, яке, якщо придивитися, одно
|000>
. Далі воно направляється в гейт Адамара для трьох кубітів, в результаті чого виходить равновероятностних суперпозиція з восьми квантових станів, які можуть бути на трьох кубітах. Потім два рази прогоняется цикл Гровера, оскільки 2 ≈ √ 2 3 . Після цього здійснюється вимір.
 
Що буде, якщо додати в цю квантову схему третій цикл Гровера? Все просто — результати стануть гірше. Читачеві пропонується самостійно подумати над відповіддю на запитання «Чому?».
 
Оскільки алгоритм Гровера є імовірнісним, він видає правильну відповідь тільки з якоюсь дуже високою ймовірністю. Це означає, що часом при запуску функції
grover
ми будемо отримувати неправильну відповідь, тому в даному випадку пропонується оцінити ймовірність отримання правильної відповіді. Реалізуємо таку функцію:
 
 
main f n = do l <- replicateM n $ grover f
              return $
                map (length &&& head) $ group $ sort l

Вона застосовує алгоритм Гровера для заданого оракула задану кількість разів, а результатом її роботи є гістограма результатів алгоритму (тобто список пар виду (частота появи, результат)). Далі ця функція була запущена мільйон разів, у результаті чого був побудований ось такий графік:
  
 
Правильний результат був отриманий приблизно в 94.5% випадків, а інші результати мають частоту приблизно в 0.78% . Цього цілком достатньо для того, щоб мати можливість запустити алгоритм Гровера три рази і вибрати з цих трьох запусків результат, повторившийся принаймні двічі.
 
Вдумливий читач до цього часу вже повинен був задатися питанням, а що якщо оракул повертатиме фазу -1 на декількох вхідних даних, а не на одному? У цьому випадку алгоритм Гровера теж працює, як це не дивно (хоча нічого дивного в цьому якраз і немає, якщо розглянути послідовність множень матриць). Однак для знаходження однієї правильної відповіді з безлічі потрібно набагато менше ітерацій.
 
Нехай l — кількість значень вхідних параметрів, на яких функція приймає значення 1 (тобто оракул повертає фазу -1). Тоді для знаходження одного правильного значення з великою ймовірністю вимагається √ 2 n / l ) ітерацій Гровера. Це можна продемонструвати таким кодом:
 
 
oracle' :: Matrix (Complex Double)
oracle' = matrixToComplex [[1,  0, 0, 0,  0, 0, 0,  0],
                           [0, -1, 0, 0,  0, 0, 0,  0],
                           [0,  0, 1, 0,  0, 0, 0,  0],
                           [0,  0, 0, 1,  0, 0, 0,  0],
                           [0,  0, 0, 0, -1, 0, 0,  0],
                           [0,  0, 0, 0,  0, 1, 0,  0],
                           [0,  0, 0, 0,  0, 0, 1,  0],
                           [0,  0, 0, 0,  0, 0, 0, -1]]

Якщо запустити функцію
main
з цим оракулом і дати можливість виконати побудову гістограми на мільйоні запусках, то буде явлена ​​приблизно наступна діаграма:
  
 
Що це? Правильні відповіді отримали найменшу частоту? А все правильно, оскільки зараз функція
grover
, яка викликається з функції
main
, виконує дві ітерації Гровера, а для оракула з трьома правильними відповідями необхідна одна ітерація. Як тільки виконано більше ітерацій, ніж потрібно за алгоритмом, ситуація перевертається з ніг на голову (оскільки у нас відбувається переворот щодо середнього). Але в даному конкретному випадку однієї ітерації так само недостатньо, оскільки частотні ймовірності правильних і неправильних відповідей будуть досить близькі один до одного (це резонно, оскільки була зроблена тільки одна ітерація).
 
Загалом, як показує цей приклад, розробник при використанні алгоритму Гровера завжди повинен уважно стежити за кількістю ітерацій і не допускати перевороту ситуації в протилежну сторону.

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

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

Мої попередні статті по темі квантових обчислень:

Слово мале про оборотних обчисленнях
Реалізація алгоритму Дойча на мові Haskell
Квантова схемотехніка: деякі прийоми і техніки
Розвертаємо мову квантового програмування Quipper
Продовжуємо вивчати квантові обчислення: алгоритм Дойча-Йожі


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.