Є дві функції

Привіт

Є дві булеві функції nаргументів, одна — константна, інша — збалансована. На яку сам сядеш, на яку фронтендера посадиш? Ось тільки функції невідомі, а викликати їх дозволяється лише один раз.

Якщо не знаєш, як вирішити подібну задачу, ласкаво просимо під кат. Там я розповім про квантові алгоритми і покажу як їх емулювати на самому народному мовою — на Python.

i've come to talk with you again
Давайте трохи більш формально поставимо задачу про двох функціях. Нехай дана булева функція f: \{0, 1\}^n \to \{0, 1\}і про неї апріорно відомо, що вона або константна, тобто для будь-якого з своїх аргументів завжди повертає або 0, або 1, або збалансована, тобто рівно на половині своїх аргументів повертає 0, а рівно на половині 1. Потрібно визначити, константна функція або збалансована. При цьому вважається, що час виклику функції набагато більше будь-яких інших операцій, тому складність алгоритму визначається кількістю викликів функції.

hard_choice

Приклад:
  1. f(x_1, x_2) = x_1 \otimes x_2збалансована:








    x_1 x_2 f 0 0 0 0 1 1 1 0 1 1 1 0
  2. f(x_1, x_2) = x_1 \vee x_2 \vee (\neg x_1 \wedge \neg x_2)константна:








    x_1 x_2 f 0 0 1 0 1 1 1 0 1 1 1 1
  3. f(x_1, x_2) = x_1 \wedge x_2ні збалансована, ні константна:








    x_1 x_2 f 0 0 0 0 1 0 1 0 0 1 1 1
Завдання, безумовно, штучна і навряд чи коли-небудь кому-небудь зустрінеться на практиці, однак вона — класичний провідник в чудовий новий світ квантових обчислень, а порушувати традиції я не насмілюся.

Класичне детерміноване рішення
bruteforce

Давайте, для початку, вирішимо завдання у класичній моделі обчислень. Для цього в гіршому випадку потрібно викликати функцію на 2^{n-1}+1аргументах: рівно на половині і ще одному. Якщо всі обчислені значення однакові, то функція, очевидно, константна. Якщо існують хоча б два різних результату, функція збалансована. Складність детермінованого алгоритму экспоненциальна і становить O(2^{n-1} + 1).

Алгоритм на Python:

from itertools import product, starmap, tee

def попарно(xs):
a, b = tee(xs)
next(b, None)
return zip(a, b)

def is_constant(f, n):
m = 2 ** (n - 1)

for i, (x, y) in enumerate(pairwise(starmap(f, product({0, 1}, repeat=n)))):
if i > m:
break

if x != y:
return False

return True

Класичне ймовірнісний рішення
rasta

А що, якщо замість половини аргументів ми перевіримо менша їх кількість і винесемо вердикт? Точним відповідь вже не буде, але з якою ймовірністю ми помилимося? Припустимо, ми вирахували функцію на k < 2^{n-1} + 1аргументах. Якщо серед значень функції є два різних, то все просто — функція збалансована. Інакше, ми оголошуємо її константною з імовірністю p(k) < 1. Припустимо, що ми помилилися і функція насправді збалансована. Порахуємо ймовірність помилки 1 - p(k). Якщо ми вибирали аргументи рівномірно, то ймовірність того, що два поспіль йдуть значення функції однакові, дорівнює 1/2, а імовірність же зустріти kоднакових поспіль йдуть значень дорівнює 1/2^k. Таким чином:

1 - p(k) = \frac{1}{2^k},
p(k) = 1 - \frac{1}{2^k}.
Зворотна функція:

k(p) = \log_2{\frac{1}{1 - p}}.
При фіксованому pскладність класичного імовірнісного алгоритму константна і дорівнює O(\log_2{\frac{1}{1 - p})}.Щоб бути впевненим у відповіді на 99.99%, необхідно викликати функцію всього 14 разів.

Алгоритм на Python:

import random
from itertools import product, starmap, tee


def попарно(xs):
a, b = tee(xs)
next(b, None)
return zip(a, b)


def is_constant(f, n, k=14):
xs = list(product({0, 1}, repeat=n))
random.shuffle(xs)
xs = xs [k]

for x, y in попарно(starmap(f, xs)):
if x != y:
return False

return True

А якщо я скажу вам, що існує константна детермининированное рішення зі складністю O(1), дозволяє викликати функцію всього один раз?

Правда, перш ніж його розглянути, доведеться відволіктися…

Because a vision softly creeping
Міфи
Раніше ніж почати, хотілося б обговорити кілька розхожих міфів, пов'язаних з квантовими обчисленнями:
  1. Квантові алгоритми — це складно.
    difficult

    Так, їх складно синтезувати, бо потрібно для цього математичне уяву і проникливість. Їх складно реалізовувати на справжніх квантових комп'ютерах: для цього необхідно досконало знати фізику і щодня допізна засиджуватися в лабараторії на кафедрі. Але що точно не вимагає ніяких особливих знань і неймовірної кількості старанності, так це їх розуміння. Я стверджую, що кожен може розуміти квантові алгоритми: вони спираються на вкрай просту математику, доступну кожному першокурснику. Все, що від вас потрібно — лише трохи часу на вивчення.
  2. Вже існують квантові комп'ютери на тисячі кубітів від D-Wave
    Ні, це не справжні квантові комп'ютери.
  3. Не існує жодного справжнього квантового комп'ютера
    Ні, існують. В лабораторних умовах і мають вони лише кількома кубітами.
  4. Квантові комп'ютери дозволять вирішувати задачі, недоступні раніше
    Ні, безліч завдань, вычислимых у класичної і квантової моделі, збігаються. Квантові обчислення дозволяють лише знизити складність невеликого підмножини цих завдань.
  5. На квантовому комп'ютері Crysis на максималках буде літати
    wat

    За винятком деякого підмножини задач, які квантова модель обчислень здатна прискорити, інші можуть бути вирішені лише емуляцією класичного комп'ютера. Що, як ви розумієте, дуже повільно. Crysis, швидше за все, буде лагают.
  6. Квантовий комп'ютер — це чорна коробочка з входом і виходом, заглянувши в яку можна все зіпсувати
    blackbox

    Якщо вам 12 років, така аналогія згодиться. В будь-якому іншому випадку вона, як і всі інші аналогії з коробками, котами, лупами і «зв'язаними» нитками електронами, так активно просувні у всіх науково-популярних джерелах, лише заплутує, створює ілюзію помилкового розуміння і скоріше шкідлива, ніж корисна. Відмовтеся від цих аналогій.


Навіщо?
Навіщо прикладного математику (програмісту) вміти розбиратися в квантових алгоритмах на прикладному рівні? Тут все просто, я готовий запропонувати вам два доводи:
  1. Для саморозвитку. Чому б і ні?
  2. Вони вже йдуть. Вони, квантові комп'ютери. Вони вже поруч. Моргнути не встигнете, як парочка з'явиться в серверній вашої компанії, а ще через кілька років і у вигляді співпроцесора у вашому ноутбуці. І бігти вже нікуди. Доведеться під них програмувати, викликати квантові співпрограми. А без розуміння це робити складно, погодьтеся.
Left its seeds while I was sleeping
Базової складової квантових обчислень є квантова система. Квантова система — фізична система, всі дії якої можна порівняти за величиною з постійної Планка. Це визначення і той факт, що квантові системи підкоряються законам матричної механіки — всі знання, які нам потрібні з фізики. Далі — тільки математика.

loldontinterrupt

Як і будь-яка інша фізична система, квантова система може перебувати в певному стані. Всі можливі стану квантової системи утворюють гільбертів простір \mathcal{H}над полем комплексних чисел. Сподіваюся, з концепцією комплексних чисел читач знайомий — їх розуміння необхідно скрізь надалі. Якщо ні, раджу познайомитися і повертатися. Гільбертів простір є повним нормативним метричними лінійним простором з нормою \Vert x \Vert = \sqrt{(x, x)}, де (x, y)— скалярний добуток. По порядку з кінця:
  1. Лінійне (векторне) простір — безліч елементів Xз введеними на ньому операціями додавання елементів <img src=«tex.s2cms.ru/svg/x%20%2B%20y» alt=x + y"/> і множення x \cdot \lambdaна елемент поля K(в нашому випадку поля комплексних чисел). Ці операції повинні бути замкнені (результат повинен належати множині X) і повинні виконуватися 8 аксіом. Переглянути повний їх список, а так само ознайомитися детальніше з лінійними просторами рекомендую тут.
  2. метричному просторі Xдля будь-яких елементів x, y \in Xвизначено відстань \rho(x, y), яке задовольняє вимогам (аксіомам метричного
    простору):
    • \rho(x, y) \geqslant 0, при цьому \rho(x, y) = 0тоді і тільки тоді, коли xyзбігаються;
    • \rho(x, y) = \rho(y, x);
    • \rho(x, y) \leqslant \rho(x, z) + \rho(z, y)— нерівність трикутника.
  3. нормованому просторі Xдля будь-якого елемента x \in Xіснує дійсне число \Vert x \Vert \in R, зване його нормою і удовлетворяюещее, знову ж таки, трьом аксіомам:


Введемо в отриманому просторі скалярний твір, що задовольняє звичайним вимогам скалярного твори, введемо норму як показано вище і отримаємо простір Гільберта.

hilbertalmost

Обговоримо ще поняття спряженого простору. Простором, спряженим до \mathcal{H}називається простір \mathcal{H^*}лінійних операторів над \mathcal{H}. Що таке лінійний оператор? Можна думати про нього як про узагальнення лінійної функції: для линейноного оператора A: \mathcal{H} \to Yповинно виконуватися:

A (\lambda_1 x_1 + \lambda_2 x_2) = \lambda_1 A x_1 + \lambda_2 A x_2,
де x_1, x_2 \in \mathcal{H}\lambda_1, \lambda_2 \in K. (Насправді, ще і його норма повинна бути обмежена на одиничної гиперсфере, але, щоб уникнути ще десятка громіздких визначень, обмежимося таким інтуїтивним уявленням.)

У квантової інформатики з історичних причин використовуються позначення Дірака. Вони можуть здаватися необґрунтовано громіздкими і химерними, але вони — стандарт, якого варто дотримуватися. В цих позначеннях елемент нашого гильбертова простору, що описує стан системи, називається кет-вектором і позначається

\left| \psi \right\rangle \in \mathcal{H}.
Бра-вектором називається елемент спряженого простору

\langle\left \phi \right| \in \mathcal{H^*},
такий що

(\langle\left \phi \right|) \left| \psi \right\rangle = (\left| \phi \right\rangle, \left| \psi \right\rangle) = \langle\left \phi | \psi \right\rangle.
Тобто, це лінійний оператор, застосування якого до нашого вектору стану аналогічно скалярному добутку на відповідний йому елемент «оригінального» гильбертова простору. Для зручності запису при застосуванні бра-вектора до кет-вектору дві вертикальні лінії зливаються в одну, що показано у вираженні вище.

Тепер можна зробити важливу поправку: квантову систему може описувати не будь-гільбертів простір, а лише таке, що

\langle\left \psi | \psi \right\rangle = 1\; \forall \left| \psi \right\rangle \in \mathcal{H},
тобто норма кожного елемента дорівнює одиниці.

Якщо ми виділимо в нашому гільбертовому просторі станів деякий базис \{\left| e_i \right\rangle\}_{i=1}^m \subset \mathcal{H}, то будь-кет-вектор зможемо записати у вигляді вектора комплексних чисел — коефіцієнтів його розкладання з цього базису:

\left| \psi \right\rangle = \sum_{i=1}^m{\langle\left e_i | \psi \right\rangle \left| e_i \right\rangle},
при цьому матрична механіка говорить нам, що квадрати модулів коефіцієнтів розкладання \vert \langle\left e_i | \psi \right\rangle \vert^2фізично означають ймовірності знаходження квантової системи у відповідному базисному стані при вимірюванні в цьому базисі.

Ось воно — перше і основне властивість квантових систем, яке так часто мусолять в популярних статтях: якщо виміряти систему в деякому базисі, то вона перейде в один з базисних станів, втратить інформацію і не зможе повернутися назад. Ось тільки при прочитанні складається відчуття, що все відбувається абсолютно випадково і вплинути на це ніяк не можна, тоді як насправді ймовірності переходу відомі заздалегідь і, більш того, залежать від вимірювального базису. Якби все було так випадково, як нам подають, детерменированные квантові алгоритми були б неможливі.

Якщо ми можемо уявити елемент Гильбертова простору вектором при деякому фіксованому базисі, то лінійний оператор над цим простором ми можемо представити матрицею.

Дійсно,

A \left| \psi \right\rangle = \sum_{i=1}^m{\langle\left e_i | \psi \right\rangle A \left| e_i \right\rangle}
еквівалентно

A \left| \psi \right\rangle = \hat{A} \hat{\psi},
де \hat{A}виходить почерговим застосуванням оператора Aдо базисним елементам \left| e_i \right\rangleі виписуванням одержані елементів по рядках, а \hat{\psi}— розкладання \left| \psi \right\rangleу цьому ж базисі.

Нехай оператор Aпредставляється матрицею

A = \begin{pmatrix}
a_{11} &amp;amp; a_{12} &amp;amp; a_{13} &amp;amp; \dots &amp;amp; a_{1m} \\
a_{21} &amp;amp; a_{22} &amp;amp; a_{23} &amp;amp; \dots &amp;amp; a_{2m} \\
\vdots &amp;amp; \vdots &amp;amp; \vdots &amp;amp; \ddots &amp;amp; \vdots \\
a_{m1} &amp;amp; a_{m2} &amp;amp; a_{m3} &amp;amp; \dots &amp;amp; a_{mm}
\end{pmatrix}.
Елементи матриці — комплексні числа. Давайте візьмемо кожен елемент і замінимо його комплексно зв'язаних (комплексно спряженим до <img src=»tex.s2cms.ru/svg/x%20%2B%20iy" alt=x + iy"/> називається число x - iy) і, заодно, транспонируем всю матрицю:

A^\dagger = \overline{A}^T = \begin{pmatrix}
\overline{a_{11}} &amp;amp; \overline{a_{21}} &amp;amp; \overline{a_{31}} &amp;amp; \dots &amp;amp; \overline{a_{m1}} \\
\overline{a_{12}} &amp;amp; \overline{a_{22}} &amp;amp; \overline{a_{32}} &amp;amp; \dots &amp;amp; \overline{a_{m2}} \\
\vdots &amp;amp; \vdots &amp;amp; \vdots &amp;amp; \ddots &amp;amp; \vdots \\
\overline{a_{1m}} &amp;amp; \overline{a_{2m}} &amp;amp; \overline{a_{3}} &amp;amp; \dots &amp;amp; \overline{a_{mm}}
\end{pmatrix}.
Така матриця A^\daggerназивається эрмитово-сполученої A. Якщо A A^\dagger = A^\dagger A = I, де I— одиничний оператор (з одиничною матрицею), то відповідний оператор називається унітарною.

Друге правило, яке диктує нам матрична механіка: на квантову систему можуть діяти лише унітарні оператори. Чому? Тому що такі перетворення оборотні в часі і не втрачають інформацію. Дійсно, якщо

U \left| \psi_0 \right\rangle = \left| \psi_1 \right\rangle,
то можна застосувати зворотне перетворення

U^\dagger \left| \psi_1 \right\rangle = U^\dagger U \left| \psi_0 \right\rangle = \left| \psi_0 \right\rangle
і отримати початковий стан системи.

Наостанок найважливіше: тензорну твір. Тензорним добутком двох гільбертових просторів \mathcal{H}_1\mathcal{H}_2називається гільбертів простір, що позначається \mathcal{H}_1 \otimes \mathcal{H}_2. Я не буду приводити формальне визначення, лише зазначу нам важливі властивості:
  1. Розмірність отриманого простору дорівнює добутку вимірності вихідних просторів:
    \dim{\mathcal{H}_1 \otimes \mathcal{H}_2$} = \dim{\mathcal{H}_1} \cdot \dim{\mathcal{H}_2};
  2. Якщо \{\left| e_i \right\rangle\}_{i=1}^m— базис \mathcal{H}_1\{\left| f_i \right\rangle\}_{i=1}^n— базис \mathcal{H}_2\{\left| e_i \otimes f_j \right\rangle\}_{i=1, j=1}^{m, n}— породжує базис \mathcal{H}_1 \otimes \mathcal{H}_2.
Тензорним ж произведенем операторів A\mathcal{H}_1^*B\mathcal{H}_2^*(оператор Aпредставлений матрицею, показаної вище) називається оператор A \otimes B\big[ \mathcal{H}_1 \otimes \mathcal{H}_2 \big]^*з матрицею

A \otimes B = \begin{pmatrix}
a_{11} \cdot B &amp;amp; a_{12} \cdot B &amp;amp; a_{13} \cdot B &amp;amp; \dots &amp;amp; a_{1m} \cdot B \\
a_{21} \cdot B &amp;amp; a_{22} \cdot B &amp;amp; a_{23} \cdot B &amp;amp; \dots &amp;amp; a_{2m} \cdot B \\
\vdots &amp;amp; \vdots &amp;amp; \vdots &amp;amp; \ddots &amp;amp; \vdots \\
a_{m1} \cdot B &amp;amp; a_{m2} \cdot B &amp;amp; a_{m3} \cdot B &amp;amp; \dots &amp;amp; a_{mm} \cdot B
\end{pmatrix}.
Таке твір ще називається твором Кронекера: ми множимо другу матрицю на кожний елемент першої матриці і з отриманих блоків складаємо блочну матрицю. Якщо розмірність Aдорівнювала n \times n, а розмірність Bдорівнювала m \times m, то розмірність матриці, отриманої в ході тензорного добутку, буде дорівнює n \cdot m \times n \cdot m.

Приклад:

A = \begin{bmatrix}
1 &amp;amp; 2 \\
3 &amp;amp; 0
\end{bmatrix},\;
B = \begin{bmatrix}
1 &amp;amp; 1 \\
1 &amp;amp; 2
\end{bmatrix},
A \otimes B = \begin{bmatrix}
1 \cdot \begin{pmatrix}
1 &amp;amp; 1 \\
1 &amp;amp; 2
\end{pmatrix} &amp;amp; 2 \cdot \begin{pmatrix}
1 &amp;amp; 1 \\
1 &amp;amp; 2
\end{pmatrix} \\
3 \cdot \begin{pmatrix}
1 &amp;amp; 1 \\
1 &amp;amp; 2
\end{pmatrix} &amp;amp; 0 \cdot \begin{pmatrix}
1 &amp;amp; 1 \\
1 &amp;amp; 2
\end{pmatrix}
\end{bmatrix} = \begin{bmatrix}
1 &amp;amp; 1 &amp;amp; 2 &amp;amp; 2 \\
1 &amp;amp; 2 &amp;amp; 2 &amp;amp; 4 \\
3 &amp;amp; 3 &amp;amp; 0 &amp;amp; 0 \\
3 &amp;amp; 6 &amp;amp; 0 &amp;amp; 0 \\
\end{bmatrix}.

A = \begin{bmatrix}
1 \\
0 \\
\end{bmatrix},\;
B = \begin{bmatrix}
1 \\
2
\end{bmatrix},
A \otimes B = \begin{bmatrix}
1 \\
2 \\
0 \\
0 \\
\end{bmatrix}.
Третя важлива властивість квантових систем: дві квантові системи можуть перебувати у стані суперпозиції, при цьому новий простір станів являє собою тензорну твір вихідних просторів, а стан нової системи буде тензорним добутком станів вихідних систем. Так, суперпозицією систем в станах \left| \psi \right\rangle \in \mathcal{H}_1\left| \phi \right\rangle \in \mathcal{H}_2нова система в змозі \left| \psi \right\rangle \otimes \left| \phi \right\rangle, описувана гильбертовым простором \mathcal{H}_1 \otimes \mathcal{H}_2.

And the vision that was planted in my brain
Ось і вся математика, що нам знадобиться. На всяк випадок, резюмуючи:
  1. При фіксованому базисі квантову систему можна описати комплексним вектором, а еволюцію цієї системи — унітарної комплексної матрицею;
  2. Квантову систему можна виміряти в якому-небудь базисі і вона перейде в один з базисних станів у відповідності із заздалегідь певними ймовірностями.
Виходить, щоб описувати, вивчати, розуміти і емулювати на класичному комп'ютері квантові алгоритми, достатньо лише множити матриці на вектор — це навіть простіше, ніж нейронні мережі: тут немає нелінійностей!

woooho

Кубіт
Давайте розглянемо деяку квантову систему, описувану двовимірним гильбертовым простором \mathcal{H}^2і виділимо в ній деякий базис, вектор якої позначимо як \left| 0 \right\rangle\left| 1 \right\rangle. Усередині дужок записується індекс базисного вектора в двійковій системі числення, починаючи з нуля без додаткових символів. Такі позначення виявляться дуже зручними. Таким чином,

\left| 0 \right\rangle = \begin{bmatrix}
1 \\
0 
\end{bmatrix},\;
\left| 1 \right\rangle = \begin{bmatrix}
0 \\
1 
\end{bmatrix},
і довільний вектор \left| \psi \right\rangle \in \mathcal{H}^2можна виразити наступним чином:

\left| \psi \right\rangle = \alpha \left| 0 \right\rangle + \beta \left| 1 \right\rangle,
де \alpha\beta— деякі комплексні числа, такі що \vert \alpha \vert^2 + \vert \beta \vert^2 = 1(всплмните інтерпретацію коефіцієнтів розкладання і умова нормування з попереднього параграфа). Так от, така проста квантова система називається кубитом quantum bit, qbit). Кубіт — аналог класичного біта в квантової моделі обчислень. Неважко бачити, що простір можливих станів одного кубіта \mathcal{H}^2представляє з себе тривимірну сферу, звану сферою Блоха, де \left| 0 \right\rangleвідповідає нижнього полюса, а \left| 1 \right\rangle— верхнього.

sphere

Регістр
Один кубіт, як і один біт — надто нудно, тому відразу розглянемо суперпозицію декількох кубітів. Така суперпозиція називається квантовим регістром quantum register, qregister nкубітів. Наприклад, квантовий регістр з 2 кубітів буде описуватися простором \mathcal{H}^4і мати 4 базисних стану:

\left| 00 \right\rangle = \left| 0 \right\rangle \otimes \left| 0 \right\rangle = \begin{bmatrix}
1 \\
0 \\
0 \\
0
\end{bmatrix},
\left| 01 \right\rangle = \left| 0 \right\rangle \otimes \left| 1 \right\rangle = \begin{bmatrix}
0 \\
1 \\
0 \\
0
\end{bmatrix},
\left| 10 \right\rangle = \left| 1 \right\rangle \otimes \left| 0 \right\rangle = \begin{bmatrix}
0 \\
0 \\
1 \\
0
\end{bmatrix},
\left| 11 \right\rangle = \left| 1 \right\rangle \otimes \left| 1 \right\rangle = \begin{bmatrix}
0 \\
0 \\
0 \\
1
\end{bmatrix}.
Відповідно, будь-який стан такого регістру \left| \phi \right\rangle \in \mathcal{H}^4можна представити у вигляді

\left| \phi \right\rangle = \alpha_1 \left| 00 \right\rangle + \alpha_2 \left| 01 \right\rangle + \alpha_3 \left| 10 \right\rangle + \alpha_4 \left| 11 \right\rangle,
де \vert \alpha_1 \vert^2 + \vert \alpha_2 \vert^2 + \vert \alpha_1 \vert^3 + \vert \alpha_4 \vert^2 = 1. Зауважте, що в наших позначеннях базисний вектор з одиницею на k-му місці обозначется числом k, записаним в двійковому вигляді.

Далі аналогічно. Квантовий регістр mкубітів буде описуватися 2^m-мірним гильбертовым простором \mathcal{H}^{2^m}мати 2^mбазисних станів, що формуються аналогічним чином. Не відкладаючи надовго, навчимося емулювати квантові регістри:

import numpy as np


class QRegister:
def __init__(self, n_qbits, init):
self._n = n_qbits
assert len(init) == self._n

self._data = np.zeros((2 ** self._n), dtype=np.complex64)
self._data[int('0b' + init, 2)] = 1

3 строчки коду для створення квантового регістра — зовсім не складно, погодьтеся. Можна використовувати таким чином:

a = QRegister(1, '0') # |0>
b = QRegister(1, '1') # |1>
c = QRegister(3, '010') # |010>

Квантовий алгоритм включає в себе:
  1. Ініціалізацію квантового регістра;
  2. Набір унітарних перетворень над ним;
  3. Вимірювання результату.
Вимір
З першим пунктом розібралися і навчилися його емулювати, давайте тепер навчимося емулювати останній: вимірювання. Як ви пам'ятаєте, квадрати коефіцієнтів вектора стану фізично означають ймовірності переходу в цей стан. У відповідності з цим реалізуємо новий метод у класі QRegister:

def measure(self):
probs = np.real(self._data) ** 2 + np.imag(self._data) ** 2
states = np.arange(2 ** self._n)
mstate = np.random.choice(states, size=1, p=alone)[0]
return f'{mstate:>0{self._n}b}'

Генеруємо ймовірності
probs
вибору одного з 2^nстанів
states
і випадково вибираємо його з допомогою
np.random.choice
. Залишається тільки повернути бінарну рядок з відповідною кількістю доповнюючих нулів. Очевидно, що для базисних станів відповідь завжди буде однаковий і рівний самому цього стану. Перевіримо:

>>> QRegister(1, '0').measure()
'0'
>>> QRegister(2, '10').measure()
'10'
>>> QRegister(8, '01001101').measure()
'01001101'

Майже все готово, щоб вирішити нашу задачу! Залишилося лише навчитися впливати на квантові регістри. Ми вже знаємо, що зробити це можна унітарними перетвореннями. У квантової інформатики унітарне перетворення називається гейтом quantum gate, qgate, gate.

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

Одиничний

Одиничний гейт — найпростіший, який тільки можна розглянути. Його матриця виглядає наступним чином:

I = \begin{bmatrix}
1 &amp;amp; 0\\
0 &amp;amp; 1
\end{bmatrix}.
Він ніяк не змінює кубіт, на який діє:

I \left| 0 \right\rangle = \left| 0 \right\rangle,\; I \left| 1 \right\rangle = \left| 1 \right\rangle, \; I \left| \psi \right\rangle = \left| \psi \right\rangle,
однак не варто вважати його марним — він нам знадобиться, і не раз.

Гейт Адамара

H = \frac{1}{\sqrt{2}}
\begin{bmatrix}
1 &amp;amp; 1\\
1 &amp;amp; -1
\end{bmatrix}
Неважко перевірити, що унітарна матриця:

H H^\dagger = \frac{1}{\sqrt{2}}
\begin{bmatrix}
1 &amp;amp; 1\\
1 &amp;amp; -1
\end{bmatrix} \cdot \frac{1}{\sqrt{2}}
\begin{bmatrix}
1 &amp;amp; 1\\
1 &amp;amp; -1
\end{bmatrix} = \frac{1}{2} \begin{bmatrix}
2 &amp;amp; 0\\
0 &amp;amp; 2
\end{bmatrix} = I.
Розглянемо дію гейта Адамара на базисні кубіти:

H \left| 0 \right\rangle = \frac{1}{\sqrt{2}}
\begin{bmatrix}
1 &amp;amp; 1\\
1 &amp;amp; -1
\end{bmatrix}
\begin{bmatrix}
1\\
0
\end{bmatrix} = \frac{1}{\sqrt{2}}
\begin{bmatrix}
1\\
1
\end{bmatrix} = \frac{1}{\sqrt{2}} (\left| 0 \right\rangle + \left| 1 \right\rangle),
H \left| 1 \right\rangle = \frac{1}{\sqrt{2}}
\begin{bmatrix}
1 &amp;amp; 1\\
1 &amp;amp; -1
\end{bmatrix}
\begin{bmatrix}
0\\
1
\end{bmatrix} = \frac{1}{\sqrt{2}}
\begin{bmatrix}
1\\
-1
\end{bmatrix} = \frac{1}{\sqrt{2}} (\left| 0 \right\rangle - \left| 1 \right\rangle).
Або в загальному вигляді [1]:

H \left| x \right\rangle = \frac{1}{\sqrt{2}} \sum_{y \in \lbrace 0,1 \rbrace} (-1)^{x \cdot y} \left| y \right\rangle.
Як можна помітити, гейт Адамара будь базисне стан переводить в равновероятное — при вимірюванні з рівною ймовірністю можна отримати будь-який результат.

Гейти Паулі

Три карйне важливих гейта, яким відповідають матриці, введені Вольфгангом Паулі:

X =
\begin{bmatrix}
0 &amp;amp; 1\\
1 &amp;amp; 0
\end{bmatrix},\;
Y =
\begin{bmatrix}
0 &amp;amp; -i\\
i &amp;amp; 0
\end{bmatrix},\;
Z =
\begin{bmatrix}
1 &amp;amp; 0\\
0 &amp;amp; -1
\end{bmatrix}.
Гейт Xще називається NOT-гейтом:

X \left| 0 \right\rangle = \left| 1 \right\rangle, \; X \left| 1 \right\rangle = \left| 0 \right\rangle,
а геометрично його застосування еквівалентно повороту на сфері Блоха на \piрадіан навколо осі x.

X gate

Гейти YZаналогічні гейту Xза тим винятком, що обертання здійснюється навколо відповідної осі.

Існує теорема, згідно з якою з допомогою гейтів IXYZможна висловити будь однокубитный гейт. Наприклад:

H = \frac{1}{\sqrt{2}}\big(X + Z\big),
звідки видно, що гейт Адамара геометрично означає обертання на \piрадіан навколо осі \frac{x + y}{\sqrt{2}}.

Реалізуємо всі розглянуті гейти на Python. Для цього створимо ще один клас:

class QGate:
def __init__(self, matrix):
self._data = np.array(matrix, dtype=np.complex64)

assert len(self._data.shape) == 2
assert self._data.shape[0] == self._data.shape[1]

self._n = np.log2(self._data.shape[0])

assert self._n.is_integer()

self._n = int(self._n)

А в клас
QRegister
додамо операцію застосування гейта:

def apply(self, gate):
assert isinstance(gate, QGate)
assert self._n == gate._n
self._data = gate._data @ self._data

І створимо вже відомі нам гейти:

I = QGate([[1, 0], [0, 1]])
H = QGate(np.array([[1, 1], [1, -1]]) / np.sqrt(2))
X = QGate([[0, 1], [1, 0]])
Y = QGate([[0, -1j], [1j, 0]])
Z = QGate([[1, 0], [0, -1]])

Орел або решка?
Давайте для прикладу розглянемо найпростіший квантовий алгоритм: він буде генерувати випадковий біт — нуль або один, орла чи решку. Це буде сама чесна монета у всесвіті — результат стане відомий лише при вимірі, а природа випадковості зашита в саму основу всесвіту і вплинути на неї неможливо жодним чином.

Для алгоримта нам знадобиться всього один кубіт. Нехай в початковий момент часу він перебуває в стані \left| 0 \right\rangle:

\left| 0 \right\rangle = \begin{bmatrix}
1\\
0
\end{bmatrix}.
Тепер застосуємо до нього гейт Адамара Hщоб отримати стан

H \left| 0 \right\rangle = \frac{1}{\sqrt{2}}
\begin{bmatrix}
1\\
1
\end{bmatrix}.
Якщо ми зараз виміряємо отриману систему, з імовірністю \Big\vert \frac{1}{\sqrt{2}} \Big\vert^2 = \frac{1}{2}вона виявиться в стані \left| 0 \right\rangleз точно такою ж вірогідністю в змозі \left| 1 \right\rangle. Залишиться тільки записати отриманий результат.

Перевіримо алгоритм, емулюючи його на нашому класичному комп'ютері:

from quantum import QRegister, H


def quantum_randbit():
a = QRegister(1, '0')
a.apply(H)

return a.measure()


for i in range(32):
print(quantum_randbit(), end=")
print()

Результати:

➜ python example-randbit.py
11110011101010111010011100000111

➜ python example-randbit.py
01110000111100011000101010100011

➜ python example-randbit.py
11111110011000001101010000100000

Весь наведений вище алгоритм може бути записаний парою формул:

\left| q_0 \right\rangle = \left| 0 \right\rangle\\
\left| q_1 \right\rangle = H \left| q_0 \right\rangle\\
r = measure(\left| q_1 \right\rangle)
Однак, з таким записом не дуже зручно працювати: структура списку — послідовності дій, добре підходить для класичних алгоритмів, не застосовна в квантовому випадку: тут у нас немає ні циклів, ні умов, лише протягом стану вперед (а іноді і назад) у часі. Тому для опису алгоритмів в квантової інформатики широко використовуються квантові схеми. Ось схема наведеного вище алгоритму:

simple

Зліва завжди позначено початковий стан системи. У прямокутниках зазначаються унітарні перетворення, вироблені над цим станом, а в кінці на всіх або на декількох кубітах розташований значок вимірювального приладу — операція вимірювання. Існує ще «синтаксичний цукор» для деяких многокубитных перетворень у вигляді точок, розгалужень і кружечків. І все. Якщо ви вмієте відрізнити квадрат від трикутника і кола, ви без проблем зрозумієте будь-яку схему квантового алгоритму.

holes

кубітів богу кубітів
А що, якщо ми працюємо не з одним кубитом, а з цілим їх регістром? І, припустимо, хочемо застосувати гейт лише до одного кубиту? На допомогу приходять властивості тензорного добутку. За визначенням тензорного добутку оператора A: V \to WB: X \to Y:

(A \otimes B)(v \otimes x) = Av \otimes Bx,
де v \in Vx \in X. Тоді:

(A \otimes I)(v \otimes x) = Av \otimes Ix = Av \otimes x,
тобто, все одно — застосувати гейт до одного кубиту, а потім зв'язати його з другим і отримати квантовий регістр або ж застосувати до всього регістру оператор A \otimes I. Аналогічно, якщо ми хочемо застосувати оператор Aтільки до другого кубиту, ми можемо застосувати до всього регістру оператор I \otimes A. Це означає, що така схема:

example0

Повністю аналогічна такий:

example1

Лише поодинокі гейти для зручності опускають.

А якщо ми, навпаки, хочемо застосувати гейт відразу до декількох кубитам? Знову ж таки, з визначення тензорного добутку, для цього ми можемо застосувати до них цей гейт, тензорно помножений сам на себе необхідну кількість разів:

Hv \otimes Hx = (H \otimes H) (v \otimes x) = H^{\otimes2} (v \otimes x).
A^{\otimes n}означає тензорну зведення в ступінь. До речі, \left| \psi \right \rangle^{\otimes n}для стислості записують як \left| \psi^n \right \rangle. Таким чином,

H^{\otimes n} \left| 0^n \right \rangle
означає: до кожного кубиту квантового регістра nнульових кубітів застосувати перетворення Адамара.

Додамо тензорну твір і зведення в ступінь в наш
QGate
:

def __matmul__(self, other):
return QGate(np.kron(self._data, other._data))

def __pow__(self, n, modulo=None):
x = self._data.copy()

for _ in range(n - 1):
x = np.kron(x, self._data)

return QGate(x)

Квантовий оракул
Кожній бінарної функції f : \{0, 1\}^n \to \{0, 1\}відповідає єдиний многокубитный гейт розмірності n + 1, який позначається U_fі називається квантовим оракулом для цієї функції. Він містить в собі всю інформацію про функції fі «дозволяє» одночасно викликати її на всіх її можливих аргументів.

Чому його розмірність n + 1? Вся справа в тому, що згідно ще одному фундаментальному властивості квантових обчислень, в них не втрачається інформація і вони оборотні в часі. Якщо ми в класичній моделі обчислень викличемо функцію f(x, y) = x \oplus yі отримаємо результат, то по ньому ми не зможемо сказати, з якими аргументами функція була викликана і, відповідно, не зможемо звернути обчислення в часі.

diagram0

Один зі способів уникнути цього — запам'ятати аргументи, з якими була викликана функція.

diagram1

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

Квантовий оракул U_fвизначається як унітарне перетворення, що переводить стан \left| x \right \rangle \left| y \right \rangleу стан \left| x \right \rangle \left| y \oplus f(x) \right \rangle, де nкубітів, позначених x, несуть в собі інформацію про аргумент функції і залишаються незмінними, а єдиний кубіт y— її результат. \oplusпозначає додавання по модулю 2.

Розберемося на прикладі. Припустимо, ми хочемо побудувати оракул для функції одного аргументу f(x) = x. Це означає, що відповідний оператор U_fдвухкубитным і може бути описаний квадратною матрицею розмірності 2^2 = 4. У відповідності з описаним вище правилом подивимося, які стани далжны перейти всі можливі базисні стану регістра:

\left| 00 \right \rangle = \left| 0 \right \rangle \left| 0 \right \rangle \to \left| 0 \right \rangle \left| 0 \oplus f(0) \right \rangle = \left| 00 \right \rangle
\left| 01 \right \rangle = \left| 0 \right \rangle \left| 1 \right \rangle \to \left| 0 \right \rangle \left| 0 \oplus f(1) \right \rangle = \left| 01 \right \rangle
\left| 10 \right \rangle = \left| 1 \right \rangle \left| 0 \right \rangle \to \left| 1 \right \rangle \left| 1 \oplus f(0) \right \rangle = \left| 11 \right \rangle
\left| 11 \right \rangle = \left| 1 \right \rangle \left| 1 \right \rangle \to \left| 1 \right \rangle \left| 1 \oplus f(1) \right \rangle = \left| 10 \right \rangle
Оператор з одиничною матрицею переводить будь-який стан у себе, так як при множенні матриці на i-ую рядок ми беремо i-ий же компонент вектора і ставимо його на те ж саме місце. Якщо в матриці на i-ой рядку всі елементи, крім j-го будуть нулями, а він одиницею, то на j-е місце результуючого вектора ми поставимо елемент, який стояв на i-му місці вихідного вектора. У наведеному вище прикладі, нам потрібно залишити на місці {00}_2 = 0{01}_2 = 1елементи вектора стану і поміняти місцями {10}_2 = 3{11}_2 = 4елементи. Тоді U_fбуде виглядати наступним чином:

U_f = \begin{bmatrix}
1 &amp;amp; 0 &amp;amp; 0 &amp;amp; 0\\
0 &amp;amp; 1 &amp;amp; 0 &amp;amp; 0\\
0 &amp;amp; 0 &amp;amp; 0 &amp;amp; 1\\
0 &amp;amp; 0 &amp;amp; 1 &amp;amp; 0\\
\end{bmatrix}.
Перевіримо:

\begin{bmatrix}
1 &amp;amp; 0 &amp;amp; 0 &amp;amp; 0\\
0 &amp;amp; 1 &amp;amp; 0 &amp;amp; 0\\
0 &amp;amp; 0 &amp;amp; 0 &amp;amp; 1\\
0 &amp;amp; 0 &amp;amp; 1 &amp;amp; 0\\
\end{bmatrix}\begin{bmatrix}
x_{00} \\
x_{01} \\
x_{10} \\
x_{11} \\
\end{bmatrix} = \begin{bmatrix}
x_{00} \\
x_{01} \\
x_{11} \\
x_{10} \\
\end{bmatrix}.
Аналогічно для будь-якої іншої функції довільного числа аргументів. Реалізуємо оракл:

def U(f, n):
m = n + 1

U = np.zeros((2**m, 2**m), dtype=np.complex64)

def bin2int(xs):
r = 0
for i, x in enumerate(reversed(xs)):
r += x * 2 ** i
return r

for xs in product({0, 1}, repeat=m):
x = xs[:~0]
y = xs[~0]

z = y ^ f(*x)

instate = bin2int(xs)
outstate = bin2int(list(x) + [z])
U[instate, outstate] = 1

return QGate(U)

Still remains
Ну ось ми і розглянули весь базис, який необхідний для вирішення поставленої задачі і навіть встигли написати невеликий фреймворк на пітоні, який нам допоможе це рішення перевірити. Алгоритм, що дозволяє за один виклик функції визначити, константна функція або збалансована, називається алгоритмом Дечани — Йожи. Версія алгоритму для функції однієї змінної була розроблена в 1985 році Девідом Дойчем, а потім узагальнена на випадок декількох змінних в 1992 році з допомогою Річарда Йожи. Ось схема цього алгоритму:

dj

Якщо результатом вимірювання стане 0, то функція константна, інакше — збалансована. Відразу реалізуємо алгоритм:

from quantum import QRegister, H, I, U


def is_constant(f, n):
q = QRegister(n + 1, '0' * n + '1')
q.apply(H ** (n + 1))
q.apply(U(f, n))
q.apply(H ** n @ I)

if q.measure()[:~0] == '0' * n:
return True
else:
return False

І перевіримо:

def f1(x):
return x


def f2(x):
return 1


def f3(x, y):
return x ^ y


def f4(x, y, z):
return 0


print('f(x) = x is {}'.format('constant' if is_constant(f1, 1) else 'balansed'))
print('f(x) = 1 is {}'.format('constant' if is_constant(f2, 1) else 'balansed'))
print('f(x, y) = x ^ y is {}'.format('constant' if is_constant(f3, 2) else 'balansed'))
print('f(x, y, z) = 0 is {}'.format('constant' if is_constant(f4, 3) else 'balansed'))

Результат:

f(x) = x is balansed
f(x) = 1 constant is
f(x, y) = x ^ y is balansed
f(x, y, z) = 0 constant is

Працює. Чудово. А чому він працює? Доведемо коректність алгоритму і заодно подивимося на принцип його роботи.

Розглянемо дію гейта Hна квантовий регістр в довільному базисному стані [1]:

H^{\otimes n} \left|x_1, x_2, \ldots, x_n\right\rangle =
(за властивістю тензорного добутку)

= H \left| x_1 \right\rangle \otimes H \left| x_2 \right\rangle \otimes \dots \otimes H \left| x_n \right\rangle =
(застосуємо до кожного окремого кубиту)

=\frac{1}{\sqrt{2^n}} \Big(\sum \limits_{y_1 \in \lbrace 0,1 \rbrace} (-1)^{x_1 \cdot y_1} \left| y_1 \right\rangle \otimes \sum \limits_{y_2 \in \lbrace 0,1 \rbrace} (-1)^{x_2 \cdot y_2} \left| y_2 \right\rangle \otimes \ldots \otimes \sum \limits_{y_n \in \lbrace 0,1 \rbrace} (-1)^{x_n \cdot y_n} \left| y_n \right\rangle \Big) =
(винесемо -1 за знак тензорного добутку)

=\frac{1}{\sqrt{2^n}} \sum \limits_{(y_1, y_2, \ldots, y_n) \in \lbrace 0,1 \rbrace^n} (-1)^{x_1 \cdot y_1 \oplus x_2 \cdot y_2 \oplus \dots \oplus x_n \cdot y_n} \left| {y_1 y_2 \ldots y_n} \right\rangle =
(переобозначим для компактності)

=\frac{1}{\sqrt{2^n}} \sum \limits_{y \in \lbrace 0,1 \rbrace^n} (-1)^{(x, y)} \left| y \right\rangle,
де \oplus— додавання по модулю 2, а (x, y)— скалярний твір по модулю 2.

У початковий момент часу система перебуває в стані \left| {q_0} \right\rangle \left| {q_1} \right\rangle = \left| 0 \right\rangle^{\otimes n} \left| 1 \right\rangleі під дією перетворення Адамара перейде в стан

H^{\otimes n} \left| 0 \right\rangle^{\otimes n} (H \left| 1 \right\rangle) = \frac{1}{\sqrt{2^{n+1}}}\displaystyle\sum_{x=0}^{2^n} \left| x \right\rangle \big(\left| 0 \right\rangle - \left|1 \right\rangle \big).
Оракул U_fпереведе систему в стан

\frac{1}{\sqrt{2^{n+1}}}\displaystyle\sum_{x=0}^{2^n} \left| x \right\rangle \Big(\left| {f(x)} \right\rangle \oplus \big(\left| 0 \right\rangle - \ \left| 1 \right\rangle \big) \Big) = \frac{1}{\sqrt{2^{n+1}}}\displaystyle\sum_{x=0}^{2^n} \left| x \right\rangle \Big( \left| {f(x)} \right\rangle - \left| {f(x) \oplus 1} \right\rangle \Big).
Зауважте, що якщо на деякому фіксованому аргументі xфункція f(x)набуде значення 0, то коефіцієнт перед \left| x \right\rangleне зміниться, інакше — змінить знак. Виходячи з цього спостереження можна переписати поточний стан

\frac{1}{\sqrt{2^{n+1}}}\displaystyle\sum_{x=0}^{2^n} (-1)^{f(x)} \left| x \right\rangle \big( \left| 0 \right\rangle - \left| 1 \right\rangle \big).
На даному етапі відкинемо невикористаний далі останній кубіт і застосуємо повторне перетворення Адамара до першим nкубитам, щоб отримати стан

H^{\otimes n} \Big( \frac{1}{\sqrt{2^n}}\displaystyle\sum_{x=0}^{2^n} (-1)^{f(x)} \left| x \right\rangle \Big) = \frac{1}{2^n}\displaystyle\sum_{y=0}^{2^n} \Big( \displaystyle\sum_{x=0}^{2^n} (-1)^{f(x) + x \cdot y} \Big) \left| y \right\rangle.
А так як x \cdot 0^n = 0, ймовірність спостереження результату \left| {0^n} \right\rangleдорівнює

\frac{1}{2^n}\displaystyle\sum_{x=0}^{2^n} (-1)^{f(x)} = 
\begin{cases}
1 &amp;amp;\text{, якщо $f(x)$ константна}\\
0 &amp;amp;\text{, якщо $f(x)$ збалансована}
\end{cases}.
От і все. Ми розглянули досить спрощену модель квантових обчислень, написали міні-фреймворк на пітоні для їх емуляції на локальному комп'ютері і розібрали один з найпростіших «справжніх» квантових алгоритмів — алгоритм Дечани-Йожи. От котик для тих, хто не полінувався, прочитав статтю і розібрався в темі:

.

З кодом можна ознайомитися на GitHub.

Спасибі за прочитання! Ставте лайки, підписуйтесь на профіль, залишайте коментарі, займайтеся корисними справами. Доповнення вітаються.

Література
  • [1] М. Млявий, «Квантові алгоритми: можливості та
    обмеження»
  • [2] А. С. Холево, «Введення в квантову теорію інформації»
  • [3] M. A. Nielsen, «Quantum Information Theory»
P. S: Формули на хабре — відстій. Спасибі Roman Parpalak за сервіс upmath.me, без нього пост з такою кількістю формул був би неможливий.
Джерело: Хабрахабр

0 коментарів

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