Теорема про поріг

Фінальна тема обговорення в уроці — надзвичайно важлива теорема, відома як теорема про поріг. Ось її дещо неформальне формулювання.

Теорема

Теорема про поріг: квантова схема розміру $N$ може бути реалізована з високою точністю зашумленою квантовою схемою, за умови що ймовірність помилки в кожній локації зашумленої схеми нижча за фіксоване ненульове порогове значення $p_{\text{th}} > 0.$ Розмір зашумленої схеми масштабується як $O(N \log^c(N))$ для деякої додатної константи $c.$

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

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

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

Формальні доведення (формальних формулювань) цієї теореми охоплюють безліч технічних деталей, які тут не розглядатимуться — але основні ідеї можна пояснити на інтуїтивному рівні. Щоб це пояснення було якомога простішим, уявімо, що ми використовуємо $7$-кубітний код Стіна для виправлення помилок. Це був би непрактичний вибір для реальної фізичної реалізації — що відбилося б у мінімальному пороговому значенні $p_{\text{th}}$ — але він добре допомагає передати основні ідеї. У поясненні також будемо досить невимогливими щодо моделі шуму, припускаючи, що помилка вражає кожну локацію у відмовостійкій реалізації незалежно з ймовірністю $p$.

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

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

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

Детальніше: щоб у оригінальній схемі виникла логічна помилка, у відмовостійкій реалізації в один кодовий блок мають потрапити щонайменше дві помилки, оскільки код Стіна може виправити будь-яку одну помилку в блоці. Пам'ятаючи про те, що існує багато різних способів отримати дві або більше помилок в одному кодовому блоці, можна аргументувати, що ймовірність логічної помилки в кожній локації оригінальної схеми не перевищує $C p^2$ для деякого фіксованого додатного дійсного числа $C$, що залежить від коду та гаджетів, але критично не залежить від $N$, розміру оригінальної схеми. Якщо $p$ менше за $1/C$, яке ми можемо взяти як наше порогове значення $p_{\text{th}}$, це означає зниження рівня помилок.

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

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

Починаємо з ймовірністю помилки $p$ для локацій оригінальної схеми. Припускаючи, що $p < p_{\text{th}} = 1/C$, після першої ітерації логічний рівень помилок можна обмежити зверху як $Cp^2 = (Cp) p$. Розглядаючи відмовостійку реалізацію як будь-яку іншу схему і реалізуючи її відмовостійко, отримуємо оцінку для логічного рівня помилок:

$$C \bigl((Cp) p \bigr)^2 = (Cp)^3 p.$$

Ще одна ітерація знижує оцінку помилок далі, до

$$C \bigl((Cp)^3 p \bigr)^2 = (Cp)^7 p.$$

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

$$(Cp)^{2^k - 1} p,$$

що є подвійно експоненційним у $k$.

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

То яке ж це порогове значення на практиці? Відповідь залежить від коду та гаджетів. Для коду Стіна разом із дистиляцією магічних станів воно мінімальне і, мабуть, недосяжне на практиці. Але для поверхневих кодів і найсучасніших гаджетів поріг оцінюється порядку від 0,1% до 1%.

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

Опитування після курсу

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