Týdeník věnovaný aktualitám a novinkám z fyziky a astronomie.
Vydavatel: AGA (Aldebaran Group for Astrophysics)
Číslo 44 – vyšlo 8. listopadu, ročník 17 (2019)
© Copyright Aldebaran Group for Astrophysics
Publikování nebo šíření obsahu je zakázáno.
ISSN: 1214-1674,
Email: bulletin@aldebaran.cz

Kvantové algoritmy okem programátora

Lukáš Karas

Internetový gigant Google v říjnu 2019 uvedl, že se svým 54-qubitovým procesorem Sycamore dokázal „kvantovou nadřazenost“, tedy že jeho kvantový počítač dokáže vyřešit úlohu, která je klasickým počítačem neřešitelná. Řešení na klasickém superpočítači by podle odhadů Googlu trvalo deset tisíc let, zatímco jejich stroji trvala úloha 200 sekund. Vědci z konkrurečního IBM s tímto vyjádřením nesouhlasí a tvrdí, že úlohu by bylo možné na superpočítači spočítat přesněji a za „pouhých“ 2,5 dne. Rozdíl v odhadech vyplývá z použití pomalejšího, ale paměťově úspornějšího algoritmu (Schrödingerova-Feynmanova) na straně Googlu, a využití „swapování“ na disk v kombinaci s rychlejším, paměťově náročnějším algoritmem (Schrödingerovým) na straně IBM. I když daná úloha, hledání vzorců v posloupnosti náhodných čísel, není prakticky příliš využitelná, je jasné že se svět kvantových počítačů vyvíjí závratným tempem.

54-qubitový procesor Sycamore společnosti Google.
Zdroj: Forest Stearns, Erik Lucero, Google.

Kvantový počítač – počítač využívající k zápisu informace kvantově mechanické vlastnosti částic, například spin elektronů, spin atomových jader nebo jiné vlastnosti kvantově se chovajících objektů. Kvantový počítač nese současně informaci o všech možných hodnotách kvantované veličiny, a tím provádí paralelně výpočet všech možností, které mohou nastat. Výpočet je mnohonásobně efektivnější než u klasického počítače. Základní jednotka informace se nazývá qubit (kvantový bit). Zatím jsou kvantové počítače ve stádiu ověřování principů.

Superpozice stavů – pokud dva stavy představují fyzikálně realizovatelný stav systému, je možná i superpozice těchto stavů. Například kvantově mechanická kočka nemusí být jen živá nebo mrtvá, může být i „obojí zároveň“. Takový stav značíme a|Ž⟩+b|M⟩, kde a a b jsou čísla vyjadřující váhu. Pokud na kočce v tomto superponovaném stavu provedeme měření, s pravděpodobností |a|² ji najdeme živou a s pravděpodobností |b|² mrtvou. Kvantová superpozice stavů je běžná pro kvantové objekty, například elementární částice nebo atomy. U makroskopických objektů (kočka, člověk) komunikujících s okolím je nemožná.

Provázaný stav – entanglement, kvantově korelovaný stav systému dvou a více částic, v němž nemá smysl mluvit o stavech jednotlivých složek. Například z provázaného stavu dvojice fotonů nelze vyjádřit stavy jednotlivých fotonů. Značíme |AB>+|XY>, což znamená, že najdeme-li první částici ve stavu A, je druhá ve stavu B. Je-li první ve stavu X, pak druhá je ve stavu Y. Měřením provedeným na jedné částici se dozvíme určitou informaci o částici druhé. Je to způsobeno tím, že mají společnou minulost. Někdy se také hovoří o propletených stavech.

Kvantová interference – skládání amplitud pravděpodobnosti několika možností vývoje systému. Amplitudy se mohou vyrušit, potom hovoříme o destruktivní interferenci. Pravděpodobnosti dějů jsou druhou mocninou součtu amplitud pravděpodobností jednotlivých možností.

Z marketingových prohlášení předních výrobců čipů se zdá, že kvantové počítače budou brzy dostupné široké veřejnosti. Krom Google je na poli kvantových počítačů velmi aktivní již zmíněné IBM, kde již v roce 2017 vyrobili univezální procesor s 20 qubity, o kterém jsme psali v bulletinu AB 38/2017 a společnost D-Wave disponující systémem, který lze nazvat kvantovým optimalizátorem. Další hráč, největší výrobce klasických procesorů – Intel, technické detaily o svém kvantovém procesoru bohužel nezveřejňuje. Jeho marketingové oddělení se ale v roce 2018 na veletrhu CES pochlubilo 49-qubitovým testovacím procesorem. Mnoho dalších společností v této oblasti investuje do výzkumu a připravují svá vývojová prostředí (Rigetti, Microsoft, Huawei…).

O fyzikálních principech kvantových počítačů jsme psali již před patnácti lety v AB 21/2003, podrobněji pak v aktuálnějším bulletinu AB 37/2017. Shrnuto do pár vět – registry kvantového počítače jsou složeny z několika provázaných qubitů. Každý qubit v jeden okamžik nese s určitou pravděpodobností jak informaci 0 (koeficient ?) tak 1 (koeficient ß). Tyto koeficenty jsou komplexní čísla, která mají reálnou a imaginární složku. Pravděpodobnost daného stavu je druhou mocninou tohoto koefientu, tedy |?|² a |ß|². Součet těchto dvou pravděpodobností je vždy jedna (|?|² + |ß|² = 1). Koeficienty qubitů lze modifikovat elementárními hradly, která lze skládat do složitějších výpočetních jednotek, podobně jako v klasických počítačích (řízená kvantová evoluce). Výpočet probíhá z principu paralelně se všemi možnými hodnotami registru (superpozice), v okamžiku měření je pak jedna z hodnot realizována – změříme konkrétní hodnoty koeficientů.

Jak ale s takovým počítačem pracovat až k němu budeme mít přístup a na jaký typ úloh bude vhodný? Dnes bych se rád podíval na kvantové procesory očima programátora.

Existuje mnoho úloh, které nelze na klasických počítačích řešit, respektive jejich řešení by trvalo neúnostně dlouho. Složitost algoritmů vyjadřujeme jako počet elementárních kroků, které je potřeba v nejhorším případě provést při dané velikosti vstupních dat (takzvaná asymptotická složitost). Pokud má algoritmus složitost n (kde n je velikost vstupu), říkáme že je lineárně složitý, kⁿ nazýváme exponenciálně a n! faktoriálně složitý. Pokud například jeden elementární krok trvá 0,3 nanosekundy (zhruba jeden takt procesoru o frekvenci 3,5 GHz), exponeniálně složitý výpočet (2ⁿ) o velikosti vstupních dat n = 50 trvá čtyři dny, při n = 60 už deset let.

Kvantové počítače provádí operace přirozeně paralelně, ideální stupeň paralelizmu odpovídá 2ⁿ kde n je počet qubitů v jednotlivých registrech. Teoreticky je tedy možné na něm řešit exponenciálně složité úlohy v konstantím čase. Ale pouze za předpokladu, že máme k dispozici kvantový počítač, kde počet qubitů odpovídá velikosti vstupních dat a podaří se nalézt algoritmus realizovatelný na daném procesoru.

Faktorizace čísel

Patrně nejznámějším kvantovým algoritmem je Shorův faktorizační algoritmus, publikovaný Peterem Shorem v roce 1994. Jedná se o první v praxi využitelný algoritmus, na kterém byla předvedena výhodnost kvantového počítače před klasickým. Faktorizace čísla je proces, při kterém je číslo rozloženo na součin prvočísel. Tento algoritmus upoutal značnou pozornost, protože na obtížnosti faktorizace je postavena velká část šifrovacích algoritmů a její proveditelnost v rozumném čase by způsobila mnoho problémů.

Zápis algoritmu provádějící faktorizaci čísel může pro klasické počítače vypadat například takto:

/**
 * Příkaz pro kompilaci pomocí GCC:
 * g++ -O2 -Wall -pedantic --std=c++17 -ofact fact.cpp
 * 
 * Vyzkoušejte svoji trpělivost a spusťte program
 * s argumentem 18446744073709551557 
 * Jedná se o největší prvočíslo které jde uložit 
 * do 64 bitového, neznaménkového registru :-)
 */

#include <iostream>
#include <cmath>

using namespace std;

/**
 * Rozloží číslo n >= 2 na prvočíselné součinitele.
 * Součinitele vypíše na obrazovku (do konzole).
 */
void faktorizuj(uint64_t n) {

    uint64_t zbytek = n;
    for (uint64_t i = 2; i <= sqrt(zbytek); i++) {
        while (zbytek % i == 0) {
            zbytek = zbytek / i;
            cout << i << " ";
        }
    }
    
    // Pokud je zbytek větši než 1, pak je to prvočíslo,
    // které je třeba vypsat také.
    if (zbytek > 1) {
        cout << zbytek;
    }
    cout << endl;
}

int main(int argc, char* args[]){
  if (argc < 2){
    cerr << "Nebyl zadán argument" << endl;
    return 1;
  }
  faktorizuj(stoull(args[1]));
  return 0;
}

Zdroj: algoritmy.net, autor

Jedná se o zápis v jazyce C++. Ten je během kompilace zoptimalizován a převedem na instrukce pro konkrétní procesor. V nástroji Compiler Explorer si můžeme vyzkoušet, Jak vypadá výsledný program po kompilaci. Při vypnutých optimalizacích (přepínač kompilátoru -O0) a při základních znalostech assembleru cílové platformy lze ještě rozpoznat původní algoritmus. Velmi zjednodušeně řečeno se za každou instrukcí procesoru nalézá vykonání operace s pamětí, skoku programu nebo operace s hodnotou jednoho či více registrů. Procesor je složen z logických a aritmetických bloků, jako jsou registry, sčítačky, násobičky… Tyto bloky jdou dále „poskládat“ ze základních binárních hradel.

Obdobně jsou v kvantovém počítači složitější obvody složeny ze základních hradel. Dnešní kvantové počítače ale nemají pevně definované univerzální aritmeticko-logické jednotky, propojení qubitů hradly je programovatelné. Programátor si tedy sám musí obvod pro daný algoritmus „poskládat“ a psaní algoritmů je tak bližší programování hradlových polí než psaní programu v progamovacím jazyce. Při návrhu obvodu je potřeba respektovat topologii konkrétní architektury a její omezení. Například Sycamore od Google má qubity umístěné ve 2D mřížce, kde každý může interagovat pouze se čtyřmi nejbližšími sousedy (diagonálně). V osmiqubitovém systému Agave od Rigetti jsou pro změnu qubity uspořádány v kruhu. Dalším omezením mohou být výrobní vady konkrétního procesoru (některé qubity nebo propoje mohou být nefunkční) a především fyzikální omezení konkrétní technologie. Tedy jak dlouho vydrží qubity koherentní, jak dlouho trvá provedení konkrétních hradel… Každý reálný procesor je navíc ovlivňován šumem jehož negativní účinky se v hradlech zesilují. Google uvádí, že pro dosažení použitelného výsledku na systému Sycamore je potřeba udržet počet hradel pod hodnotou 1 000.

Hradla pracující s jedním qubitem	vstup	matice	výstup
Pauliho X hradlo (NOT)	(?, ß)	\[\small {\rm{X}} = \left( {\begin{array}{*{20}{c}} 0&1\\ 1&0 \end{array}} \right) \]	(ß, ?)
Pauliho Y hradlo	(?, ß)	\[\small {\rm{Y}} = \left( {\begin{array}{*{20}{c}} 0&{ - {\rm{i}}}\\ {\rm{i}}&0 \end{array}} \right)\]	(-i ß, i ?)
Pauliho Z hradlo (flip)	(?, ß)	\[\small {\rm{Z}} = \left( {\begin{array}{*{20}{c}} 1&0\\ 0&{ - 1} \end{array}} \right)\]	(?, -ß)
Hadamard	(?, ß)	\[\small {\rm{H}} = \frac{1}{{\sqrt 2 }}\left( {\begin{array}{*{20}{c}} 1&1\\ 1&{ - 1} \end{array}} \right)\]	(? + ß, ? − ß) / ?2

Qubit lze zapsat jako superpozici dvou stavových vektorů. První prvek vektoru udává pravděpodobnost stavu 0, druhý stavu 1. V Diracově notaci zapisované jako |0? a |1?. Operace s jedním qubitem lze tedy jednoduše zapsat jako matici 2×2. Zdroj: AB 37/2017, Rigetti.

Hradla pracující se dvěma qubity	vstup	matice	výstup
Řízená negace (CNOT)	(?, ß, ?, ?)	\[\small{\rm{CNOT}} = \left( {\begin{array}{*{20}{c}} 1&0&0&0\\ 0&1&0&0\\ 0&0&0&1\\ 0&0&1&0 \end{array}} \right)\]	(?, ß, ?, ?)
Prohození (SWAP)	(?, ß, ?, ?)	\[\small{\rm{SWAP}} = \left( {\begin{array}{*{20}{c}} 1&0&0&0\\ 0&0&1&0\\ 0&1&0&0\\ 0&0&0&1 \end{array}} \right)\]	(?, ?, ß, ?)

První prvek vektoru udává pravděpodobnost stavu 00, druhý 01, třetí 10 a čtvrtý 11. V Diracově notaci zapisované jako |00?, |01?, |10? a |11?. Popis hradel, jejich charakteristik a možného matematického zápisu by vydal na samostatný článek. Čtenáře odkážeme na intro k developerskému manuálu PyQuil. Zdroj: Rigetti.

Vývojová prostředí

Naštěstí je široké veřejnosti dostupných několik programovacích jazyků, v kterých lze program včetně zapojení hradel deklarovat a nechat optimalizace pro konkrétní architekturu či simulátor na kompilátoru. S dostupností reálných kvantových systémů pro širokou veřejnost je to horší. Prakticky jediné, na které je možné si vzdáleně „sáhnout“ jsou procesory od Rigetti a IBM (stav z března 2019). Takže pokud nechceme zůstat pouze u simulací, můžeme si vybrat jedno ze tří vývojových prostředí – Forest od Rigetti, Qiskit od IBM nebo ProjectQ od ETH Zurich

Přehled kvantových systémů dostupných široké veřejnosti

Stručný přehled vývojových prostředí, simulátorů a reálných kvantových systémů dostupných široké veřejnosti (stav z března 2019). Zelenou barvou jsou označena vývojová prostředí, šedou simulátory spustitelné lokálně, žlutě pak vzdáleně přístupné „cloudy“ a oranžově reálné kvantové systémy. Zdroj: Ryan LaRose.

Shorův faktorizační algoritmus

Zpátky k problému faktorizace celých čísel. Klasický naivní algoritmus ukázaný dříve má exponenicální složitost (2ⁿ), nejlepší známý algoritmus proveditelný na klasických počítačích využívající „číselného síta“ (GNFS) má složitost sub-exponenicální (zhruba e^log₁₀(n)). Shorův algoritmus je se svojí polynomiální složitostí (zhruba log₁₀(n)) řádově rychlejší. Bohužel vyžaduje kvantový počítač alespoň s 2n + 3 qubitů a n³log₂(n) hradel (kde n je počet bitů potřebných pro uložení faktorizovaného čísla). Takže současné systémy jsou schopny faktorizovat pouze relativně malá čísla.

Algoritmus se skládá z klasické a kvantové části (čtvrtý krok).

Zvolí se náhodné číslo a > 2 a zároveň a < N.
Spočítáme největší společný dělitel gcd(a, N), například použitím Eukleidova algoritmu.
Pokud gcd(a, N) != 1, nalezli jsme dělitele, končíme.
Pomocí kvantové Fourierovy transformace hledáme periodu r funce f(x) = a^x v grupě Z_N. Tedy nejmenší r, pro které platí a^r mod N = 1.
Pokud je r liché nebo rovno N-1 (-1 v grupě Z_N), pokračuje se od začátku. Pravděpodnost této podmínky je menší než 50 %.
Jinak, alespoň gcd(a^r/2 +1, N) nebo gcd(a^r/2 -1, N) je dělitelem N. Končíme.

Obvodů pro kvantovou Fourierovu transformaci existuje několik variant. Některé se snaží optimalizovat hloubku hradel, tedy rychlost obvodu, jiné počet potřebných qubitů. K jeho sestavení je krom základních hradel zapotřebí kvantová sčítačka, sčítačka v grupě Z_N (a + b mod N) a násobička v grupě Z_N. Kompletní popis přesahuje rozsah buletinu, čtenáře můžeme odkázat na popis upraveného algoritmu od Stephane Beauregarda.

Obvod pro kvantovou Fourierovu transformaci

Jedna z variant obvodu pro kvantovou Fourierovu transformaci.
Zdroj: Stephane Beauregard.

Pro prográtora bývá často mnohem srozumitelnější kód než matematický popis. Implementace výše zmíněného algoritmu od Aleca Bricknera v PyQuil je dostupná ve formě kompletních zdrojových kódů na Githubu. Pro snažší představu uvedeme alespoň jednoduchou sčítačku. Pro její konstrukci potřebujeme hradlo fázového posunu (PHASE) parametrizovaného kontantou k.

matice	Schématické znároznění
\[\small {\rm{PHASE}} = \left( {\begin{array}{*{20}{c}} 1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&{{{\mathop{\rm e}\nolimits} ^{\frac{{2\pi i}}{{{2^k}}}}}} \end{array}} \right)\]

Obvod kvantové sčítačky realizující součet registrů a a b o šířce n qubitů. Registr a zůstane nezměněn, hodnota druhého registru odpovídá kvantové Fourierově transformaci (a + b) mod 2ⁿ. Zdroj: Stephane Beauregard.

Implementace sčítačky v PyQuil pak může vypadat například takto:

from pyquil import Program
from pyquil.gates import PHASE

def bitfield(a, N):
    bits = [1 if digit=='1' else 0 for digit in bin(a)[2:]]
    prefix = [0] * (N - len(bits))
    return prefix + bits

# Adding
def add(b, a):
    add_gate = lambda k: 
        (lambda q: PHASE(math.pi / (2 ** (k - 1)), q))

    pq = Program()
    a_bits = bitfield(a, len(b))
    for i in range(0, len(b)):
        for j in range(i, len(b)):
            if a_bits[j] == 1:
                gate = add_gate(j - i + 1)(b[i])
                pq += gate
    return pq

Zdroj: Alec Brickner, autor

Video týdne

Google: Demonstrating Quantum Supremacy. Zdroj: YT.

Odkazy