Actis: A Strictly Local Union–Find Decoder

Actis: A Strictly Local Union–Find Decoder

Χρονική σήμανση: 14 Νοεμβρίου 2023 6:58 π.μ.

Τιμ Τσαν1 και Simon C. Benjamin1,2

1Department of Materials, University of Oxford, Parks Road, Oxford OX1 3PH, Ηνωμένο Βασίλειο
2Quantum Motion, 9 Sterling Way, Λονδίνο N7 9HJ, Ηνωμένο Βασίλειο

Βρείτε αυτό το άρθρο ενδιαφέρουσα ή θέλετε να συζητήσετε; Scite ή αφήστε ένα σχόλιο για το SciRate.

Περίληψη

Ο κβαντικός υπολογισμός με ανοχή σε σφάλματα απαιτεί κλασικό υλικό για την εκτέλεση της αποκωδικοποίησης που είναι απαραίτητη για τη διόρθωση σφαλμάτων. Ο αποκωδικοποιητής Union–Find είναι ένας από τους καλύτερους υποψήφιους για αυτό. Έχει εξαιρετικά οργανικά χαρακτηριστικά, που περιλαμβάνουν την ανάπτυξη και τη συγχώνευση δομών δεδομένων μέσω βημάτων πλησιέστερου γείτονα. Αυτό φυσικά υποδηλώνει τη δυνατότητα πραγματοποίησής του χρησιμοποιώντας ένα πλέγμα απλών επεξεργαστών με συνδέσμους πλησιέστερου γείτονα. Με αυτόν τον τρόπο το υπολογιστικό φορτίο μπορεί να κατανεμηθεί με σχεδόν ιδανικό παραλληλισμό. Εδώ δείχνουμε για πρώτη φορά ότι αυτή η αυστηρή (και όχι μερική) τοποθεσία είναι πρακτική, με χρόνο εκτέλεσης στη χειρότερη περίπτωση $mathcal O(d^3)$ και μέσο όρο χρόνου εκτέλεσης υποτετραγωνικό στην απόσταση του κωδικού επιφάνειας $d$. Χρησιμοποιείται ένα νέο σχήμα υπολογισμού ισοτιμίας που μπορεί να απλοποιήσει προηγουμένως προτεινόμενες αρχιτεκτονικές και η προσέγγισή μας είναι βελτιστοποιημένη για θόρυβο σε επίπεδο κυκλώματος. Συγκρίνουμε την τοπική μας υλοποίηση με μια επαυξημένη από συνδέσμους μεγάλης εμβέλειας. ενώ το τελευταίο είναι φυσικά πιο γρήγορο, σημειώνουμε ότι η τοπική ασύγχρονη λογική θα μπορούσε να αναιρέσει τη διαφορά.

Actis: A Strictly Local Union–Find Decoder PlatoBlockchain Data Intelligence. Κάθετη αναζήτηση. Ολα συμπεριλαμβάνονται.

Επιλεγμένη εικόνα: Το δίκτυο που χρησιμοποιείται για την επικοινωνία ελεγκτή-κόμβου στο Actis για έναν κωδικό επιφάνειας απόστασης-3. Αυτό το δέντρο είναι παρόμοιο με το γράφημα αποκωδικοποίησης για το θόρυβο σε επίπεδο κυκλώματος.

Δημοφιλή περίληψη

Οι κβαντικοί υπολογιστές έχουν τη δυνατότητα να προσφέρουν πρωτοποριακή υπολογιστική ισχύ, αλλά μόνο εάν προστατεύονται από το θόρυβο. Αυτό γίνεται μέσω διόρθωσης σφαλμάτων: ένας τρόπος ανταλλαγής πολλών θορυβωδών qubit (μονάδες υπολογισμού) για λιγότερα αλλά πιο τέλεια qubits. Η κρίσιμη δευτερεύουσα εργασία της παρακολούθησης των μετρήσεων από τον κβαντικό επεξεργαστή για να συμπεράνουμε πότε έχουν συμβεί σφάλματα ονομάζεται αποκωδικοποίηση. Αυτό πρέπει να γίνει εξαιρετικά γρήγορα για να συμβαδίσει με την κβαντική μηχανή. Εδώ τροποποιούμε έναν υπάρχοντα αλγόριθμο αποκωδικοποίησης για να τον καταστήσουμε τοπικό, π.χ. εκτελούμενο σε ένα πλέγμα πανομοιότυπων κυψελών επεξεργασίας, το καθένα επικοινωνώντας μόνο με τους πλησιέστερους γείτονές του. Η τοπικότητα έχει διάφορα πρακτικά πλεονεκτήματα σε ταχύτητα, διάταξη και στιβαρότητα. Δοκιμάζουμε τον τοπικό μας σχεδιασμό και διαπιστώνουμε ότι ο χρόνος εκτέλεσης του συμπεριφέρεται όντως πιο ευνοϊκά από τον αρχικό αλγόριθμο. Στη συνέχεια προτείνουμε τη χρήση «ασύγχρονου» υλικού για να μεγιστοποιήσουμε την απόλυτη απόδοση του σχεδιασμού μας.

► Δεδομένα BibTeX

► Αναφορές

[1] Eric Dennis, Alexei Kitaev, Andrew Landahl και John Preskill. «Τοπολογική κβαντική μνήμη». Journal of Mathematical Physics 43, 4452–4505 (2002).
https: / / doi.org/ 10.1063 / 1.1499754

[2] Austin G. Fowler, Matteo Mariantoni, John M. Martinis και Andrew N. Cleland. «Κώδικες επιφανειών: Προς πρακτικούς κβαντικούς υπολογισμούς μεγάλης κλίμακας». Physical Review A 86, 032324 (2012).
https: / / doi.org/ 10.1103 / PhysRevA.86.032324

[3] Ντάνιελ Λιτίνσκι. «Ένα παιχνίδι επιφανειακών κωδίκων: Κβαντικοί υπολογιστές μεγάλης κλίμακας με χειρουργική πλέγματος». Quantum 3, 128 (2019).
https:/​/​doi.org/​10.22331/​q-2019-03-05-128

[4] Τζακ Έντμοντς. «Μονοπάτια, δέντρα και λουλούδια». Canadian Journal of Mathematics 17, 449–467 (1965).
https: / / doi.org/ 10.4153 / CJM-1965-045-4

[5] Austin G. Fowler, Adam C. Whiteside και Lloyd CL Hollenberg. «Προς πρακτική κλασική επεξεργασία για τον επιφανειακό κώδικα». Physical Review Letters 108, 180501 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.108.180501

[6] Guillaume Duclos-Cianci και David Poulin. «Γρήγοροι αποκωδικοποιητές για τοπολογικούς κβαντικούς κώδικες». Physical Reviw Letters 104, 050504 (2010).
https: / / doi.org/ 10.1103 / PhysRevLett.104.050504

[7] Guillaume Duclos-Cianci και David Poulin. «Αλγόριθμος αποκωδικοποίησης ομάδας επανακανονικοποίησης για τοπολογικούς κβαντικούς κώδικες». Το 2010 IEEE Information Theory Workshop. Σελίδες 1–5. (2010).
https://doi.org/​10.1109/​CIG.2010.5592866

[8] James R. Wootton και Daniel Loss. «Διόρθωση σφάλματος υψηλού ορίου για τον κωδικό επιφάνειας». Physical Review Letters 109, 160503 (2012).
https: / / doi.org/ 10.1103 / PhysRevLett.109.160503

[9] Ben Criger και Imran Ashraf. «Άθροισμα πολλαπλών διαδρομών για αποκωδικοποίηση δισδιάστατων τοπολογικών κωδίκων». Quantum 2, 2 (102).
https:/​/​doi.org/​10.22331/​q-2018-10-19-102

[10] Oscar Higgott, Thomas C. Bohdanowicz, Aleksander Kubica, Steven T. Flammia και Earl T. Campbell. «Βελτιωμένη αποκωδικοποίηση θορύβου κυκλώματος και εύθραυστα όρια προσαρμοσμένων επιφανειακών κωδικών». Physical Review X 13, 031007 (2023).
https: / / doi.org/ 10.1103 / PhysRevX.13.031007

[11] Oscar Higgott και Nikolas P. Breuckmann. «Βελτιωμένη αποκωδικοποίηση μονής λήψης κωδίκων υπεργραφικών προϊόντων υψηλότερης διάστασης». PRX Quantum 4, 020332 (2023).
https: / / doi.org/ 10.1103 / PRXQuantum.4.020332

[12] Kao-Yueh Kuo και Ching-Yi Lai. «Αξιοποίηση του εκφυλισμού στην αποκωδικοποίηση διάδοσης πεποιθήσεων των κβαντικών κωδίκων». npj Quantum Information 8, 111 (2022).
https:/​/​doi.org/​10.1038/​s41534-022-00623-2

[13] Milap Sheth, Sara Zafar Jafarzadeh και Vlad Gheorghiu. «Αποκωδικοποίηση νευρωνικού συνόλου για τοπολογικούς κβαντικούς κώδικες διόρθωσης σφαλμάτων». Φυσική Ανασκόπηση A 101, 032338 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.101.032338

[14] Ramon WJ Overwater, Masoud Babaie και Fabio Sebastiano. «Αποκωδικοποιητές νευρωνικών δικτύων για διόρθωση κβαντικών σφαλμάτων χρησιμοποιώντας επιφανειακούς κώδικες: Μια εξερεύνηση του διαστήματος των αντισταθμίσεων κόστους-απόδοσης υλικού». IEEE Transactions on Quantum Engineering 3, 1–19 (2022).
https: / / doi.org/ 10.1109 / TQE.2022.3174017

[15] Nicolas Delfosse. «Ιεραρχική αποκωδικοποίηση για μείωση των απαιτήσεων υλικού για κβαντικό υπολογισμό» (2020). arXiv:2001.11427.
arXiv: 2001.11427

[16] Kai Meinerz, Chae-Yeun Park και Simon Trebst. «Κλιμακόμενος νευρωνικός αποκωδικοποιητής για τοπολογικούς επιφανειακούς κώδικες». 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 και Frederic T. Chong. "Καλύτερη από τη χειρότερη αποκωδικοποίηση για κβαντική διόρθωση σφαλμάτων". In Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages ​​and Operating Systems, Τόμος 2. Σελίδες 88–102. Νέα Υόρκη, Νέα Υόρκη, ΗΠΑ (2023). Ένωση Υπολογιστικών Μηχανημάτων.
https: / / doi.org/ 10.1145 / 3575693.3575733

[18] Samuel C. Smith, Benjamin J. Brown και Stephen D. Bartlett. «Τοπικός προαποκωδικοποιητής για μείωση του εύρους ζώνης και της καθυστέρησης της κβαντικής διόρθωσης σφαλμάτων». Εφαρμογή φυσικής αναθεώρησης 19, 034050 (2023).
https: / / doi.org/ 10.1103 / PhysRevApplied.19.034050

[19] Nicolas Delfosse και Gilles Zémor. «Αποκωδικοποίηση μέγιστης πιθανότητας γραμμικού χρόνου των επιφανειακών κωδίκων μέσω του καναλιού κβαντικής διαγραφής». Physical Review Research 2, 033042 (2020).
https: / / doi.org/ 10.1103 / PhysRevResearch.2.033042

[20] Nicolas Delfosse και Naomi H. Nickerson. «Σχεδόν γραμμικός αλγόριθμος αποκωδικοποίησης χρόνου για τοπολογικούς κώδικες». Quantum 5, 595 (2021).
https:/​/​doi.org/​10.22331/​q-2021-12-02-595

[21] Namitha Liyanage, Yue Wu, Alexander Deters και Lin Zhong. «Κλιμακόμενη κβαντική διόρθωση σφαλμάτων για επιφανειακούς κώδικες με χρήση FPGA» (2023). arXiv:2301.08419.
arXiv: 2301.08419

[22] Αλεξέι Γιου Κιτάεφ. «Κβαντικός υπολογισμός με ανοχή σε σφάλματα από οποιονδήποτε». Annals of Physics 303, 2–30 (2003).
https:/​/​doi.org/​10.1016/​S0003-4916(02)00018-0

[23] Τιμ Τσαν (2023). κωδικός: timchan0/​localuf.
https://github.com/​timchan0/​localuf

[24] Τιμ Τσαν. «Δεδομένα για «Actis: A Strictly Local Union–Find Decoder»» (2023).
https: / / doi.org/ 10.5281 / zenodo.10075207

[25] Michael A. Nielsen και Isaac L. Chuang. «Κβαντικός υπολογισμός και κβαντικές πληροφορίες: 10η επετειακή έκδοση». Cambridge University Press. (2010).
https: / / doi.org/ 10.1017 / CBO9780511976667

[26] Xinyu Tan, Fang Zhang, Rui Chao, Yaoyun Shi και Jianxin Chen. «Κλιμακόμενοι αποκωδικοποιητές επιφανειακών κωδικών με παραλληλοποίηση στο χρόνο» (2022). arXiv:2209.09219.
arXiv: 2209.09219

[27] Luka Skoric, Dan E. Browne, Kenton M. Barnes, Neil I. Gillespie και Earl T. Campbell. "Η αποκωδικοποίηση παράλληλου παραθύρου επιτρέπει τον κλιμακωτό κβαντικό υπολογισμό με ανοχή σε σφάλματα". Nature Communications 14, 7040 (2023).
https:/​/​doi.org/​10.1038/​s41467-023-42482-1

[28] Σούι Χου. «Οικονομικός αλγόριθμος αποκωδικοποίησης χρόνου για τοπολογικούς κώδικες με υψηλό όριο σφάλματος». Μεταπτυχιακή εργασία. Τεχνολογικό Πανεπιστήμιο του Ντελφτ. (2020).
https://doi.org/​10.13140/​RG.2.2.13495.96162

[29] Όσκαρ Χίγκοτ. "PyMatching: Ένα πακέτο Python για την αποκωδικοποίηση κβαντικών κωδίκων με τέλεια αντιστοίχιση ελάχιστου βάρους". ACM Transactions on Quantum Computing 3, 1–16 (2022).
https: / / doi.org/ 10.1145 / 3505637

[30] Yue Wu, Namitha Liyanage και Lin Zhong. «Μια ερμηνεία του αποκωδικοποιητή Union-Find σε σταθμισμένα γραφήματα» (2022). arXiv:2211.03288.
arXiv: 2211.03288

[31] Ρόμπερτ Έντρε Ταριάν. «Αποτελεσματικότητα ενός καλού αλλά όχι γραμμικού αλγορίθμου ένωσης συνόλου». Journal of the ACM 22, 215–225 (1975).
https: / / doi.org/ 10.1145 / 321879.321884

[32] Shilin Huang, Michael Newman και Kenneth R. Brown. "Αποκωδικοποίηση σταθμισμένης ένωσης εύρεσης με ανοχή σε σφάλματα στον κώδικα toric". Φυσική Ανασκόπηση 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 και M. Veldhorst. «Διασύνδεση spin qubits σε κβαντικές κουκκίδες και δότες—–καυτά, πυκνά και συνεκτικά». npj Quantum Information 3, 34 (2017).
https: / / doi.org/ 10.1038 / s41534-017-0038-y

[34] Άντριου Ρίτσαρντς. "Πανεπιστήμιο της Οξφόρδης Προηγμένη Έρευνα Υπολογιστών". (2015).
https: / / doi.org/ 10.5281 / zenodo.22558

[35] Sam J. Griffiths και Dan E. Browne. "Union–find quantum decoding without 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 και Abbas B. Ζιάντ. «Ένας σε πραγματικό χρόνο, επεκτάσιμος, γρήγορος και εξαιρετικά αποδοτικός αποκωδικοποιητής πόρων για έναν κβαντικό υπολογιστή» (2023). arXiv:2309.05558.
arXiv: 2309.05558

[37] David S. Wang, Austin G. Fowler και Lloyd CL Hollenberg. «Κβαντικός υπολογισμός επιφανειακού κώδικα με ποσοστά σφάλματος άνω του 1%». Φυσική Ανασκόπηση A 83, 020302 (2011).
https: / / doi.org/ 10.1103 / PhysRevA.83.020302

[38] Εμάνουελ Νιλ. «Κβαντικός υπολογισμός με ρεαλιστικά θορυβώδεις συσκευές». Nature 434, 39–44 (2005).
https: / / doi.org/ 10.1038 / nature03350

[39] Oscar Higgott και Craig Gidney. "Sparse Blossom: διόρθωση ενός εκατομμυρίου σφαλμάτων ανά δευτερόλεπτο πυρήνα με αντιστοίχιση ελάχιστου βάρους" (2023). arXiv:2303.15933.
arXiv: 2303.15933

[40] Austin G. Fowler, Adam C. Whiteside και Lloyd CL Hollenberg. «Προς πρακτική κλασική επεξεργασία για τον επιφανειακό κώδικα: Ανάλυση χρονισμού». Physical Review A 86, 042313 (2012).
https: / / doi.org/ 10.1103 / PhysRevA.86.042313

[41] Yue Wu και Lin Zhong. "Fusion Blossom: Γρήγοροι αποκωδικοποιητές MWPM για QEC" (2023). arXiv:2305.08307.
arXiv: 2305.08307

Αναφέρεται από

[1] Sam J. Griffiths και Dan E. Browne, “Union-find quantum decoding without union-find”, arXiv: 2306.09767, (2023).

[2] Asmae Benhemou, Kaavya Sahay, Lingling Lao και Benjamin J. Brown, «Ελαχιστοποίηση αστοχιών επιφανειακού κώδικα με χρήση αποκωδικοποιητή χρωματικού κώδικα». arXiv: 2306.16476, (2023).

Οι παραπάνω αναφορές είναι από SAO / NASA ADS (τελευταία ενημέρωση επιτυχώς 2023-11-14 13:28:32). Η λίστα μπορεί να είναι ελλιπής, καθώς δεν παρέχουν όλοι οι εκδότες τα κατάλληλα και πλήρη στοιχεία αναφοράς.

Δεν ήταν δυνατή η λήψη Crossref αναφερόμενα δεδομένα κατά την τελευταία προσπάθεια 2023-11-14 13:28:31: Δεν ήταν δυνατή η λήψη των αναφερόμενων δεδομένων για το 10.22331 / q-2023-11-14-1183 από την Crossref. Αυτό είναι φυσιολογικό αν το DOI καταχωρήθηκε πρόσφατα.

Αυτό το Βιβλίο δημοσιεύεται στο Quantum στο πλαίσιο του Creative Commons Attribution 4.0 Διεθνής (CC BY 4.0) άδεια. Τα πνευματικά δικαιώματα παραμένουν στους κατόχους των πρωτότυπων δικαιωμάτων πνευματικής ιδιοκτησίας όπως οι δημιουργοί ή τα ιδρύματά τους

Σφραγίδα ώρας:

Περισσότερα από Quantum Journal