Actis: A Strictly Local Union – Finn dekoder

Actis: A Strictly Local Union – Finn dekoder

Tidsstempel: 14. november 2023, kl

Tim Chan1 og Simon C. Benjamin1,2

1Institutt for materialer, University of Oxford, Parks Road, Oxford OX1 3PH, Storbritannia
2Quantum Motion, 9 Sterling Way, London N7 9HJ, Storbritannia

Finn dette papiret interessant eller vil diskutere? Scite eller legg igjen en kommentar på SciRate.

Abstrakt

Feiltolerant kvanteberegning krever klassisk maskinvare for å utføre dekodingen som er nødvendig for feilretting. Union–Find-dekoderen er en av de beste kandidatene for dette. Den har bemerkelsesverdige organiske egenskaper, som involverer vekst og sammenslåing av datastrukturer gjennom nærmeste nabotrinn; dette antyder naturligvis muligheten for realisering ved hjelp av et gitter av enkle prosessorer med nærmeste nabolenker. På denne måten kan beregningsbelastningen fordeles med nesten ideell parallellitet. Her viser vi for første gang at denne strenge (snarere enn delvise) lokaliteten er praktisk, med en worst-case runtime $mathcal O(d^3)$ og gjennomsnittlig runtime subquadratic i overflatekodeavstanden $d$. Et nytt paritetsberegningsskjema er brukt som kan forenkle tidligere foreslåtte arkitekturer, og vår tilnærming er optimalisert for støy på kretsnivå. Vi sammenligner vår lokale realisering med en utvidet med langdistansekoblinger; mens sistnevnte selvfølgelig er raskere, merker vi at lokal asynkron logikk kan oppheve forskjellen.

Actis: A Strictly Local Union – Finn dekoder PlatoBlockchain Data Intelligence. Vertikalt søk. Ai.

Utvalgt bilde: Nettverket som brukes for kontroller-node-kommunikasjon i Actis for en avstand-3-overflatekode. Dette treet ligner på dekodingsgrafen for støy på kretsnivå.

Populært sammendrag

Kvantedatamaskiner har potensial til å tilby banebrytende beregningskraft, men bare hvis de er beskyttet mot støy. Dette gjøres via feilretting: en måte å bytte ut mange støyende qubits (beregningsenheter) for færre, men mer perfekte qubits. Den avgjørende deloppgaven med å overvåke målinger fra kvanteprosessoren for å utlede når feil har oppstått kalles dekoding. Dette må utføres ekstremt raskt for å holde tritt med kvantemaskinen. Her modifiserer vi en eksisterende dekodingsalgoritme for å gjøre den lokal, dvs. kjørebar på et rutenett av identiske prosesseringsceller, som hver kommuniserer kun med sine nærmeste naboer. Lokalitet har ulike praktiske fordeler i hastighet, planløsning og robusthet. Vi tester vårt lokale design og finner ut at kjøretiden faktisk oppfører seg mer gunstig enn den opprinnelige algoritmen; Vi foreslår da bruk av 'asynkron' maskinvare for å maksimere designens absolutte ytelse.

► BibTeX-data

► Referanser

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

[2] Austin G. Fowler, Matteo Mariantoni, John M. Martinis og Andrew N. Cleland. "Overflatekoder: Mot praktisk storskala kvanteberegning". Physical Review A 86, 032324 (2012).
https: / / doi.org/ 10.1103 / PhysRevA.86.032324

[3] Daniel Litinski. "Et spill med overflatekoder: Storskala kvanteberegning med gitterkirurgi". Quantum 3, 128 (2019).
https:/​/​doi.org/​10.22331/​q-2019-03-05-128

[4] Jack Edmonds. "Stier, trær og blomster". Canadian Journal of Mathematics 17, 449–467 (1965).
https: / / doi.org/ 10.4153 / Mesowest-1965-045-4

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

[6] Guillaume Duclos-Cianci og David Poulin. "Raske dekodere for topologiske kvantekoder". Physical Review Letters 104, 050504 (2010).
https: / / doi.org/ 10.1103 / PhysRevLett.104.050504

[7] Guillaume Duclos-Cianci og David Poulin. "En renormaliseringsgruppedekodingsalgoritme for topologiske kvantekoder". I 2010 IEEE Information Theory Workshop. Side 1–5. (2010).
https://​/​doi.org/​10.1109/​CIG.2010.5592866

[8] James R. Wootton og Daniel Loss. "Høyterskel feilkorrigering for overflatekoden". Physical Review Letters 109, 160503 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.160503

[9] Ben Criger og Imran Ashraf. "Multi-path summering for dekoding 2D topologiske 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 og Earl T. Campbell. "Forbedret dekoding av kretsstøy og skjøre grenser for skreddersydde overflatekoder". Fysisk gjennomgang X 13, 031007 (2023).
https: / / doi.org/ 10.1103 / PhysRevX.13.031007

[11] Oscar Higgott og Nikolas P. Breuckmann. "Forbedret enkeltbildsdekoding av høyere dimensjonale hypergraf-produktkoder". PRX Quantum 4, 020332 (2023).
https: / / doi.org/ 10.1103 / PRXQuantum.4.020332

[12] Kao-Yueh Kuo og Ching-Yi Lai. "Utnytte degenerasjon i trosforplantningsdekoding av kvantekoder". npj Quantum Information 8, 111 (2022).
https:/​/​doi.org/​10.1038/​s41534-022-00623-2

[13] Milap Sheth, Sara Zafar Jafarzadeh og Vlad Gheorghiu. "Neural ensemble-dekoding for topologiske kvantefeilkorrigerende koder". Physical Review A 101, 032338 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.101.032338

[14] Ramon WJ Overwater, Masoud Babaie og Fabio Sebastiano. "Neural-nettverksdekodere for kvantefeilkorreksjon ved bruk av overflatekoder: En romutforskning av maskinvarekostnad-ytelse-avveiningene". IEEE Transactions on Quantum Engineering 3, 1–19 (2022).
https: / / doi.org/ 10.1109 / TQE.2022.3174017

[15] Nicolas Delfosse. "Hierarkisk dekoding for å redusere maskinvarekrav for kvantedatabehandling" (2020). arXiv:2001.11427.
arxiv: 2001.11427

[16] Kai Meinerz, Chae-Yeun Park og Simon Trebst. "Skalerbar nevrale dekoder for topologiske overflatekoder". 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 og Frederic T. Chong. "Bedre enn worst-case-dekoding for kvantefeilkorreksjon". I Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages ​​and Operating Systems, bind 2. Side 88–102. New York, NY, USA (2023). Foreningen for datamaskiner.
https: / / doi.org/ 10.1145 / 3575693.3575733

[18] Samuel C. Smith, Benjamin J. Brown og Stephen D. Bartlett. "Lokal forkoder for å redusere båndbredden og latensen for kvantefeilkorreksjon". Fysisk gjennomgang Søkt 19, 034050 (2023).
https: / / doi.org/ 10.1103 / PhysRevApplied.19.034050

[19] Nicolas Delfosse og Gilles Zémor. "Lineær-tids maksimal sannsynlighetsdekoding av overflatekoder over kvanteslettingskanalen". Physical Review Research 2, 033042 (2020).
https: / / doi.org/ 10.1103 / PhysRevResearch.2.033042

[20] Nicolas Delfosse og Naomi H. Nickerson. "Nesten lineær tidsdekodingsalgoritme for topologiske koder". Quantum 5, 595 (2021).
https:/​/​doi.org/​10.22331/​q-2021-12-02-595

[21] Namitha Liyanage, Yue Wu, Alexander Deters og Lin Zhong. "Skalerbar kvantefeilkorreksjon for overflatekoder ved bruk av FPGA" (2023). arXiv:2301.08419.
arxiv: 2301.08419

[22] Alexei Yu Kitaev. "Filtolerant kvanteberegning av noen". Annals of Physics 303, 2–30 (2003).
https:/​/​doi.org/​10.1016/​S0003-4916(02)00018-0

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

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

[25] Michael A. Nielsen og Isaac L. Chuang. "Kvanteberegning og kvanteinformasjon: 10-årsjubileumsutgave". Cambridge University Press. (2010).
https: / / doi.org/ 10.1017 / CBO9780511976667

[26] Xinyu Tan, Fang Zhang, Rui Chao, Yaoyun Shi og Jianxin Chen. "Skalerbare overflatekodedekodere med parallellisering i tid" (2022). arXiv:2209.09219.
arxiv: 2209.09219

[27] Luka Skoric, Dan E. Browne, Kenton M. Barnes, Neil I. Gillespie og Earl T. Campbell. "Parallell vindusdekoding muliggjør skalerbar feiltolerant kvanteberegning". Nature Communications 14, 7040 (2023).
https:/​/​doi.org/​10.1038/​s41467-023-42482-1

[28] Shui Hu. "Kvasilineær tidsdekodingsalgoritme for topologiske koder med høy feilterskel". Masteroppgave. Delft teknologiske universitet. (2020).
https://​/​doi.org/​10.13140/​RG.2.2.13495.96162

[29] Oscar Higgott. "PyMatching: En Python-pakke for dekoding av kvantekoder med perfekt matching med minimumsvekt". ACM Transactions on Quantum Computing 3, 1–16 (2022).
https: / / doi.org/ 10.1145 / 3505637

[30] Yue Wu, Namitha Liyanage og Lin Zhong. "En tolkning av Union-Find-dekoder på vektede grafer" (2022). arXiv:2211.03288.
arxiv: 2211.03288

[31] Robert Endre Tarjan. "Effektiviteten til en god, men ikke lineær sett unionsalgoritme". Journal of the ACM 22, 215–225 (1975).
https: / / doi.org/ 10.1145 / 321879.321884

[32] Shilin Huang, Michael Newman og Kenneth R. Brown. "Filtolerant vektet union-finn-dekoding på den toriske koden". 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 og M. Veldhorst. "Interfacing spin qubits i kvanteprikker og donorer - varme, tette og sammenhengende". 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 og Dan E. Browne. "Union-finn kvantedekoding uten union-finn" (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 og Abbas B. Ziad. "En sanntids, skalerbar, rask og svært ressurseffektiv dekoder for en kvantedatamaskin" (2023). arXiv:2309.05558.
arxiv: 2309.05558

[37] David S. Wang, Austin G. Fowler og Lloyd CL Hollenberg. "Overflatekodekvanteberegning med feilrater over 1 %". Physical Review A 83, 020302 (2011).
https: / / doi.org/ 10.1103 / PhysRevA.83.020302

[38] Emanuel Knill. "Kvantedatabehandling med realistisk støyende enheter". Nature 434, 39–44 (2005).
https: / / doi.org/ 10.1038 / nature03350

[39] Oscar Higgott og Craig Gidney. "Sparse Blossom: korrigere en million feil per kjernesekund med matching av minimumsvekt" (2023). arXiv:2303.15933.
arxiv: 2303.15933

[40] Austin G. Fowler, Adam C. Whiteside og Lloyd CL Hollenberg. "Mot praktisk klassisk prosessering for overflatekoden: tidsanalyse". Physical Review A 86, 042313 (2012).
https: / / doi.org/ 10.1103 / PhysRevA.86.042313

[41] Yue Wu og Lin Zhong. "Fusion Blossom: Fast MWPM-dekodere for QEC" (2023). arXiv:2305.08307.
arxiv: 2305.08307

Sitert av

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

[2] Asmae Benhemou, Kaavya Sahay, Lingling Lao og Benjamin J. Brown, "Minimering av overflatekodefeil ved bruk av en fargekodedekoder", arxiv: 2306.16476, (2023).

Sitatene ovenfor er fra SAO / NASA ADS (sist oppdatert vellykket 2023-11-14 13:28:32). Listen kan være ufullstendig fordi ikke alle utgivere gir passende og fullstendige sitasjonsdata.

Kunne ikke hente Crossref sitert av data under siste forsøk 2023-11-14 13:28:31: Kunne ikke hente siterte data for 10.22331 / q-2023-11-14-1183 fra Crossref. Dette er normalt hvis DOI nylig ble registrert.

Denne artikkelen er utgitt i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) tillatelse. Opphavsrett forblir hos de opprinnelige rettighetshaverne som forfatterne eller institusjonene deres.

Tidstempel:

Mer fra Kvantejournal