Коди повторення

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

Класичне кодування та декодування

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

Зокрема, спочатку розглянемо 3-бітовий код повторення суто в контексті класичної інформації. Цей код кодує один біт у три, повторюючи його тричі, тобто $0$ кодується як $000,$ а $1$ — як $111.$

$$\begin{aligned} 0 & \mapsto 000\\ 1 & \mapsto 111 \end{aligned}$$

Якщо нічого не піде не так, ми очевидно можемо розрізнити два варіанти вихідного біта за їх кодуваннями. Суть у тому, що якщо трапилася помилка і один із трьох бітів перевернувся, тобто 0 змінилося на 1 або 1 — на 0, то ми все одно можемо визначити, яким був вихідний біт, з'ясувавши, яке з двох двійкових значень зустрічається двічі. Еквівалентно, можна декодувати, обчислюючи мажоритарне значення (тобто двійкове значення, яке зустрічається найчастіше).

$$a b c \mapsto \operatorname{majority}(a,b,c)$$

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

Зменшення шуму для двійкового симетричного каналу

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

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

Імовірність того, що два біти перевернуться під час передачі, дорівнює $3p^2(1-p)$ — це $p^2(1-p)$ для кожного з трьох варіантів того, який біт не перевернувся — а ймовірність того, що всі три біти перевернуться, дорівнює $p^3.$ Загальна ймовірність перевертання двох або трьох бітів:

$$3 p^2 (1 - p) + p^3 = 3 p^2 - 2 p^3.$$

Для значень $p$ менше половини це призводить до зменшення ймовірності того, що отримувач отримає неправильний біт. Шанс помилки все ще залишається, але код зменшує його ймовірність. (Для значень $p$ більше половини, навпаки, код фактично збільшує ймовірність того, що отримувач отримає неправильний біт.)

Кодування кубітів

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

Щоб було зрозуміло: коли ми говоримо про використання 3-бітового коду повторення для кубітів, ми маємо на увазі кодування кубіта, де стани стандартного базису повторюються тричі, так що вектор стану одного кубіта кодується так:

$$\alpha \vert 0\rangle + \beta \vert 1\rangle \mapsto \alpha \vert 000\rangle + \beta \vert 111\rangle$$

Це кодування легко реалізується такою квантовою схемою, яка використовує два ініціалізованих робочих кубіти та два вентилі CNOT.

Зауваж, зокрема, що це кодування не те саме, що потрійне повторення квантового стану, тобто кодування вигляду $\vert\psi\rangle \mapsto \vert\psi\rangle\vert\psi\rangle\vert\psi\rangle.$ Таке кодування не може бути реалізоване для невідомого квантового стану $\vert\psi\rangle$ через теорему про заборону клонування.

Помилки перевертання біта

Припустимо тепер, що після виконання кодування трапляється помилка. Зокрема, нехай вентиль $X,$ тобто перевертання біта, відбувається на одному з кубітів. Наприклад, якщо середній кубіт зазнає перевертання біта, стан трьох кубітів перетворюється на такий:

$$\alpha \vert 010\rangle + \beta \vert 101\rangle.$$

Звісно, це не єдиний можливий тип помилки — і також варто поставити під сумнів припущення, що помилка має форму ідеальної унітарної операції. Ми повернемося до цих питань в останньому розділі уроку, а поки що можемо розглядати помилку такого виду як один можливий тип помилки (хоч і фундаментально важливий).

Зі математичного виразу для стану вище видно, що середній біт відрізняється від решти всередині кожного кету. Але припустимо, що ти маєш три кубіти і не знаєш їхній стан. Якщо ти підозрюєш, що могло відбутися перевертання біта, одним з варіантів перевірки була б стандартна базисна вимірювання, яке в даному випадку показало б $010$ або $101$ з ймовірностями $\vert\alpha\vert^2$ та $\vert\beta\vert^2$ відповідно. У будь-якому разі ми б дійшли висновку, що середній біт перевернувся — але, на жаль, втратили б вихідний квантовий стан $\alpha\vert 0\rangle + \beta \vert 1\rangle.$ Це стан, який ми намагаємось захистити, тому вимірювання у стандартному базисі не є задовільним варіантом.

Натомість можна скористатися такою квантовою схемою, подаючи закодований стан на три верхніх кубіти. Ця схема неруйнівно вимірює парність станів стандартного базису двох верхніх кубітів і двох нижніх кубітів 3-кубітного кодування.

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

Що надзвичайно важливо: стан трьох верхніх кубітів не колапсує ні в одному з випадків, що дозволяє виправити помилку перевертання біта — просто застосувавши ще одне перевертання за допомогою вентиля $X.$ У таблиці нижче наведено стани, які ми отримуємо при не більш ніж одному перевертанні біта, результати вимірювань (які у контексті виправлення помилок називаються синдромом) та виправлення, необхідні для повернення до вихідного кодування.

Стан	Синдром	Виправлення
$\alpha\vert 000\rangle + \beta \vert 111\rangle$	$00$	$\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}$
$\alpha\vert 001\rangle + \beta \vert 110\rangle$	$01$	$\mathbb{I}\otimes\mathbb{I}\otimes X$
$\alpha\vert 010\rangle + \beta \vert 101\rangle$	$11$	$\mathbb{I}\otimes X\otimes\mathbb{I}$
$\alpha\vert 100\rangle + \beta \vert 011\rangle$	$10$	$X\otimes\mathbb{I}\otimes\mathbb{I}$

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

Помилки перевертання фази

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

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

На жаль, 3-бітовий код повторення взагалі не захищає від перевертань фази. Наприклад, нехай стан кубіта $\alpha\vert 0\rangle + \beta\vert 1\rangle$ закодовано за допомогою 3-бітового коду повторення, і на середньому кубіті відбувається помилка перевертання фази. Це призводить до стану

$$(\mathbb{I} \otimes Z \otimes \mathbb{I}) ( \alpha \vert 000\rangle + \beta \vert 111\rangle) = \alpha \vert 000\rangle - \beta \vert 111\rangle,$$

що є точно тим самим станом, який ми отримали б, закодувавши стан кубіта $\alpha\vert 0\rangle - \beta\vert 1\rangle.$ Насправді помилка перевертання фази на будь-якому з трьох кубітів кодування дає той самий ефект, що еквівалентно помилці перевертання фази на вихідному кубіті до кодування. За умови, що вихідний квантовий стан є невідомим, неможливо виявити, що помилка відбулася, оскільки отриманий стан є цілком дійсним кодуванням іншого стану кубіта. Зокрема, запуск схеми виявлення помилок на стані $\alpha \vert 000\rangle - \beta \vert 111\rangle$ гарантовано дасть синдром $00,$ що помилково свідчить про відсутність помилок.

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

$$3 p (1 - p)^2 + p^3.$$

Це значення більше за $p$ при $0<p<1/2,$ тому код збільшує ймовірність помилки перевертання фази для значень $p$ у цьому діапазоні.

Модифікований код повторення для помилок перевертання фази

Ми переконалися, що 3-бітовий код повторення зовсім не реагує на помилки перевертання фази, тому, здається, не дуже корисний для боротьби з таким видом помилок. Однак ми можемо просто модифікувати 3-бітовий код повторення так, щоб він виявляв помилки перевертання фази. Ця модифікація зробить код нечутливим до помилок перевертання бітів — але, як ми побачимо в наступному розділі, можна об'єднати 3-бітовий код повторення та цю модифіковану версію, щоб отримати код Шора, який може виправляти і помилки перевертання бітів, і помилки перевертання фази.

Нижче наведена модифікована версія схеми кодування, яка тепер зможе виявляти помилки перевертання фази. Модифікація дуже проста: після двох вентилів CNOT до кожного кубіта застосовується вентиль Адамара.

Вентиль Адамара перетворює стан $\vert 0\rangle$ на стан $\vert + \rangle,$ а стан $\vert 1\rangle$ — на стан $\vert - \rangle,$ тому загальний ефект полягає в тому, що стан одного кубіта $\alpha\vert 0\rangle + \beta \vert 1\rangle$ кодується як

$$\alpha \vert {+}\,{+}\,{+} \rangle + \beta \vert {-}\,{-}\,{-} \rangle$$

де $\vert {+}\,{+}\,{+} \rangle = \vert + \rangle \otimes \vert + \rangle \otimes\vert + \rangle$ та $\vert {-}\,{-}\,{-} \rangle = \vert - \rangle \otimes \vert - \rangle \otimes\vert - \rangle.$

Помилка перевертання фази, тобто вентиль $Z,$ переводить стан $\vert + \rangle$ у стан $\vert - \rangle$ і навпаки, тому таке кодування буде корисним для виявлення (та виправлення) помилок перевертання фази. Зокрема, схему виявлення помилок зі попереднього розділу можна модифікувати так.

Іншими словами, ми беремо попередню схему і додаємо вентилі Адамара на трьох верхніх кубітах і на початку, і в кінці. Ідея полягає в тому, що перші три вентилі Адамара перетворюють стани $\vert + \rangle$ та $\vert - \rangle$ назад на стани $\vert 0\rangle$ та $\vert 1\rangle,$ потім виконуються ті самі перевірки парності, що й раніше, після чого другий шар вентилів Адамара повертає стан у $\vert + \rangle$ та $\vert - \rangle$, відновлюючи кодування. Для подальшого використання зауважимо, що цю схему виявлення помилок перевертання фази можна спростити ось так.

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

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

Стан	Синдром	Виправлення
$\alpha\vert {+}\,{+}\,{+} \rangle + \beta \vert {-}\,{-}\,{-}\rangle$	$00$	$\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}$
$\alpha\vert {+}\,{+}\,{-}\rangle + \beta \vert {-}\,{-}\,{+}\rangle$	$01$	$\mathbb{I}\otimes\mathbb{I}\otimes Z$
$\alpha\vert {+}\,{-}\,{+}\rangle + \beta \vert {-}\,{+}\,{-}\rangle$	$11$	$\mathbb{I}\otimes Z\otimes\mathbb{I}$
$\alpha\vert {-}\,{+}\,{+} \rangle + \beta \vert {+}\,{-}\,{-}\rangle$	$10$	$Z\otimes\mathbb{I}\otimes\mathbb{I}$

На жаль, ця модифікована версія 3-бітового коду повторення тепер не може виправляти помилки перевертання бітів. Однак все ще не все втрачено. Як і було запропоновано раніше, ми зможемо об'єднати два коди, які щойно розглянули, в один — 9-кубітний код Шора, — який може виправляти і помилки перевертання бітів, і помилки перевертання фази, а загалом — будь-яку помилку на одному кубіті.