Пом'якшення помилок зчитування для примітива Sampler з використанням M3

Оцінка використання: менше однієї хвилини на процесорі Heron r2 (ПРИМІТКА: Це лише оцінка. Ваш час виконання може відрізнятися.)

Передумови

На відміну від примітива Estimator, примітив Sampler не має вбудованої підтримки для пом'якшення помилок. Декілька методів, що підтримуються Estimator, спеціально розроблені для очікуваних значень, і тому не застосовні до примітива Sampler. Винятком є пом'якшення помилок зчитування, яке є високоефективним методом, що також застосовується до примітива Sampler.

Доповнення M3 для Qiskit реалізує ефективний метод для пом'якшення помилок зчитування. Цей підручник пояснює, як використовувати доповнення M3 для Qiskit для пом'якшення помилок зчитування для примітива Sampler.

Що таке помилка зчитування?

Безпосередньо перед вимірюванням стан регістра кубітів описується суперпозицією станів обчислювального базису, або матрицею щільності. Вимірювання регістра кубітів у класичний бітовий регістр потім відбувається у два кроки. Спочатку виконується власне квантове вимірювання. Це означає, що стан регістра кубітів проектується на єдиний базисний стан, який характеризується рядком з $1$ та $0$. Другий крок полягає у зчитуванні бітового рядка, що характеризує цей базисний стан, і записі його в пам'ять класичного комп'ютера. Цей крок ми називаємо зчитуванням. Виявляється, що другий крок (зчитування) створює більше помилок, ніж перший крок (проекція на базисні стани). Це має сенс, коли Ви пригадуєте, що зчитування вимагає виявлення мікроскопічного квантового стану та його посилення до макроскопічного рівня. Резонатор зчитування з'єднується з (трансмонним) кубітом, таким чином зазнаючи дуже малого зсуву частоти. Мікрохвильовий імпульс потім відбивається від резонатора, у свою чергу зазнаючи малих змін у його характеристиках. Відбитий імпульс потім посилюється та аналізується. Це делікатний процес і він піддається безлічі помилок.

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

Теоретичні передумови

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

Точніше, для кожної пари бітових рядків $(i, j)$, існує (умовна) ймовірність ${M}_{i,j}$ того, що $i$ прочитано, за умови що справжнє значення є $j.$ Тобто,

$${M}_{i,j} = \Pr(\text{readout value is } i | \text{true value is } j) \text{ for } i,j \in (0,...,2^n - 1), \tag{1}$$

де $n$ — це кількість бітів у регістрі зчитування. Для конкретності, ми припускаємо, що $i$ є десятковим цілим числом, двійкове представлення якого є бітовим рядком, який позначає стани обчислювального базису. Ми називаємо матрицю ${M}$ розміру $2^n \times 2^n$ матрицею призначення. Для фіксованого справжнього значення $j$, сумування ймовірності по всіх зашумлених результатах $i$ повинно давати $1$. Тобто

$$\sum_{i=0}^{2^n - 1} {M}_{i,j} = 1 \text{ for all } j$$

Матриця без від'ємних записів, яка задовольняє (1), називається ліво-стохастичною. Ліво-стохастична матриця також називається стовпцево-стохастичною, тому що кожен з її стовпців дає суму $1$. Ми експериментально визначаємо приблизні значення для кожного елемента ${M}_{i,j}$, повторно підготовляючи кожен базисний стан $|j \rangle$ і потім обчислюючи частоти появи відібраних бітових рядків.

Якщо експеримент передбачає оцінювання розподілу ймовірностей над вихідними бітовими рядками шляхом повторної вибірки, то ми можемо використовувати ${M}$ для пом'якшення помилки зчитування на рівні розподілу. Перший крок полягає у повторенні фіксованої схеми інтересу багато разів, створюючи гістограму відібраних бітових рядків. Нормалізована гістограма є виміряним розподілом ймовірностей над $2^n$ можливими бітовими рядками, який ми позначаємо як ${\tilde{p}} \in \mathbb{R}^{2^n}$. (Оцінена) ймовірність ${{\tilde{p}}}_i$ відбору бітового рядка $i$ дорівнює сумі по всіх справжніх бітових рядках $j$, кожен з яких зважений ймовірністю того, що він помилково прийнятий за $i$. Це твердження в матричній формі є

$${\tilde{p}} = {M} {\vec{p}}, \tag{2},$$

де ${\vec{p}}$ — це справжній розподіл. Словами, помилка зчитування має ефект множення ідеального розподілу над бітовими рядками ${\vec{p}}$ на матрицю призначення ${M}$ для отримання спостережуваного розподілу ${\tilde{p}}$. Ми виміряли ${\tilde{p}}$ та ${M}$, але не маємо прямого доступу до ${\vec{p}}$. У принципі, ми отримаємо справжній розподіл бітових рядків для нашої схеми, розв'язуючи рівняння (2) для ${\vec{p}}$ чисельно.

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

• На практиці рівняння (2) не розв'язується інверсією ${M}$. Процедури лінійної алгебри у програмних бібліотеках використовують методи, які є більш стабільними, точними та ефективними.
• При оцінюванні ${M}$, ми припускали, що сталися лише помилки зчитування. Зокрема, ми припускаємо, що не було помилок підготовки стану та квантового вимірювання — або принаймні, що вони були іншим чином пом'якшені. Наскільки це є хорошим припущенням, ${M}$ дійсно представляє лише помилку зчитування. Але коли ми використовуємо ${M}$ для виправлення виміряного розподілу над бітовими рядками, ми не робимо такого припущення. Насправді, ми очікуємо, що цікава схема вноситиме шум, наприклад, помилки воріт. "Справжній" розподіл все ще включає ефекти від будь-яких помилок, які не пом'якшені іншим чином.

Цей метод, хоча корисний у деяких обставинах, має кілька обмежень.

Просторові та часові ресурси, необхідні для оцінювання ${M}$, зростають експоненційно в $n$:

• Оцінювання ${M}$ та ${\tilde{p}}$ піддається статистичній помилці через кінцеву вибірку. Цей шум може бути зроблений таким малим, як бажано, за рахунок більшої кількості вимірів (до часової шкали дрейфу параметрів обладнання, що призводить до систематичних помилок у ${M}$). Однак, якщо не робиться припущень щодо бітових рядків, спостережуваних при виконанні пом'якшення, кількість вимірів, необхідних для оцінювання ${M}$, зростає принаймні експоненційно в $n$.
• ${M}$ є матрицею $2^n \times 2^n$. Коли $n>10$, обсяг пам'яті, необхідний для зберігання ${M}$, перевищує пам'ять, доступну на потужному ноутбуці.

Подальші обмеження:

• Відновлений розподіл ${\vec{p}}$ може мати одну або більше від'ємних ймовірностей (хоча все ще дає суму один). Одне рішення — мінімізувати $||{M} {\vec{p}} - {\tilde{p}}||^2$ за умови обмеження, що кожен запис у ${\vec{p}}$ є невід'ємним. Однак, час виконання такого методу на порядки довший, ніж пряме розв'язання рівняння (2).
• Ця процедура пом'якшення працює на рівні розподілу ймовірностей над бітовими рядками. Зокрема, вона не може виправити помилку в окремому спостережуваному бітовому рядку.

Доповнення M3 для Qiskit: Масштабування до довших бітових рядків

Розв'язання рівняння (2) за допомогою стандартних процедур чисельної лінійної алгебри обмежене бітовими рядками не довшими приблизно за 10 біт. M3, однак, може обробляти набагато довші бітові рядки. Дві ключові властивості M3, які роблять це можливим:

• Кореляції в помилках зчитування порядку три та вище серед колекцій бітів вважаються незначними та ігноруються. У принципі, за рахунок більшої кількості вимірів, можна також оцінити вищі кореляції.
• Замість того, щоб конструювати ${M}$ явно, ми використовуємо набагато меншу ефективну матрицю, яка записує ймовірності лише для бітових рядків, зібраних при конструюванні ${\tilde{p}}$.

На високому рівні процедура працює наступним чином.

Спочатку ми конструюємо будівельні блоки, з яких ми можемо побудувати спрощений, ефективний, опис ${M}$. Потім ми повторно виконуємо схему інтересу та збираємо бітові рядки, які ми використовуємо для конструювання як ${\tilde{p}}$, так і, за допомогою будівельних блоків, ефективної ${M}$.

Точніше,

• Матриці призначення для одного кубіта оцінюються для кожного кубіта. Для цього ми повторно підготовляємо регістр кубітів у стані всіх нулів $|0 ... 0 \rangle$, а потім у стані всіх одиниць $|1 ... 1 \rangle$, і записуємо ймовірність для кожного кубіта, що він прочитаний неправильно.

• Кореляції порядку три та вище вважаються незначними та ігноруються.

  Натомість ми конструюємо число $n$ матриць призначення для одного кубіта розміру $2 \times 2$, і число $n(n-1)/2$ матриць призначення для двох кубітів розміру $4 \times 4$. Ці матриці призначення для одного та двох кубітів зберігаються для подальшого використання.

• Після повторної вибірки схеми для конструювання ${\tilde{p}}$, ми конструюємо ефективне наближення до ${M}$, використовуючи лише бітові рядки, які відібрані при конструюванні ${\tilde{p}}$. Ця ефективна матриця будується за допомогою матриць для одного та двох кубітів, описаних у попередньому пункті. Лінійна розмірність цієї матриці є щонайбільше порядку кількості вимірів, використаних при конструюванні ${\tilde{p}}$, що є набагато меншою за розмірність $2^n$ повної матриці призначення ${M}$.

Для технічних деталей про M3 Ви можете звернутися до Scalable Mitigation of Measurement Errors on Quantum Computers.

Застосування M3 до квантового алгоритму

Ми застосуємо пом'якшення помилок зчитування M3 до проблеми прихованого зсуву. Проблема прихованого зсуву, та близькі пов'язані проблеми, такі як проблема прихованої підгрупи, були спочатку задумані у налаштуванні відмовостійкості (точніше, перед тим, як відмовостійкі квантові процесори були доведені як можливі!). Але вони також вивчаються з доступними процесорами. Приклад алгоритмічного експоненційного прискорення, отриманого для варіанту проблеми прихованого зсуву, отриманого на 127-кубітних квантових процесорах IBM®, можна знайти в цій статті (версія arXiv).

У наступному всі арифметичні операції є булевими. Тобто, для $a, b \in \mathbb{Z}_2 = \{0, 1\}$, додавання, $a + b$ є логічною функцією XOR. Крім того, множення $a \times b$ (або $a b$) є логічною функцією AND. Для $x, y \in \{0, 1\}^n$, $x + y$ визначається побітовим застосуванням XOR. Скалярний добуток $\cdot: {\mathbb{Z}_2^n} \rightarrow \mathbb{Z}_2$ визначається як $x \cdot y = \sum_i x_i y_i$.

Оператор Адамара та перетворення Фур'є

У реалізації квантових алгоритмів дуже поширеним є використання оператора Адамара як перетворення Фур'є. Стани обчислювального базису іноді називаються класичними станами. Вони знаходяться у взаємно-однозначному відношенні з класичними бітовими рядками. $n$-кубітний оператор Адамара на класичних станах може розглядатися як перетворення Фур'є на булевому гіперкубі:

$$H^{\otimes n} = \frac{1}{\sqrt{2^n}} \sum_{x,y \in {\mathbb{Z}_2^n}} (-1)^{x \cdot y} {|{y}\rangle}{\langle{x}|}.$$

Розглянемо стан ${|{s}\rangle}$, що відповідає фіксованому бітовому рядку $s$. Застосовуючи $H^{\otimes n}$, та використовуючи ${\langle {x}|{s}\rangle} = \delta_{x,s}$, ми бачимо, що перетворення Фур'є від ${|{s}\rangle}$ може бути записане як

$$H^{\otimes n} {|{s}\rangle} = \frac{1}{\sqrt{2^n}} \sum_{y \in {\mathbb{Z}_2^n}} (-1)^{s \cdot y} {|{y}\rangle}.$$

Адамар є своїм власним оберненим, тобто, $H^{\otimes n} H^{\otimes n} = (H H)^{\otimes n} = I^{\otimes n}$. Таким чином, обернене перетворення Фур'є є тим самим оператором, $H^{\otimes n}$. Явно, ми маємо,

$${|{s}\rangle} = H^{\otimes n} H^{\otimes n} {|{s}\rangle} = H^{\otimes n} \frac{1}{\sqrt{2^n}} \sum_{y \in {\mathbb{Z}_2^n}} (-1)^{s \cdot y} {|{y}\rangle}.$$

Проблема прихованого зсуву

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

Нехай $x,y \in {\mathbb{Z}_2^m}$ є бітовими рядками довжини $m$. Ми визначаємо ${f}: {\mathbb{Z}_2^m} \times {\mathbb{Z}_2^m} \rightarrow \{-1,1\}$ як

$${f}(x, y) = (-1)^{x \cdot y}.$$

Нехай $a,b \in {\mathbb{Z}_2^m}$ є фіксованими бітовими рядками довжини $m$. Ми далі визначаємо $g: {\mathbb{Z}_2^m} \times {\mathbb{Z}_2^m} \rightarrow \{-1,1\}$ як

$$g(x, y) = {f}(x+a, y+b) = (-1)^{(x+a) \cdot (y+b)},$$

де $a$ та $b$ є (прихованими) параметрами. Нам дано дві чорні скриньки, одна реалізує $f$, а інша $g$. Ми припускаємо, що знаємо, що вони обчислюють функції, визначені вище, за винятком того, що ми не знаємо ні $a$, ні $b$. Гра полягає у визначенні прихованих бітових рядків (зсувів) $a$ та $b$ шляхом виконання запитів до $f$ та $g$. Зрозуміло, що якщо ми граємо класично, нам потрібні $O(2m)$ запити для визначення $a$ та $b$. Наприклад, ми можемо запитувати $g$ з усіма парами рядків таким чином, що один елемент пари всі нулі, а інший елемент має рівно один елемент встановлений у $1$. На кожному запиті ми дізнаємось один елемент або $a$, або $b$. Однак, ми побачимо, що, якщо чорні скриньки реалізовані як квантові схеми, ми можемо визначити $a$ та $b$ з одним запитом до кожної з $f$ та $g$.

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

Квантові схеми для $f$ та $g$

Нам потрібні наступні інгредієнти для реалізації $f$ та $g$ як квантових схем.

Для однокубітних класичних станів ${|{x_1}\rangle}, {|{y_1}\rangle}$, з $x_1,y_1 \in \mathbb{Z}_2$, керований-$Z$ вентиль ${CZ}$ може бути записаний як

$${CZ} {|{x_1}\rangle}{|{y_1}\rangle}{x_1} = (-1)^{x_1 y_1} {|{x_1}\rangle}{x_1}{|{y_1}\rangle}.$$

Ми будемо оперувати з $m$ вентилями CZ, одним на $(x_1, y_1)$, та одним на $(x_2, y_2)$, і так далі, через $(x_m, y_m)$. Ми називаємо цей оператор ${CZ}_{x,y}$.

$U_f = {CZ}_{x,y}$ є квантовою версією ${f} = {f}(x,y)$:

$$U_f {|{x}\rangle}{|{y}\rangle} = {CZ}_{x,y} {|{x}\rangle}{|{y}\rangle} = (-1)^{x \cdot y} {|{x}\rangle}{|{y}\rangle}.$$

Нам також потрібно реалізувати зсув бітового рядка. Ми позначаємо оператор на регістрі $x$ $X^{a_1}\cdots X^{a_m}$ як $X_a$ і аналогічно на регістрі $y$ $X_b = X^{b_1}\cdots X^{b_m}$. Ці оператори застосовують $X$ там, де окремий біт є $1$, та тотожність $I$ там, де він $0$. Тоді ми маємо

$$X_a X_b {|{x}\rangle}{|{y}\rangle} = {|{x+a}\rangle}{|{y+b}\rangle}.$$

Друга чорна скринька $g$ реалізується унітарним оператором $U_g$, заданим

$$U_g = X_aX_b {CZ}_{x,y} X_aX_b.$$

Щоб побачити це, ми застосовуємо оператори справа наліво до стану ${|{x}\rangle}{|{y}\rangle}$. Спочатку

$$X_a X_b {|{x}\rangle}{|{y}\rangle} = {|{x+a}\rangle}{|{y+b}\rangle}.$$

Потім,

$${CZ}_{x,y} {|{x+a}\rangle}{|{y+b}\rangle} = (-1)^{(x+a)\cdot (y+b)} {|{x+a}\rangle}{|{y+b}\rangle}.$$

Нарешті,

$$X^a X^b (-1)^{(x+a)\cdot (y+b)} {|{x+a}\rangle}{|{y+b}\rangle} = (-1)^{(x+a)\cdot (y+b)} {|{x}\rangle}{|{y}\rangle},$$

що дійсно є квантовою версією $f(x+a, y+b)$.

Алгоритм прихованого зсуву

Тепер ми збираємо частини разом для розв'язання проблеми прихованого зсуву. Ми починаємо із застосування Адамарів до регістрів, ініціалізованих у стані всіх нулів.

$$H^{\otimes 2m} = H^{\otimes m} \otimes H^{\otimes m} {{|{0}\rangle}^{\otimes m}}{{|{0}\rangle}^{\otimes m}} = \frac{1}{\sqrt{2^{2m}}} \sum_{x, y \in {\mathbb{Z}_2^m}} (-1)^{x \cdot y} {|{x}\rangle}{|{y}\rangle}.$$

Далі, ми запитуємо оракул $g$, щоб прийти до

$$U_g H^{\otimes 2m} {{|{0}\rangle}^{\otimes m}}{{|{0}\rangle}^{\otimes m}} = \frac{1}{\sqrt{2^{2m}}} \sum_{x, y \in {\mathbb{Z}_2^m}} (-1)^{(x+a) \cdot (y+b)} {|{x}\rangle}{|{y}\rangle}$$ $$\approx \frac{1}{\sqrt{2^{2m}}} \sum_{x, y \in {\mathbb{Z}_2^m}} (-1)^{x \cdot y + x \cdot b + y \cdot a} {|{x}\rangle}{|{y}\rangle}.$$

В останньому рядку ми опустили постійний глобальний фазовий фактор $(-1)^{a \cdot b}$, та позначаємо рівність з точністю до фази як $\approx$. Далі, застосування оракула $f$ вводить інший фактор $(-1)^{x \cdot y}$, скасовуючи той, що вже присутній. Тоді ми маємо:

$$U_f U_g H^{\otimes 2m} {{|{0}\rangle}^{\otimes m}}{{|{0}\rangle}^{\otimes m}} \approx \frac{1}{\sqrt{2^{2m}}} \sum_{x, y \in {\mathbb{Z}_2^m}} (-1)^{x \cdot b + y \cdot a} {|{x}\rangle}{|{y}\rangle}.$$

Останній крок — застосувати обернене перетворення Фур'є, $H^{\otimes 2m} = H^{\otimes m} \otimes H^{\otimes m}$, що призводить до

$$H^{\otimes 2m} U_f U_g H^{\otimes 2m} {{|{0}\rangle}^{\otimes m}}{{|{0}\rangle}^{\otimes m}} \approx {|{b}\rangle}{|{a}\rangle}.$$

Схема завершена. За відсутності шуму відбір квантових регістрів поверне бітові рядки $b, a$ з ймовірністю $1$.

Булевий внутрішній добуток є прикладом так званих зігнутих функцій. Ми не будемо визначати зігнуті функції тут, але лише зазначимо, що вони "максимально стійкі проти атак, які намагаються експлуатувати залежність виходів від деякого лінійного підпростору входів." Ця цитата з статті Quantum algorithms for highly non-linear Boolean functions, яка дає ефективні алгоритми прихованого зсуву для декількох класів зігнутих функцій. Алгоритм у цьому підручнику з'являється в розділі 3.1 статті.

У більш загальному випадку схема для знаходження прихованого зсуву $s \in \mathbb{Z}^n$ є

$$H^{\otimes n} U_{\tilde{f}} H^{\otimes n} U_g H^{\otimes n} {|{0}\rangle}^{\otimes n} = {|{s}\rangle}.$$

У загальному випадку $f$ та $g$ є функціями однієї змінної. Наш приклад внутрішнього добутку має цю форму, якщо ми дозволимо $f(x, y) \to f(z)$, з $z$, що дорівнює конкатенації $x$ та $y$, та $s$, що дорівнює конкатенації $a$ та $b$. Загальний випадок вимагає рівно двох оракулів: Один оракул для $g$ та один для $\tilde{f}$, де останній є функцією, відомою як дуальна для зігнутої функції $f$. Функція внутрішнього добутку має самодуальну властивість $\tilde{f}=f$.

У нашій схемі для прихованого зсуву на внутрішньому добутку ми опустили середній шар Адамарів, який з'являється в схемі для загального випадку. Хоча в загальному випадку цей шар є необхідним, ми заощадили трохи глибини, опустивши його, за рахунок трохи пост-обробки, тому що вихід є ${|{b}\rangle}{|{a}\rangle}$ замість бажаного ${|{a}\rangle}{|{b}\rangle}$.

Вимоги

Перед початком цього навчального посібника переконайтеся, що у Вас встановлено наступне:

• Qiskit SDK v2.1 або новіша версія, з підтримкою візуалізації
• Qiskit Runtime v0.41 або новіша версія (pip install qiskit-ibm-runtime)
• M3 Qiskit addon v3.0 (pip install mthree)

Налаштування

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

from collections.abc import Iterator, Sequence
from random import Random
from qiskit.circuit import (
    CircuitInstruction,
    QuantumCircuit,
    QuantumRegister,
    Qubit,
)
from qiskit.circuit.library import CZGate, HGate, XGate
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
from qiskit_ibm_runtime import QiskitRuntimeService
import timeit
import matplotlib.pyplot as plt
from qiskit_ibm_runtime import SamplerV2 as Sampler
import mthree

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

Спочатку ми напишемо функції для реалізації задачі прихованого зсуву у вигляді QuantumCircuit.

def apply_hadamards(qubits: Sequence[Qubit]) -> Iterator[CircuitInstruction]:
    """Apply a Hadamard gate to every qubit."""
    for q in qubits:
        yield CircuitInstruction(HGate(), [q], [])

def apply_shift(
    qubits: Sequence[Qubit], shift: int
) -> Iterator[CircuitInstruction]:
    """Apply X gates where the bits of the shift are equal to 1."""
    for i, q in zip(range(shift.bit_length()), qubits):
        if shift >> i & 1:
            yield CircuitInstruction(XGate(), [q], [])

def oracle_f(qubits: Sequence[Qubit]) -> Iterator[CircuitInstruction]:
    """Apply the f oracle."""
    for i in range(0, len(qubits) - 1, 2):
        yield CircuitInstruction(CZGate(), [qubits[i], qubits[i + 1]])

def oracle_g(
    qubits: Sequence[Qubit], shift: int
) -> Iterator[CircuitInstruction]:
    """Apply the g oracle."""
    yield from apply_shift(qubits, shift)
    yield from oracle_f(qubits)
    yield from apply_shift(qubits, shift)

def determine_hidden_shift(
    qubits: Sequence[Qubit], shift: int
) -> Iterator[CircuitInstruction]:
    """Determine the hidden shift."""
    yield from apply_hadamards(qubits)
    yield from oracle_g(qubits, shift)
    # We omit this layer in exchange for post processing
    # yield from apply_hadamards(qubits)
    yield from oracle_f(qubits)
    yield from apply_hadamards(qubits)

def run_hidden_shift_circuit(n_qubits, rng):
    hidden_shift = rng.getrandbits(n_qubits)

    qubits = QuantumRegister(n_qubits, name="q")
    circuit = QuantumCircuit.from_instructions(
        determine_hidden_shift(qubits, hidden_shift), qubits=qubits
    )
    circuit.measure_all()
    # Format the hidden shift as a string.
    hidden_shift_string = format(hidden_shift, f"0{n_qubits}b")
    return (circuit, hidden_shift, hidden_shift_string)

def display_circuit(circuit):
    return circuit.remove_final_measurements(inplace=False).draw(
        "mpl", idle_wires=False, scale=0.5, fold=-1
    )

Ми почнемо з невеликого прикладу:

n_qubits = 6
random_seed = 12345
rng = Random(random_seed)
circuit, hidden_shift, hidden_shift_string = run_hidden_shift_circuit(
    n_qubits, rng
)

print(f"Hidden shift string {hidden_shift_string}")

display_circuit(circuit)

Hidden shift string 011010

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

job_tags = [
    f"shift {hidden_shift_string}",
    f"n_qubits {n_qubits}",
    f"seed = {random_seed}",
]
job_tags

['shift 011010', 'n_qubits 6', 'seed = 12345']

# Uncomment this to run the circuits on a quantum computer on IBMCloud.
service = QiskitRuntimeService()
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=100
)

# from qiskit_ibm_runtime.fake_provider import FakeMelbourneV2
# backend = FakeMelbourneV2()
# backend.refresh(service)

print(f"Using backend {backend.name}")

def get_isa_circuit(circuit, backend):
    pass_manager = generate_preset_pass_manager(
        optimization_level=3, backend=backend, seed_transpiler=1234
    )
    isa_circuit = pass_manager.run(circuit)
    return isa_circuit

isa_circuit = get_isa_circuit(circuit, backend)
display_circuit(isa_circuit)

Using backend ibm_kingston

Крок 3: Виконання схем за допомогою примітивів Qiskit

# submit job for solving the hidden shift problem using the Sampler primitive
NUM_SHOTS = 50_000

def run_sampler(backend, isa_circuit, num_shots):
    sampler = Sampler(mode=backend)
    sampler.options.environment.job_tags
    pubs = [(isa_circuit, None, NUM_SHOTS)]
    job = sampler.run(pubs)
    return job

def setup_mthree_mitigation(isa_circuit, backend):
    # retrieve the final qubit mapping so mthree knows which qubits to calibrate
    qubit_mapping = mthree.utils.final_measurement_mapping(isa_circuit)

    # submit jobs for readout error calibration
    mit = mthree.M3Mitigation(backend)
    mit.cals_from_system(qubit_mapping, rep_delay=None)

    return mit, qubit_mapping

job = run_sampler(backend, isa_circuit, NUM_SHOTS)
mit, qubit_mapping = setup_mthree_mitigation(isa_circuit, backend)

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

У теоретичному обговоренні вище ми визначили, що для входу $ab$ ми очікуємо вихід $ba$. Додаткове ускладнення полягає в тому, що для того, щоб мати простішу (до транспіляції) схему, ми вставили необхідні CZ гейти між сусідніми парами кубітів. Це означає чергування бітових рядків $a$ і $b$ як $a1 b1 a2 b2 \ldots$. Вихідний рядок $ba$ буде чергуватися подібним чином: $b1 a1 b2 a2 \ldots$. Функція unscramble нижче перетворює вихідний рядок з $b1 a1 b2 a2 \ldots$ на $a1 b1 a2 b2 \ldots$ так, щоб вхідні та вихідні рядки можна було порівняти безпосередньо.

# retrieve bitstring counts
def get_bitstring_counts(job):
    result = job.result()
    pub_result = result[0]
    counts = pub_result.data.meas.get_counts()
    return counts, pub_result

counts, pub_result = get_bitstring_counts(job)

Відстань Хеммінга між двома бітовими рядками - це кількість індексів, на яких біти відрізняються.

def hamming_distance(s1, s2):
    weight = 0
    for c1, c2 in zip(s1, s2):
        (c1, c2) = (int(c1), int(c2))
        if (c1 == 1 and c2 == 1) or (c1 == 0 and c2 == 0):
            weight += 1

    return weight

# Replace string of form a1b1a2b2... with b1a1b2a1...
# That is, reverse order of successive pairs of bits.
def unscramble(bitstring):
    ps = [bitstring[i : i + 2][::-1] for i in range(0, len(bitstring), 2)]
    return "".join(ps)

def find_hidden_shift_bitstring(counts, hidden_shift_string):
    # convert counts to probabilities
    probs = {
        unscramble(bitstring): count / NUM_SHOTS
        for bitstring, count in counts.items()
    }

    # Retrieve the most probable bitstring.
    most_probable = max(probs, key=lambda x: probs[x])

    print(f"Expected hidden shift string: {hidden_shift_string}")
    if most_probable == hidden_shift_string:
        print("Most probable bitstring matches hidden shift 😊.")
    else:
        print("Most probable bitstring didn't match hidden shift ☹️.")
    print("Top 10 bitstrings and their probabilities:")
    display(
        {
            k: (v, hamming_distance(hidden_shift_string, k))
            for k, v in sorted(
                probs.items(), key=lambda x: x[1], reverse=True
            )[:10]
        }
    )

    return probs, most_probable

probs, most_probable = find_hidden_shift_bitstring(
    counts, hidden_shift_string
)

Expected hidden shift string: 011010
Most probable bitstring matches hidden shift 😊.
Top 10 bitstrings and their probabilities:

{'011010': (0.9743, 6),
 '001010': (0.00812, 5),
 '010010': (0.0063, 5),
 '011000': (0.00554, 5),
 '011011': (0.00492, 5),
 '011110': (0.00044, 5),
 '001000': (0.00012, 4),
 '010000': (8e-05, 4),
 '001011': (6e-05, 4),
 '000010': (6e-05, 4)}

Давайте запишемо ймовірність найбільш ймовірного бітового рядка перед застосуванням пом'якшення помилок зчитування за допомогою M3.

max_probability_before_M3 = probs[most_probable]
max_probability_before_M3

0.9743

Тепер ми застосовуємо корекцію зчитування, засвоєну M3, до підрахунків. Функція apply_corrections повертає квазіймовірнісний розподіл. Це список об'єктів float, які в сумі дають $1$. Але деякі значення можуть бути від'ємними.

def perform_mitigation(mit, counts, qubit_mapping):
    # mitigate readout error
    quasis = mit.apply_correction(counts, qubit_mapping)

    # print results
    most_probable_after_m3 = unscramble(max(quasis, key=lambda x: quasis[x]))

    is_hidden_shift_identified = most_probable_after_m3 == hidden_shift_string
    if is_hidden_shift_identified:
        print("Most probable bitstring matches hidden shift 😊.")
    else:
        print("Most probable bitstring didn't match hidden shift ☹️.")
    print("Top 10 bitstrings and their quasi-probabilities:")
    topten = {
        unscramble(k): f"{v:.2e}"
        for k, v in sorted(quasis.items(), key=lambda x: x[1], reverse=True)[
            :10
        ]
    }
    max_probability_after_M3 = float(topten[most_probable_after_m3])
    display(topten)

    return max_probability_after_M3, is_hidden_shift_identified

print(f"Expected hidden shift string: {hidden_shift_string}")
max_probability_after_M3, is_hidden_shift_identified = perform_mitigation(
    mit, counts, qubit_mapping
)

Expected hidden shift string: 011010
Most probable bitstring matches hidden shift 😊.
Top 10 bitstrings and their quasi-probabilities:

{'011010': '1.01e+00',
 '001010': '8.75e-04',
 '001000': '7.38e-05',
 '010000': '4.51e-05',
 '111000': '2.18e-05',
 '001011': '1.74e-05',
 '000010': '6.42e-06',
 '011001': '-7.18e-06',
 '011000': '-4.53e-04',
 '010010': '-1.28e-03'}

Порівняння ідентифікації рядка прихованого зсуву до і після застосування корекції M3

def compare_before_and_after_M3(
    max_probability_before_M3,
    max_probability_after_M3,
    is_hidden_shift_identified,
):
    is_probability_improved = (
        max_probability_after_M3 > max_probability_before_M3
    )
    print(f"Most probable probability before M3: {max_probability_before_M3}")
    print(f"Most probable probability after M3: {max_probability_after_M3}")
    if is_hidden_shift_identified and is_probability_improved:
        print("Readout error mitigation effective! 😊")
    else:
        print("Readout error mitigation not effective. ☹️")

compare_before_and_after_M3(
    max_probability_before_M3,
    max_probability_after_M3,
    is_hidden_shift_identified,
)

Most probable probability before M3: 0.9743
Most probable probability after M3: 1.01
Readout error mitigation effective! 😊

Візуалізація того, як процесорний час, необхідний для M3, масштабується зі вимірами

# Collect samples for numbers of shots varying from 5000 to 25000.
shots_range = range(5000, NUM_SHOTS + 1, 2500)
times = []
for shots in shots_range:
    print(f"Applying M3 correction to {shots} shots...")
    t0 = timeit.default_timer()
    _ = mit.apply_correction(
        pub_result.data.meas.slice_shots(range(shots)).get_counts(),
        qubit_mapping,
    )
    t1 = timeit.default_timer()
    print(f"\tDone in {t1 - t0} seconds.")
    times.append(t1 - t0)

fig, ax = plt.subplots()
ax.plot(shots_range, times, "o--")
ax.set_xlabel("Shots")
ax.set_ylabel("Time (s)")
ax.set_title("Time to apply M3 correction")

Applying M3 correction to 5000 shots...
	Done in 0.003321983851492405 seconds.
Applying M3 correction to 7500 shots...
	Done in 0.004425413906574249 seconds.
Applying M3 correction to 10000 shots...
	Done in 0.006366567220538855 seconds.
Applying M3 correction to 12500 shots...
	Done in 0.0071477219462394714 seconds.
Applying M3 correction to 15000 shots...
	Done in 0.00860048783943057 seconds.
Applying M3 correction to 17500 shots...
	Done in 0.010026784148067236 seconds.
Applying M3 correction to 20000 shots...
	Done in 0.011459112167358398 seconds.
Applying M3 correction to 22500 shots...
	Done in 0.012727141845971346 seconds.
Applying M3 correction to 25000 shots...
	Done in 0.01406092382967472 seconds.
Applying M3 correction to 27500 shots...
	Done in 0.01546052098274231 seconds.
Applying M3 correction to 30000 shots...
	Done in 0.016769016161561012 seconds.
Applying M3 correction to 32500 shots...
	Done in 0.019537431187927723 seconds.
Applying M3 correction to 35000 shots...
	Done in 0.019739801064133644 seconds.
Applying M3 correction to 37500 shots...
	Done in 0.021093040239065886 seconds.
Applying M3 correction to 40000 shots...
	Done in 0.022840639110654593 seconds.
Applying M3 correction to 42500 shots...
	Done in 0.023974396288394928 seconds.
Applying M3 correction to 45000 shots...
	Done in 0.026412792038172483 seconds.
Applying M3 correction to 47500 shots...
	Done in 0.026364430785179138 seconds.
Applying M3 correction to 50000 shots...
	Done in 0.02820305060595274 seconds.

Text(0.5, 1.0, 'Time to apply M3 correction')

Інтерпретація графіка

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

Масштабування

n_qubits = 80
rng = Random(12345)
circuit, hidden_shift, hidden_shift_string = run_hidden_shift_circuit(
    n_qubits, rng
)

print(f"Hidden shift string {hidden_shift_string}")

Hidden shift string 00000010100110101011101110010001010000110011101001101010101001111001100110000111

isa_circuit = get_isa_circuit(circuit, backend)

job = run_sampler(backend, isa_circuit, NUM_SHOTS)
mit, qubit_mapping = setup_mthree_mitigation(isa_circuit, backend)

counts, pub_result = get_bitstring_counts(job)

probs, most_probable = find_hidden_shift_bitstring(
    counts, hidden_shift_string
)

Expected hidden shift string: 00000010100110101011101110010001010000110011101001101010101001111001100110000111
Most probable bitstring matches hidden shift 😊.
Top 10 bitstrings and their probabilities:

{'00000010100110101011101110010001010000110011101001101010101001111001100110000111': (0.50402,
  80),
 '00000010100110101011101110010001010000110011100001101010101001111001100110000111': (0.0396,
  79),
 '00000010100110101011101110010001010000110011101001101010101001111001100100000111': (0.0323,
  79),
 '00000010100110101011101110010001010000110011101001101010101001101001100110000111': (0.01936,
  79),
 '00000010100110101011101110010011010000110011101001101010101001111001100110000111': (0.01432,
  79),
 '00000010100110101011101110010001010000110011101001101010101001011001100110000111': (0.0101,
  79),
 '00000010100110101011101110010001010000110011101001101010101001110001100110000111': (0.00924,
  79),
 '00000010100110101011101110010001010000010011101001101010101001111001100110000111': (0.00908,
  79),
 '00000010100110101011100110010001010000110011101001101010101001111001100110000111': (0.00888,
  79),
 '00000010100110101011101110010001010000110011101001100010101001111001100110000111': (0.0082,
  79)}

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

max_probability_before_M3 = probs[most_probable]
max_probability_before_M3

0.50402

print(f"Expected hidden shift string: {hidden_shift_string}")
max_probability_after_M3, is_hidden_shift_identified = perform_mitigation(
    mit, counts, qubit_mapping
)

Expected hidden shift string: 00000010100110101011101110010001010000110011101001101010101001111001100110000111
Most probable bitstring matches hidden shift 😊.
Top 10 bitstrings and their quasi-probabilities:

{'00000010100110101011101110010001010000110011101001101010101001111001100110000111': '9.85e-01',
 '00000010100110101011101110010001010000110011100001101010101001111001100110000111': '6.84e-03',
 '00000010100110101011100110010001010000110011101001101010101001111001100110000111': '3.87e-03',
 '00000010100110101011101110010011010000110011101001101010101001111001100110000111': '3.42e-03',
 '00000010100110101011101110010001010000110011101001101010101001111001100100000111': '3.30e-03',
 '00000010100110101011101110010001010000110011101001101010101001110001100110000111': '3.28e-03',
 '00000010100010101011101110010001010000110011101001101010101001111001100110000111': '2.62e-03',
 '00000010100110101011101110010001010000110011101001101010101001101001100110000111': '2.43e-03',
 '00000010100110101011101110010000010000110011101001101010101001111001100110000111': '1.73e-03',
 '00000010100110101011101110010001010000110011101001101010101001111001000110000111': '1.63e-03'}

compare_before_and_after_M3(
    max_probability_before_M3,
    max_probability_after_M3,
    is_hidden_shift_identified,
)

Most probable probability before M3: 0.54348
Most probable probability after M3: 0.99
Readout error mitigation effective! 😊