Spotlight #30 – Informacja kwantowa i obliczenia: kubity, splątanie, BB84 i algorytmy kwantowe

Komputery klasyczne przechowują informację w postaci bitów — wartości binarnych, które są jednoznacznie 0 albo 1. Komputer kwantowy przechowuje informację w kubitach: dwupoziomowych układach kwantowych, które mogą znajdować się w ciągłej superpozycji |0⟩ i |1⟩ aż do momentu pomiaru. Moc obliczeń kwantowych nie wynika z samej superpozycji (pojedynczy kubit przechowuje jedynie punkt na sferze Blocha, nie więcej informacji niż klasyczny kąt), lecz ze splątania między kubitami: nieklasycznych korelacji, których nie da się wyjaśnić żadnym wspólnym stanem klasycznym.

Teoria informacji kwantowej formalizuje granice tego, co układy kwantowe mogą przekazywać i obliczać. Ma zastosowania praktyczne w kryptografii (kwantowa dystrybucja kluczy BB84, której bezpieczeństwo można udowodnić na podstawie praw fizyki), w algorytmach (wyszukiwanie Grovera w czasie O(√N), faktoryzacja Shora w czasie wielomianowym) oraz w fizyce fundamentalnej (testy Bella, teleportacja, kodowanie gęste). Sześć poniższych sekcji buduje ten szkielet — od geometrii pojedynczego kubitu aż po złożoność algorytmiczną.

1. Kubity i sfera Blocha

Kubit jest kwantowym odpowiednikiem klasycznego bitu: układem dwupoziomowym opisanym wektorem stanu |ψ⟩ = α|0⟩ + β|1⟩, gdzie α, β ∈ ℂ oraz |α|² + |β|² = 1. Pełna przestrzeń stanów (z dokładnością do globalnej fazy) to powierzchnia sfery Blocha — każdy punkt odpowiada odrębnemu stanowi czystemu. Biegun północny i południowy to bazowe stany obliczeniowe |0⟩ i |1⟩; okrąg równikowy reprezentuje stany o równych prawdopodobieństwach pomiaru.

Ogólny czysty stan kubitu:
  |ψ⟩ = cos(θ/2)|0⟩ + e^{iφ} sin(θ/2)|1⟩
  θ ∈ [0, π]   (kąt biegunowy, wyznacza prawdopodobieństwa pomiaru)
  φ ∈ [0, 2π) (kąt azymutalny, wyznacza fazę)

Wektor Blocha: n = (sinθcosφ, sinθsinφ, cosθ)  — wektor jednostkowy na S²

Pomiar w bazie obliczeniowej:
  P(|0⟩) = cos²(θ/2)
  P(|1⟩) = sin²(θ/2)
  Po pomiarze stan nieodwracalnie kolapsuje do |0⟩ lub |1⟩.

Kluczowe stany równikowe:
  |+⟩ = (|0⟩ + |1⟩)/√2   (θ = π/2, φ = 0;  stan własny bramki X)
  |−⟩ = (|0⟩ − |1⟩)/√2  (θ = π/2, φ = π)
  |i⟩  = (|0⟩ + i|1⟩)/√2  (θ = π/2, φ = π/2; stan własny bramki Y)

Macierz gęstości (dla stanów mieszanych i dekoherencji):
  ρ = |ψ⟩⟨ψ|   (stan czysty)
  ρ = (I + n·σ) / 2   (σ = wektor Pauliego)
  Stan mieszany: |n| < 1; maksymalnie mieszany: ρ = I/2 (wektor Blocha = 0, pełna dekoherencja)
  Tr(ρ²) = 1 dla stanu czystego, < 1 dla mieszanego: miara czystości.

Skale czasowe dekoherencji:
  T_1: czas relaksacji energetycznej (|1⟩ → |0⟩ spontanicznie)
  T_2: czas defazowania (φ losowo zmienia się pod wpływem szumu środowiska)
  T_2 ≤ 2T_1 zawsze; dla kubitów nadprzewodnikowych T_1 ~ T_2 ~ 10–500 µs (stan techniki na 2024 r.)

2. Splątanie kwantowe i nierówności Bella

Splątanie to swoista kwantowa forma korelacji. Dwa kubity w stanie Bella |Φ&sup+;⟩ = (|00⟩ + |11⟩)/√2 znajdują się indywidualnie w stanach maksymalnie mieszanych — pełna niewiedza o każdym z kubitów — a mimo to pomiary są idealnie skorelowane: jeśli Alicja otrzyma |0⟩, Bob również otrzyma |0⟩, niezależnie od ich wzajemnej odległości. Bell (1964) pokazał, że żadna lokalna teoria zmiennych ukrytych nie jest w stanie odtworzyć wszystkich korelacji kwantowych; nierówność CHSH jest testowalną konsekwencją tego faktu.

Cztery maksymalnie splątane stany Bella (EPR) dla dwóch kubitów:
  |Φ&sup+;⟩ = (|00⟩ + |11⟩) / √2
  |Φ−⟩ = (|00⟩ − |11⟩) / √2
  |Ψ&sup+;⟩ = (|01⟩ + |10⟩) / √2
  |Ψ−⟩ = (|01⟩ − |10⟩) / √2

Rozkład Schmidta: dowolny dwuczęściowy stan czysty |ψ_{AB}⟩ = Σ_i λ_i |a_i⟩|b_i⟩
  Jeśli wszystkie λ_i są równe: stan maksymalnie splątany.
  Entropia splątania: S = −Σ_i λ_i² log_2(λ_i²)

Nierówność CHSH (Clauser–Horne–Shimony–Holt):
  Korelacja C(a, b) = ⟨A_a B_b⟩ dla kierunków pomiaru a, b
  Granica klasyczna (dowolny model lokalnych zmiennych ukrytych):
    |C(a,b) − C(a,b') + C(a',b) + C(a',b')| ≤ 2
  Maksimum kwantowe (granica Tsirelsona):
    |S_CHSH| ≤ 2√2 ≈ 2,828   (osiągane dla |Φ&sup+;⟩ przy optymalnych kątach)
  Rekord eksperymentalny bez luk (Delft 2015): S = 2,42 ± 0,20 > 2

Twierdzenie o zakazie klonowania:
  Nie istnieje unitarne U takie, że U|ψ⟩|0⟩ = |ψ⟩|ψ⟩ dla każdego |ψ⟩.
  Dowód: unitarność zachowuje iloczyny skalarne; jeśli |ψ⟩ i |φ⟩ są nieortogonalne,
  ⟨ψ|φ⟩ = ⟨ψ|φ⟩² ⇒ ⟨ψ|φ⟩ = 0 lub 1 — sprzeczność.
  Konsekwencja: nieznanych stanów kwantowych nie można kopiować; podsłuchujący zakłóca linię.

Teleportacja kwantowa (wykorzystuje splątanie + komunikację klasyczną):
  Zasoby: 1 para EPR + 2 bity klasyczne → teleportacja stanu 1 kubitu
  Alicja mierzy w bazie Bella → 2 bity klasyczne → Bob stosuje unitarną korekcję
  Teleportacja nie jest nadświetlna: bity klasyczne muszą zostać przesłane najpierw.

3. BB84 — kwantowa dystrybucja kluczy

BB84 (Bennett i Brassard, 1984) to pierwszy protokół kryptografii kwantowej. Pozwala dwóm stronom ustanowić wspólny tajny klucz, którego bezpieczeństwo gwarantowane jest przez prawa mechaniki kwantowej: każdy podsłuchujący nieuchronnie zaburza stany kwantowe, wprowadzając wykrywalne błędy. W odróżnieniu od klasycznej wymiany kluczy (opartej na trudności obliczeniowej), BB84 jest bezpieczny w sensie teorioinformacyjnym nawet wobec przeciwnika o nieograniczonej mocy obliczeniowej.

Krok 1 — Transmisja (Alicja → Bob):
  Alicja wybiera losowy bit (0/1) oraz losową bazę (prostokątną + lub diagonalną ×).
  Kodowanie:   bit 0 w + → |0⟩;  bit 1 w + → |1⟩
              bit 0 w × → |+⟩;  bit 1 w × → |−⟩
  Alicja wysyła kubit; powtarza dla n kubitów.

Krok 2 — Pomiar (Bob):
  Bob mierzy każdy kubit w losowo wybranej bazie (+ lub ×).
  Jeśli bazy się zgadzają (prawdopodobieństwo 1/2): wynik poprawny z całą pewnością.
  Jeśli bazy się nie zgadzają: wynik losowy, nieskorelowany z bitem Alicji.

Krok 3 — Uzgadnianie baz (kanał publiczny):
  Alicja i Bob ogłaszają swoje bazy (nie bity).
  Zachowują tylko ~n/2 kubitów, dla których bazy się zgadzały: „przesiany klucz”.

Krok 4 — Wykrywanie podsłuchu:
  Podsłuchujący typu przechwyć-i-wyślij (Ewa) trafia z bazą poprawnie w 50% przypadków.
  Gdy baza Ewy jest błędna, kolapsuje ona stan → Bob widzi wynik losowy.
  Ewa wprowadza 25% QBER (kwantowy współczynnik błędów bitowych) w przesianym kluczu.
  Alicja i Bob publicznie porównują podzbiór przesianych bitów:
    QBER = 0: nie wykryto podsłuchu.
    QBER ≈ 11%: Ewa obecna, przy maksymalnym pozyskaniu informacji.
    → Przerywają protokół, jeśli QBER przekracza próg (~11%).

Krok 5 — Wzmacnianie prywatności:
  Zastosowanie uniwersalnej funkcji skrótu do przesianego klucza → skrócenie, ale sprowadzenie
  informacji Ewy do zaniedbywalnej. Pozostały klucz jest bezpieczny kompozycyjnie (Renner 2005).

Parametr bezpieczeństwa:
  Szybkość klucza R ≥ 1 − h(e) − h(e)  (h = entropia binarna, e = QBER)
  Przy e = 0: R = 1 (idealna efektywność). Przy e = 11%: R = 0 (próg E91).

4. Bramki kwantowe i uniwersalne obwody kwantowe

Obliczenia kwantowe polegają na stosowaniu do kubitów przekształceń unitarnych (bramek kwantowych). W odróżnieniu od klasycznych bramek logicznych, bramki kwantowe są odwracalne: każda bramka ma swoją odwrotność. Uniwersalny zestaw bramek to skończony zbiór bramek, za pomocą których można przybliżyć dowolne przekształcenie unitarne z dowolną dokładnością (twierdzenie Solovaya–Kitajewa).

Bramki Pauliego (obroty o π wokół osi x, y, z sfery Blocha):
  X = [[0,1],[1,0]]    (odwrócenie bitu: |0⟩↔|1⟩)
  Y = [[0,−i],[i,0]]  (odwrócenie bitu i fazy)
  Z = [[1,0],[0,−1]]  (odwrócenie fazy: |1⟩→−|1⟩)

Bramka Hadamarda (tworzy równą superpozycję):
  H = (1/√2)[[1,1],[1,−1]]
  H|0⟩ = |+⟩;  H|1⟩ = |−⟩
  H jest sama sobie odwrotna: H² = I

Bramka fazowa / S:
  S = [[1,0],[0,i]]  (ćwierćobrót wokół osi Z)

Bramka T (bramka pi/8, potrzebna do uniwersalności):
  T = [[1,0],[0,e^{iπ/4}]]

CNOT (CX) — splątująca bramka dwukubitowa:
  |00⟩→|00⟩, |01⟩→|01⟩, |10⟩→|11⟩, |11⟩→|10⟩
  (bit docelowy jest odwracany, gdy bit kontrolny = |1⟩)
  Macierz (w bazie {|00⟩,|01⟩,|10⟩,|11⟩}):
  [[1,0,0,0],[0,1,0,0],[0,0,0,1],[0,0,1,0]]

Toffoli (CCNOT) — uniwersalna dla odwracalnych obliczeń klasycznych:
  Odwraca kubit docelowy tylko wtedy, gdy oba kubity kontrolne są |1⟩

Uniwersalne zestawy bramek:
  {H, T, CNOT} jest uniwersalny dla obliczeń kwantowych.
  {H, T} generuje gęste obroty na sferze Blocha (niewymierne wielokrotności π).
  Solovay–Kitajew: dowolna bramka U(2) przybliżana do ε za pomocą O(log^c(1/ε)) bramek.

Obwód kwantowy do przygotowania stanu Bella:
  Wejście |00⟩ → H na kubicie 1 → CNOT (kontrola=1, cel=2) → |Φ&sup+;⟩
  Wynik: (|00⟩ + |11⟩)/√2

5. Algorytm wyszukiwania Grovera — przyspieszenie kwadratowe

Algorytm Grovera (1996) przeszukuje nieposortowaną bazę danych o N elementach w poszukiwaniu oznaczonego wpisu, wykonując O(√N) zapytań do wyroczni — w porównaniu z O(N) klasycznie. Choć to „jedynie” przyspieszenie kwadratowe (wykładnicze przyspieszenie Shora robi większe wrażenie), uniwersalność algorytmu Grovera jest niezwykła: stosuje się do każdego problemu NP, którego rozwiązania można zweryfikować w czasie wielomianowym, dając ogólne przyspieszenie dla wyszukiwania nieustrukturyzowanego.

Konfiguracja (n kubitów, N = 2^n elementów):
  |s⟩ = H^⊗n |0⟩^⊗n = (1/√N) Σ_{x=0}^{N−1} |x⟩   (równa superpozycja)
  Oznaczony stan |ω⟩ (amplituda 1/√N na początku)

Iteracja Grovera G = D · O_f:
  O_f (wyrocznia):  |x⟩ → −|x⟩ jeśli x = ω, w przeciwnym razie |x⟩ (sztuczka odbicia fazy)
  D  (dyfuzja): 2|s⟩⟨s| − I  (odbicie względem średniej)
  Każda iteracja zwiększa amplitudę |ω⟩ o ~ 2/√N

Po k iteracjach:
  α_ω(k) ≈ sin((2k+1)θ)   gdzie sinθ = 1/√N
  Optymalne k* = floor(π/4 · √N) ≈ (π/4)√N
  P(|ω⟩) ≈ 1 przy k = k*

Złożoność zapytań do wyroczni:
  Grover: O(√N)
  Klasycznie: O(N) (przypadek najgorszy), O(N/2) (średnio)
  Dolna granica (BBBV 1996): Ω(√N) — algorytm Grovera jest optymalny.

Uogólniona amplifikacja amplitudy:
  Działa dla dowolnego rozkładu początkowego; jeśli ułamek „dobrych” elementów wynosi a, potrzeba O(1/√a) iteracji.
  Wykorzystywana w algorytmach błądzenia kwantowego (ewaluacja drzewa NAND, rozróżnianie elementów).

Przykład wymagań sprzętowych (N = 2^{20} ≈ 10^6):
  Klasycznie: średnio 500 000 zapytań
  Grover: ~ 804 iteracje operatora Grovera
  Przy częstotliwości bramek 1 MHz: < 1 ms dla Grovera wobec 0,5 s klasycznie — umiarkowana realna przewaga w tej skali.

6. Algorytm Shora — faktoryzacja, zagrożenie dla RSA i przewaga kwantowa

Algorytm Shora (1994) faktoryzuje n-bitową liczbę całkowitą N w czasie poly(n) na komputerze kwantowym, wykorzystując O(n² log n log log n) bramek kwantowych. Najlepszy znany algorytm klasyczny (ogólne sito ciała liczbowego) wymaga czasu subwykładniczego exp(O(n^{1/3})). Dla 2048-bitowych kluczy RSA algorytm Shora na odpornym na błędy komputerze kwantowym zająłby godziny; klasyczny GNFS zająłby więcej czasu niż wiek wszechświata.

Podstawowa redukcja (klasyczna): faktoryzacja N → wyszukiwanie okresu
  Wybierz losowe a względnie pierwsze z N.
  Znajdź rząd r: najmniejsze r > 0 takie, że a^r ≡ 1 (mod N).
  Jeśli r jest parzyste i a^{r/2} ¬≡ −1 (mod N):
    gcd(a^{r/2} ± 1, N) daje nietrywialne dzielniki N.
  Klasyczne wyszukiwanie okresu: O(exp(n^{1/3})) — trudna część.

Kwantowe wyszukiwanie okresu (kwantowa transformata Fouriera):
  1. Przygotuj |s⟩ = (1/√2^m) Σ_{x=0}^{2^m-1} |x⟩|0⟩
  2. Zastosuj potęgowanie modularne: |x⟩|0⟩ → |x⟩|a^x mod N⟩
  3. QFT na pierwszym rejestrze: tworzy piki przy wielokrotnościach 2^m/r
  4. Zmierz pierwszy rejestr: kolaps do wartości bliskiej k·2^m/r
  5. Rozwinięcie w ułamek łańcuchowy: odzyskaj r z oszacowania k/r.

Kwantowa transformata Fouriera (n kubitów):
  QFT|j⟩ = (1/√2^n) Σ_{k=0}^{2^n−1} e^{2πijk/2^n} |k⟩
  Głębokość obwodu: O(n²) bramek (dokładna), O(n log n) (przybliżona QFT)

Liczba bramek dla faktoryzacji 2048-bitowego RSA:
  Potrzebne fizyczne kubity: ~4 000 logicznych kubitów + korekcja błędów → ~4 miliony fizycznych kubitów
  Stan obecny (2024): IBM Eagle 127 kubitów, IBM Condor 1121 kubitów
  Szacowany horyzont czasowy: odporna na błędy faktoryzacja RSA-2048 — zakres 2035–2050 (dyskutowany)

Kryptografia postkwantowa (standardy NIST PQC, 2024):
  CRYSTALS-Kyber (ML-KEM): kapsułkowanie kluczy oparte na kratach
  CRYSTALS-Dilithium (ML-DSA): podpisy cyfrowe oparte na kratach
  SPHINCS+: podpisy oparte na funkcjach skrótu
  Uznaje się, że są bezpieczne zarówno wobec komputerów klasycznych, jak i kwantowych.