Алгоритм Гровера

Для цього модуля Qiskit in Classrooms студенти повинні мати робоче середовище Python з наступними встановленими пакетами:

• qiskit v2.1.0 або новіше
• qiskit-ibm-runtime v0.40.1 або новіше
• qiskit-aer v0.17.0 або новіше
• qiskit.visualization
• numpy
• pylatexenc

Щоб налаштувати та встановити пакети вище, переглянь посібник Install Qiskit. Щоб запускати завдання на реальних квантових комп'ютерах, студентам потрібно буде налаштувати обліковий запис IBM Quantum®, виконавши кроки в посібнику Set up your IBM Cloud account.

Цей модуль був протестований і використав 12 секунд часу QPU. Це оцінка добросовісності; твоє фактичне використання може відрізнятися.

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Вступ

Алгоритм Гровера є фундаментальним квантовим алгоритмом, який розв'язує задачу неструктурованого пошуку: маючи множину з $N$ елементів та спосіб перевірити, чи є будь-який даний елемент тим, який ти шукаєш, як швидко ти можеш знайти бажаний елемент? У класичних обчисленнях, якщо дані не відсортовані і немає структури, яку можна використати, найкращий підхід — перевіряти кожен елемент один за одним, що призводить до складності запитів $O(N)$ — в середньому тобі потрібно буде перевірити приблизно половину елементів, перш ніж знайти ціль.

Алгоритм Гровера, представлений Ловом Гровером у 1996 році, демонструє, як квантовий комп'ютер може розв'язати цю задачу набагато ефективніше, потребуючи лише $O(\sqrt{N})$ кроків для знаходження позначеного елемента з високою ймовірністю. Це представляє квадратичне прискорення порівняно з класичними методами, що є значущим для великих наборів даних.

Алгоритм працює в наступному контексті:

• Постановка задачі: У тебе є функція $f(x)$, яка повертає 1, якщо $x$ є елементом, який ти хочеш, і 0 в іншому випадку. Ця функція часто називається оракулом або чорною скринькою, оскільки ти можеш дізнатися про дані лише запитуючи $f(x)$.
• Корисність квантового підходу: Хоча класичні алгоритми для цієї задачі вимагають, в середньому, $N/2$ запитів, алгоритм Гровера може знайти розв'язок приблизно за $\pi\sqrt{N}/4$ запитів, що набагато швидше для великих $N$.
• Як це працює (на високому рівні):
  • Квантовий комп'ютер спочатку створює суперпозицію всіх можливих станів, представляючи всі можливі елементи одночасно.
  • Потім він багаторазово застосовує послідовність квантових операцій (ітерація Гровера), які посилюють ймовірність правильної відповіді та зменшують інші.
  • Після достатньої кількості ітерацій вимірювання квантового стану дає правильну відповідь з високою ймовірністю.

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

Кілька речей, які слід зауважити про алгоритм Гровера:

• Він є оптимальним для неструктурованого пошуку: жоден квантовий алгоритм не може розв'язати задачу з менш ніж $O(\sqrt{N})$ запитами.
• Він забезпечує лише квадратичне, а не експоненціальне прискорення — на відміну від деяких інших квантових алгоритмів (наприклад, алгоритм Шора для факторизації).
• Він має практичне значення, наприклад, потенційно прискорюючи атаки грубої сили на криптографічні системи, хоча прискорення недостатньо для зламу більшості сучасних шифрів саме по собі.

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

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

Тут ми демонструємо, як побудувати оракули Гровера та використовувати GroverOperator з бібліотеки схем Qiskit для легкого налаштування екземпляра пошуку Гровера. Примітив Sampler з runtime дозволяє безшовне виконання схем Гровера.

Теорія

Припустимо, що існує функція $f$, яка відображає бінарні рядки в одну бінарну змінну, тобто

$$f: \Sigma^n \rightarrow \Sigma$$

Один приклад, визначений на $\Sigma^6$, є

$$f(x)= \begin{cases} 1 \qquad \text{якщо }x=\{010101\}\\ 0 \qquad \text{інакше } \end{cases}$$

Інший приклад, визначений на $\Sigma^{2n}$, є

$$f(x)= \begin{cases} 1 \qquad \text{якщо рівна кількість 1 і 0 в рядку}\\ 0 \qquad \text{інакше } \end{cases}$$

Перед тобою стоїть завдання знайти квантові стани, що відповідають тим аргументам $x$ функції $f(x)$, які відображаються в 1. Іншими словами, знайди усі $\{x_1\}\in \Sigma^n$ такі, що $f(x_1)=1$ (або якщо немає розв'язку, повідом про це). Ми б називали не-розв'язки як $x_0$. Звичайно, ми зробимо це на квантовому комп'ютері, використовуючи квантові стани, тому корисно виразити ці бінарні рядки як стани:

$$\{|x_1\rangle\} \in |\Sigma^n\rangle$$

Використовуючи нотацію квантового стану (Дірака), ми шукаємо один або більше спеціальних станів $\{|x_1\rangle\}$ в множині з $N=2^n$ можливих станів, де $n$ — кількість кубітів, а не-розв'язки позначені $\{|x_0\rangle\}.$

Ми можемо думати про функцію $f$ як про таку, що надається оракулом: чорною скринькою, яку ми можемо запитати, щоб визначити її вплив на стан $|x\rangle.$ На практиці ми часто знатимемо функцію, але її може бути дуже складно реалізувати, що означає, що зменшення кількості запитів або застосувань $f$ може бути важливим. Альтернативно, ми можемо уявити парадигму, в якій одна людина запитує оракул, контрольований іншою особою, так що ми не знаємо функцію оракула, ми знаємо лише його дію на конкретні стани з запитів.

Це "задача неструктурованого пошуку", в тому сенсі, що немає нічого особливого в $f$, що допомагає нам в нашому пошуку. Виходи не відсортовані, і не відомо, що розв'язки кластеризуються, і так далі. Розглянемо старі паперові телефонні книги як аналогію. Цей неструктурований пошук буде подібний до сканування через нього в пошуках певного номера, а не як пошук через алфавітно впорядкований список імен.

У випадку, коли шукається один розв'язок, класично це вимагає кількості запитів, що лінійно залежить від $N$. Очевидно, ти можеш знайти розв'язок при першій спробі, або ти можеш не знайти розв'язків у перших $N-1$ спробах, так що тобі потрібно запитати $N$-й вхід, щоб перевірити, чи є взагалі якийсь розв'язок. Оскільки функції не мають структури, яку можна використати, тобі знадобиться $N/2$ спроб в середньому. Алгоритм Гровера вимагає кількості запитів або обчислень $f$, яка масштабується як $\sqrt{N}.$

Схематичний огляд схем в алгоритмі Гровера

Повний математичний огляд алгоритму Гровера можна знайти, наприклад, в Fundamentals of quantum algorithms, курсі Джона Ватруса на IBM Quantum Learning. Стислий виклад наведено в додатку в кінці цього модуля. Але зараз ми лише переглянемо загальну структуру квантової схеми, яка реалізує алгоритм Гровера.

Алгоритм Гровера може бути розбитий на наступні етапи:

• Підготовка початкової суперпозиції (застосування вентилів Адамара до всіх кубітів)
• "Позначення" цільового стану(ів) перекиданням фази
• Етап "дифузії", на якому вентилі Адамара та перекидання фази застосовуються до всіх кубітів.
• Можливі повторення етапів позначення та дифузії для максимізації ймовірності вимірювання цільового стану
• Вимірювання

Часто вентиль позначення $Z_f$ та шари дифузії, що складаються з $H,$ $Z_{\text{OR}},$ та $H$, спільно називаються "оператором Гровера". На цій діаграмі показано лише одне повторення оператора Гровера.

Вентилі Адамара $H$ добре відомі та широко використовуються в квантових обчисленнях. Вентиль Адамара створює стани суперпозиції. Зокрема, він визначається як

$$H|0\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)\\ H|1\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)$$

Його дія на будь-який інший стан визначається через лінійність. Зокрема, шар вентилів Адамара дозволяє нам перейти від початкового стану з усіма кубітами в $|0\rangle$ (позначений $|0\rangle^{\otimes n}$) до стану, де кожен кубіт має деяку ймовірність бути виміряним або в $|0\rangle$ або в $|1\rangle;$ це дозволяє нам досліджувати простір всіх можливих станів інакше, ніж у класичних обчисленнях.

Важливою наслідковою властивістю вентиля Адамара є те, що діючи вдруге, можна скасувати такі стани суперпозиції:

$$H\frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)=|0\rangle\\ H\frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)=|1\rangle$$

Це буде важливим через мить.

Перевір своє розуміння

Прочитай питання нижче, подумай над своєю відповіддю, потім натисни трикутник, щоб побачити розв'язок.

Виходячи з визначення вентиля Адамара, продемонструй, що друге застосування вентиля Адамара скасовує такі суперпозиції, як заявлено вище.

Відповідь:

Коли ми застосовуємо X до стану $|+\rangle$, ми отримуємо значення +1, а до стану $|-\rangle$ ми отримуємо -1, тому якщо ми маємо розподіл 50-50, ми отримаємо очікуване значення 0.

Вентиль $Z_\text{OR}$ менш поширений і визначається згідно з

$$\text{Z}_\text{OR}|x\rangle = \begin{cases} |x\rangle & \text{якщо } x = 0^n \\ -|x\rangle & \text{якщо } x \neq 0^n \end{cases} \qquad \forall x \in \Sigma^n$$

Нарешті, вентиль $Z_f$ визначається як

$$Z_f:|x\rangle \rightarrow (-1)^{f(x)}|x\rangle \qquad \forall x \in \Sigma^n$$

Зверни увагу на ефект того, що $Z_f$ перевертає знак на цільовому стані, для якого $f(x) = 1$, і залишає інші стани незмінними.

На дуже високому, абстрактному рівні ти можеш думати про кроки в схемі наступним чином:

• Перший шар Адамара: ставить кубіти в суперпозицію всіх можливих станів.
• $Z_f$: позначає цільовий стан(и), додаючи знак "-" попереду. Це не змінює негайно ймовірності вимірювання, але змінює те, як цільовий стан поводитиметься на наступних кроках.
• Ще один шар Адамара: знак "-", введений на попередньому кроці, змінить відносний знак між деякими членами. Оскільки вентилі Адамара перетворюють одну суміш обчислювальних станів $(|0\rangle+|1\rangle)/\sqrt{2}$ в один обчислювальний стан, $|0\rangle,$ і вони перетворюють $(|0\rangle-|1\rangle)/\sqrt{2}$ в $|1\rangle$, ця різниця відносних знаків тепер може почати відігравати роль в тому, які стани вимірюються.
• Один останній шар вентилів Адамара застосовується, а потім виконуються вимірювання.

Ми побачимо більш детально, як це працює, в наступному розділі.

Приклад

Щоб краще зрозуміти, як працює алгоритм Гровера, розгляньмо невеликий приклад з двома кубітами. Це може вважатися необов'язковим для тих, хто не зосереджений на квантовій механіці та нотації Дірака. Але для тих, хто сподівається істотно працювати з квантовими комп'ютерами, це дуже рекомендується.

Ось діаграма схеми з квантовими станами, позначеними в різних позиціях. Зверни увагу, що маючи лише два кубіти, є лише чотири можливі стани, які можуть бути виміряні за будь-яких обставин: $|00\rangle$, $|01\rangle$, $|10\rangle$ і $|11\rangle$.

Припустимо, що оракул ($Z_f$, невідомий нам) позначає стан $|01\rangle$. Ми розглянемо дії кожного набору квантових вентилів, включаючи оракул, і побачимо, який розподіл можливих станів виходить під час вимірювання.

На самому початку ми маємо

$$|\psi_0\rangle = |00\rangle$$

Використовуючи визначення вентилів Адамара, ми маємо

$$|\psi_1\rangle = \frac{1}{2}\left(|0\rangle+|1\rangle\right)\left(|0\rangle+|1\rangle\right)=\frac{1}{2}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)$$

Тепер оракул позначає цільовий стан:

$$|\psi_2\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle+|11\rangle\right)$$

Зверни увагу, що в цьому стані всі чотири можливі результати мають однакову ймовірність бути виміряними. Усі вони мають вагу величиною $1/2,$ що означає, що кожен має шанс $|1/2|^2=1/4$ бути виміряним. Тож хоча стан $|01\rangle$ позначений через фазу "-", це ще не призвело до будь-якого збільшення ймовірності вимірювання цього стану. Ми продовжуємо, застосовуючи наступний шар вентилів Адамара.

$$\begin{aligned} |\psi_3\rangle = &\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

Об'єднуючи подібні члени, ми знаходимо

$$|\psi_3\rangle = \frac{1}{2}\left(|00\rangle+|01\rangle-|10\rangle+|11\rangle\right)$$

Тепер $Z_{\text{OR}}$ перевертає знак на всіх станах, окрім $|00\rangle$:

$$|\psi_4\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)$$

І нарешті, ми застосовуємо останній шар вентилів Адамара:

$$\begin{aligned} |\psi_5\rangle =&\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

Варто пропрацювати об'єднання цих членів, щоб переконати себе, що результат дійсно такий:

$$|\psi_5\rangle =|01\rangle$$

Тобто, ймовірність вимірювання $|01\rangle$ становить 100% (за відсутності шуму та помилок), а ймовірність вимірювання будь-якого іншого стану дорівнює нулю.

Цей приклад з двома кубітами був особливо чистим випадком; алгоритм Гровера не завжди спрацьовуватиме так, щоб дати 100% шанс вимірювання цільового стану. Натомість він посилить ймовірність вимірювання цільового стану. Крім того, оператор Гровера може знадобитися повторити більше одного разу.

У наступному розділі ми застосуємо цей алгоритм на практиці, використовуючи реальні квантові комп'ютери IBM®.

Геометрична інтерпретація

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

Встановлення площини. Ми можемо розкласти початковий стан суперпозиції $|\psi\rangle$ на дві складові. Правильний стан — той, який ми шукаємо — ми називаємо $|A_1\rangle$. Усі інші стани, об'єднані разом, ми називаємо $|A_0\rangle$. За визначенням, $|A_1\rangle$ та $|A_0\rangle$ ортогональні один одному, тому ми можемо зобразити їх як перпендикулярні осі в абстрактному двовимірному просторі. Оскільки $|\psi\rangle$ є лінійною комбінацією цих двох складових, він розташований під деяким малим кутом $\theta$ до осі $|A_0\rangle$ — близько до $|A_0\rangle$, тому що на початку лише мала частка стану знаходиться в правильній складовій $|A_1\rangle$.

Відображення. Ключовий математичний факт, який нам потрібен, полягає в тому, що оператор виду

$$2|v\rangle\langle v| - I$$

відображає будь-який стан відносно осі, визначеної $|v\rangle.$ Щоб зрозуміти чому, розглянь два випадки: стан вздовж $|v\rangle$ залишається незмінним, а стан перпендикулярний до $|v\rangle$ отримує перевернутий знак. Будь-який інший стан можна розкласти на ці дві складові, і оператор діє на кожну відповідно — що є саме відображенням відносно $|v\rangle$.

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

Оракул як відображення. Оракул перевертає знак стану $|A_1\rangle$ і залишає все інше без змін. Це те саме, що відображення відносно осі $|A_0\rangle$.

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

$$H^{\otimes n}\, Z_{\text{OR}}\, H^{\otimes n}$$

$Z_{\text{OR}}$ сам по собі є відображенням відносно стану всіх нулів, оскільки він перевертає знак кожного стану, що не є $|0\rangle^{\otimes n}$. Це можна записати як $2|0\rangle\langle 0| - I$. Навколишні шари Адамара ефективно виконують зміну базису, трансформуючи вісь відображення. Пригадай, що $H^{\otimes n}$ відображає $|0\rangle^{\otimes n}$ на рівномірну суперпозицію $|u\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle$. Оскільки Адамар є власним оберненим, повний вираз стає

$$H^{\otimes n}\left(2|0\rangle\langle 0| - I\right)H^{\otimes n} = 2|u\rangle\langle u| - I$$

що є відображенням відносно $|u\rangle$. Оскільки $|u\rangle$ дуже близький до $|\psi\rangle$ (обидва майже вздовж $|A_0\rangle$), це друге відображення посилає стан на кут $2\theta$ від його початкового положення.

Обертання на $2\theta$. Комбінований ефект цих двох відображень є обертанням на $2\theta$ у напрямку $|A_1\rangle$. Кожна наступна ітерація оператора Гровера обертає стан ще на $2\theta.$

Оптимальна кількість ітерацій. Наша мета — обернути стан якомога ближче до $|A_1\rangle$, що означає обертання загалом приблизно на $\pi/2$ радіан (чверть оберту). Якщо кожна ітерація вносить $2\theta$, оптимальна кількість ітерацій $t$ задовольняє

$$(2t + 1)\theta \approx \frac{\pi}{2}$$

Для одного розв'язку серед $N$ станів початковий кут є $\theta \approx \sin^{-1}(1/\sqrt{N}) \approx 1/\sqrt{N}$ (для великого $N$). Підставляючи,

$$t \approx \frac{\pi}{4}\sqrt{N} - \frac{1}{2}$$

Ось звідки береться знамените прискорення $\sqrt{N}$: нам потрібно лише $O(\sqrt{N})$ ітерацій для досягнення мети, а не $O(N)$ перевірок, яких вимагатиме класичний пошук.

У загальному випадку, якщо є $|A_1|$ станів-розв'язків серед $N$ загальних станів, оптимальна кількість ітерацій є

$$t \approx \frac{\pi}{4}\sqrt{\frac{N}{|A_1|}} - \frac{1}{2}$$

Зверни увагу, що якщо ти застосовуєш занадто багато ітерацій, ти оберташся за $|A_1\rangle$ і ймовірність знаходження цільового стану почне знову зменшуватися. Знаходження правильної кількості ітерацій важливе, хоча на зашумленому квантовому обладнанні експериментально оптимальна кількість може відрізнятися від цієї ідеальної формули.

Чому алгоритм Гровера є корисним?

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

Це справедливе питання, і є кілька хороших відповідей.

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

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

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

• Існують задачі, де можна побудувати оракул, не знаючи відповіді. Ключова ідея полягає в тому, що існує цілий клас задач, для яких дуже важко знайти розв'язок, але дуже легко перевірити, що даний розв'язок є правильним. Факторизація є одним прикладом: маючи добуток двох великих простих чисел, надзвичайно важко визначити, що це за прості числа, але якщо у тебе вони є, ти можеш легко перемножити їх для верифікації. (У нас є кращий алгоритм, ніж Гровера для факторизації конкретно — дивись алгоритм Шора — але це далеко не єдина задача з такою властивістю.) Судоку, задоволення обмежень і навіть класична гра Сапер — це всі задачі, які важко вирішити, але легко перевірити.

Чому це важливо? Це означає, що ми можемо знати всі умови та вимоги, яким повинен задовольняти розв'язок, і можемо кодувати ці вимоги в квантову схему, яка служить оракулом — навіть якщо ми не знаємо самого розв'язку. Алгоритм Гровера знайде його за нас.

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

Загальні імпорти та підхід

Ми починаємо з імпорту кількох необхідних пакетів.

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import grover_operator, MCMTGate, ZGate
from qiskit.visualization import plot_distribution
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

Протягом цього та інших підручників ми використовуватимемо framework для квантових обчислень, відомий як "Qiskit patterns", який розбиває робочі процеси на наступні кроки:

• Крок 1: Відобразити класичні входи на квантову задачу
• Крок 2: Оптимізувати задачу для квантового виконання
• Крок 3: Виконати, використовуючи Qiskit Runtime Primitives
• Крок 4: Постобробка та класичний аналіз

Ми загалом будемо слідувати цим крокам, хоча не завжди будемо явно позначати їх.

Активність 1: Знайти один заданий цільовий стан

Крок 1: Відобразити класичні входи на квантову задачу

Нам потрібен вентиль фазового запиту, щоб поставити загальну фазу (-1) на стани розв'язку, і залишити стани не-розв'язку незмінними. Інший спосіб сказати це полягає в тому, що алгоритм Гровера вимагає оракула, який вказує один або більше позначених обчислювальних базисних станів, де "позначений" означає стан з фазою -1. Це робиться за допомогою керованого Z-вентиля, або його мультикерованого узагальнення над $N$ кубітами. Щоб побачити, як це працює, розглянемо конкретний приклад бітового рядка {110}. Ми б хотіли схему, яка діє на стан $|\psi\rangle = |q_2,q_1,q_0\rangle$ і застосовує фазу, якщо $|\psi\rangle = |011\rangle$ (де ми перевернули порядок бінарного рядка через нотацію в Qiskit, яка ставить найменш значущий (часто 0) кубіт справа).

Таким чином, ми хочемо схему $Z_f$, яка досягає

$$Z_f|\psi\rangle = \begin{cases} -|\psi\rangle \qquad \text{якщо} \qquad |\psi\rangle = |011\rangle \\ |\psi\rangle \qquad \text{якщо} \qquad |\psi\rangle \neq |011\rangle\end{cases}$$

Ми можемо використовувати вентиль з множинним керуванням і множинними цілями (MCMTGate), щоб застосувати Z-вентиль, керований усіма кубітами (перевернути фазу, якщо всі кубіти перебувають у стані $|1\rangle$). Звичайно, деякі з кубітів у нашому бажаному стані можуть бути $|0\rangle$. Тому для цих кубітів ми повинні спочатку застосувати X-вентиль, потім виконати мультикерований Z-вентиль, потім застосувати ще один X-вентиль, щоб скасувати нашу зміну. MCMTGate виглядає так:

mcmt_ex = QuantumCircuit(3)
mcmt_ex.compose(MCMTGate(ZGate(), 3 - 1, 1), inplace=True)
mcmt_ex.draw(output="mpl", style="iqp")

Зверни увагу, що багато кубітів можуть бути залучені до процесу керування (тут три кубіти), але жоден окремий кубіт не позначений як ціль. Це тому, що весь стан отримує загальний знак "-" (перекидання фази); вентиль впливає на всі кубіти еквівалентно. Це відрізняється від багатьох інших багатокубітових вентилів, як вентиль CX, який має один керуючий кубіт і один цільовий кубіт.

У наступному коді ми визначаємо вентиль фазового запиту (або оракул), який робить те, що ми щойно описали вище: позначає один або більше вхідних базисних станів, визначених через їх представлення у вигляді бітових рядків. Вентиль MCMT використовується для реалізації мультикерованого Z-вентиля.

def grover_oracle(marked_states):
    """Build a Grover oracle for multiple marked states

    Here we assume all input marked states have the same number of bits

    Parameters:
        marked_states (str or list): Marked states of oracle

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle
    """
    if not isinstance(marked_states, list):
        marked_states = [marked_states]
    # Compute the number of qubits in circuit
    num_qubits = len(marked_states[0])

    qc = QuantumCircuit(num_qubits)
    # Mark each target state in the input list
    for target in marked_states:
        # Flip target bitstring to match Qiskit bit-ordering
        rev_target = target[::-1]
        # Find the indices of all the '0' elements in bitstring
        zero_inds = [
            ind for ind in range(num_qubits) if rev_target.startswith("0", ind)
        ]
        # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)
        # where the target bitstring has a '0' entry
        qc.x(zero_inds)
        qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)
        qc.x(zero_inds)
    return qc

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

marked_states = ["1110"]
oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

Якщо кубіти 1-3 перебувають у стані $|1\rangle$, а кубіт 0 спочатку перебуває в стані $|0\rangle$, перший X-вентиль перевернеце кубіт 0 на $|1\rangle$, і всі кубіти будуть в $|1\rangle.$ Це означає, що вентиль MCMT застосує загальну зміну знаку або перекидання фази, як потрібно. Для будь-якого іншого випадку кубіти 1-3 перебувають у стані $|0\rangle$, або кубіт 0 перевертається в стан $|0\rangle$, і перекидання фази не буде застосовано. Ми бачимо, що ця схема дійсно позначає наш бажаний стан $|0111\rangle,$ або бітовий рядок {1110}.

Повний оператор Гровера складається з вентиля фазового запиту (оракула), шарів Адамара та оператора $Z_\text{OR}$. Ми можемо використовувати вбудований grover_operator, щоб побудувати це з оракула, який ми визначили вище.

grover_op = grover_operator(oracle)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

Як ми обговорювали в геометричній картині вище, нам може знадобитися застосувати оператор Гровера кілька разів. Оптимальна кількість ітерацій $t$ для максимізації амплітуди цільового стану за відсутності шуму є

$$t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

де $|A_1|$ — кількість станів-розв'язків, а $N=2^n$ — загальна кількість станів. На сучасних шумних квантових комп'ютерах експериментально оптимальна кількість ітерацій може бути іншою — але тут ми обчислюємо і використовуємо це теоретичне, оптимальне число, використовуючи $|A_1|=1$.

optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)
print(optimal_num_iterations)

3

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

qc = QuantumCircuit(grover_op.num_qubits)
# Create even superposition of all basis states
qc.h(range(grover_op.num_qubits))
# Apply Grover operator the optimal number of times
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
# Measure all qubits
qc.measure_all()
qc.draw(output="mpl", style="iqp")

Ми побудували нашу схему Гровера!

Крок 2: Оптимізувати задачу для виконання на квантовому обладнанні

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

Нижче наведено код для збереження твоїх облікових даних при першому використанні. Обов'язково видали цю інформацію з notebook після збереження її у твоє середовище, щоб твої облікові дані не були випадково розкриті, коли ти ділишся notebook. Дивись Set up your IBM Cloud account та Initialize the service in an untrusted environment для додаткового керівництва.

# To run on hardware, select the backend with the fewest number of jobs in the queue
from qiskit_ibm_runtime import QiskitRuntimeService

# Syntax for first saving your token.  Delete these lines after saving your credentials.

# QiskitRuntimeService.save_account(channel='ibm_quantum_platform',
# instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')

# Load saved credentials
service = QiskitRuntimeService()

backend = service.least_busy(operational=True, simulator=False)
backend.name

qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:19,931: Default instance not set. Searching all available instances.

'ibm_brisbane'

Тепер ми використовуємо попередньо встановлений менеджер проходів, щоб оптимізувати нашу квантову схему для backend, який ми обрали.

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

circuit_isa = pm.run(qc)
# The transpiled circuit will be very large. Only draw it if you are really curious.
# circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

Варто зазначити в цей час, що глибина транспільованої квантової схеми є значною.

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

The total depth is  439
The depth of two-qubit gates is  113

Це фактично досить великі числа, навіть для цього простого випадку. Оскільки всі квантові вентилі (і особливо двокубітові вентилі) зазнають помилок і підлягають шуму, серія з понад 100 двокубітових вентилів призведе до нічого, окрім шуму, якщо кубіти не будуть надзвичайно високопродуктивними. Подивімося, як вони працюють.

Крок 3: Виконати, використовуючи примітиви Qiskit

Ми хочемо зробити багато вимірювань і побачити, який стан є найбільш ймовірним. Таке посилення амплітуди є задачею вибірки, яка підходить для виконання за допомогою примітиву Sampler Qiskit Runtime.

Зверни увагу, що метод run() Qiskit Runtime SamplerV2 приймає ітерацію примітивних уніфікованих блоків (PUB). Для Sampler кожен PUB є ітерацією у форматі (схема, значення_параметрів). Однак, як мінімум, він приймає список квантової(их) схеми(схем).

# To run on a real quantum computer (this was tested on a Heron r2 processor and
# used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

Щоб отримати максимум від цього досвіду, ми настійно рекомендуємо запускати твої експерименти на реальних квантових комп'ютерах, доступних від IBM Quantum. Однак, якщо ти вичерпав свій час QPU, ти можеш розкоментувати рядки нижче, щоб завершити цю активність, використовуючи симулятор.

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

Крок 4: Постобробка та повернення результату в бажаному класичному форматі

Тепер ми можемо побудувати графік результатів нашої вибірки в гістограмі.

plot_distribution(dist)

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

Перевір своє розуміння

Прочитай питання нижче, подумай над своєю відповіддю, потім натисни трикутник, щоб побачити розв'язок.

Ми щойно шукали один розв'язок у множині з $2^4=16$ можливих станів. Ми визначили оптимальну кількість повторень оператора Гровера як $t=3$. Чи це оптимальне число збільшилося б або зменшилося, якщо ми шукали (a) будь-який з кількох розв'язків, або (b) один розв'язок у просторі з більшою кількістю можливих станів?

Відповідь:

Пригадай, що поки кількість розв'язків мала в порівнянні з усім простором розв'язків, ми можемо розкласти функцію синуса навколо малих кутів і використовувати

$$(2t+1)\theta = (2t+1) \sin^{-1}{\sqrt{\frac{|\mathcal{A}_1|}{N}}}\approx (2t+1) \sqrt{\frac{|\mathcal{A}_1|}{N}} \approx \pi/2\\ t \approx \frac{\pi}{4}\sqrt{\frac{N}{|\mathcal{A}_1|}}-\frac{1}{2}$$

(a) Ми бачимо з наведеного вище виразу, що збільшення кількості станів розв'язку зменшить кількість ітерацій. За умови, що частка $\frac{|\mathcal{A}_1|}{N}$ все ще мала, ми можемо описати, як $t$ зменшиться: $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}.$

(b) Оскільки простір можливих розв'язків ($N$) збільшується, кількість необхідних ітерацій збільшується, але тільки як $t~\sqrt{N}$.

Припустимо, ми могли б збільшити розмір цільового бітового рядка до довільно великого і все одно мати результат, що цільовий стан має амплітуду ймовірності, яка принаймні на порядок більша, ніж будь-який інший стан. Чи означає це, що ми могли б використовувати алгоритм Гровера для надійного знаходження цільового стану?

Відповідь:

Ні. Припустимо, ми повторили першу активність з 20 кубітами, і ми запускаємо квантову схему певну кількість разів num_shots = 10,000. Рівномірний розподіл ймовірностей означав би, що кожен стан має ймовірність $10,000/2^{20}=0.00954$ бути виміряним навіть один раз. Якщо ймовірність вимірювання цільового стану була в 10 разів більшою, ніж для не-розв'язків (і ймовірність кожного не-розв'язку була відповідно трохи зменшена), була б лише близько 10% шансу виміряти цільовий стан навіть один раз. Було б вкрай малоймовірно виміряти цільовий стан кілька разів, що зробило б його невідрізненним від багатьох випадково отриманих станів не-розв'язків. Хороша новина полягає в тому, що ми можемо отримати результати ще більшої точності, використовуючи придушення та пом'якшення помилок.

Активність 2: Точний робочий процес алгоритму запиту

Ми почнемо цю активність точно так само, як і першу, за винятком того, що тепер ти об'єднаєшся в пару з іншим ентузіастом Qiskit. Ти обереш секретний бітовий рядок, а твій партнер обере (загалом) інший бітовий рядок. Ви кожен створите квантову схему, яка функціонує як оракул, і обміняєтеся ними. Потім ти використаєш алгоритм Гровера з цим оракулом, щоб визначити секретний бітовий рядок твого партнера.

Крок 1: Відобразити класичні входи на квантову задачу

Використовуючи функцію grover_oracle, визначену вище, побудуй схему оракула для одного або більше позначених станів. Переконайся, що ти повідомиш свого партнера, скільки станів ти позначив, щоб вони могли застосувати оператор Гровера оптимальну кількість разів. Не роби свій бітовий рядок занадто довгим. 3-5 бітів має працювати без великих труднощів. Довші бітові рядки призведуть до глибоких схем, які потребують більш просунутих технік, таких як пом'якшення помилок.

# Modify the marked states to mark those you wish to target.
marked_states = ["1000"]
oracle = grover_oracle(marked_states)

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

from qiskit import qpy

# Save to a QPY file at a location where you can easily find it.
# You might want to specify a global address.
with open("C:\\Users\\...put your own address here...\\my_circuit.qpy", "wb") as f:
    qpy.dump(oracle, f)

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

from qiskit import qpy

# Load the circuit from your partner's qpy file from the folder where you saved it.
with open("C:\\Users\\...file location here...\\my_circuit.qpy", "rb") as f:
    circuits = qpy.load(f)

# qpy.load always returns a list of circuits
oracle_partner = circuits[0]

# You could visualize the circuit, but this would break the model of a query algorithm.
# oracle_partner.draw("mpl")

Запитай свого партнера, скільки цільових станів вони закодували, і введи це нижче.

# Update according to your partner's number of target states.
num_marked_states = 1

Це використовується в наступному виразі для визначення оптимальної кількості ітерацій Гровера.

grover_op = grover_operator(oracle_partner)
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(num_marked_states / 2**grover_op.num_qubits)))
)
qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()

Крок 2: Оптимізувати задачу для виконання на квантовому обладнанні

Це проходить точно так само, як і раніше.

# To run on hardware, select the backend with the fewest number of jobs in the queue
service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
backend.name

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_partner_isa = pm.run(qc)

Крок 3: Виконати, використовуючи примітиви Qiskit

Це також ідентично процесу в першій активності.

# To run on a real quantum computer (this was tested on a Heron r2 processor and used
# 4 seconds of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_partner_isa]).result()
dist = result[0].data.meas.get_counts()

Крок 4: Постобробка та повернення результату в бажаному класичному форматі

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

plot_distribution(dist)

Перевір своє розуміння

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

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

Підказки:

• Візуалізуй/намалюй схему твого партнера та переконайся, що вона завантажилася правильно.
• Порівняй використані схеми та порівняй очікуваний результат з тим, який ти отримав.
• Перевір глибину схем, що використовуються, щоб переконатися, що бітовий рядок не був занадто довгим або кількість ітерацій Гровера непомірно високою.

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

Підказки:

• Пригадай, що завдання оракула — перевернути знак на цільовому стані.
• Пригадай, що MCMTGate перевертає знак на стані тоді і тільки тоді, коли всі кубіти, залучені до керування, перебувають у стані $|1\rangle$.
• Якщо твій цільовий стан вже матиме $|1\rangle$ на конкретному кубіті, то тобі не потрібно робити нічого з цим кубітом. Якщо твоя ціль має $|0\rangle$ на конкретному кубіті, і ти хочеш, щоб MCMTGate перевернув знак, тобі потрібно застосувати вентиль X до цього кубіта у твоєму оракулі (а потім скасувати вентиль X після MCMTGate).

Повтори експеримент з однією меншою ітерацією оператора Гровера. Чи все ще отримуєш правильну відповідь? Чому так чи ні?

Керівництво:

Ймовірно, так, хоча це може залежати від кількості закодованих розв'язків. Це підкреслює тонкість: "оптимальна" кількість ітерацій Гровера — це кількість, яка робить ймовірність вимірювання позначеного стану якомога вищою. Але менша кількість ітерацій, ніж це, може все ще зробити позначений стан істотно більш ймовірним, ніж інші стани. Тому ти можеш обійтися меншою кількістю ітерацій, ніж оптимальне число. Це зменшує глибину схеми, і таким чином зменшує рівень помилок.

Чому хтось може захотіти використовувати менше ітерацій Гровера, ніж "оптимальне число", визначене тут?

Відповідь:

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

Активність 3: Розв'яжи сітку Сапера за допомогою алгоритму Гровера

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

Доведено, що Сапер є NP-повним: його важко розв'язати, але легко перевірити. Це робить його природним кандидатом для алгоритму Гровера. Звісно, ми ще не можемо розв'язати повну сітку 9$\times$9 на шумному квантовому комп'ютері — схеми були б занадто глибокими. Замість цього ми використаємо крихітну сітку як іграшкову демонстрацію того, як підходити до більшої дошки на майбутньому відмовостійкому пристрої.

Кілька важливих застережень. Алгоритм Гровера забезпечує лише квадратичне прискорення порівняно з неструктурованим класичним пошуком. Сапер майже напевно має структуру, яку розумний класичний алгоритм може використати. І для експоненційно зростаючого простору пошуку навіть покращення $\sqrt{N}$ не йде так далеко. Але відкладемо ці проблеми осторонь і використаємо цю іграшкову задачу, щоб проілюструвати, як обмеження задачі кодуються в квантовий оракул.

Сітка

Ось наша маленька сітка Сапера:

Кожна порожня клітинка може бути представлена бінарною змінною, яка вказує, чи містить вона міну. Ми позначаємо їх $x_0$, $x_1$ та $x_2$, де $x_i = 1$ означає, що на цій клітинці є міна, а $x_i = 0$ — що немає:

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

Закодуй обмеження

Кожна пронумерована клітинка встановлює умову для сусідніх порожніх клітинок. Нам потрібно виразити ці умови як булеві вирази, які можна закодувати в квантову схему.

Клітинка "1", сусідня з $x_0$ та $x_1$, говорить, що рівно одна з них містить міну. Це саме операція виключного АБО (XOR), $\oplus$, яка повертає true, коли рівно один з її входів є true:

$$(x_0 \oplus x_1)$$

Аналогічно, інша клітинка "1" (сусідня з $x_1$ та $x_2$) дає нам:

$$(x_1 \oplus x_2)$$

Клітинка "2" говорить, що дві з трьох порожніх клітинок повинні містити міни. Оскільки XOR є операцією парності, $x_0 \oplus x_1 \oplus x_2$ повертає true, коли непарна кількість змінних є true. Ми хочемо, щоб парна кількість (конкретно дві) була true, тому заперечуємо з $\lnot$:

$$\lnot(x_0 \oplus x_1 \oplus x_2)$$

Сам по собі цей вираз задовольнявся б або нулем, або двома кубітами в стані $|1\rangle$, оскільки це твердження про парність. Але в поєднанні з двома іншими умовами, кожна з яких вимагає принаймні однієї міни, єдине задовільне присвоєння має рівно дві міни.

Усі три умови мають бути виконані одночасно, тому ми з'єднуємо їх символами і $\land$:

$$(x_0 \oplus x_1) \;\land\; (x_1 \oplus x_2) \;\land\; \lnot(x_0 \oplus x_1 \oplus x_2)$$

Крок 1: Відобразити класичні входи на квантову задачу

Тепер нам потрібно закодувати цей булевий вираз у квантову схему, яка служить оракулом. Квантова версія XOR може бути реалізована за допомогою вентилів CX (CNOT): застосування двох вентилів CX від кубітів даних до робочого (анциллярного) кубіта ефективно обчислює їх XOR і зберігає результат в анциллі.

Ми вводимо три робочі кубіти — по одному для кожної умови. Ми зберігаємо результат кожного булевого виразу у відповідному робочому кубіті, а потім використовуємо вентиль Z з множинним керуванням для перекидання фази тризубітового стану, який робить всі три робочі кубіти $|1\rangle$ (тобто всі умови виконані одночасно).

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

x = QuantumRegister(3, "x")
a = QuantumRegister(3, "a")
qc = QuantumCircuit(x, a)

# Clause 1: x0 XOR x1 -> stored in a[0]
qc.cx(x[0], a[0])
qc.cx(x[1], a[0])

# Clause 2: x1 XOR x2 -> stored in a[1]
qc.cx(x[1], a[1])
qc.cx(x[2], a[1])

# Clause 3: NOT(x0 XOR x1 XOR x2) -> stored in a[2]
qc.cx(x[0], a[2])
qc.cx(x[1], a[2])
qc.cx(x[2], a[2])
qc.x(a[2])  # The NOT

qc.draw("mpl", style="iqp")

На цьому етапі результат кожної умови зберігається у відповідному робочому кубіті. Тепер нам потрібно, щоб тризубітовий стан даних, який робить всі три робочі кубіти $|1\rangle$, отримав знак мінус. Ми робимо це за допомогою вентиля Z з множинним керуванням (реалізованого як вентиль MCX, оточений вентилями Адамара на цілі).

Після застосування перекидання фази ми повинні скасувати обчислення — скасувати всі кроки оцінки умов у зворотньому порядку — щоб скинути робочі кубіти назад до $|0\rangle.$ Це необхідно, щоб робочі кубіти були чистими для наступних ітерацій оператора Гровера.

# Multi-controlled Z: flip phase if all workspace qubits are |1>
qc.h(a[2])
qc.mcx([a[0], a[1]], a[2])
qc.h(a[2])

# Uncompute clause 3: NOT(x0 XOR x1 XOR x2)
qc.x(a[2])
qc.cx(x[2], a[2])
qc.cx(x[1], a[2])
qc.cx(x[0], a[2])

# Uncompute clause 2: x1 XOR x2
qc.cx(x[2], a[1])
qc.cx(x[1], a[1])

# Uncompute clause 1: x0 XOR x1
qc.cx(x[1], a[0])
qc.cx(x[0], a[0])

qc.draw("mpl", style="iqp")

Ця схема є нашим оракулом: вона перекидає фазу стану кубітів даних, що задовольняє всі три обмеження Сапера, і залишає робочі кубіти назад у $|0\rangle.$

Тепер ми будуємо повний оператор Гровера з цього оракула. Зверни увагу на аргумент reflection_qubits: ми передаємо лише кубіти даних x, тому що робочі кубіти не є частиною простору пошуку. Їхня робота виконана, як тільки оракул було застосовано.

grover_op = grover_operator(qc, reflection_qubits=x)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

З трьома кубітами даних та одним станом-розв'язком оптимальна кількість ітерацій Гровера є $t \approx \frac{\pi}{4}\sqrt{8} - \frac{1}{2} \approx 1.7$, тому ми використовуємо дві ітерації. Ми застосовуємо вентилі Адамара до кубітів даних для створення початкової суперпозиції, складаємо оператор Гровера двічі і вимірюємо лише кубіти даних.

x = QuantumRegister(3, "x")
a = QuantumRegister(4, "a")
meas = ClassicalRegister(3, "meas")

qc = QuantumCircuit(x, a, meas)
# Create superposition over the data qubits only
qc.h(x)
# Apply 2 iterations of the Grover operator
qc.compose(grover_op.power(2), inplace=True)
# Measure only the data qubits
qc.measure(x, meas)
qc.decompose().draw(output="mpl", style="iqp")

Крок 2: Оптимізувати задачу для виконання на квантовому обладнанні

Як і раніше, ми транспілюємо схему для цільового бекенду.

service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
print(backend.name)

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_isa = pm.run(qc)

Тепер ми можемо перевірити глибину транспільованої схеми. Оскільки оракул Сапера використовує робочі кубіти та кілька вентилів CX, транспільована схема буде глибшою, ніж схеми з попередніх активностей.

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

Крок 3: Виконати, використовуючи примітиви Qiskit

# To run on a real quantum computer (this was tested on a Heron r2 processor and
#  used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

Крок 4: Постобробка та повернення результату в бажаному класичному форматі

plot_distribution(dist)

Стан 101 повинен з'явитися з набагато вищою ймовірністю, ніж будь-який інший, що вказує на те, що міни розташовані на $x_0$ та $x_2$. Ми використали квантовий комп'ютер для розв'язання крихітної гри Сапер!

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

Питання та ключові концепції:

Ключові концепції:

У цьому модулі ми дізналися деякі ключові особливості алгоритму Гровера:

• У той час як класичні алгоритми неструктурованого пошуку вимагають кількості запитів, яка масштабується лінійно з розміром простору, $N,$ алгоритм Гровера вимагає кількості запитів або обчислень $f$, яка масштабується як $\sqrt{N}.$
• Алгоритм Гровера включає повторення серії операцій (зазвичай називається "оператор Гровера") певну кількість разів $t,$ обрану для того, щоб цільові стани оптимально ймовірно були виміряні.
• Алгоритм Гровера може бути запущений з меншою кількістю ітерацій, ніж $t$, і все ще посилює цільові стани.
• Алгоритм Гровера вписується в модель обчислень запиту і має найбільший сенс, коли одна особа контролює пошук, а інша контролює/конструює оракул. Він також може бути корисним як підпрограма в інших квантових обчисленнях.
• Оракул можна побудувати з обмежень задачі, а не зі знання розв'язку, як продемонстровано на прикладі Сапера.

Питання правда/неправда:

1. П/Н Алгоритм Гровера забезпечує експоненціальне покращення порівняно з класичними алгоритмами в кількості запитів, необхідних для знаходження одного позначеного стану в неструктурованому пошуку.

2. П/Н Алгоритм Гровера працює шляхом ітеративного збільшення ймовірності того, що стан розв'язку буде виміряний.

3. П/Н Чим більше разів ти ітеруєш оператор Гровера, тим вища ймовірність вимірювання стану розв'язку.

Питання з множинним вибором:

1. Вибери найкращий варіант для завершення речення. Найкраща стратегія для успішного використання алгоритму Гровера на сучасних квантових комп'ютерах полягає в ітерації оператора Гровера...

• a. Тільки один раз.
• b. Завжди $t$ разів, щоб максимізувати амплітуду ймовірності стану(ів) розв'язку.
• c. До $t$ разів, хоча менше може бути достатньо, щоб зробити стани розв'язку виділеними.
• d. Не менше 10 разів.

2. Схема фазового запиту показана тут, яка функціонує як оракул для позначення певного стану перекиданням фази. Який з наступних станів позначається цією схемою?

• a. $|0000\rangle$
• b. $|0101\rangle$
• c. $|0110\rangle$
• d. $|1001\rangle$
• e. $|1010\rangle$
• f. $|1111\rangle$

3. Припустимо, ти хочеш шукати три позначені стани з множини 128. Яка оптимальна кількість ітерацій оператора Гровера для максимізації амплітуд позначених станів?

• a. 1
• b. 3
• c. 5
• d. 6
• e. 20
• f. 33

Питання для обговорення:

1. Які ще задачі ти міг би сформулювати як пошук Гровера? Подумай про задачі, в яких важко знайти розв'язок, але легко його перевірити.

2. Чи бачиш ти якісь проблеми зі масштабуванням алгоритму Гровера на сучасних квантових комп'ютерах?