Actis: En strikt lokal fackförening

Återutgiven av Platon

anhängare: 0

¹Institutionen för material, University of Oxford, Parks Road, Oxford OX1 3PH, Storbritannien
²Quantum Motion, 9 Sterling Way, London N7 9HJ, Storbritannien

Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.

Abstrakt

Feltolerant kvantberäkning kräver klassisk hårdvara för att utföra den avkodning som krävs för felkorrigering. Union–Find-avkodaren är en av de bästa kandidaterna för detta. Den har anmärkningsvärt organiska egenskaper, som involverar tillväxt och sammanslagning av datastrukturer genom närmaste granne; detta antyder naturligtvis möjligheten att den kan förverkligas med hjälp av ett gitter av enkla processorer med länkar till närmaste granne. På detta sätt kan beräkningsbelastningen fördelas med nära idealisk parallellism. Här visar vi för första gången att denna strikta (snarare än partiella) lokalitet är praktisk, med ett värsta tänkbart körtid $mathcal O(d^3)$ och genomsnittlig körtid subkvadratisk i ytkodavståndet $d$. Ett nytt paritetsberäkningsschema används som kan förenkla tidigare föreslagna arkitekturer, och vårt tillvägagångssätt är optimerat för brus på kretsnivå. Vi jämför vår lokala realisering med en förstärkt av långväga länkar; medan det senare naturligtvis är snabbare, noterar vi att lokal asynkron logik kan upphäva skillnaden.

Actis: A Strictly Local Union–Find Decoder PlatoBlockchain Data Intelligence. Vertikal sökning. Ai.

Utvald bild: Nätverket som används för styrenhet-nod-kommunikation i Actis för en avstånd-3 ytkod. Detta träd liknar avkodningsgrafen för brus på kretsnivå.

Populär sammanfattning

Kvantdatorer har potential att erbjuda banbrytande beräkningskraft, men bara om de är skyddade från brus. Detta görs via felkorrigering: ett sätt att byta ut många brusiga qubits (beräkningsenheter) mot färre men mer perfekta qubits. Den avgörande deluppgiften att övervaka mätningar från kvantprocessorn för att härleda när fel har uppstått kallas avkodning. Detta måste utföras extremt snabbt för att hålla jämna steg med kvantmaskinen. Här modifierar vi en befintlig avkodningsalgoritm för att göra den lokal, dvs. körbar på ett rutnät av identiska bearbetningsceller, var och en kommunicerar endast med sina närmaste grannar. Lokalitet har olika praktiska fördelar i hastighet, layout och robusthet. Vi testar vår lokala design och finner att dess körtid verkligen beter sig mer fördelaktigt än den ursprungliga algoritmen; vi föreslår sedan användning av "asynkron" hårdvara för att maximera vår designs absoluta prestanda.

► BibTeX-data

@article{Chan2023actisstrictlylocal, doi = {10.22331/q-2023-11-14-1183}, url = {https://doi.org/10.22331/q-2023-11-14-1183}, title = {Actis: {A} {S}trikt {L}lokal {U}nion–{F}ind {D}ecoder}, författare = {Chan, Tim och Benjamin, Simon C.}, journal = {{Quantum}}, issn = {2521-327X}, utgivare = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volym = {7}, sidor = {1183}, månad = nov, år = {2023 } }

► Referenser

[1] Eric Dennis, Alexei Kitaev, Andrew Landahl och John Preskill. "Topologiskt kvantminne". Journal of Mathematical Physics 43, 4452–4505 (2002).
https: / / doi.org/ 10.1063 / 1.1499754

[2] Austin G. Fowler, Matteo Mariantoni, John M. Martinis och Andrew N. Cleland. "Ytkoder: Mot praktisk storskalig kvantberäkning". Physical Review A 86, 032324 (2012).
https: / / doi.org/ 10.1103 / PhysRevA.86.032324

[3] Daniel Litinski. "Ett spel med ytkoder: Storskalig kvantberäkning med gallerkirurgi". Quantum 3, 128 (2019).
https://doi.org/10.22331/q-2019-03-05-128

[4] Jack Edmonds. "Stigar, träd och blommor". Canadian Journal of Mathematics 17, 449–467 (1965).
https: / / doi.org/ 10.4153 / CJM-1965-045-4

[5] Austin G. Fowler, Adam C. Whiteside och Lloyd CL Hollenberg. "Mot praktisk klassisk bearbetning av ytkoden". Physical Review Letters 108, 180501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.108.180501

[6] Guillaume Duclos-Cianci och David Poulin. "Snabba avkodare för topologiska kvantkoder". Physical Review Letters 104, 050504 (2010).
https: / / doi.org/ 10.1103 / PhysRevLett.104.050504

[7] Guillaume Duclos-Cianci och David Poulin. "En avkodningsalgoritm för renormaliseringsgrupp för topologiska kvantkoder". 2010 IEEE Information Theory Workshop. Sidorna 1–5. (2010).
https:///doi.org/10.1109/CIG.2010.5592866

[8] James R. Wootton och Daniel Loss. "Högtröskelfelkorrigering för ytkoden". Physical Review Letters 109, 160503 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.160503

[9] Ben Criger och Imran Ashraf. "Multi-path summering för avkodning av 2D topologiska koder". Quantum 2, 102 (2018).
https://doi.org/10.22331/q-2018-10-19-102

[10] Oscar Higgott, Thomas C. Bohdanowicz, Aleksander Kubica, Steven T. Flammia och Earl T. Campbell. "Förbättrad avkodning av kretsbrus och ömtåliga gränser för skräddarsydda ytkoder". Physical Review X 13, 031007 (2023).
https: / / doi.org/ 10.1103 / PhysRevX.13.031007

[11] Oscar Higgott och Nikolas P. Breuckmann. "Förbättrad enkelbildsavkodning av högredimensionella hypergraf-produktkoder". PRX Quantum 4, 020332 (2023).
https: / / doi.org/ 10.1103 / PRXQuantum.4.020332

[12] Kao-Yueh Kuo och Ching-Yi Lai. "Utnyttja degeneration i trospridningsavkodning av kvantkoder". npj Quantum Information 8, 111 (2022).
https://doi.org/10.1038/s41534-022-00623-2

[13] Milap Sheth, Sara Zafar Jafarzadeh och Vlad Gheorghiu. "Neural ensembleavkodning för topologiska kvantfelkorrigerande koder". Physical Review A 101, 032338 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.101.032338

[14] Ramon WJ Overwater, Masoud Babaie och Fabio Sebastiano. "Neurala nätverksavkodare för kvantfelskorrigering med hjälp av ytkoder: En rymdutforskning av hårdvarans kostnads-prestanda avvägningar". IEEE Transactions on Quantum Engineering 3, 1–19 (2022).
https: / / doi.org/ 10.1109 / TQE.2022.3174017

[15] Nicolas Delfosse. "Hierarkisk avkodning för att minska hårdvarukraven för kvantberäkning" (2020). arXiv:2001.11427.
arXiv: 2001.11427

[16] Kai Meinerz, Chae-Yeun Park och Simon Trebst. "Skalbar neural avkodare för topologiska ytkoder". Physical Review Letters 128, 080505 (2022).
https: / / doi.org/ 10.1103 / PhysRevLett.128.080505

[17] Gokul Subramanian Ravi, Jonathan M. Baker, Arash Fayyazi, Sophia Fuhui Lin, Ali Javadi-Abhari, Massoud Pedram och Frederic T. Chong. "Bättre än värsta tänkbara avkodning för kvantfelskorrigering". I Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volym 2. Sidorna 88–102. New York, NY, USA (2023). Föreningen för Datormaskiner.
https: / / doi.org/ 10.1145 / 3575693.3575733

[18] Samuel C. Smith, Benjamin J. Brown och Stephen D. Bartlett. "Lokal förkodare för att minska bandbredden och latensen för kvantfelskorrigering". Fysisk granskning tillämpad 19, 034050 (2023).
https: / / doi.org/ 10.1103 / PhysRevApplied.19.034050

[19] Nicolas Delfosse och Gilles Zémor. "Linjär-tids maximal sannolikhetsavkodning av ytkoder över kvantraderingskanalen". Physical Review Research 2, 033042 (2020).
https: / / doi.org/ 10.1103 / PhysRevResearch.2.033042

[20] Nicolas Delfosse och Naomi H. Nickerson. "Nästan linjär tidsavkodningsalgoritm för topologiska koder". Quantum 5, 595 (2021).
https://doi.org/10.22331/q-2021-12-02-595

[21] Namitha Liyanage, Yue Wu, Alexander Deters och Lin Zhong. "Skalbar kvantfelskorrigering för ytkoder med FPGA" (2023). arXiv:2301.08419.
arXiv: 2301.08419

[22] Alexei Yu Kitaev. "Feltolerant kvantberäkning av vem som helst". Annals of Physics 303, 2–30 (2003).
https://doi.org/10.1016/S0003-4916(02)00018-0

[23] Tim Chan (2023). kod: timchan0/localuf.
https:///github.com/timchan0/localuf

[24] Tim Chan. "Data för `Actis: A Strictly Local Union-Find Decoder"' (2023).
https: / / doi.org/ 10.5281 / zenodo.10075207

[25] Michael A. Nielsen och Isaac L. Chuang. "Kvantberäkning och kvantinformation: 10-årsjubileumsutgåva". Cambridge University Press. (2010).
https: / / doi.org/ 10.1017 / CBO9780511976667

[26] Xinyu Tan, Fang Zhang, Rui Chao, Yaoyun Shi och Jianxin Chen. ”Skalbara ytkodsavkodare med parallellisering i tid” (2022). arXiv:2209.09219.
arXiv: 2209.09219

[27] Luka Skoric, Dan E. Browne, Kenton M. Barnes, Neil I. Gillespie och Earl T. Campbell. "Parallell fönsteravkodning möjliggör skalbar feltolerant kvantberäkning". Nature Communications 14, 7040 (2023).
https://doi.org/10.1038/s41467-023-42482-1

[28] Shui Hu. "Kvasilinjär tidsavkodningsalgoritm för topologiska koder med hög feltröskel". Magisteruppsats. Delfts tekniska universitet. (2020).
https:///doi.org/10.13140/RG.2.2.13495.96162

[29] Oscar Higgott. "PyMatching: Ett Python-paket för avkodning av kvantkoder med perfekt matchning av lägsta vikt". ACM Transactions on Quantum Computing 3, 1–16 (2022).
https: / / doi.org/ 10.1145 / 3505637

[30] Yue Wu, Namitha Liyanage och Lin Zhong. "En tolkning av Union-Find-avkodare på viktade grafer" (2022). arXiv:2211.03288.
arXiv: 2211.03288

[31] Robert Endre Tarjan. "Effektiviteten hos en bra men inte linjär uppsättning unionsalgoritm". Journal of the ACM 22, 215–225 (1975).
https: / / doi.org/ 10.1145 / 321879.321884

[32] Shilin Huang, Michael Newman och Kenneth R. Brown. "Feltålig viktad unionshit-avkodning på torisk kod". Physical Review A 102, 012419 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.102.012419

[33] LMK Vandersypen, H. Bluhm, JS Clarke, AS Dzurak, R. Ishihara, A. Morello, DJ Reilly, LR Schreiber och M. Veldhorst. "Interfacing spin qubits i kvantprickar och donatorer - heta, täta och koherenta". npj Quantum Information 3, 34 (2017).
https: / / doi.org/ 10.1038 / s41534-017-0038-y

[34] Andrew Richards. "University of Oxford Advanced Research Computing". (2015).
https: / / doi.org/ 10.5281 / zenodo.22558

[35] Sam J. Griffiths och Dan E. Browne. "Union-find kvantavkodning utan union-find" (2023). arXiv:2306.09767.
arXiv: 2306.09767

[36] Ben Barber, Kenton M. Barnes, Tomasz Bialas, Okan Buğdaycı, Earl T. Campbell, Neil I. Gillespie, Kauser Johar, Ram Rajan, Adam W. Richardson, Luka Skoric, Canberk Topal, Mark L. Turner och Abbas B. Ziad. "En skalbar, snabb och mycket resurseffektiv dekoder för en kvantdator i realtid" (2023). arXiv:2309.05558.
arXiv: 2309.05558

[37] David S. Wang, Austin G. Fowler och Lloyd CL Hollenberg. "Kvantberäkning av ytkod med felfrekvenser över 1%". Physical Review A 83, 020302 (2011).
https: / / doi.org/ 10.1103 / PhysRevA.83.020302

[38] Emanuel Knill. "Quantum computing med realistiskt bullriga enheter". Nature 434, 39–44 (2005).
https: / / doi.org/ 10.1038 / nature03350

[39] Oscar Higgott och Craig Gidney. "Sparse Blossom: korrigera en miljon fel per kärnsekund med minsta viktmatchning" (2023). arXiv:2303.15933.
arXiv: 2303.15933

[40] Austin G. Fowler, Adam C. Whiteside och Lloyd CL Hollenberg. "Mot praktisk klassisk bearbetning av ytkoden: tidsanalys". Physical Review A 86, 042313 (2012).
https: / / doi.org/ 10.1103 / PhysRevA.86.042313

[41] Yue Wu och Lin Zhong. "Fusion Blossom: Fast MWPM-avkodare för QEC" (2023). arXiv:2305.08307.
arXiv: 2305.08307

Citerad av

[1] Sam J. Griffiths och Dan E. Browne, "Union-find quantum decoding without union-find", arXiv: 2306.09767, (2023).

[2] Asmae Benhemou, Kaavya Sahay, Lingling Lao och Benjamin J. Brown, "Minimering av ytkodsfel med hjälp av en färgkodsavkodare", arXiv: 2306.16476, (2023).

Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2023-11-14 13:28:32). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.

Det gick inte att hämta Crossref citerade data under senaste försöket 2023-11-14 13:28:31: Det gick inte att hämta citerade data för 10.22331 / q-2023-11-14-1183 från Crossref. Detta är normalt om DOI registrerades nyligen.

Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.