On the Addressability Problem on CSS Codes
Understand this faster with AI
AbstractRecent discoveries in asymptotically good quantum codes have intensified research on their application in quantum computation and fault-tolerant operations. This study focuses on the addressability problem within CSS codes: we ask what circuits might implement logical gates on strict subsets of logical qubits. With some notion of fault-tolerance, we prove several impossibility results: for CSS codes with non-zero rate, one cannot address a logical $H$, $HS$, $SH$, or $\mathsf{CNOT}$ to any non-empty strict subset of logical qubits using a circuit made only from 1-local Clifford gates. Furthermore, we show that one cannot permute the logical qubits in a code purely by permuting the physical qubits, if the rate of the code is (asymptotically) greater than 1/3 and the distance is at least 3. We can show a similar no-go result for $\mathsf{CNOT}$s and $\mathsf{CZ}$s between two such high-rate codes, albeit under a more restrictive assumption on the circuit, which we call "global" (though recent addressable CCZ gates use global circuits). This work pioneers the study of distance-preserving addressability in quantum codes, mainly by considering automorphisms of the code. This perspective offers new insights and potential directions for future research. We argue that studying this trade off between addressability and efficiency of the codes is essential to understand better how to do efficient quantum computation.► BibTeX data@article{Guyot2026addressability, doi = {10.22331/q-2026-06-30-2145}, url = {https://doi.org/10.22331/q-2026-06-30-2145}, title = {On the {A}ddressability {P}roblem on {CSS} {C}odes}, author = {Guyot, J{\'{e}}r{\^{o}}me and Jaques, Samuel}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2145}, month = jun, year = {2026} }► References [1] A. Leverrier and G. Zemor. ``Quantum Tanner codes''. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). Pages 872–883. Los Alamitos, CA, USA (2022). IEEE Computer Society. https://doi.org/10.1109/FOCS54457.2022.00117 [2] Pavel Panteleev and Gleb Kalachev. ``Asymptotically good quantum and locally testable classical LDPC codes''. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Page 375–388. STOC 2022New York, NY, USA (2022). Association for Computing Machinery. https://doi.org/10.1145/3519935.3520017 [3] Markus Grassl and Martin Roetteler. ``Leveraging automorphisms of quantum codes for fault-tolerant quantum computation''. In 2013 IEEE International Symposium on Information Theory. Pages 534–538. (2013). https://doi.org/10.1109/ISIT.2013.6620283 [4] Alexander J. Malcolm, Andrew N. Glaudell, Patricio Fuentes, Daryus Chandra, Alexis Schotte, Colby DeLisle, Rafael Haenel, Amir Ebrahimi, Joschka Roffe, Armanda O. Quintavalle, Stefanie J. Beale, Nicholas R. Lee-Hone, and Stephanie Simmons. ``Computing efficiently in qldpc codes''. Nature Communications (2026). https://doi.org/10.1038/s41467-026-73061-9 [5] Zhiyang He, Vinod Vaikuntanathan, Adam Wills, and Rachel Yun Zhang. ``Quantum codes with addressable and transversal non-Clifford gates'' (2025). arXiv:2502.01864. arXiv:2502.01864 [6] Guanyu Zhu, Shehryar Sikander, Elia Portnoy, Andrew W. Cross, and Benjamin J. Brown. ``Non-clifford and parallelizable fault-tolerant logical gates on constant and almost-constant rate homological quantum low-density parity-check codes via higher symmetries''. PRX Quantum 6, 040361 (2025). https://doi.org/10.1103/wcxs-w69t [7] Adway Patra and Alexander Barg. ``Targeted Clifford logical gates for hypergraph product codes''. Quantum 9, 1842 (2025). https://doi.org/10.22331/q-2025-08-29-1842 [8] Armanda O. Quintavalle, Paul Webster, and Michael Vasmer. ``Partitioning qubits in hypergraph product codes to implement logical gates''. Quantum 7, 1153 (2023). https://doi.org/10.22331/q-2023-10-24-1153 [9] Narayanan Rengaswamy, Robert Calderbank, Swanand Kadhe, and Henry D. Pfister. ``Logical clifford synthesis for stabilizer codes''. IEEE Transactions on Quantum Engineering 1, 1–17 (2020). https://doi.org/10.1109/TQE.2020.3023419 [10] Ting-Chun Lin. ``Transversal non-Clifford gates for quantum LDPC codes on sheaves'' (2024). arXiv:2410.14631. arXiv:2410.14631 [11] Bryan Eastin and Emanuel Knill. ``Restrictions on transversal encoded quantum gate sets''. Phys. Rev. Lett. 102, 110502 (2009). https://doi.org/10.1103/PhysRevLett.102.110502 [12] Sergey Bravyi and Robert König. ``Classification of topologically protected gates for local stabilizer codes''. Phys. Rev. Lett. 110, 170503 (2013). https://doi.org/10.1103/PhysRevLett.110.170503 [13] Nouédyn Baspin and Anirudh Krishna. ``Quantifying nonlocality: How outperforming local quantum codes is expensive''. Phys. Rev. Lett. 129, 050505 (2022). https://doi.org/10.1103/PhysRevLett.129.050505 [14] Tomas Jochym-O'Connor, Aleksander Kubica, and Theodore J. Yoder. ``Disjointness of stabilizer codes and limitations on fault-tolerant logical gates''. Phys. Rev. X 8, 021047 (2018). https://doi.org/10.1103/PhysRevX.8.021047 [15] Aranya Chakraborty and Daniel Gottesman. ``No-go theorem on fault tolerant gadgets for multiple logical qubits'' (2026). url: https://arxiv.org/abs/2602.13395. arXiv:2602.13395 [16] Theerapat Tansuwannont, Tim Chan, and Ryuji Takagi. ``Construction of the full logical clifford group for high-rate quantum reed-muller codes using only transversal and fold-transversal gates'' (2026). arXiv:2602.09788. arXiv:2602.09788 [17] Esha Swaroop, Tomas Jochym-O’Connor, and Theodore J. Yoder. ``Universal adapters between quantum low-density parity check codes''. PRX Quantum 7 (2026). https://doi.org/10.1103/1g44-jp62 [18] Laura Pecorari, Francesco Paolo Guerci, Hugo Perrin, and Guido Pupillo. ``Addressable gate-based logical computation with quantum LDPC codes'' (2025). quant-ph:2511.06124. arXiv:2511.06124 [19] Qian Xu, Hengyun Zhou, Guo Zheng, Dolev Bluvstein, J.
Pablo Bonilla Ataides, Mikhail D. Lukin, and Liang Jiang. ``Fast and parallelizable logical computation with homological product codes''. Physical Review X 15 (2025). https://doi.org/10.1103/physrevx.15.021065 [20] Christine Li, John Preskill, and Qian Xu. ``Transversal dimension jump for product qLDPC codes'' (2025). quant-ph:2510.07269. arXiv:2510.07269 [21] Shi Jie Samuel Tan, Yifan Hong, Ting-Chun Lin, Michael J. Gullans, and Min-Hsiu Hsieh. ``Single-shot universality in quantum LDPC codes via code-switching'' (2025). arXiv:2510.08552. arXiv:2510.08552 [22] Andrew W. Cross, Zhiyang He, Patrick J. Rall, and Theodore J. Yoder. ``Improved QLDPC surgery: Logical measurements and bridging codes'' (2025). arXiv:2407.18393. arXiv:2407.18393 [23] Qian Xu, Hengyun Zhou, Dolev Bluvstein, Madelyn Cain, Marcin Kalinowski, John Preskill, Mikhail D. Lukin, and Nishad Maskara. ``Batched high-rate logical operations for quantum LDPC codes'' (2025). quant-ph:2510.06159. arXiv:2510.06159 [24] A. R. Calderbank and Peter W. Shor. ``Good quantum error-correcting codes exist''. Phys. Rev. A 54, 1098–1105 (1996). https://doi.org/10.1103/PhysRevA.54.1098 [25] E.M. Rains. ``Nonbinary quantum codes''. IEEE Transactions on Information Theory 45, 1827–1832 (1999). https://doi.org/10.1109/18.782103 [26] Nicolas J. Cerf and Richard Cleve. ``Information-theoretic interpretation of quantum error-correcting codes''. Phys. Rev. A 56, 1721–1732 (1997). https://doi.org/10.1103/PhysRevA.56.1721 [27] Sergey Bravyi and Jeongwan Haah. ``Magic-state distillation with low overhead''. Phys. Rev. A 86, 052329 (2012). https://doi.org/10.1103/PhysRevA.86.052329 [28] Burniston, John. ``Pre-privacy amplification: A post-processing technique for quantum key distribution with application to the simplified trusted relay''. Master's thesis (2023). url: http://hdl.handle.net/10012/19329. http://hdl.handle.net/10012/19329Cited byCould not fetch Crossref cited-by data during last attempt 2026-06-30 10:00:52: Could not fetch cited-by data for 10.22331/q-2026-06-30-2145 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-06-30 10:00:52: 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. AbstractRecent discoveries in asymptotically good quantum codes have intensified research on their application in quantum computation and fault-tolerant operations. This study focuses on the addressability problem within CSS codes: we ask what circuits might implement logical gates on strict subsets of logical qubits. With some notion of fault-tolerance, we prove several impossibility results: for CSS codes with non-zero rate, one cannot address a logical $H$, $HS$, $SH$, or $\mathsf{CNOT}$ to any non-empty strict subset of logical qubits using a circuit made only from 1-local Clifford gates. Furthermore, we show that one cannot permute the logical qubits in a code purely by permuting the physical qubits, if the rate of the code is (asymptotically) greater than 1/3 and the distance is at least 3. We can show a similar no-go result for $\mathsf{CNOT}$s and $\mathsf{CZ}$s between two such high-rate codes, albeit under a more restrictive assumption on the circuit, which we call "global" (though recent addressable CCZ gates use global circuits). This work pioneers the study of distance-preserving addressability in quantum codes, mainly by considering automorphisms of the code. This perspective offers new insights and potential directions for future research. We argue that studying this trade off between addressability and efficiency of the codes is essential to understand better how to do efficient quantum computation.► BibTeX data@article{Guyot2026addressability, doi = {10.22331/q-2026-06-30-2145}, url = {https://doi.org/10.22331/q-2026-06-30-2145}, title = {On the {A}ddressability {P}roblem on {CSS} {C}odes}, author = {Guyot, J{\'{e}}r{\^{o}}me and Jaques, Samuel}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2145}, month = jun, year = {2026} }► References [1] A. Leverrier and G. Zemor. ``Quantum Tanner codes''. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). Pages 872–883. Los Alamitos, CA, USA (2022). IEEE Computer Society. https://doi.org/10.1109/FOCS54457.2022.00117 [2] Pavel Panteleev and Gleb Kalachev. ``Asymptotically good quantum and locally testable classical LDPC codes''. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Page 375–388. STOC 2022New York, NY, USA (2022). Association for Computing Machinery. https://doi.org/10.1145/3519935.3520017 [3] Markus Grassl and Martin Roetteler. ``Leveraging automorphisms of quantum codes for fault-tolerant quantum computation''. In 2013 IEEE International Symposium on Information Theory. Pages 534–538. (2013). https://doi.org/10.1109/ISIT.2013.6620283 [4] Alexander J. Malcolm, Andrew N. Glaudell, Patricio Fuentes, Daryus Chandra, Alexis Schotte, Colby DeLisle, Rafael Haenel, Amir Ebrahimi, Joschka Roffe, Armanda O. Quintavalle, Stefanie J. Beale, Nicholas R. Lee-Hone, and Stephanie Simmons. ``Computing efficiently in qldpc codes''. Nature Communications (2026). https://doi.org/10.1038/s41467-026-73061-9 [5] Zhiyang He, Vinod Vaikuntanathan, Adam Wills, and Rachel Yun Zhang. ``Quantum codes with addressable and transversal non-Clifford gates'' (2025). arXiv:2502.01864. arXiv:2502.01864 [6] Guanyu Zhu, Shehryar Sikander, Elia Portnoy, Andrew W. Cross, and Benjamin J. Brown. ``Non-clifford and parallelizable fault-tolerant logical gates on constant and almost-constant rate homological quantum low-density parity-check codes via higher symmetries''. PRX Quantum 6, 040361 (2025). https://doi.org/10.1103/wcxs-w69t [7] Adway Patra and Alexander Barg. ``Targeted Clifford logical gates for hypergraph product codes''. Quantum 9, 1842 (2025). https://doi.org/10.22331/q-2025-08-29-1842 [8] Armanda O. Quintavalle, Paul Webster, and Michael Vasmer. ``Partitioning qubits in hypergraph product codes to implement logical gates''. Quantum 7, 1153 (2023). https://doi.org/10.22331/q-2023-10-24-1153 [9] Narayanan Rengaswamy, Robert Calderbank, Swanand Kadhe, and Henry D. Pfister. ``Logical clifford synthesis for stabilizer codes''. IEEE Transactions on Quantum Engineering 1, 1–17 (2020). https://doi.org/10.1109/TQE.2020.3023419 [10] Ting-Chun Lin. ``Transversal non-Clifford gates for quantum LDPC codes on sheaves'' (2024). arXiv:2410.14631. arXiv:2410.14631 [11] Bryan Eastin and Emanuel Knill. ``Restrictions on transversal encoded quantum gate sets''. Phys. Rev. Lett. 102, 110502 (2009). https://doi.org/10.1103/PhysRevLett.102.110502 [12] Sergey Bravyi and Robert König. ``Classification of topologically protected gates for local stabilizer codes''. Phys. Rev. Lett. 110, 170503 (2013). https://doi.org/10.1103/PhysRevLett.110.170503 [13] Nouédyn Baspin and Anirudh Krishna. ``Quantifying nonlocality: How outperforming local quantum codes is expensive''. Phys. Rev. Lett. 129, 050505 (2022). https://doi.org/10.1103/PhysRevLett.129.050505 [14] Tomas Jochym-O'Connor, Aleksander Kubica, and Theodore J. Yoder. ``Disjointness of stabilizer codes and limitations on fault-tolerant logical gates''. Phys. Rev. X 8, 021047 (2018). https://doi.org/10.1103/PhysRevX.8.021047 [15] Aranya Chakraborty and Daniel Gottesman. ``No-go theorem on fault tolerant gadgets for multiple logical qubits'' (2026). url: https://arxiv.org/abs/2602.13395. arXiv:2602.13395 [16] Theerapat Tansuwannont, Tim Chan, and Ryuji Takagi. ``Construction of the full logical clifford group for high-rate quantum reed-muller codes using only transversal and fold-transversal gates'' (2026). arXiv:2602.09788. arXiv:2602.09788 [17] Esha Swaroop, Tomas Jochym-O’Connor, and Theodore J. Yoder. ``Universal adapters between quantum low-density parity check codes''. PRX Quantum 7 (2026). https://doi.org/10.1103/1g44-jp62 [18] Laura Pecorari, Francesco Paolo Guerci, Hugo Perrin, and Guido Pupillo. ``Addressable gate-based logical computation with quantum LDPC codes'' (2025). quant-ph:2511.06124. arXiv:2511.06124 [19] Qian Xu, Hengyun Zhou, Guo Zheng, Dolev Bluvstein, J.
Pablo Bonilla Ataides, Mikhail D. Lukin, and Liang Jiang. ``Fast and parallelizable logical computation with homological product codes''. Physical Review X 15 (2025). https://doi.org/10.1103/physrevx.15.021065 [20] Christine Li, John Preskill, and Qian Xu. ``Transversal dimension jump for product qLDPC codes'' (2025). quant-ph:2510.07269. arXiv:2510.07269 [21] Shi Jie Samuel Tan, Yifan Hong, Ting-Chun Lin, Michael J. Gullans, and Min-Hsiu Hsieh. ``Single-shot universality in quantum LDPC codes via code-switching'' (2025). arXiv:2510.08552. arXiv:2510.08552 [22] Andrew W. Cross, Zhiyang He, Patrick J. Rall, and Theodore J. Yoder. ``Improved QLDPC surgery: Logical measurements and bridging codes'' (2025). arXiv:2407.18393. arXiv:2407.18393 [23] Qian Xu, Hengyun Zhou, Dolev Bluvstein, Madelyn Cain, Marcin Kalinowski, John Preskill, Mikhail D. Lukin, and Nishad Maskara. ``Batched high-rate logical operations for quantum LDPC codes'' (2025). quant-ph:2510.06159. arXiv:2510.06159 [24] A. R. Calderbank and Peter W. Shor. ``Good quantum error-correcting codes exist''. Phys. Rev. A 54, 1098–1105 (1996). https://doi.org/10.1103/PhysRevA.54.1098 [25] E.M. Rains. ``Nonbinary quantum codes''. IEEE Transactions on Information Theory 45, 1827–1832 (1999). https://doi.org/10.1109/18.782103 [26] Nicolas J. Cerf and Richard Cleve. ``Information-theoretic interpretation of quantum error-correcting codes''. Phys. Rev. A 56, 1721–1732 (1997). https://doi.org/10.1103/PhysRevA.56.1721 [27] Sergey Bravyi and Jeongwan Haah. ``Magic-state distillation with low overhead''. Phys. Rev. A 86, 052329 (2012). https://doi.org/10.1103/PhysRevA.86.052329 [28] Burniston, John. ``Pre-privacy amplification: A post-processing technique for quantum key distribution with application to the simplified trusted relay''. Master's thesis (2023). url: http://hdl.handle.net/10012/19329. http://hdl.handle.net/10012/19329Cited byCould not fetch Crossref cited-by data during last attempt 2026-06-30 10:00:52: Could not fetch cited-by data for 10.22331/q-2026-06-30-2145 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-06-30 10:00:52: 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.
Tags
Source Information
Discussion
0 professional contributions
Sign in to join this professional discussion.
Be the first to add a constructive contribution.