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

Для цього модуля 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®.

Очевидне застереження

Щоб застосувати алгоритм Гровера, нам потрібно було побудувати оператор Гровера, що означає, що ми повинні мати змогу перевернути фазу на станах, які задовольняють наші критерії розв'язку. Це викликає питання: якщо ми так добре знаємо наш набір розв'язків, що можемо спроектувати квантову схему для позначення кожного з них, що ми шукаємо?! Відповідь є троякою, і ми повернемося до цього протягом підручника:

(1) Ці види алгоритмів запитів часто включають дві сторони: одна, яка має оракул, що встановлює критерії розв'язку, і інша, яка намагається вгадати/знайти стан розв'язку. Той факт, що одна особа може побудувати оракул, не заперечує потреби в пошуку.

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

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

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

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

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

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit
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,$ для максимізації амплітуди цільового стану за відсутності шуму можна отримати з цього виразу:

$$(2t+1)\theta = (2t+1)\sin^{-1}\left( \sqrt{\frac{|A_1|}{N}}\right) \approx (2t+1)\sqrt{\frac{|A_1|}{N}} \approx \frac{\pi}{2}\\ t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

Тут $A_1$ — кількість розв'язків або цільових станів. На сучасних шумних квантових комп'ютерах експериментально оптимальна кількість ітерацій може бути іншою — але тут ми обчислюємо і використовуємо це теоретичне, оптимальне число, використовуючи $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 двокубітових вентилів призведе до нічого, окрім шуму, якщо кубіти не будуть надзвичайно високопродуктивними. Давайте подивимося, як вони працюють.

Виконати, використовуючи примітиви 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: Критерій, відмінний від конкретного бітового рядка

Як остання ілюстрація того, як алгоритм Гровера може бути корисним в контексті підпрограми, уявімо, що нам потрібні квантові стани з певною кількістю 1 у представленні бітового рядка. Це є поширеним у ситуаціях, де задіяні закони збереження. Наприклад, в контексті квантової хімії часто відображають стан 1 кубіта на зайнятість електронної орбіталі. Щоб заряд був збережений, загальна кількість 1 також має залишатися постійною. Обмеження на зразок цих є настільки поширеними, що мають спеціальну назву: обмеження ваги Хемінга, і кількість 1 у стані називається вагою Хемінга.

Крок 1:

Спочатку напишемо функцію, яка позначає стани з бажаною вагою Хемінга. Ми напишемо це загалом для невказаної кількості кубітів num_qubits та цільової ваги Хемінга target_weight.

from qiskit import QuantumCircuit

def grover_oracle_hamming_weight(num_qubits, target_weight):
    """
    Build a Grover oracle that marks all states with Hamming weight == target_weight.

    Parameters:
        num_qubits (int): Number of qubits in the circuit.
        target_weight (int): The Hamming weight to mark.

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle.
    """
    qc = QuantumCircuit(num_qubits)
    marked_count = 0
    marked_list = []
    for x in range(2**num_qubits):
        bitstr = format(x, f"0{num_qubits}b")
        if bitstr.count("1") == target_weight:
            # Count the number of target states
            marked_count = marked_count + 1
            marked_list.append(bitstr)
            # Reverse for Qiskit bit order (qubit 0 is rightmost)
            rev_target = bitstr[::-1]
            zero_inds = [i for i, b in enumerate(rev_target) if b == "0"]
            # Apply X gates to 'open' controls (where bit is 0)
            qc.x(zero_inds)
            # Multi-controlled Z (as MCX conjugated by H)
            if num_qubits == 1:
                qc.z(0)
            else:
                qc.h(num_qubits - 1)
                qc.mcx(list(range(num_qubits - 1)), num_qubits - 1)
                qc.h(num_qubits - 1)
            # Undo X gates
            qc.x(zero_inds)
    return qc, marked_count, marked_list

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(3, 2)
print(marked_states)
oracle.draw(output="mpl", style="iqp")

['011', '101', '110']

Звідси весь процес ідентичний процесу з попередніх двох активностей. Для стислості, кроки Qiskit patterns показані тільки в коментарях коду тут.

from qiskit_ibm_runtime import SamplerV2 as Sampler

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(4, 2)
oracle.draw(output="mpl", style="iqp")

grover_op = grover_operator(oracle)
grover_op.decompose().draw(output="mpl", style="iqp")
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(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()
qc.draw(output="mpl", style="iqp")

# Step 2: Optimize for running on real quantum computers

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)

# Step 3: Execute using Qiskit primitives
# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 seconds of QPU time)

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()

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

ibm_brisbane

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  502
The depth of two-qubit gates is  130

num_marked_states

6

plot_distribution(dist)

Тут алгоритм Гровера дійсно підготував стани з вагою Хемінга 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. Чи бачите Виякісь проблеми зі масштабуванням алгоритму Гровера на сучасних квантових комп'ютерах?