Торичний код

Далі ми розглянемо конкретний CSS-код, відомий як торичний код, відкритий Алексієм Кітаєвим у 1997 році. Власне, торичний код — це не один код, а ціла сім'я кодів, по одному для кожного натурального числа починаючи від 2. Ці коди мають кілька ключових властивостей:

• Генератори стабілізатора мають малу вагу, і зокрема всі вони мають вагу 4. У термінах теорії кодування торичний код є прикладом квантового коду перевірки парності малої щільності, або квантового LDPC-коду (де мала означає 4 в даному випадку). Це зручно, бо вимірювання кожного генератора стабілізатора не потребує задіювання занадто багатьох кубітів.

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

• Члени сімейства торичних кодів мають дедалі більшу відстань і здатні витримувати відносно високий рівень помилок.

Опис торичного коду

Нехай $L\geq 2$ — натуральне число, і розглянемо решітку $L\times L$ з так званими periodical межами. Наприклад, на цьому рисунку зображено решітку $L\times L$ для $L=9$.

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

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

Те, що ми отримаємо, — це тор, або, іншими словами, пончик (хоча краще уявляти собі внутрішню камеру шини, бо це не суцільний об'єкт: решітка перетворюється лише на поверхню тора). Звідси й назва «торичний код».

Спосіб «переміщуватися» по такому тору між сусідніми точками решітки, мабуть, знайомий тим, хто грав у старовинні відеоігри, де вихід за верхній край екрану призводив до появи знизу, і так само з лівим та правим краями. Саме так ми розглядатимемо цю решітку з periodical межами, не говорячи про тор у тривимірному просторі.

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

Зверни увагу, що кубіти на пунктирних лініях не суцільні, бо вони вже представлені на верхній та лівій лініях решітки. Загалом є $2L^2$ кубітів: $L^2$ кубітів на горизонтальних лініях і $L^2$ кубітів на вертикальних.

Для опису самого торичного коду залишається описати генератори стабілізатора:

• Для кожної клітинки, утвореної лініями решітки, є один генератор стабілізатора $Z$, що отримується тензорним множенням матриць $Z$ на чотири кубіти, що торкаються цієї клітинки, разом із матрицями тотожності на всіх інших кубітах.

• Для кожної вершини, утвореної лініями решітки, є один генератор стабілізатора $X$, що отримується тензорним множенням матриць $X$ на чотири кубіти, суміжні з цією вершиною, разом із матрицями тотожності на всіх інших кубітах.

В обох випадках ми отримуємо операцію Паулі ваги 4. Окремо ці генератори стабілізатора можна проілюструвати так.

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

Для того щоб це був допустимий стабілізаторний код, генератори стабілізатора мають комутувати між собою. Як зазвичай, всі генератори стабілізатора $Z$ комутують один з одним, бо $Z$ комутує сам з собою, а тотожність комутує з усім; аналогічно для генераторів стабілізатора $X$. Генератори стабілізатора $Z$ та $X$ очевидно комутують, коли вони нетривіально діють на непересічних наборах кубітів, як у прикладах на попередньому рисунку. Решта можливостей — це коли генератор стабілізатора $Z$ та генератор стабілізатора $X$ перекриваються на кубітах, де вони нетривіально діють, і щоразу це перекриття обов'язково відбувається рівно на двох кубітах, як на наступному рисунку.

Відповідно, два таких генератори стабілізатора комутують, так само як комутують $Z\otimes Z$ та $X\otimes X$. Отже, всі генератори стабілізатора комутують між собою.

Друга необхідна умова на генератори стабілізатора стабілізаторного коду — це те, що вони утворюють мінімальний набір генераторів. Ця умова фактично не виконується для цієї сукупності: якщо перемножити всі генератори стабілізатора $Z$, отримаємо тотожну операцію, і аналогічно для генераторів $X$. Таким чином, будь-який з генераторів стабілізатора $Z$ можна виразити як добуток усіх решти, і аналогічно будь-який з генераторів $X$ можна виразити через решту генераторів $X$. Однак якщо прибрати по одному генератору стабілізатора кожного типу, ми отримаємо мінімальний набір генераторів.

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

Це залишає $L^2 - 1$ генераторів стабілізатора кожного типу, або $2L^2 - 2$ загалом, у (гіпотетичному) мінімальному наборі генераторів. Оскільки загалом є $2L^2$ кубітів, це означає, що торичний код кодує $2L^2 - 2 (L^2 - 1) = 2$ кубіти.

Остання умова, необхідна для генераторів стабілізатора, — щоб існував щонайменше один вектор квантового стану, фіксований усіма генераторами стабілізатора. Ми побачимо, що це так, продовжуючи аналіз коду, але також можна міркувати, що не існує способу отримати $-1$, помноженого на тотожність на всіх $2L^2$ кубітах, з генераторів стабілізатора.

Виявлення помилок

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

Торичний код є CSS-кодом, бо всі наші генератори стабілізатора є або $Z$, або $X$ генераторами. Це означає, що помилки $X$ та $Z$ можна виявляти (і, можливо, виправляти) незалежно. Фактично, між генераторами стабілізатора $Z$ та $X$ існує проста симетрія, яка дозволяє аналізувати помилки $X$ та $Z$ практично однаково. Тому ми зосередимося на помилках $X$, які виявляються генераторами стабілізатора $Z$ — але все подальше обговорення можна перенести з помилок $X$ на помилки $Z$, що аналогічно виявляються генераторами $X$.

Наступна діаграма показує ефект помилки $X$ на одному кубіті. Тут припускається, що наші $2L^2$ кубітів раніше перебували в стані, що належить до кодового простору торичного коду, внаслідок чого всі вимірювання генераторів стабілізатора давали результат $+1$. Генератори стабілізатора $Z$ виявляють помилки $X$, і для кожної клітинки на рисунку є один такий генератор, тому результат вимірювання відповідного генератора можна позначити кольором клітинки: результати $+1$ позначені білими клітинками, а $-1$ — сірими. Якщо на одному з кубітів виникає помилка перекидання біта, то вимірювання генераторів стабілізатора для двох клітинок, що торкаються ураженого кубіта, тепер дають $-1$.

Це інтуїтивно зрозуміло, якщо розглянути генератори стабілізатора $Z$ і їхню поведінку. По суті, кожен генератор стабілізатора $Z$ вимірює парність чотирьох кубітів, що торкаються відповідної клітинки (відносно стандартного базису). Тому результат $+1$ не означає, що на цих чотирьох кубітах не виникло жодної помилки $X$, а означає, що виникла парна кількість помилок $X$, тоді як результат $-1$ означає, що виникла непарна кількість помилок $X$. Одна помилка $X$ тому змінює парність чотирьох бітів на обох клітинках, яких вона торкається, що призводить до результату $-1$ для відповідних вимірювань.

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

Обидва генератори стабілізатора $Z$ на кінцях ланцюжка в цьому випадку дають результат $-1$, бо на обох відповідних клітинках виникла непарна кількість помилок $X$. Усі інші генератори стабілізатора $Z$, навпаки, дають результат $+1$, включно з тими, що торкаються ланцюжка, але не є його кінцями, бо на кубітах, що торкаються відповідних клітинок, виникла парна кількість помилок $X$.

Таким чином, поки ланцюжок помилок $X$ має кінці, торичний код виявить, що помилки виникли, давши результат $-1$ для вимірювань генераторів стабілізатора $Z$, що відповідають кінцям ланцюжка. Зверни увагу, що фактичний ланцюжок помилок не розкривається — видно лише кінці! Це нормально — у наступному підрозділі ми побачимо, що для виправлення помилок не потрібно знати точно, які кубіти були уражені. (Торичний код є прикладом сильно виродженого коду, в тому сенсі що він зазвичай не ідентифікує однозначно помилки, які виправляє.)

Однак можливо, що ланцюжок суміжних помилок $X$ не матиме кінців, тобто ланцюжок помилок може утворювати замкнений контур, як на наступному рисунку.

У такому випадку на кожній клітинці виникла парна кількість помилок $X$, тому кожне вимірювання генератора стабілізатора дає результат $+1$. Замкнені контури суміжних помилок $X$ тому не виявляються кодом.

Це може здаватися розчаровуючим, бо для утворення замкненого контуру потрібно лише чотири помилки $X$ (а ми сподіваємося на щось набагато краще, ніж код з відстанню 4). Однак замкнений контур помилок $X$ вигляду, що показаний на попередньому рисунку, насправді не є помилкою — адже він є частиною стабілізатора! Нагадаємо, що на додаток до генераторів стабілізатора $Z$ у нас є генератор стабілізатора $X$ для кожної вершини в решітці. І якщо перемножити суміжні генератори стабілізатора $X$, у результаті отримаємо замкнені контури операцій $X$. Наприклад, замкнений контур на попередньому рисунку можна отримати, перемноживши генератори стабілізатора $X$, що показані на наступному рисунку.

Однак це не єдиний тип замкнених контурів помилок $X$, що можуть виникнути — і не кожен замкнений контур помилок $X$ входить до стабілізатора. Зокрема, різні типи контурів можна охарактеризувати так.

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

2. Замкнені контури помилок $X$ з непарною кількістю помилок $X$ щонайменше на одній горизонтальній або щонайменше одній вертикальній лінії кубітів. Контури такої форми ніколи не входять до стабілізатора і тому представляють нетривіальні помилки, що не виявляються кодом.

Приклад замкненого контуру помилок $X$ другої категорії показаний на наступній діаграмі.

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

Ключове те, що єдиний спосіб утворити контур другого типу — це обійти тор навколо, тобто або навколо отвору в середині тора, або крізь нього, або обома шляхами. Інтуїтивно, ланцюжок помилок $X$ такого роду не можна «стягнути» до нічого, перемножуючи на генератори стабілізатора $X$, бо топологія тора це забороняє. Саме тому торичний код іноді класифікується як топологічний квантовий код виправлення помилок. Найкоротший такий контур має довжину $L$, і тому це відстань торичного коду: будь-який замкнений контур помилок $X$ довжиною менше $L$ обов'язково потрапляє в першу категорію і тому входить до стабілізатора; а будь-який ланцюжок помилок $X$ з кінцями виявляється кодом.

Оскільки торичний код використовує $2L^2$ кубітів для кодування $2$ кубітів і має відстань $L$, він є стабілізаторним кодом $[[2L^2,2,L]]$.

Виправлення помилок

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

Якщо при вимірюванні генераторів стабілізатора $Z$ з'являється синдром, відмінний від синдрому $(+1,\ldots,+1)$, результати $-1$ розкривають кінці одного або кількох ланцюжків помилок $X$. Ми можемо спробувати виправити ці помилки, спарувавши результати $-1$ і утворивши ланцюжок виправлень $X$ між ними. При цьому має сенс вибирати найкоротші шляхи, якими проходять виправлення.

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

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

Ця стратегія не завжди буде успішною. Наприклад, інше пояснення того самого синдрому, що і в попередньому рисунку, показано на наступному.

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

Можливо, залежно від моделі шуму, частіше вимірюватиметься синдром із більш ніж двома записами $-1$, як свідчить наступний рисунок.

У такому випадку відомі різні стратегії виправлень. Одна природна стратегія — спробувати спарувати результати $-1$ і виконати виправлення вздовж найкоротших шляхів, що з'єднують пари, як показано на рисунку жовтим. Зокрема, можна обчислити мінімальне ідеальне зіставлення між результатами $-1$ і з'єднати пари найкоротшими шляхами виправлень $X$. Обчислення мінімального ідеального зіставлення можна виконати ефективно за допомогою класичного алгоритму, відомого як алгоритм квіткового покриття, що був відкритий Едмондсом у 1960-х роках.

Цей підхід загалом не є оптимальним для найбільш поширених моделей шуму, але на основі числових симуляцій він добре працює на практиці при рівні шуму нижче приблизно 10%, за умови незалежних помилок Паулі, де $X$, $Y$ та $Z$ рівноймовірні. Збільшення $L$ не суттєво впливає на точку беззбитковості, при якій код починає допомагати, але призводить до швидшого зниження ймовірності логічної помилки зі зменшенням рівня помилок нижче цієї точки.