ZX-kalkul - ZX-calculus
The ZX-kalkul je přísný grafický jazyk pro uvažování o lineárních mapách mezi qubits, které jsou reprezentovány jako ZX diagramy. ZX-diagram se skládá ze sady generátorů, které se nazývají pavouci které představují konkrétní tenzory. Ty jsou spojeny dohromady a tvoří a tenzorová síť podobný Penrosova grafická notace. Kvůli symetrii pavouků a vlastnostem podkladu kategorie, topologicky deformující ZX diagram (tj. pohybující se generátory bez změny jejich připojení) nemá vliv na lineární mapu, kterou představuje. Kromě rovností mezi ZX-diagramy, které jsou generovány topologickými deformacemi, má ZX-kalkul také sadu pravidla grafického přepisování pro transformaci ZX diagramů do druhého. ZX-kalkul je univerzální v tom smyslu, že jakoukoli lineární mapu mezi qubity lze reprezentovat jako ZX diagram a různé sady pravidel grafického přepisování jsou kompletní pro různé rodiny lineárních map. ZX-diagramy lze chápat jako zobecnění kvantový zápis obvodu.
Dějiny
ZX-kalkul poprvé představil Bob Coecke a Ross Duncan v roce 2008 jako rozšíření Kategorická kvantová mechanika škola uvažování. Představili základní pojmy pavouků, silná komplementarita a většina standardních pravidel přepisování.[1][2]
V roce 2009 Duncan a Perdrix našli další Eulerův rozklad pravidlo pro Hadamardova brána[3], který Backens použil v roce 2013 k vytvoření prvního výsledku úplnosti pro ZX-kalkul[4]. Jmenovitě, že existuje sada přepisovacích pravidel, která stačí k prokázání všech rovností mezi nimi stabilizátor ZX diagramy, kde fáze jsou násobky , až po globální skaláry. Tento výsledek byl později upřesněn na úplnost včetně skalárních faktorů[5].
V roce 2017 dokončení ZX-kalkulu pro přibližně univerzální fragment byl nalezen[6], navíc ke dvěma různým výsledkům úplnosti pro univerzální ZX-kalkul (kde fáze mohou nabývat jakékoli skutečné hodnoty)[7][8].
Také v roce 2017 kniha Zobrazování kvantových procesů byl propuštěn, který staví kvantovou teorii od základu pomocí ZX-kalkulu[9]. Viz také kniha 2019 Kategorie pro kvantovou teorii[10].
Neformální úvod
Schémata ZX se skládají ze zelených a červených uzlů pavouci, které jsou spojeny dráty. Dráty se mohou křivit a protínat, libovolně se mnoho vodičů může připojit ke stejnému pavoukovi a více vodičů může procházet mezi stejnou dvojicí uzlů. Existují také Hadamardovy uzly, obvykle označené žlutým rámečkem, které se vždy připojují k přesně dvěma vodičům.
ZX diagramy představují lineární mapy mezi nimi qubits, podobně jako způsob, jakým kvantové obvody zastupovat unitární mapy mezi qubits. ZX diagramy se liší od kvantových obvodů dvěma hlavními způsoby. První je, že ZX diagramy nemusí odpovídat rigidní topologické struktuře obvodů, a proto je lze libovolně deformovat. Druhým je to, že ZX diagramy jsou vybaveny sadou pravidel přepisu, souhrnně označovaných jako ZX-kalkul. Pomocí těchto pravidel lze výpočty provádět v samotném grafickém jazyce.
Generátory
Stavební bloky nebo generátory ZX-kalkulu jsou grafická znázornění konkrétních státy, unitární operátory, lineární izometrie, a projekce ve výpočetní bázi a Hadamardově transformovaný základ a . Zelená barva (nebo někdy bílá) se používá k reprezentaci výpočetního základu a červená barva (nebo někdy šedá) se používá k reprezentaci Hadamardově transformovaného základu. Každý z těchto generátorů může být dále označen fází, což je reálné číslo z intervalu . Pokud je fáze nulová, obvykle není zapsána.
Generátory jsou:
Typ | Generátor | Odpovídající lineární mapa | Poznámky |
---|---|---|---|
Stát | Pro a , tato mapa odpovídá nenormalizovaným verzím Hadamardově transformovaných základních stavů a , resp. Pro , toto je nenormalizovaná verze T magický stav[11] . | ||
Stát | Pro a , tato mapa odpovídá nenormalizovaným verzím stavů výpočetní báze a , resp. | ||
jednotná mapa | Tato mapa je rotace kolem osy Z Bloch koule o úhel . Pro , to je Z Pauliho matice. | ||
jednotná mapa | Tato mapa je rotace kolem osy X Blochovy koule o úhel . Pro , to je X Pauliho matice. | ||
jednotná mapa | Tato mapa je Hadamardova brána často se používá v kvantových obvodech. | ||
izometrie | Pro , tato mapa představuje operaci kopírování na výpočetním základě. Pro stejnou hodnotu , odpovídá také hladké rozdělení provoz mřížová chirurgie.[12] | ||
izometrie | Pro , tato mapa představuje operaci kopírování na Hadamardově transformovaném základě. Pro stejnou hodnotu , odpovídá také hrubý rozkol provoz mřížová chirurgie.[12] | ||
parciální izometrie | Pro , tato mapa představuje operaci řízeného NOT následovanou destruktivním měřením Z na cílovém qubitu po výběru státu . Pro stejnou hodnotu , odpovídá také hladké sloučení (bez operátorů vedlejších produktů) příhradová chirurgie.[12] | ||
parciální izometrie | Pro , tato mapa představuje operaci řízeného NOT následovanou destruktivním měřením X na kontrolním qubitu po výběru do stavu . Pro stejnou hodnotu , odpovídá také hrubé sloučení (bez operátorů vedlejších produktů) mřížová chirurgie.[12] | ||
projekce | Pro nebo , tato mapa odpovídá destruktivnímu X měření po výběru státu nebo , resp. | ||
projekce | Pro nebo , tato mapa odpovídá destruktivnímu měření Z. po výběru státu nebo , resp. |
Složení
Generátory lze skládat dvěma způsoby:
- postupně připojením výstupních vodičů jednoho generátoru ke vstupním vodičům druhého;
- paralelně stohováním dvou generátorů svisle.
Tyto zákony odpovídají složení a tenzorovému produktu lineárních map.
Jakýkoli diagram napsaný tímto způsobem skládáním generátorů se nazývá ZX-diagram. ZX-diagramy jsou uzavřeny podle obou zákonů o složení: připojení výstupu jednoho ZX-diagramu ke vstupu druhého vytvoří platný ZX-diagram a svislé stohování dvou ZX-diagramů vytvoří platný ZX-diagram.
Záleží pouze na topologii
Dva diagramy představují stejného lineárního operátora, pokud se skládají ze stejných generátorů připojených stejným způsobem. Jinými slovy, kdykoli lze topografickou deformací transformovat dva ZX diagramy do druhého, představují stejnou lineární mapu. To znamená, že řízená brána NOT lze reprezentovat následovně:
Přepisování diagramů
Následující příklad konstrukce kvantového obvodu a Stav GHZ. Jeho převodem do ZX-diagramu, pomocí pravidel, že „sousední pavouci stejné barvy se slučují“, „Hadamard mění barvu pavouků“ a „pavouci arity-2 jsou identity“, lze graficky zredukovat na GHZ -Stát:
Libovolná lineární mapa mezi qubity může být reprezentována jako ZX diagram, tj. ZX diagramy jsou univerzální. Daný ZX-diagram může být transformován do jiného ZX-diagramu pomocí pravidel přepisu ZX-kalkulu právě tehdy, když dva diagramy představují stejnou lineární mapu, tj. ZX-kalkul je zvuk a kompletní.
Formální definice
The kategorie diagramů ZX je a dýka kompaktní kategorie, což znamená, že má symetrický monoidal struktura (tenzorový produkt), je kompaktní uzavřen (má to šálky a čepice) a je vybaven a dýka, takže všechny tyto struktury vhodně interagují. Objekty kategorie jsou přirozená čísla, přičemž tenzorový součin je dán sčítáním (kategorie je a PODPĚRA ). Morfismy této kategorie jsou diagramy ZX. Dva ZX-diagramy se skládají tak, že se srovnávají vodorovně a spojují se výstupy levého diagramu se vstupy pravého diagramu. Monoidální součin dvou diagramů je reprezentován umístěním jednoho diagramu nad druhý.
Ve skutečnosti jsou všechny diagramy ZX vytvořeny volně ze sady generátorů prostřednictvím složení a monoidního produktu upravte rovnosti vyvolané kompaktní strukturou a pravidly ZX-kalkulu uvedenými níže. Například identita objektu je zobrazen jako paralelní vodiče zleva doprava se speciálním pouzdrem je prázdný diagram.
Následující tabulka uvádí generátory spolu s jejich standardními interpretacemi jako lineární mapy vyjádřené v Diracova notace. Stavy výpočetního základu jsou označeny a Hadamard -transformované základní stavy jsou . The -násobný tenzorový produkt vektoru je označen .
název | Diagram | Typ | Lineární mapa, kterou představuje |
---|---|---|---|
prázdný diagram | 1 | ||
drát / identita | |||
Stav Bell | |||
Bell efekt | |||
vyměnit | |||
Z pavouk | |||
X pavouk | |||
Hadamard |
Existuje mnoho různých verzí ZX-kalkulu, které používají různé systémy přepisovacích pravidel jako axiomy. Všichni sdílejí meta pravidlo „záleží pouze na topologii“, což znamená, že dva diagramy jsou stejné, pokud se skládají ze stejných generátorů připojených stejným způsobem, bez ohledu na to, jak jsou tyto generátory v diagramu uspořádány. Následuje několik základních soubor přepisovacích pravidel, zde uvedený „až do skalárního faktoru“: tj. dva diagramy jsou považovány za rovnocenné, pokud se jejich interpretace jako lineárních map liší od nenulového komplexního faktoru.
Název pravidla | Pravidlo | Popis |
---|---|---|
Fúze Z-pavouka | Kdykoli se dva Z-spider dotknou, mohou se spojit dohromady a jejich fáze se sčítají. Toto pravidlo odpovídá skutečnosti, že Z-spider představuje ortonormální základ - výpočetní základ. | |
Fúze X-spider | Viz fúze Z-spider. | |
Pravidlo identity | Bezfázový arity 2 Z- nebo X-spider se rovná identitě. Toto pravidlo stanoví, že Stav zvonu je stejný, ať už je vyjádřen ve výpočetním základě nebo v Hadamardově transformovaném základě. Z teoreticko-teoretického hlediska se říká, že kompaktní struktura indukovaná pavoukem Z a X se shoduje. | |
Změna barvy | Hadamardova brána mění barvu pavouků. To vyjadřuje vlastnost, kterou Hadamardova brána mapuje mezi výpočetním základem a Hadamardovým transformovaným základem. | |
Kopírovat pravidlo | Z-pavouk kopíruje arity-1 X-pavouky. To vyjadřuje skutečnost, že X-pavouk arity-1 je úměrný stavu výpočetní báze (v tomto případě ). | |
Pravidlo Bialgebra | 2-cyklus pavouků Z a X se zjednodušuje. To vyjadřuje vlastnost, kterou jsou výpočetní základ a Hadamardově transformovaný základ silně se doplňují. | |
-kopírovat pravidlo | NOT-brána (arity-2 X-spider s a fáze) kopíruje koryto Z-pavouka a převrátí fázi tohoto pavouka. Toto pravidlo uvádí dvě vlastnosti najednou. Za prvé, že NENÍ je funkční mapa výpočetního základu (mapuje základní stavy na základní stavy) a za druhé, že když se NOT dojíždí bránou Z-rotace, tato rotace se převrátí. | |
Eulerův rozklad | Hadamardova brána může být roztažena do tří rotací kolem Blochovy koule (odpovídající jejímu Eulerovy úhly ). Někdy je toto pravidlo bráno jako definice Hadamardova generátoru, v takovém případě jsou jedinými generátory ZX diagramů Z- a X-spider. |
Aplikace
ZX-kalkul byl použit v řadě kvantová informace a výpočet úkoly.
- Byl použit k popisu kvantový výpočet založený na měření a stavy grafů[3][15][16].
- ZX-kalkul je jazyk pro mřížová chirurgie na povrchové kódy[17][18].
- Používá se k nalezení a ověření správnosti kódy opravující kvantovou chybu[19][20][21].
- Používá se k optimalizaci kvantových obvodů[22].
Nástroje
Pravidla přepisování ZX-kalkulu lze implementovat formálně jako instanci dvojité přepisování. Toto bylo použito v softwaru Kvantomatická umožnit automatické přepisování diagramů ZX (nebo obecněji) řetězcové diagramy )[23]. Tento software používá za účelem formalizace použití „teček“ k označení libovolného počtu drátů, které se používají v pravidle spider fusion bang-box notace[24] implementovat pravidla přepisování, kde mohou mít pavouci libovolný počet vstupů nebo výstupů.
Novější projekt pro zpracování ZX diagramů je PyZX, která je primárně zaměřena na optimalizaci obvodů[14].
Související grafické jazyky
ZX-kalkul je pouze jedním z několika grafických jazyků pro popis lineárních map mezi qubity. The ZW-kalkul byl vyvinut spolu s ZX-kalkulem a může přirozeně popsat Stav W a fermionické kvantové výpočty[25][26]. Jednalo se o první grafický jazyk, který měl úplnou sadu pravidel pro přibližně univerzální sadu lineárních map mezi qubity[7]a výsledky rané úplnosti ZX-kalkulu používají redukci na ZW-kalkul.
Novějším jazykem je ZH-kalkul. Tím se přidá H-box jako generátor, který zobecňuje Hadamardovu bránu ze ZX kalkulu. Může přirozeně popsat kvantové obvody zahrnující brány Toffoli[27].
Související algebraické pojmy
Bezfázové pavouky v kalkulu ZX uspokojují axiomy a Hopfova algebra s triviální mapou jako protipólem. To lze zkontrolovat pozorováním, že je izomorfní vůči skupinové algebře .
Viz také
Reference
- ^ Coecke, Bob; Duncan, Ross (2008), „Interacting Quantum Observables“, Automaty, jazyky a programování, Přednášky v informatice, 5126Springer Berlin Heidelberg, str. 298–310, CiteSeerX 10.1.1.381.2573, doi:10.1007/978-3-540-70583-3_25, ISBN 9783540705826
- ^ Coecke, Bob; Duncan, Ross (14.04.2011). "Interagující kvantové pozorovatelnosti: kategorická algebra a schéma". New Journal of Physics. 13 (4): 043016. arXiv:0906.4725. Bibcode:2011NJPh ... 13d3016C. doi:10.1088/1367-2630/13/4/043016. ISSN 1367-2630.
- ^ A b Duncan, Ross; Perdrix, Simon (2009), „Grafové stavy a nutnost Eulerova rozkladu“, Matematická teorie a výpočetní praxeSpringer Berlin Heidelberg, s. 167–177, doi:10.1007/978-3-642-03073-4_18, ISBN 9783642030727
- ^ Backens, Miriam (2014-09-17). „ZX-kalkul je kompletní pro kvantovou mechaniku stabilizátoru“. New Journal of Physics. 16 (9): 093021. arXiv:1307.7025. Bibcode:2014NJPh ... 16i3021B. doi:10.1088/1367-2630/16/9/093021. ISSN 1367-2630.
- ^ Backens, Miriam (04.11.2015). "Dokončení výpočtu ZX-stabilizátoru pro skaláry". Elektronické řízení v teoretické informatice. 195: 17–32. arXiv:1507.03854. Bibcode:2015arXiv150703854B. doi:10,4204 / eptcs.195.2. ISSN 2075-2180.
- ^ Jeandel, Emmanuel; Perdrix, Simon; Vilmart, Renaud (2018). „Kompletní axiomatizace ZX-kalkulu pro kvantovou mechaniku Clifford + T“. Sborník 33. výročního sympózia ACM / IEEE o logice v informatice - LICS '18. New York, New York, USA: ACM Press: 559–568. arXiv:1705.11151. doi:10.1145/3209108.3209131. ISBN 9781450355834.
- ^ A b Hadzihasanovic, Amar; Ng, Kang Feng; Wang, Quanlong (2018). „Dvě úplné axiomatisace kvantového výpočtu Qubit v čistém stavu“. Proceedings of the 33.rd ACM / IEEE Symposium on Logic in Computer Science. ACM: 502–511. doi:10.1145/3209108.3209128. ISBN 9781450355834. Citováno 21. května 2019.
- ^ Jeandel, Emmanuel; Perdrix, Simon; Vilmart, Renaud (2018). „Schématické uvažování nad rámec kvantové mechaniky Clifford + T“. Sborník 33. výročního sympózia ACM / IEEE o logice v informatice - LICS '18. New York, New York, USA: ACM Press: 569–578. arXiv:1801.10142. Bibcode:2018arXiv180110142J. doi:10.1145/3209108.3209139. ISBN 9781450355834.
- ^ Coecke, Bob; Kissinger, Aleks (2017). Zobrazování kvantových procesů. Cambridge: Cambridge University Press. doi:10.1017/9781316219317. ISBN 9781316219317.
- ^ Heunen, Chris; Vicary, Jamie (2019). Kategorie pro kvantovou teorii. Oxford University Press. doi:10.1093 / oso / 9780198739623.001.0001. ISBN 9780198739616.
- ^ Bravyi, Sergey; Haah, Jeongwan (2012-11-27). „Destilace v magickém stavu s nízkou režií“. Fyzický přehled A. 86 (5): 052329. arXiv:1209.2426. Bibcode:2012PhRvA..86e2329B. doi:10.1103 / physreva.86.052329. ISSN 1050-2947.
- ^ A b C d Jezdec, Dominic; de Beaudrap, Niel (2017-04-27). „ZX kalkul je jazyk pro mřížkovou chirurgii povrchového kódu“. arXiv:1704.08670v2 [kvant. ph ].
- ^ Backens, Miriam; Perdrix, Simon; Wang, Quanlong (01.01.2017). „Zjednodušený stabilizátor ZX-kalkul“. Elektronické řízení v teoretické informatice. 236: 1–20. doi:10,4204 / eptcs.236.1. ISSN 2075-2180.
- ^ A b van de Wetering, John; Kissinger, Aleks (2019-04-09). "PyZX: Velké měřítko automatizovaného diagramatického uvažování". arXiv:1904.04735v1 [kvant. ph ].
- ^ Duncan, Ross; Perdrix, Simon (2010), „Přepis kvantových výpočtů založených na měření s generalizovaným tokem“, Automaty, jazyky a programováníSpringer Berlin Heidelberg, str. 285–296, doi:10.1007/978-3-642-14162-1_24, ISBN 9783642141614, S2CID 34644953
- ^ Kissinger, Aleks; van de Wetering, John (26.04.2019). „Univerzální MBQC s generalizovanými interakcemi paritní fáze a Pauliho měřeními“. Kvantové. 3: 134. doi:10.22331 / q-2019-04-26-134. ISSN 2521-327X.
- ^ Jezdec, Dominic; de Beaudrap, Niel (2017-04-27). „ZX kalkul je jazyk pro mřížkovou chirurgii povrchového kódu“. arXiv:1704.08670v1 [kvant. ph ].
- ^ Perdrix, Simon; Jezdec, Dominic; Duncan, Ross; de Beaudrap, Niel (2019-04-29). „Pauli Fusion: výpočetní model pro realizaci kvantových transformací z hlediska ZX“. arXiv:1904.12817v1 [kvant. ph ].
- ^ Jezdec, Dominic; Zohren, Stefan; Roffe, Joschka; Kissinger, Aleks; Kancléř, Nicholas (2016-11-23). "Grafické struktury pro návrh a ověření kvantové korekce chyb". arXiv:1611.08012v3 [kvant. ph ].
- ^ Duncan, Ross; Lucas, Maxime (2014-12-27). „Ověření kódu Steane pomocí Quantomatic“. Elektronické řízení v teoretické informatice. 171: 33–49. doi:10,4204 / eptcs.171.4. ISSN 2075-2180.
- ^ Garvie, Liam; Duncan, Ross (2018-02-27). „Ověření nejzajímavějšího barevného kódu pomocí Quantomatic“. Elektronické řízení v teoretické informatice. 266: 147–163. doi:10,4204 / eptcs.266.10. ISSN 2075-2180.
- ^ Fagan, Andrew; Duncan, Ross (31.01.2019). "Optimalizace obvodů Clifford pomocí Quantomatic". Elektronické řízení v teoretické informatice. 287: 85–105. arXiv:1901.10114. Bibcode:2019arXiv190110114F. doi:10,4204 / eptcs.287.5. ISSN 2075-2180.
- ^ Kissinger, Aleks; Zamdzhiev, Vladimir (2015), „Quantomatic: Proof Assistant for Diagrammatic Reasoning“, Automatizovaný odpočet - CADE-25, Springer International Publishing, s. 326–336, arXiv:1503.01034, Bibcode:2015arXiv150301034K, doi:10.1007/978-3-319-21401-6_22, ISBN 9783319214009
- ^ Rychle, Davide; Kissinger, Aleks (02.05.2015). "Logika prvního řádu pro řetězcové diagramy". arXiv:1505.00343v1 [math.CT ].
- ^ Coecke, Bob; Kissinger, Aleks (2010), „The Compositional Structure of Multipartite Quantum Entanglement“, Automaty, jazyky a programováníSpringer Berlin Heidelberg, str. 297–308, arXiv:1002.2540, Bibcode:2010arXiv1002.2540C, doi:10.1007/978-3-642-14162-1_25, ISBN 9783642141614
- ^ Hadzihasanovic, Amar; Duncan, Ross (2015). "Schematická axiomatizace pro Qubit Entanglement". 30. 30. výroční sympozium ACM / IEEE o logice v informatice. 573–584. arXiv:1501.07082. doi:10.1109 / lics.2015.59. ISBN 9781479988754.
- ^ Backens, Miriam; Kissinger, Aleks (2019-01-31). „ZH: Kompletní grafický počet pro kvantové výpočty zahrnující klasickou nelinearitu“. Elektronické řízení v teoretické informatice. 287: 23–42. doi:10,4204 / eptcs.287.2. ISSN 2075-2180.