quantum-computing

A local automaton for the 2D toric code

Quantum Journal

14 min read

0 likes

⚡ Quantum Brief

Researchers Shankar Balasubramanian, Margarita Davydova, and Ethan Lake developed a local decoder for the 2D toric code using hierarchical cellular automata principles from Tsirelson and Gács. The decoder uses strictly local quantum operations to preserve logical states exponentially longer under circuit-level noise, eliminating the need for non-local classical computation or communication. While the construction lacks spacetime translation invariance, it achieves time-translation invariance in 3D by stacking 2D toric codes, addressing a long-standing challenge. This breakthrough solves the open problem of creating a local topological quantum memory in fewer than four dimensions, advancing fault-tolerant quantum storage. The work builds on classical cellular automata theory, bridging quantum error correction with self-correcting classical systems for robust quantum memory.

Summarize this article with:

AbstractWe construct a local decoder for the 2D toric code using ideas from the hierarchical classical cellular automata of Tsirelson and Gács. Our decoder is a circuit of strictly local quantum operations preserving a logical state for exponential time in the presence of circuit-level noise without the need for non-local classical computation or communication. Our construction is not translation invariant in spacetime, but can be made time-translation invariant in 3D with stacks of 2D toric codes. This solves the open problem of constructing a local topological quantum memory below four dimensions.► BibTeX data@article{Balasubramanian2026localautomatond, doi = {10.22331/q-2026-06-02-2125}, url = {https://doi.org/10.22331/q-2026-06-02-2125}, title = {A local automaton for the 2{D} toric code}, author = {Balasubramanian, Shankar and Davydova, Margarita and Lake, Ethan}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2125}, month = jun, year = {2026} }► References [1] Dorit Aharonov and Michael Ben-Or. ``Fault-tolerant quantum computation with constant error''. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. Pages 176–188. (1997). https://doi.org/10.1145/258533.258579 [2] Dorit Aharonov and Michael Ben-Or. ``Fault-tolerant quantum computation with constant error rate''. SIAM Journal on Computing 38, 1207–1282 (2008). arXiv:https://doi.org/10.1137/S0097539799359385. https://doi.org/10.1137/S0097539799359385 arXiv:https://doi.org/10.1137/S0097539799359385 [3] Emanuel Knill, Raymond Laflamme, and Wojciech H Zurek. ``Resilient quantum computation''. Science 279, 342–345 (1998). https://doi.org/10.1098/rspa.1998.0166 [4] A Yu Kitaev. ``Fault-tolerant quantum computation by anyons''. Annals of physics 303, 2–30 (2003). https://doi.org/10.1016/S0003-4916(02)00018-0 [5] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. ``Topological quantum memory''. Journal of Mathematical Physics 43, 4452–4505 (2002). https://doi.org/10.1063/1.1499754 [6] Nikolas P. Breuckmann and Jens Niklas Eberhardt. ``Quantum low-density parity-check codes''. PRX Quantum 2, 040101 (2021). https://doi.org/10.1103/PRXQuantum.2.040101 [7] Daniel Gottesman. ``Fault-tolerant quantum computation with local gates''. Journal of Modern Optics 47, 333–345 (2000). https://doi.org/10.1080/09500340008244046 [8] Barbara M. Terhal. ``Quantum error correction for quantum memories''. Rev. Mod. Phys. 87, 307–346 (2015). https://doi.org/10.1103/RevModPhys.87.307 [9] Emanuel Knill and Raymond Laflamme. ``Concatenated quantum codes'' (1996). arXiv:quant-ph/9608012. arXiv:quant-ph/9608012 [10] Daniel Gottesman. ``Surviving as a quantum computer in a classical world'' (2024). [Online book]. [11] Robert Alicki, Michal Horodecki, Pawel Horodecki, and Ryszard Horodecki. ``On thermal stability of topological qubit in kitaev's 4d model''. Open Systems & Information Dynamics 17, 1–20 (2010). https://doi.org/10.1142/S1230161210000023 [12] John Von Neumann. ``Probabilistic logics and the synthesis of reliable organisms from unreliable components''. Automata studies 34, 43–98 (1956). [13] John Von Neumann, Arthur Walter Burks, et al. ``Theory of self-reproducing automata''. University of Illinois press Urbana. (1966). [14] Andrei L Toom. ``Stable and attractive trajectories in multicomponent systems''. Multicomponent random systems 6, 549–575 (1980). [15] Charlene Sonja Ahn. ``Extending quantum error correction: new continuous measurement protocols and improved fault-tolerant overhead''. PhD thesis. Caltech. (2004). url: https://thesis.library.caltech.edu/1873/. https://thesis.library.caltech.edu/1873/ [16] Nikolas P Breuckmann, Kasper Duivenvoorden, Dominik Michels, and Barbara M Terhal. ``Local decoders for the 2d and 4d toric code''. Quantum Information and Computation 17, 181–208 (2017). [17] Peter Gács. ``Reliable computation with cellular automata''. In Proceedings of the fifteenth annual ACM symposium on Theory of computing. Pages 32–41. (1983). https://doi.org/10.1145/800061.808730 [18] Peter Peter Gács. ``Reliable cellular automata with self-organization''. Journal of Statistical Physics 103, 45–267 (2001). https://doi.org/10.1023/a:1004823720305 [19] Lawrence F. Gray. ``A Reader's Guide to Gacs's "Positive Rates" Paper''. J. Stat. Phys. 103, 1–44 (2001). https://doi.org/10.1023/A:1004824203467 [20] B. S. Tsirelson. ``Reliable storage of information in a system of unreliable components with local interactions''.

In Locally Interacting Systems and Their Application in Biology. Pages 15–30. Springer, Berlin, Germany (2006). https://doi.org/10.1007/BFb0070081 [21] Michael Ben-Or, Daniel Gottesman, and Avinatan Hassidim. ``Quantum refrigerator'' (2013). arXiv:1301.1995. arXiv:1301.1995 [22] Panos Aliferis, Daniel Gottesman, and John Preskill. ``Quantum accuracy threshold for concatenated distance-3 codes'' (2005). arXiv:quant-ph/0504218. arXiv:quant-ph/0504218 [23] Daniel Gottesman. ``An introduction to quantum error correction and fault-tolerant quantum computation'' (2009). arXiv:0904.2557. arXiv:0904.2557 [24] Peter Peter Gács and Lawrence Gray. ``Reliably computing cellular automata: lecture slides'' (2012). [25] Shankar Balasubramanian, Margarita Davydova, and Ethan Lake (2024). code: ethanlake/local-decoders. https://github.com/ethanlake/local-decoders [26] Aleksander Kubica and John Preskill. ``Cellular-automaton decoders with provable thresholds for topological codes''. Physical review letters 123, 020501 (2019). https://doi.org/10.1103/PhysRevLett.123.020501 [27] Luka Skoric, Dan E Browne, Kenton M Barnes, Neil I Gillespie, and Earl T Campbell. ``Parallel window decoding enables scalable fault tolerant quantum computation''. Nature Communications 14, 7040 (2023). https://doi.org/10.1038/s41467-023-42482-1 [28] James William Harrington. ``Analysis of Quantum Error-Correcting Codes: Symplectic Lattice Codes and Toric Codes''. PhD thesis. Caltech. (2004). url: https://thesis.library.caltech.edu/1747. https://thesis.library.caltech.edu/1747 [29] Guillaume Duclos-Cianci and David Poulin. ``Fast decoders for topological quantum codes''. Phys. Rev. Lett. 104, 050504 (2010). https://doi.org/10.1103/PhysRevLett.104.050504 [30] Sergey Bravyi and Jeongwan Haah. ``Quantum self-correction in the 3d cubic code model''. Phys. Rev. Lett. 111, 200501 (2013). https://doi.org/10.1103/PhysRevLett.111.200501 [31] Guillaume Dauphinais and David Poulin. ``Fault-tolerant quantum error correction for non-abelian anyons''. Communications in Mathematical Physics 355, 519–560 (2017). https://doi.org/10.1007/s00220-017-2923-9 [32] Michael Herold, Earl T Campbell, Jens Eisert, and Michael J Kastoryano. ``Cellular-automaton decoders for topological quantum memories''. npj Quantum information 1, 1–8 (2015). https://doi.org/10.1038/npjqi.2015.10 [33] Sergey Bravyi, Guillaume Duclos-Cianci, David Poulin, and Martin Suchara. ``Subsystem surface codes with three-qubit check operators'' (2013). [34] Matthew B Hastings and Jeongwan Haah. ``Dynamically generated logical qubits''. Quantum 5, 564 (2021). https://doi.org/10.22331/q-2021-10-19-564 [35] Andreas Bauer. ``Topological error correcting processes from fixed-point path integrals''. Quantum 8, 1288 (2024). https://doi.org/10.22331/q-2024-03-20-1288 [36] Jeongwan Haah. ``Local stabilizer codes in three dimensions without string logical operators''. Physical Review A 83 (2011). https://doi.org/10.1103/physreva.83.042330 [37] Matthew B Hastings. ``Decoding in hyperbolic spaces: Ldpc codes with linear rate and efficient error correction'' (2013). [38] Hayata Yamasaki and Masato Koashi. ``Time-efficient constant-space-overhead fault-tolerant quantum computation''. Nature Physics 20, 247–253 (2024). https://doi.org/10.1038/s41567-023-02325-8 [39] B.S. Tsirelson. ``Probabilistic cellular automata: An introduction'' (1996). (Unpublished). [40] Benjamin J. Brown and Sam Roberts. ``Universal fault-tolerant measurement-based quantum computation''. Phys. Rev. Res. 2, 033305 (2020). https://doi.org/10.1103/PhysRevResearch.2.033305 [41] Margarita Davydova, Andreas Bauer, Julio C. Magdalena de la Fuente, Mark Webster, Dominic J. Williamson, and Benjamin J. Brown. ``Universal fault tolerant quantum computation in 2d without getting tied in knots''. Phys. Rev. X (2026). https://doi.org/10.1103/vrty-qs5h [42] Weiguo Wang. ``An asynchronous two-dimensional self-correcting cellular automaton''. In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science. Page 278–287. SFCS '91USA (1991). IEEE Computer Society. https://doi.org/10.1109/SFCS.1991.185379 [43] Matthew Cook, Peter Gács, and Erik Winfree. ``Self-stabilizing synchronization in 3 dimensions (draft)''. Technical report. Tech. report, Boston University, Department of Computer Science, Boston, MA (2008). url: https://www.cs.bu.edu/faculty/gacs/papers/3Dasync.pdf. https://www.cs.bu.edu/faculty/gacs/papers/3Dasync.pdf [44] Piotr Berman and J'anos Simon. ``Investigations of fault-tolerant networks of computers''. In Proceedings of the twentieth annual ACM symposium on Theory of computing. Pages 66–77. (1988). https://doi.org/10.1145/62212.62219 [45] Sergey Bravyi, David Poulin, and Barbara Terhal. ``Tradeoffs for reliable quantum information storage in 2d systems''.

Physical Review Letters 104 (2010). https://doi.org/10.1103/physrevlett.104.050503 [46] Péter Gács, Georgy L Kurdyumov, and Leonid Anatolevich Levin. ``One-dimensional uniform arrays that wash out finite islands''.

Problemy Peredachi Informatsii 14, 92–96 (1978). [47] Kihong Park. ``Ergodicity and mixing rate of one-dimensional cellular automata''. Technical report.

Boston University Computer Science Department (1997). [48] Tibor Rakovszky, Sarang Gopalakrishnan, and Curt von Keyserlingk. ``Defining stable phases of open quantum systems''. Phys. Rev. X 14, 041031 (2024). https://doi.org/10.1103/PhysRevX.14.041031 [49] David Poulin, Roger G. Melko, and Matthew B. Hastings. ``Self-correction in wegner's three-dimensional ising lattice gauge theory''. Phys. Rev. B 99, 094103 (2019). https://doi.org/10.1103/PhysRevB.99.094103 [50] Pablo Serna, Andrés M. Somoza, and Adam Nahum. ``Worldsheet patching, 1-form symmetries, and ${\mathrm{landau}}^{*}$ phase transitions''. Phys. Rev. B 110, 115102 (2024). https://doi.org/10.1103/PhysRevB.110.115102 [51] Thomas M. Liggett. ``Interacting Particle Systems''. Springer. Berlin, Germany (2005). url: https://link.springer.com/book/10.1007/b138374. https://link.springer.com/book/10.1007/b138374 [52] Peter Gács and John Reif. ``A simple three-dimensional real-time reliable cellular array''. Journal of Computer and System Sciences 36, 125–147 (1988). https://doi.org/10.1016/0022-0000(88)90024-4Cited byCould not fetch Crossref cited-by data during last attempt 2026-06-02 08:20:58: Could not fetch cited-by data for 10.22331/q-2026-06-02-2125 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-06-02 08:20:59: Cannot retrieve data from ADS due to rate limitations.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractWe construct a local decoder for the 2D toric code using ideas from the hierarchical classical cellular automata of Tsirelson and Gács. Our decoder is a circuit of strictly local quantum operations preserving a logical state for exponential time in the presence of circuit-level noise without the need for non-local classical computation or communication. Our construction is not translation invariant in spacetime, but can be made time-translation invariant in 3D with stacks of 2D toric codes. This solves the open problem of constructing a local topological quantum memory below four dimensions.► BibTeX data@article{Balasubramanian2026localautomatond, doi = {10.22331/q-2026-06-02-2125}, url = {https://doi.org/10.22331/q-2026-06-02-2125}, title = {A local automaton for the 2{D} toric code}, author = {Balasubramanian, Shankar and Davydova, Margarita and Lake, Ethan}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2125}, month = jun, year = {2026} }► References [1] Dorit Aharonov and Michael Ben-Or. ``Fault-tolerant quantum computation with constant error''. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. Pages 176–188. (1997). https://doi.org/10.1145/258533.258579 [2] Dorit Aharonov and Michael Ben-Or. ``Fault-tolerant quantum computation with constant error rate''. SIAM Journal on Computing 38, 1207–1282 (2008). arXiv:https://doi.org/10.1137/S0097539799359385. https://doi.org/10.1137/S0097539799359385 arXiv:https://doi.org/10.1137/S0097539799359385 [3] Emanuel Knill, Raymond Laflamme, and Wojciech H Zurek. ``Resilient quantum computation''. Science 279, 342–345 (1998). https://doi.org/10.1098/rspa.1998.0166 [4] A Yu Kitaev. ``Fault-tolerant quantum computation by anyons''. Annals of physics 303, 2–30 (2003). https://doi.org/10.1016/S0003-4916(02)00018-0 [5] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. ``Topological quantum memory''. Journal of Mathematical Physics 43, 4452–4505 (2002). https://doi.org/10.1063/1.1499754 [6] Nikolas P. Breuckmann and Jens Niklas Eberhardt. ``Quantum low-density parity-check codes''. PRX Quantum 2, 040101 (2021). https://doi.org/10.1103/PRXQuantum.2.040101 [7] Daniel Gottesman. ``Fault-tolerant quantum computation with local gates''. Journal of Modern Optics 47, 333–345 (2000). https://doi.org/10.1080/09500340008244046 [8] Barbara M. Terhal. ``Quantum error correction for quantum memories''. Rev. Mod. Phys. 87, 307–346 (2015). https://doi.org/10.1103/RevModPhys.87.307 [9] Emanuel Knill and Raymond Laflamme. ``Concatenated quantum codes'' (1996). arXiv:quant-ph/9608012. arXiv:quant-ph/9608012 [10] Daniel Gottesman. ``Surviving as a quantum computer in a classical world'' (2024). [Online book]. [11] Robert Alicki, Michal Horodecki, Pawel Horodecki, and Ryszard Horodecki. ``On thermal stability of topological qubit in kitaev's 4d model''. Open Systems & Information Dynamics 17, 1–20 (2010). https://doi.org/10.1142/S1230161210000023 [12] John Von Neumann. ``Probabilistic logics and the synthesis of reliable organisms from unreliable components''. Automata studies 34, 43–98 (1956). [13] John Von Neumann, Arthur Walter Burks, et al. ``Theory of self-reproducing automata''. University of Illinois press Urbana. (1966). [14] Andrei L Toom. ``Stable and attractive trajectories in multicomponent systems''. Multicomponent random systems 6, 549–575 (1980). [15] Charlene Sonja Ahn. ``Extending quantum error correction: new continuous measurement protocols and improved fault-tolerant overhead''. PhD thesis. Caltech. (2004). url: https://thesis.library.caltech.edu/1873/. https://thesis.library.caltech.edu/1873/ [16] Nikolas P Breuckmann, Kasper Duivenvoorden, Dominik Michels, and Barbara M Terhal. ``Local decoders for the 2d and 4d toric code''. Quantum Information and Computation 17, 181–208 (2017). [17] Peter Gács. ``Reliable computation with cellular automata''. In Proceedings of the fifteenth annual ACM symposium on Theory of computing. Pages 32–41. (1983). https://doi.org/10.1145/800061.808730 [18] Peter Peter Gács. ``Reliable cellular automata with self-organization''. Journal of Statistical Physics 103, 45–267 (2001). https://doi.org/10.1023/a:1004823720305 [19] Lawrence F. Gray. ``A Reader's Guide to Gacs's "Positive Rates" Paper''. J. Stat. Phys. 103, 1–44 (2001). https://doi.org/10.1023/A:1004824203467 [20] B. S. Tsirelson. ``Reliable storage of information in a system of unreliable components with local interactions''.

Problemy Peredachi Informatsii 14, 92–96 (1978). [47] Kihong Park. ``Ergodicity and mixing rate of one-dimensional cellular automata''. Technical report.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/

A local automaton for the 2D toric code

Tags

Source Information