Спотлайт #30 – Квантова інформація та обчислення: кубіти, заплутаність, BB84 та квантові алгоритми

Класичні комп'ютери зберігають інформацію у вигляді бітів — двійкових значень, що є однозначно 0 або 1. Квантовий комп'ютер зберігає інформацію у кубітах: дворівневих квантових системах, що можуть перебувати у неперервній суперпозиції |0⟩ та |1⟩ до моменту вимірювання. Потужність квантових обчислень виникає не лише з суперпозиції (один кубіт зберігає лише точку на сфері Блоха, не більше інформації, ніж класичний кут), а з заплутаності між кубітами: некласичних кореляцій, які неможливо пояснити жодним спільним класичним станом.

Теорія квантової інформації формалізує межі того, що квантові системи можуть передавати й обчислювати. Вона має практичні застосування в криптографії (квантовий розподіл ключів BB84, доказово безпечний за законами фізики), в алгоритмах (пошук Гровера за O(√N), поліноміальна за часом факторизація Шора) та у фундаментальній фізиці (тести Белла, телепортація, щільне кодування). Шість розділів нижче будують структуру від геометрії одного кубіта до алгоритмічної складності.

1. Кубіти та сфера Блоха

Кубіт — квантовий аналог класичного біта: дворівнева система, описана вектором стану |ψ⟩ = α|0⟩ + β|1⟩, де α, β ∈ ℂ і |α|² + |β|² = 1. Повний простір станів (з точністю до глобальної фази) — це поверхня сфери Блоха — кожна точка відповідає окремому чистому стану. Північний і південний полюси — це базисні обчислювальні стани |0⟩ і |1⟩; екваторіальне коло представляє стани з однаковими ймовірностями вимірювання.

Загальний чистий стан кубіта:
  |ψ⟩ = cos(θ/2)|0⟩ + e^{iφ} sin(θ/2)|1⟩
  θ ∈ [0, π]   (полярний кут, визначає ймовірності вимірювання)
  φ ∈ [0, 2π) (азимутальний кут, визначає фазу)

Вектор Блоха: n = (sinθcosφ, sinθsinφ, cosθ)  — одиничний вектор на S²

Вимірювання у обчислювальному базисі:
  P(|0⟩) = cos²(θ/2)
  P(|1⟩) = sin²(θ/2)
  Після вимірювання стан незворотно колапсує до |0⟩ або |1⟩.

Ключові екваторіальні стани:
  |+⟩ = (|0⟩ + |1⟩)/√2   (θ = π/2, φ = 0;  власний стан вентиля X)
  |−⟩ = (|0⟩ − |1⟩)/√2  (θ = π/2, φ = π)
  |i⟩  = (|0⟩ + i|1⟩)/√2  (θ = π/2, φ = π/2; власний стан вентиля Y)

Матриця густини (для мішаних станів та декогеренції):
  ρ = |ψ⟩⟨ψ|   (чистий стан)
  ρ = (I + n·σ) / 2   (σ = вектор Паулі)
  Мішаний стан: |n| < 1; максимально мішаний: ρ = I/2 (вектор Блоха = 0, повна декогеренція)
  Tr(ρ²) = 1 для чистого, < 1 для мішаного: міра чистоти.

Часові шкали декогеренції:
  T_1: час енергетичної релаксації (|1⟩ → |0⟩ спонтанно)
  T_2: час дефазування (φ рандомізується через шум середовища)
  T_2 ≤ 2T_1 завжди; для надпровідникових кубітів T_1 ~ T_2 ~ 10–500 мкс (стан техніки на 2024 рік)

2. Квантова заплутаність та нерівності Белла

Заплутаність — це специфічно квантова форма кореляції. Два кубіти у стані Белла |Φ&sup+;⟩ = (|00⟩ + |11⟩)/√2 окремо перебувають у максимально мішаних станах — повне незнання про кожен кубіт — проте вимірювання ідеально скорельовані: якщо Аліса знаходить |0⟩, Боб знаходить |0⟩ незалежно від їхньої віддаленості. Белл (1964) показав, що жодна локальна теорія прихованих змінних не може відтворити всі квантові кореляції; нерівність CHSH — перевірний наслідок цього.

Чотири максимально заплутані стани Белла (EPR) для двох кубітів:
  |Φ&sup+;⟩ = (|00⟩ + |11⟩) / √2
  |Φ−⟩ = (|00⟩ − |11⟩) / √2
  |Ψ&sup+;⟩ = (|01⟩ + |10⟩) / √2
  |Ψ−⟩ = (|01⟩ − |10⟩) / √2

Розклад Шмідта: будь-який двочастинний чистий стан |ψ_{AB}⟩ = Σ_i λ_i |a_i⟩|b_i⟩
  Якщо всі λ_i рівні: максимально заплутаний.
  Ентропія заплутаності: S = −Σ_i λ_i² log_2(λ_i²)

Нерівність CHSH (Клаузер-Горн-Шимоні-Голт):
  Кореляція C(a, b) = ⟨A_a B_b⟩ для напрямків вимірювання a, b
  Класична межа (будь-яка модель локальних прихованих змінних):
    |C(a,b) − C(a,b') + C(a',b) + C(a',b')| ≤ 2
  Квантовий максимум (межа Цирельсона):
    |S_CHSH| ≤ 2√2 ≈ 2,828   (досягається з |Φ&sup+;⟩ та оптимальними кутами)
  Експериментальний рекорд без лазівок (Делфт, 2015): S = 2,42 ± 0,20 > 2

Теорема про заборону клонування:
  Не існує унітарного U такого, що U|ψ⟩|0⟩ = |ψ⟩|ψ⟩ для всіх |ψ⟩.
  Доведення: унітарність зберігає скалярні добутки; якщо |ψ⟩ і |φ⟩ неортогональні,
  ⟨ψ|φ⟩ = ⟨ψ|φ⟩² ⇒ ⟨ψ|φ⟩ = 0 або 1 — протиріччя.
  Наслідок: невідомі квантові стани не можна скопіювати; підслуховувачі порушують лінію.

Квантова телепортація (використовує заплутаність + класичну комунікацію):
  Ресурси: 1 пара EPR + 2 класичних біти → телепортація стану 1 кубіта
  Аліса вимірює у базисі Белла → 2 класичних біти → Боб застосовує коригувальну унітарну операцію
  Телепортація не надсвітлова: класичні біти мають бути передані першими.

3. BB84 — квантовий розподіл ключів

BB84 (Беннет і Брассар, 1984) — перший протокол квантової криптографії. Він дозволяє двом сторонам встановити спільний секретний ключ, чия безпека гарантується законами квантової механіки: будь-який підслуховувач неминуче порушує квантові стани, вносячи виявні помилки. На відміну від класичного обміну ключами (що покладається на обчислювальну складність), BB84 інформаційно-теоретично безпечний проти противника з необмеженою обчислювальною потужністю.

Крок 1 — Передача (Аліса → Боб):
  Аліса обирає випадковий біт (0/1) та випадковий базис (прямокутний + або діагональний ×).
  Кодування:   біт 0 у + → |0⟩;  біт 1 у + → |1⟩
              біт 0 у × → |+⟩;  біт 1 у × → |−⟩
  Аліса надсилає кубіт; повторює для n кубітів.

Крок 2 — Вимірювання (Боб):
  Боб вимірює кожен кубіт у випадково обраному базисі (+ або ×).
  Якщо базиси збігаються (ймовірність 1/2): правильний результат напевно.
  Якщо базиси не збігаються: випадковий результат, не скорельований з бітом Аліси.

Крок 3 — Узгодження базисів (публічний канал):
  Аліса й Боб оголошують свої базиси (не біти).
  Вони залишають лише ~n/2 кубітів, де базиси збіглися: «просіяний ключ».

Крок 4 — Виявлення підслуховувача:
  Підслуховувач з перехопленням-повторним надсиланням (Єва) правильно вгадує базис у 50% випадків.
  Коли базис Єви неправильний, вона колапсує стан → Боб бачить випадковий результат.
  Єва вносить 25% QBER (квантовий рівень бітових помилок) у просіяний ключ.
  Аліса й Боб публічно порівнюють підмножину просіяних бітів:
    QBER = 0: підслуховувача не виявлено.
    QBER ≈ 11%: Єва присутня з максимальним отриманням інформації.
    → Вони переривають протокол, якщо QBER перевищує поріг (~11%).

Крок 5 — Посилення приватності:
  Застосування універсальної хеш-функції до просіяного ключа → скорочення, але зведення
  інформації Єви до нехтовної. Залишковий ключ композиційно безпечний (Реннер, 2005).

Параметр безпеки:
  Швидкість ключа R ≥ 1 − h(e) − h(e)  (h = бінарна ентропія, e = QBER)
  При e = 0: R = 1 (ідеальна ефективність). При e = 11%: R = 0 (поріг E91).

4. Квантові вентилі та універсальні квантові схеми

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

Вентилі Паулі (повороти на π навколо осей x, y, z сфери Блоха):
  X = [[0,1],[1,0]]    (інверсія біта: |0⟩↔|1⟩)
  Y = [[0,−i],[i,0]]  (інверсія біта+фази)
  Z = [[1,0],[0,−1]]  (інверсія фази: |1⟩→−|1⟩)

Вентиль Адамара (створює рівну суперпозицію):
  H = (1/√2)[[1,1],[1,−1]]
  H|0⟩ = |+⟩;  H|1⟩ = |−⟩
  H сам собі обернений: H² = I

Фазовий вентиль / S:
  S = [[1,0],[0,i]]  (чверть-оберт навколо осі Z)

Вентиль T (вентиль пі/8, потрібен для універсальності):
  T = [[1,0],[0,e^{iπ/4}]]

CNOT (CX) — заплутувальний двокубітний вентиль:
  |00⟩→|00⟩, |01⟩→|01⟩, |10⟩→|11⟩, |11⟩→|10⟩
  (ціль інвертується, якщо контроль = |1⟩)
  Матриця (у базисі {|00⟩,|01⟩,|10⟩,|11⟩}):
  [[1,0,0,0],[0,1,0,0],[0,0,0,1],[0,0,1,0]]

Тофоллі (CCNOT) — універсальний для оборотних класичних обчислень:
  Інвертує цільовий кубіт лише тоді, коли обидва контрольні = |1⟩

Універсальні набори вентилів:
  {H, T, CNOT} універсальний для квантових обчислень.
  {H, T} генерує щільні повороти на сфері Блоха (ірраціональні кратні π).
  Соловей-Кітаєв: будь-який вентиль U(2) наближається до ε за допомогою O(log^c(1/ε)) вентилів.

Квантова схема для підготовки стану Белла:
  Вхід |00⟩ → H на кубіті 1 → CNOT (контроль=1, ціль=2) → |Φ&sup+;⟩
  Результат: (|00⟩ + |11⟩)/√2

5. Алгоритм пошуку Гровера — квадратичне прискорення

Алгоритм Гровера (1996) шукає позначений елемент у несортованій базі даних із N елементів за O(√N) звернень до оракула — порівняно з O(N) класично. Хоча це «лише» квадратичне прискорення (експоненційне прискорення Шора драматичніше), універсальність алгоритму Гровера вражає: він застосовується до будь-якої задачі NP, розв'язки якої можна перевірити за поліноміальний час, даючи загальне прискорення для неструктурованого пошуку.

Налаштування (n кубітів, N = 2^n елементів):
  |s⟩ = H^⊗n |0⟩^⊗n = (1/√N) Σ_{x=0}^{N−1} |x⟩   (рівна суперпозиція)
  Позначений стан |ω⟩ (амплітуда 1/√N початково)

Ітерація Гровера G = D · O_f:
  O_f (оракул):  |x⟩ → −|x⟩ якщо x = ω, інакше |x⟩ (трюк фазового відкату)
  D  (дифузія): 2|s⟩⟨s| − I  (інверсія відносно середнього)
  Кожна ітерація збільшує амплітуду |ω⟩ на ~ 2/√N

Після k ітерацій:
  α_ω(k) ≈ sin((2k+1)θ)   де sinθ = 1/√N
  Оптимальне k* = floor(π/4 · √N) ≈ (π/4)√N
  P(|ω⟩) ≈ 1 при k = k*

Складність запитів до оракула:
  Гровер: O(√N)
  Класично: O(N) (найгірший випадок), O(N/2) (у середньому)
  Нижня межа (BBBV, 1996): Ω(√N) — Гровер оптимальний.

Узагальнене амплітудне підсилення:
  Працює для будь-якого початкового розподілу; якщо частка «хороших» елементів = a, потрібно O(1/√a) ітерацій.
  Використовується в алгоритмах квантового блукання (обчислення дерева NAND, розрізнення елементів).

Приклад апаратних вимог (N = 2^{20} ≈ 10^6):
  Класично: у середньому 500 000 запитів
  Гровер: ~ 804 ітерації оператора Гровера
  При частоті вентилів 1 МГц: < 1 мс для Гровера проти 0,5 с класично — помірна практична перевага на цьому масштабі.

6. Алгоритм Шора — факторизація, загроза RSA та квантова перевага

Алгоритм Шора (1994) факторизує n-бітне ціле число N за час poly(n) на квантовому комп'ютері, використовуючи O(n² log n log log n) квантових вентилів. Найкращий класичний алгоритм (загальне решето числового поля) вимагає субекспоненційного часу exp(O(n^{1/3})). Для 2048-бітних ключів RSA алгоритм Шора на відмовостійкому квантовому комп'ютері зайняв би години; класичний GNFS зайняв би довше за вік всесвіту.

Базова редукція (класична): факторизація N → пошук періоду
  Обрати випадкове a, взаємно просте з N.
  Знайти порядок r: найменше r > 0 таке, що a^r ≡ 1 (mod N).
  Якщо r парне і a^{r/2} ¬≡ −1 (mod N):
    gcd(a^{r/2} ± 1, N) дає нетривіальні дільники N.
  Класичний пошук періоду: O(exp(n^{1/3})) — важка частина.

Квантовий пошук періоду (квантове перетворення Фур'є):
  1. Підготувати |s⟩ = (1/√2^m) Σ_{x=0}^{2^m-1} |x⟩|0⟩
  2. Застосувати модульне піднесення до степеня: |x⟩|0⟩ → |x⟩|a^x mod N⟩
  3. КПФ на першому регістрі: створює піки на кратних 2^m/r
  4. Виміряти перший регістр: колапс до значення поблизу k·2^m/r
  5. Розклад на неперервний дріб: відновити r з оцінки k/r.

Квантове перетворення Фур'є (n кубітів):
  QFT|j⟩ = (1/√2^n) Σ_{k=0}^{2^n−1} e^{2πijk/2^n} |k⟩
  Глибина схеми: O(n²) вентилів (точна), O(n log n) (наближена QFT)

Кількість вентилів для факторизації 2048-бітного RSA:
  Потрібні фізичні кубіти: ~4 000 логічних кубітів + корекція помилок → ~4 мільйони фізичних кубітів
  Поточний стан (2024): IBM Eagle 127 кубітів, IBM Condor 1121 кубіт
  Оцінка часової шкали: відмовостійка факторизація RSA-2048 — діапазон 2035–2050 (дискутується)

Постквантова криптографія (стандарти NIST PQC, 2024):
  CRYSTALS-Kyber (ML-KEM): ґраткова інкапсуляція ключів
  CRYSTALS-Dilithium (ML-DSA): ґраткові цифрові підписи
  SPHINCS+: підписи на основі хешів
  Вважається, що вони безпечні як проти класичних, так і проти квантових комп'ютерів.