Actis: Ein ausschließlich lokaler Union-Find-Decoder

Neuauflage von Plato

Verfolger: 0

¹Department of Materials, University of Oxford, Parks Road, Oxford OX1 3PH, Vereinigtes Königreich
²Quantum Motion, 9 Sterling Way, London N7 9HJ, Vereinigtes Königreich

Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.

Abstrakt

Fehlertolerantes Quantencomputing erfordert klassische Hardware, um die zur Fehlerkorrektur erforderliche Dekodierung durchzuführen. Der Union-Find-Decoder ist hierfür einer der besten Kandidaten. Es verfügt über bemerkenswert organische Eigenschaften, die das Wachstum und die Zusammenführung von Datenstrukturen durch Schritte des nächsten Nachbarn beinhalten; Dies legt natürlich die Möglichkeit seiner Realisierung mithilfe eines Netzwerks einfacher Prozessoren mit Verbindungen zum nächsten Nachbarn nahe. Auf diese Weise kann die Rechenlast mit nahezu idealer Parallelität verteilt werden. Hier zeigen wir zum ersten Mal, dass diese strikte (statt partielle) Lokalität praktisch ist, mit einer Worst-Case-Laufzeit $mathcal O(d^3)$ und einer mittleren Laufzeit subquadratisch im Oberflächencodeabstand $d$. Es kommt ein neuartiges Paritätsberechnungsschema zum Einsatz, das zuvor vorgeschlagene Architekturen vereinfachen kann, und unser Ansatz ist für Rauschen auf Schaltungsebene optimiert. Wir vergleichen unsere lokale Realisierung mit einer durch Fernverbindungen erweiterten; Während Letzteres natürlich schneller ist, stellen wir fest, dass lokale asynchrone Logik den Unterschied zunichte machen könnte.

Actis: Eine streng lokale Union – Find Decoder PlatoBlockchain Data Intelligence. Vertikale Suche. Ai.

Ausgewähltes Bild: Das Netzwerk, das für die Controller-Knoten-Kommunikation in Actis für einen Distanz-3-Oberflächencode verwendet wird. Dieser Baum ähnelt dem Dekodierungsdiagramm für Rauschen auf Schaltungsebene.

Populäre Zusammenfassung

Quantencomputer haben das Potenzial, bahnbrechende Rechenleistung zu bieten, aber nur, wenn sie vor Rauschen geschützt sind. Dies geschieht durch Fehlerkorrektur: eine Möglichkeit, viele verrauschte Qubits (Recheneinheiten) gegen weniger, aber perfektere Qubits auszutauschen. Die entscheidende Teilaufgabe der Überwachung der Messungen des Quantenprozessors, um abzuleiten, wann Fehler aufgetreten sind, wird als Dekodierung bezeichnet. Dies muss extrem schnell erfolgen, um mit der Quantenmaschine Schritt zu halten. Hier modifizieren wir einen vorhandenen Decodierungsalgorithmus, um ihn lokal zu machen, dh auf einem Raster identischer Verarbeitungszellen ausführbar zu machen, von denen jede nur mit ihren nächsten Nachbarn kommuniziert. Locality bietet verschiedene praktische Vorteile in Bezug auf Geschwindigkeit, Layout und Robustheit. Wir testen unser lokales Design und stellen fest, dass sich seine Laufzeit tatsächlich günstiger verhält als der ursprüngliche Algorithmus; Wir schlagen dann die Verwendung von „asynchroner“ Hardware vor, um die absolute Leistung unseres Designs zu maximieren.

► BibTeX-Daten

@article{Chan2023actisstrictlylocal, doi = {10.22331/q-2023-11-14-1183}, url = {https://doi.org/10.22331/q-2023-11-14-1183}, Titel = {Actis: {A} {S}trictly {L}ocal {U}nion–{F}ind {D}ecoder}, Autor = {Chan, Tim und Benjamin, Simon C.}, Zeitschrift = {{Quantum}}, issn = {2521-327X}, Herausgeber = {{Verein zur F{“{o}}rdung des Open Access Publizierens in den Quantenwissenschaften}}, Band = {7}, Seiten = {1183}, Monat = Nov, Jahr = {2023 } }

► Referenzen

[1] Eric Dennis, Alexei Kitaev, Andrew Landahl und John Preskill. „Topologischer Quantenspeicher“. Zeitschrift für mathematische Physik 43, 4452–4505 (2002).
https: / / doi.org/ 10.1063 / 1.1499754

[2] Austin G. Fowler, Matteo Mariantoni, John M. Martinis und Andrew N. Cleland. "Oberflächencodes: Auf dem Weg zur praktischen Quantenberechnung im großen Maßstab". Physical Review A 86, 032324 (2012).
https: / / doi.org/ 10.1103 / PhysRevA.86.032324

[3] Daniel Litinski. „Ein Spiel mit Oberflächencodes: Quantencomputing im großen Maßstab mit Gitterchirurgie“. Quantum 3, 128 (2019).
https://doi.org/10.22331/q-2019-03-05-128

[4] Jack Edmonds. „Wege, Bäume und Blumen“. Canadian Journal of Mathematics 17, 449–467 (1965).
https: / / doi.org/ 10.4153 / CJM-1965-045-4

[5] Austin G. Fowler, Adam C. Whiteside und Lloyd CL Hollenberg. „Auf dem Weg zur praktischen klassischen Verarbeitung für den Oberflächencode“. Physical Review Letters 108, 180501 (2012).
https://doi.org/ 10.1103/PhysRevLett.108.180501

[6] Guillaume Duclos-Cianci und David Poulin. „Schnelle Decoder für topologische Quantencodes“. Physical Review Letters 104, 050504 (2010).
https://doi.org/ 10.1103/PhysRevLett.104.050504

[7] Guillaume Duclos-Cianci und David Poulin. „Ein Renormierungsgruppen-Dekodierungsalgorithmus für topologische Quantencodes“. Im Jahr 2010 IEEE Information Theory Workshop. Seiten 1–5. (2010).
https:///doi.org/10.1109/CIG.2010.5592866

[8] James R. Wootton und Daniel Loss. „Hochschwellige Fehlerkorrektur für den Oberflächencode“. Physical Review Letters 109, 160503 (2012).
https://doi.org/ 10.1103/PhysRevLett.109.160503

[9] Ben Criger und Imran Ashraf. "Mehrwegesummierung zum Dekodieren von 2D-topologischen Codes". 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 und Earl T. Campbell. „Verbesserte Dekodierung von Schaltungsrauschen und fragilen Grenzen maßgeschneiderter Oberflächencodes“. Körperliche Überprüfung X 13, 031007 (2023).
https://doi.org/ 10.1103/PhysRevX.13.031007

[11] Oscar Higgott und Nikolas P. Breuckmann. „Verbesserte Single-Shot-Dekodierung höherdimensionaler Hypergraph-Produktcodes“. PRX Quantum 4, 020332 (2023).
https: / / doi.org/ 10.1103 / PRXQuantum.4.020332

[12] Kao-Yueh Kuo und Ching-Yi Lai. „Ausnutzung der Entartung bei der Glaubensausbreitungsdekodierung von Quantencodes“. npj Quantum Information 8, 111 (2022).
https://doi.org/10.1038/s41534-022-00623-2

[13] Milap Sheth, Sara Zafar Jafarzadeh und Vlad Gheorghiu. „Dekodierung neuronaler Ensembles für topologische Quantenfehlerkorrekturcodes“. Physical Review A 101, 032338 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.101.032338

[14] Ramon WJ Overwater, Masoud Babaie und Fabio Sebastiano. „Neuronale Netzwerkdecoder zur Quantenfehlerkorrektur mithilfe von Oberflächencodes: Eine Weltraumforschung der Hardware-Kosten-Leistungs-Kompromisse“. IEEE Transactions on Quantum Engineering 3, 1–19 (2022).
https: / / doi.org/ 10.1109 / TQE.2022.3174017

[15] Nicolas Delfosse. „Hierarchische Dekodierung zur Reduzierung der Hardwareanforderungen für Quantencomputing“ (2020). arXiv:2001.11427.
arXiv: 2001.11427

[16] Kai Meinerz, Chae-Yeun Park und Simon Trebst. „Skalierbarer neuronaler Decoder für topologische Oberflächencodes“. 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 und Frederic T. Chong. „Besser als die Worst-Case-Dekodierung zur Quantenfehlerkorrektur“. In Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Band 2. Seiten 88–102. New York, NY, USA (2023). Verband für Rechenmaschinen.
https: / / doi.org/ 10.1145 / 3575693.3575733

[18] Samuel C. Smith, Benjamin J. Brown und Stephen D. Bartlett. „Lokaler Vordecoder zur Reduzierung der Bandbreite und Latenz der Quantenfehlerkorrektur“. Physical Review Applied 19, 034050 (2023).
https: / / doi.org/ 10.1103 / PhysRevApplied.19.034050

[19] Nicolas Delfosse und Gilles Zémor. „Linearzeit-Maximum-Likelihood-Dekodierung von Oberflächencodes über den Quantenlöschkanal“. Physical Review Research 2, 033042 (2020).
https: / / doi.org/ 10.1103 / PhysRevResearch.2.033042

[20] Nicolas Delfosse und Naomi H. Nickerson. „Annähernd linearer Zeitdekodierungsalgorithmus für topologische Codes“. Quantum 5, 595 (2021).
https://doi.org/10.22331/q-2021-12-02-595

[21] Namitha Liyanage, Yue Wu, Alexander Deters und Lin Zhong. „Skalierbare Quantenfehlerkorrektur für Oberflächencodes mittels FPGA“ (2023). arXiv:2301.08419.
arXiv: 2301.08419

[22] Alexei Yu Kitaev. „Fehlertolerante Quantenberechnung durch jedermann“. Annals of Physics 303, 2–30 (2003).
https://doi.org/10.1016/S0003-4916(02)00018-0

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

[24] Tim Chan. „Daten für „Actis: A Strictly Local Union–Find Decoder““ (2023).
https: / / doi.org/ 10.5281 / zenodo.10075207

[25] Michael A. Nielsen und Isaac L. Chuang. „Quantenberechnung und Quanteninformation: Ausgabe zum 10-jährigen Jubiläum“. Cambridge University Press. (2010).
https: / / doi.org/ 10.1017 / CBO9780511976667

[26] Xinyu Tan, Fang Zhang, Rui Chao, Yaoyun Shi und Jianxin Chen. „Skalierbare Oberflächencode-Decoder mit zeitlicher Parallelisierung“ (2022). arXiv:2209.09219.
arXiv: 2209.09219

[27] Luka Skoric, Dan E. Browne, Kenton M. Barnes, Neil I. Gillespie und Earl T. Campbell. „Parallele Fensterdekodierung ermöglicht skalierbare fehlertolerante Quantenberechnung.“ Nature Communications 14, 7040 (2023).
https://doi.org/10.1038/s41467-023-42482-1

[28] Shui Hu. „Quasilinearer Zeitdekodierungsalgorithmus für topologische Codes mit hoher Fehlerschwelle“. Masterarbeit. Technische Universität Delft. (2020).
https:///doi.org/10.13140/RG.2.2.13495.96162

[29] Oscar Higgott. „PyMatching: Ein Python-Paket zum Dekodieren von Quantencodes mit perfektem Matching mit minimalem Gewicht“. ACM-Transaktionen zum Quantencomputing 3, 1–16 (2022).
https: / / doi.org/ 10.1145 / 3505637

[30] Yue Wu, Namitha Liyanage und Lin Zhong. „Eine Interpretation des Union-Find-Decoders in gewichteten Diagrammen“ (2022). arXiv:2211.03288.
arXiv: 2211.03288

[31] Robert Endre Tarjan. „Effizienz eines guten, aber nicht linearen Mengenvereinigungsalgorithmus“. Journal of the ACM 22, 215–225 (1975).
https: / / doi.org/ 10.1145 / 321879.321884

[32] Shilin Huang, Michael Newman und Kenneth R. Brown. „Fehlertolerante gewichtete Union-Find-Dekodierung für den torischen Code“. 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 und M. Veldhorst. „Schnittstellen von Spin-Qubits in Quantenpunkten und Donoren – heiß, dicht und kohärent“. npj Quantum Information 3, 34 (2017).
https: / / doi.org/ 10.1038 / s41534-017-0038-y

[34] Andrew Richards. „Advanced Research Computing der Universität Oxford“. (2015).
https: / / doi.org/ 10.5281 / zenodo.22558

[35] Sam J. Griffiths und Dan E. Browne. „Union-Find-Quantendekodierung ohne 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 und Abbas B. Ziad. „Ein echtzeitfähiger, skalierbarer, schneller und äußerst ressourceneffizienter Decoder für einen Quantencomputer“ (2023). arXiv:2309.05558.
arXiv: 2309.05558

[37] David S. Wang, Austin G. Fowler und Lloyd CL Hollenberg. „Oberflächencode-Quantencomputing mit Fehlerraten über 1 %“. Physical Review A 83, 020302 (2011).
https: / / doi.org/ 10.1103 / PhysRevA.83.020302

[38] Emanuel Knill. „Quantencomputing mit realistisch verrauschten Geräten“. Natur 434, 39–44 (2005).
https: / / doi.org/ 10.1038 / nature03350

[39] Oscar Higgott und Craig Gidney. „Sparse Blossom: Korrektur einer Million Fehler pro Kernsekunde mit Minimum-Weight-Matching“ (2023). arXiv:2303.15933.
arXiv: 2303.15933

[40] Austin G. Fowler, Adam C. Whiteside und Lloyd CL Hollenberg. „Auf dem Weg zur praktischen klassischen Verarbeitung für den Oberflächencode: Timing-Analyse“. Physical Review A 86, 042313 (2012).
https: / / doi.org/ 10.1103 / PhysRevA.86.042313

[41] Yue Wu und Lin Zhong. „Fusion Blossom: Schnelle MWPM-Decoder für QEC“ (2023). arXiv:2305.08307.
arXiv: 2305.08307

Zitiert von

[1] Sam J. Griffiths und Dan E. Browne, „Union-Find-Quantendekodierung ohne Union-Find“, arXiv: 2306.09767, (2023).

[2] Asmae Benhemou, Kaavya Sahay, Lingling Lao und Benjamin J. Brown, „Minimierung von Oberflächencodefehlern mithilfe eines Farbcode-Decoders“, arXiv: 2306.16476, (2023).

Die obigen Zitate stammen von SAO / NASA ADS (Zuletzt erfolgreich aktualisiert am 2023, 11:14:13 Uhr). Die Liste ist möglicherweise unvollständig, da nicht alle Verlage geeignete und vollständige Zitationsdaten bereitstellen.

Konnte nicht abrufen Crossref zitiert von Daten während des letzten Versuchs 2023-11-14 13:28:31: Von Crossref konnten keine zitierten Daten für 10.22331 / q-2023-11-14-1183 abgerufen werden. Dies ist normal, wenn der DOI kürzlich registriert wurde.

Dieses Papier ist in Quantum unter dem veröffentlicht Creative Commons Namensnennung 4.0 International (CC BY 4.0) Lizenz. Das Copyright verbleibt bei den ursprünglichen Copyright-Inhabern wie den Autoren oder deren Institutionen.