"Myslím, že mohu bezpečně říci, že nikdo nerozumí kvantové mechanice." - Richard Feynman
Téma kvantových počítačů vždy fascinovalo technické spisovatele a novináře. Jeho výpočetní potenciál a složitost mu dodávaly určitou mystickou auru. Příliš často hlavní články a infografiky podrobně popisují různé vyhlídky tohoto odvětví, přičemž se sotva dotýkají jeho praktické aplikace: to může méně pozorného čtenáře uvést v omyl.
Populární vědecké články vynechávají popisy kvantových systémů a uvádějí prohlášení jako:
Běžný bit může být 1 nebo 0, ale qubit může být 1 a 0 současně.
Pokud budete mít velké štěstí (což si nejsem jistý), bude vám řečeno, že:
Qubit je v superpozici mezi "1" a "0".
Žádné z těchto vysvětlení se nezdá být pravděpodobné, protože se snažíme formulovat kvantově mechanický jev pomocí jazyka vyvinutého ve velmi tradičním světě. K jasnému vysvětlení principů kvantového počítání je nutné použít jiný jazyk – matematický.
V tomto tutoriálu se budu věnovat matematickým nástrojům potřebným k modelování a pochopení kvantových výpočetních systémů a také tomu, jak ilustrovat a aplikovat logiku kvantových počítačů. Navíc uvedu příklad kvantového algoritmu a řeknu vám, v čem je jeho výhoda oproti tradičnímu počítači.
Udělám, co bude v mých silách, abych to všechno vysvětlil jasným jazykem, ale přesto doufám, že čtenáři tohoto článku mají základní znalosti o lineární algebře a digitální logice (lineární algebře je věnována o digitální logice - ).
Nejprve si projdeme principy digitální logiky. Je založen na použití elektrických obvodů k provádění výpočtů. Aby byl náš popis abstraktnější, zjednodušíme stav elektrického vodiče na „1“ nebo „0“, což bude odpovídat stavům „zapnuto“ nebo „vypnuto“. Uspořádáním tranzistorů v určité sekvenci vytvoříme tzv. logické prvky, které převezmou jednu nebo více hodnot vstupního signálu a převedou je na výstupní signál na základě určitých pravidel booleovské logiky.
Obecná logická hradla a jejich stavové tabulky
Na základě řetězců takových základních prvků lze vytvářet složitější prvky a na základě řetězců složitějších prvků lze nakonec s velkou mírou abstrakce očekávat získání analogu centrálního procesoru.
Jak jsem již zmínil dříve, potřebujeme způsob, jak matematicky reprezentovat digitální logiku. Nejprve si představíme matematickou tradiční logiku. Pomocí lineární algebry lze klasické bity s hodnotami „1“ a „0“ reprezentovat jako dva sloupcové vektory:
kde jsou čísla vlevo vektor. Reprezentací našich bitů tímto způsobem můžeme modelovat logické operace na bitech pomocí vektorových transformací. Vezměte prosím na vědomí: ačkoli použití dvou bitů v logických hradlech může provádět mnoho operací (AND, NOT, XOR atd.), při použití jednoho bitu lze provést pouze čtyři operace: převod identity, negace, výpočet konstanty „0“ a výpočet konstanty „1“. Při převodu identity zůstává bit nezměněn, při negaci se hodnota bitu změní na opačnou (z „0“ na „1“ nebo z „1“ na „0“) a výpočet konstanty „1“ nebo „0“ nastaví bit na „1“ nebo „0“ bez ohledu na jeho předchozí hodnotu.
| Identita | Transformace identity |
| negace | Odmítnutí |
| Konstanta-0 | Výpočet konstanty "0" |
| Konstanta-1 | Výpočet konstanty "1" |
Na základě námi navržené nové reprezentace bitu je docela snadné provádět operace s odpovídajícím bitem pomocí vektorové transformace:
Než se přesuneme dále, podívejme se na koncept , z čehož jednoduše vyplývá, že pro zajištění vratnosti operace nebo logického prvku je nutné určit seznam hodnot vstupních signálů na základě výstupních signálů a názvů použitých operací. Můžeme tedy dojít k závěru, že transformace identity a negace jsou vratné, ale operace pro výpočet konstant „1“ a „0“ nikoli. Díky kvantová mechanika, kvantové počítače používají výhradně vratné operace, takže na to se zaměříme. Dále převedeme nevratné prvky na vratné prvky, abychom je umožnili použít kvantovým počítačem.
S jednotlivé bity mohou být reprezentovány mnoha bity:
Nyní, když máme téměř všechny potřebné matematické pojmy, přejděme k našemu prvnímu kvantovému logickému hradlu. Toto je operátor , nebo řízený Not (NOT), který má velký význam v reverzibilním a kvantovém počítání. Prvek CNOT se vztahuje na dva bity a vrací dva bity. První bit je označen jako „řídící“ bit a druhý jako „řídicí“ bit. Pokud je řídicí bit nastaven na „1“, řídicí bit změní svou hodnotu; Pokud je řídicí bit nastaven na "0", řídicí bit se nezmění.
Tento operátor může být reprezentován jako následující transformační vektor:
Abychom demonstrovali vše, co jsme doposud probrali, ukážu vám, jak použít prvek CNOT na více bitech:
Abychom shrnuli, co již bylo řečeno: v prvním příkladu rozložíme |10⟩ na části jeho tenzorového součinu a použijeme matici CNOT k získání nového odpovídajícího stavu součinu; to pak vynásobíme na |11⟩ podle výše uvedené tabulky hodnot CNOT.
Vzpomněli jsme si tedy na všechna matematická pravidla, která nám pomohou porozumět tradičnímu počítání a obyčejným bitům, a konečně můžeme přejít k modernímu kvantovému počítání a qubitům.
Pokud jste dočetli až sem, pak mám pro vás dobrou zprávu: qubity lze snadno vyjádřit matematicky. Obecně platí, že pokud lze klasický bit (cbit) nastavit na |1⟩ nebo |0⟩, je qubit jednoduše v superpozici a může být před měřením jak |0⟩, tak |1⟩. Po měření se zhroutí do |0⟩ nebo |1⟩. Jinými slovy, qubit může být reprezentován jako lineární kombinace |0⟩ a |1⟩ podle vzorce níže:
kde a₀ и a₁ reprezentují amplitudy |0⟩ a |1⟩. Ty lze považovat za „kvantové pravděpodobnosti“, které představují pravděpodobnost, že se qubit po změření zhroutí do jednoho ze stavů, protože v kvantové mechanice se objekt v superpozici zhroutí do jednoho ze stavů poté, co byl fixován. Rozšiřme tento výraz a získáme následující:
Pro zjednodušení mého vysvětlení, toto je reprezentace, kterou použiji v tomto článku.
U tohoto qubitu je šance na kolaps na hodnotu a₀ po měření se rovná |a₀|² a možnost kolapsu na hodnotu a₁ se rovná |a₁|². Například pro následující qubit:
šance na kolaps do „1“ se rovná |1/ √2|² nebo ½, tedy 50/50.
Protože v klasickém systému musí všechny pravděpodobnosti sčítat jednu (pro úplné rozdělení pravděpodobnosti), můžeme dojít k závěru, že druhé mocniny absolutních hodnot amplitud |0⟩ a |1⟩ musí dát jednu. Na základě těchto informací můžeme sestavit následující rovnici:
Pokud jste obeznámeni s trigonometrií, všimnete si, že tato rovnice odpovídá Pythagorově větě (a²+b²=c²), to znamená, že můžeme graficky znázornit možné stavy qubitu jako body na jednotkové kružnici, konkrétně:
Logické operátory a prvky jsou aplikovány na qubity stejně jako v situaci s klasickými bity – na základě maticové transformace. Všechny invertibilní maticové operátory, které jsme si dosud připomněli, zejména CNOT, lze použít pro práci s qubity. Takové maticové operátory vám umožňují používat každou z amplitud qubitu, aniž byste ji změřili a sbalili. Dovolte mi uvést příklad použití operátoru negace na qubit:
Než budeme pokračovat, dovolte mi připomenout, že hodnoty amplitudy a₀ a a₁ jsou ve skutečnosti , takže stav qubitu lze nejpřesněji zmapovat na trojrozměrnou jednotkovou kouli, známou také jako :
Pro zjednodušení vysvětlení se zde však omezíme na reálná čísla.
Zdá se, že je čas diskutovat o některých logických prvcích, které dávají smysl pouze v kontextu kvantových počítačů.
Jedním z nejdůležitějších operátorů je "Hadamardův prvek": vezme bit ve stavu "0" nebo "1" a umístí jej do vhodné superpozice s 50% pravděpodobností, že se zhroutí do "1" nebo "0" po měření.
Všimněte si, že v pravé dolní části operátoru Hadamard je záporné číslo. To je způsobeno tím, že výsledek aplikace operátoru závisí na hodnotě vstupního signálu: - |1⟩ nebo |0⟩, a proto je výpočet reverzibilní.
Dalším důležitým bodem Hadamardova prvku je jeho invertibilita, což znamená, že může vzít qubit do vhodné superpozice a transformovat jej na |0⟩ nebo |1⟩.
To je velmi důležité, protože nám to dává schopnost transformovat se z kvantového stavu, aniž bychom určovali stav qubitu – a tedy bez jeho zhroucení. Můžeme tedy strukturovat kvantové výpočty založené spíše na deterministickém než na pravděpodobnostním principu.
Kvantové operátory obsahující pouze reálná čísla jsou jejich vlastním opakem, takže výsledek aplikace operátoru na qubit můžeme reprezentovat jako transformaci v jednotkovém kruhu ve formě stavového automatu:
Tedy qubit, jehož stav je znázorněn na obrázku výše, se po aplikaci Hadamardovy operace převede do stavu označeného příslušnou šipkou. Podobně můžeme sestrojit další stavový stroj, který bude ilustrovat transformaci qubitu pomocí operátoru negace, jak je uvedeno výše (také známého jako operátor Pauliho negace nebo bitové inverze), jak je ukázáno níže:
Pro provádění složitějších operací na našem qubitu můžeme řetězit více operátorů nebo aplikovat prvky vícekrát. Příklad sériové transformace založené na je následující:
To znamená, že pokud začneme bitem |0⟩, použijeme bitovou inverzi a poté Hadamardovu operaci, pak další bitovou inverzi a znovu Hadamardovu operaci, po níž následuje konečná bitová inverze, skončíme s vektorem daným on pravou stranu řetězu. Vrstvením různých stavových automatů na sebe můžeme začít na |0⟩ a sledovat barevné šipky odpovídající každé z transformací, abychom pochopili, jak to celé funguje.
Protože jsme se dostali až sem, je čas zvážit jeden z typů kvantových algoritmů, konkrétně - a ukázat jeho výhodu oproti klasickému počítači. Stojí za zmínku, že Deutsch-Jozsa algoritmus je zcela deterministický, to znamená, že vrací správnou odpověď 100% času (na rozdíl od mnoha jiných kvantových algoritmů založených na pravděpodobnostní definici qubitů).
Představme si, že máte černou skříňku, která obsahuje funkci/operátor na jednom bitu (pamatujte - s jedním bitem lze provést pouze čtyři operace: převod identity, negace, vyhodnocení konstanty "0" a vyhodnocení konstanty "1" "). Jakou funkci přesně v krabici plní? Nevíte jakou, ale můžete procházet tolika variantami vstupních hodnot, kolik chcete, a vyhodnocovat výstupní výsledky.
Kolik vstupů a výstupů byste museli projít černou skříňkou, abyste zjistili, která funkce se používá? Přemýšlejte o tom na chvíli.
V případě klasického počítače budete muset provést 2 dotazy pro určení funkce, kterou chcete použít. Pokud například vstup "1" produkuje výstup "0", je jasné, že se použije buď funkce výpočtu konstanty "0" nebo funkce negace, po které budete muset změnit hodnotu vstupního signálu. na "0" a uvidíte, co se stane na výstupu.
V případě kvantového počítače budou také vyžadovány dva dotazy, protože stále potřebujete dvě různé výstupní hodnoty, abyste přesně definovali funkci, která se má použít na vstupní hodnotu. Pokud však otázku trochu přeformulujete, ukáže se, že kvantové počítače mají stále vážnou výhodu: pokud byste chtěli vědět, zda je používaná funkce konstantní nebo proměnná, kvantové počítače by měly výhodu.
Funkce použitá v rámečku je proměnná, pokud různé hodnoty vstupního signálu produkují různé výsledky na výstupu (například konverze identity a bitová inverze), a pokud se výstupní hodnota nemění bez ohledu na vstupní hodnotu, pak funkce je konstantní (například výpočet konstanty "1" nebo výpočet konstanty "0").
Pomocí kvantového algoritmu můžete na základě jediného dotazu určit, zda je funkce v černé skříňce konstantní nebo proměnná. Než se však podíváme na to, jak to udělat podrobně, musíme najít způsob, jak strukturovat každou z těchto funkcí na kvantovém počítači. Protože jakékoli kvantové operátory musí být invertibilní, okamžitě čelíme problému: funkce pro výpočet konstant „1“ a „0“ nejsou.
Běžným řešením používaným v kvantovém počítání je přidat další výstupní qubit, který vrátí jakoukoli vstupní hodnotu, kterou funkce obdrží.
| Před: | Po: |
|
|
|
Tímto způsobem můžeme určit vstupní hodnoty pouze na základě výstupní hodnoty a funkce se stane invertovatelnou. Struktura kvantových obvodů vytváří potřebu dalšího vstupního bitu. Pro vývoj odpovídajících operátorů budeme předpokládat, že další vstupní qubit je nastaven na |0⟩.
Pomocí stejné reprezentace kvantového obvodu, kterou jsme použili dříve, se podívejme, jak lze každý ze čtyř prvků (transformace identity, negace, vyhodnocení konstanty "0" a vyhodnocení konstanty "1") implementovat pomocí kvantových operátorů.
Například takto můžete implementovat funkci pro výpočet konstanty „0“:
Výpočet konstanty "0":
Tady operátory vůbec nepotřebujeme. První vstupní qubit (o kterém jsme předpokládali, že je |0⟩) se vrátí se stejnou hodnotou a druhá vstupní hodnota se vrátí sama – jako obvykle.
S funkcí pro výpočet konstanty „1“ je situace trochu jiná:
Výpočet konstanty "1":
Protože jsme předpokládali, že první vstupní qubit je vždy nastaven na |0⟩, výsledkem použití operátoru bitové inverze je, že na výstupu vždy vytvoří jedničku. A jako obvykle, druhý qubit dává na výstupu svou vlastní hodnotu.
Při mapování operátoru transformace identity se úloha začíná komplikovat. Jak na to:
Identická transformace:
Zde použitý symbol označuje prvek CNOT: horní řádek označuje řídicí bit a spodní řádek označuje řídicí bit. Dovolte mi připomenout, že při použití operátoru CNOT se hodnota řídicího bitu změní, pokud je řídicí bit roven |1⟩, ale zůstane nezměněn, pokud je řídicí bit roven |0⟩. Protože jsme předpokládali, že hodnota horního řádku je vždy rovna |0⟩, je jeho hodnota vždy přiřazena spodnímu řádku.
Podobně postupujeme s operátorem negace:
Negace:
Jednoduše převrátíme bit na konci výstupního řádku.
Nyní, když máme toto předběžné pochopení z cesty, podívejme se na konkrétní výhody kvantového počítače oproti tradičnímu počítači, pokud jde o určení stálosti nebo variability funkce skryté v černé skříňce pomocí jediného dotazu.
K vyřešení tohoto problému pomocí kvantového počítání v jediném požadavku je nutné vložit vstupní qubity do superpozice před jejich předáním funkci, jak je ukázáno níže:
Hadamardův prvek je znovu aplikován na výsledek funkce, aby se vylomily qubity ze superpozice a algoritmus byl deterministický. Spustíme systém ve stavu |00⟩ az důvodů, které krátce vysvětlím, dostaneme výsledek |11⟩, pokud je použitá funkce konstantní. Pokud je funkce uvnitř černé skříňky proměnná, pak po měření systém vrátí výsledek |01⟩.
Abychom porozuměli zbytku článku, podívejme se na ilustraci, kterou jsem ukázal dříve:
Použitím operátoru bitové inverze a následným použitím Hadamardova prvku na obě vstupní hodnoty rovné |0⟩ zajistíme, že budou převedeny do stejné superpozice |0⟩ a |1⟩, a to následovně:
Na příkladu předání této hodnoty funkci černé skříňky je snadné demonstrovat, že obě funkce s konstantní hodnotou mají výstup |11⟩.
Výpočet konstanty "0":
Podobně vidíme, že funkce pro výpočet konstanty „1“ také produkuje |11⟩ jako výstup, tedy:
Výpočet konstanty "1":
Všimněte si, že výstup bude |1⟩, protože -1² = 1.
Na stejném principu můžeme dokázat, že při použití obou proměnných funkcí dostaneme na výstupu vždy |01⟩ (za předpokladu, že použijeme stejnou metodu), byť je vše trochu složitější.
Identická transformace:
Protože CNOT je dvouqubitový operátor, nemůže být reprezentován jako jednoduchý stavový automat, a proto je nutné definovat dva výstupní signály na základě tenzorového součinu obou vstupních qubitů a násobení maticí CNOT, jak bylo popsáno výše:
Touto metodou můžeme také potvrdit, že je přijata výstupní hodnota |01⟩, pokud je negační funkce skryta v černém rámečku:
Negace:
Právě jsme tedy předvedli situaci, ve které je kvantový počítač jednoznačně efektivnější než konvenční počítač.
Co bude dál?
Navrhuji, abychom skončili tady. Už jsme odvedli skvělou práci. Pokud jste pochopili vše, co jsem probral, myslím, že nyní dobře rozumíte základům kvantového počítání a kvantové logiky a proč mohou být kvantové algoritmy v určitých situacích efektivnější než tradiční výpočty.
Můj popis lze jen stěží nazvat plnohodnotným průvodcem kvantových výpočtů a algoritmů – je to spíše stručný úvod do matematiky a zápisu, který má rozptýlit čtenářské představy o tématu vnucené populárně vědeckými zdroji (vážně, mnozí opravdu nerozumí situace!). Nestihl jsem se dotknout mnoha důležitých témat, jako např , složitost hodnot amplitudy |0⟩ a |1⟩ a fungování různých prvků kvantové logiky při transformaci Blochovou sférou.
Pokud chcete systematizovat a strukturovat své znalosti o kvantových počítačích, silně Doporučuji přečíst Emma Strubel: Navzdory množství matematických vzorců tato kniha pojednává o kvantových algoritmech mnohem podrobněji.
Zdroj: www.habr.com