Limits on the storage of quantum information in a volume of space
Steven T. Flammia1,2, Jeongwan Haah2,3, Michael J. Kastoryano4, and Isaac H. Kim5,6,7
1Centre for Engineered Quantum Systems, School of Physics, The University of Sydney, Australia
2Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, USA
3Station Q Quantum Architectures and Computation Group, Microsoft Research, Redmond, Washington, USA
4NBIA, Niels Bohr Institute, University of Copenhagen, Denmark
5IBM T. J. Watson Research Center, Yorktown Heights, New York, USA
6Perimeter Institute for Theoretical Physics, Waterloo ON N2L 2Y5, Canada
7Institute for Quantum Computing, University of Waterloo, Waterloo ON N2L 3G1, Canada
Published: 2017-04-25, volume 1, page 4
Doi: https://doi.org/10.22331/q-2017-04-25-4
Citation: Quantum 1, 4 (2017).
We study the fundamental limits on the reliable storage of quantum information in lattices of qubits by deriving tradeoff bounds for approximate quantum error correcting codes. We introduce a notion of local approximate correctability and code distance, and give a number of equivalent formulations thereof, generalizing various exact error-correction criteria. Our tradeoff bounds relate the number of physical qubits $n$, the number of encoded qubits $k$, the code distance $d$, the accuracy parameter $\delta$ that quantifies how well the erasure channel can be reversed, and the locality parameter $\ell$ that specifies the length scale at which the recovery operation can be done. In a regime where the recovery is successful to accuracy $\epsilon$ that is exponentially small in $\ell$, which is the case for perturbations of local commuting projector codes, our bound reads $kd^{\frac{2}{D-1}} \le O\bigl(n (\log n)^{\frac{2D}{D-1}} \bigr)$ for codes on $D$-dimensional lattices of Euclidean metric. We also find that the code distance of any local approximate code cannot exceed $O\bigl(\ell n^{(D-1)/D}\bigr)$ if $\delta \le O(\ell n^{-1/D})$. As a corollary of our formulation of correctability in terms of logical operator avoidance, we show that the code distance $d$ and the size $\tilde d$ of a minimal region that can support all approximate logical operators satisfies $\tilde d d^{\frac{1}{D-1}}\le O\bigl( n \ell^{\frac{D}{D-1}} \bigr)$, where the logical operators are accurate up to $O\bigl( ( n \delta / d )^{1/2}\bigr)$ in operator norm. Finally, we prove that for two-dimensional systems if logical operators can be approximated by operators supported on constant-width flexible strings, then the dimension of the code space must be bounded. This supports one of the assumptions of algebraic anyon theories, that there exist only finitely many anyon types.
Featured image: Decomposition of a lattice for local approximate quantum error correction. Region $B$ shields region $A$ from $C$ by a distance at least $\ell$, and $R$ represents the purifying space of the code. For approximate quantum codes, deleting region $A$ is an approximately correctable error, and the size of the shield region $B$ controls the accuracy of the recovery.
@article{Flammia2017limitsstorageof, doi = {10.22331/q-2017-04-25-4}, url = {https://doi.org/10.22331/q-2017-04-25-4}, title = {Limits on the storage of quantum information in a volume of space}, author = {Flammia, Steven T. and Haah, Jeongwan and Kastoryano, Michael J. and Kim, Isaac H.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {1}, pages = {4}, month = apr, year = {2017} }
[1] B. M. Terhal, Quantum error correction for quantum memories, Rev. Mod. Phys. 87, 307 (2015), arXiv:1302.3428.
[2] D. Gottesman, An introduction to quantum error correction and fault-tolerant quantum computation, in Quantum Information Science and Its Contributions to Mathematics, Vol. 68, edited by S. J. Lomonaco, Jr. (American Mathematical Society, 2010) pp. 24-69, arXiv:0904.2557.
[3] D. W. Leung, M. A. Nielsen, I. L. Chuang, and Y. Yamamoto, Approximate quantum error correction can lead to better codes, Phys. Rev. A 56, 2567-2573 (1997).
[4] C. Crépeau, D. Gottesman, and A. Smith, Approximate quantum error-correcting codes and secret sharing schemes, in Advances in Cryptology - EUROCRYPT 2005: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005. Proceedings, edited by R. Cramer (Springer Berlin Heidelberg, Berlin, Heidelberg, 2005) pp. 285-301, quant-ph/​0503139.
https:/​/​doi.org/​10.1007/​11426639_17
[5] G. Moore and N. Read, Nonabelions in the fractional quantum hall effect, Nuclear Physics B 360, 362-396 (1991).
https:/​/​doi.org/​10.1016/​0550-3213(91)90407-O
[6] A. Kitaev, Anyons in an exactly solved model and beyond, Annals of Physics 321, 2-111 (2006), cond-mat/​0506438.
https:/​/​doi.org/​10.1016/​j.aop.2005.10.005
arXiv:cond-mat/0506438
[7] S. Michalakis and J. P. Zwolak, Stability of frustration-free Hamiltonians, Communications in Mathematical Physics 322, 277-302 (2013), arXiv:1109.1588.
[8] M. B. Hastings and X.-G. Wen, Quasiadiabatic continuation of quantum states: The stability of topological ground-state degeneracy and emergent gauge invariance, Physical Review B 72, 045141 (2005), cond-mat/​0503554.
[9] S. Bravyi, M. B. Hastings, and S. Michalakis, Topological quantum order: stability under local perturbations, Journal of Mathematical Physics 51, 093512 (2010a), arXiv:1001.0344.
[10] S. Bravyi, D. Poulin, and B. Terhal, Tradeoffs for reliable quantum information storage in 2D systems, Phys. Rev. Lett. 104, 050503 (2010b), arXiv:0909.5200.
[11] J. Haah and J. Preskill, Logical operator tradeoff for local quantum codes, Phys. Rev. A 86, 032308 (2012), 1011.3529.
[12] C. G. Brell, S. T. Flammia, S. D. Bartlett, and A. C. Doherty, Toric codes and quantum doubles from two-body Hamiltonians, New Journal of Physics 13, 053039 (2011), arXiv:1011.1942.
[13] B. Criger and B. Terhal, Noise thresholds for the [4,2,2]-concatenated toric code, Quant. Inf. Comput. 16, 1261 (2016), arXiv:1604.04062.
[14] I. H. Kim and M. J. Kastoryano, Entanglement renormalization, quantum error correction, and bulk causality, (2017), arXiv:1701.00050.
[15] S. Bravyi and B. Terhal, A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes, New Journal of Physics 11, 043029 (2009), arXiv:0810.1983.
[16] N. Delfosse, Tradeoffs for reliable quantum information storage in surface codes and color codes, in 2013 IEEE International Symposium on Information Theory (Institute of Electrical & Electronics Engineers (IEEE), 2013) arXiv:1301.6588.
https:/​/​doi.org/​10.1109/​isit.2013.6620360
[17] S. Bravyi, Subsystem codes with spatially local generators, Phys. Rev. A 83, 012320 (2011), arXiv:1008.1029.
[18] D. Bacon, S. T. Flammia, A. W. Harrow, and J. Shi, Sparse Quantum Codes from Quantum Circuits, in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC '15 (ACM Press, New York, NY, USA, 2015) pp. 327-334, arXiv:1411.3334.
https:/​/​doi.org/​10.1145/​2746539.2746608
[19] C. Cafaro and P. van Loock, Approximate quantum error correction for generalized amplitude-damping errors, Phys. Rev. A 89, 022316 (2014), arXiv:1308.4582.
[20] Y. Ouyang, Permutation-invariant quantum codes, Phys. Rev. A 90, 062317 (2014), arXiv:1302.3247.
[21] M. Grassl, L. Kong, Z. Wei, Z.-Q. Yin, and B. Zeng, Quantum Error-Correcting Codes for Qudit Amplitude Damping, arXiv:1509.06829 (2015), arXiv:1509.06829.
[22] B. Schumacher and M. D. Westmoreland, Approximate quantum error correction, Quant. Info. Process. 1, 5-12 (2002), quant-ph/​0112106.
https:/​/​doi.org/​10.1023/​A:1019653202562
[23] C. Bény and O. Oreshkov, General conditions for approximate quantum error correction and near-optimal recovery channels, Phys. Rev. Lett. 104, 120501 (2010), arXiv:0907.5391.
[24] H. K. Ng and P. Mandayam, Simple approach to approximate quantum error correction based on the transpose channel, Phys. Rev. A 81, 062342 (2010), arXiv:0909.0931.
[25] J. C. Bridgeman, S. T. Flammia, and D. Poulin, Detecting Topological Order with Ribbon Operators, Phys. Rev. B 94, 205123 (2016), arXiv:1603.02275.
[26] C. T. Chubb and S. T. Flammia, Approximate symmetries of Hamiltonians, (2016), arXiv:1608.02600.
[27] A. Uhlmann, The ``transition probability'' in the state space of a $*$-algebra, Reports on Mathematical Physics 9, 273-279 (1976).
https:/​/​doi.org/​10.1016/​0034-4877(76)90060-4
[28] C. A. Fuchs and J. van de Graaf, Cryptographic distinguishability measures for quantum-mechanical states, IEEE Trans. Inf. Theory 45, 1216 (1999), quant-ph/​9712042.
https:/​/​doi.org/​10.1109/​18.761271
[29] E. Knill and R. Laflamme, Theory of quantum error-correcting codes, Phys. Rev. A 55, 900-911 (1997).
https:/​/​doi.org/​10.1103/​PhysRevA.55.900
[30] D. Kretschmann, D. Schlingemann, and R. F. Werner, The information-disturbance tradeoff and the continuity of Stinespring's representation, IEEE Transactions on Information Theory 54, 1708-1717 (2008), quant-ph/​0605009.
https:/​/​doi.org/​10.1109/​tit.2008.917696
[31] P. Hayden and A. Winter, Weak decoupling duality and quantum identification, IEEE Transactions on Information Theory 58, 4914-4929 (2012), arXiv:1003.4994.
https:/​/​doi.org/​10.1109/​tit.2012.2191695
[32] B. Schumacher and M. A. Nielsen, Quantum data processing and error correction, Phys. Rev. A 54, 2629-2635 (1996), quant-ph/​9604022.
[33] A. Y. Kitaev, A. H. Shen, and M. N. Vyalyi, Classical and Quantum Computation (American Mathematical Society, 2002).
[34] M. Müller-Lennert, F. Dupuis, O. Szehr, S. Fehr, and M. Tomamichel, On quantum Rényi entropies: a new generalization and some properties, J. Math. Phys. 54, 122203 (2013), arXiv:1306.3142.
[35] S. Beigi, Sandwiched Rényi divergence satisfies data processing inequality, J. Math. Phys. 54, 122202 (2013), arXiv:1306.5920.
[36] B. Yoshida and I. L. Chuang, Framework for classifying logical operators in stabilizer codes, Phys. Rev. A 81, 052302 (2010), arXiv:1002.0085.
[37] J. Preskill, Quantum error correction, Lecture notes for Physics 219, Caltech, (1999).
http:/​/​www.theory.caltech.edu/​~preskill/​ph229/​notes/​chap7.pdf
[38] C. Vafa, Toward classification of conformal theories, Physics Letters B 206, 421-426 (1988).
[39] C. Chamon, Quantum glassiness, Phys. Rev. Lett. 94, 040402 (2005), cond-mat/​0404182.
[40] S. Bravyi, B. Leemhuis, and B. M. Terhal, Topological order in an exactly solvable 3D spin model, Annals of Physics 326, 839-866 (2011), arXiv:1006.4871.
[41] J. Haah, Local stabilizer codes in three dimensions without string logical operators, Phys. Rev. A 83, 042330 (2011), arXiv:1310.4507.
[42] S. Vijay, J. Haah, and L. Fu, A new kind of topological quantum order: A dimensional hierarchy of quasiparticles built from stationary excitations, Phys. Rev. B 92, 235136 (2015), 1505.02576.
[43] J. Haah, Commuting Pauli Hamiltonians as maps between free modules, Commun. Math. Phys. 324, 351-399 (2013), arXiv:1204.1063.
[44] M. B. Hastings, Lieb-Schultz-Mattis in higher dimensions, Physical Review B 69, 104431 (2004), cond-mat/​0305505.
[45] S. Bachmann, S. Michalakis, B. Nachtergaele, and R. Sims, Automorphic equivalence within gapped phases of quantum lattice systems, Communications in Mathematical Physics 309, 835-871 (2012), arXiv:1102.0842.
[46] B. Eastin and E. Knill, Restrictions on transversal encoded quantum gate sets, Physical Review Letters 102, 110502 (2009), arXiv:0811.4262.
[47] S. Bravyi and R. König, Classification of topologically protected gates for local stabilizer codes, Phys. Rev. Lett. 110, 170503 (2013), arXiv:1206.1609.
[48] D. Poulin, Stabilizer formalism for operator quantum error correction, Phys. Rev. Lett. 95, 230504 (2005), quant-ph/​0508131.
[49] C. Bény, Conditions for the approximate correction of algebras, in Theory of Quantum Computation, Communication, and Cryptography (Springer, 2009) pp. 66-75, arXiv:0907.4207.
https:/​/​doi.org/​10.1007/​978-3-642-10698-9_7
[50] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Topological quantum memory, Journal of Mathematical Physics 43, 4452-4505 (2002), quant-ph/​0110143.
[51] R. Alicki, M. Horodecki, P. Horodecki, and R. Horodecki, On thermal stability of topological qubit in kitaev's 4d model, Open Systems & Information Dynamics 17, 1-20 (2010), arXiv:0811.0033.
[52] B. J. Brown, D. Loss, J. K. Pachos, C. N. Self, and J. R. Wootton, Quantum memories at finite temperature, Rev. Mod. Phys. 88, 045005 (2016), arXiv:1411.6643.
https:/​/​doi.org/​10.1103/​RevModPhys.88.045005
[53] F. Pastawski, B. Yoshida, D. Harlow, and J. Preskill, Holographic quantum error-correcting codes: Toy models for the bulk/​boundary correspondence, Journal of High Energy Physics 2015, 149 (2015), arXiv:1503.06237.
https:/​/​doi.org/​10.1007/​JHEP06(2015)149
[54] D. Harlow, The Ryu-Takayanagi formula from quantum error correction, (2016), arXiv:1607.03901.
[55] K. M. R. Audenaert, A sharp continuity estimate for the von Neumann entropy, Journal of Physics A: Mathematical and Theoretical 40, 8127-8136 (2007), quant-ph/​0610146.
https:/​/​doi.org/​10.1088/​1751-8113/​40/​28/​s18
[56] R. Alicki and M. Fannes, Continuity of quantum conditional information, J. Phys. A: Math. Gen. 37, L55-L57 (2004), quant-ph/​0312081.
https:/​/​doi.org/​10.1088/​0305-4470/​37/​5/​l01
[1] A. T. Schmitz, Han Ma, Rahul M. Nandkishore, and S. A. Parameswaran, "Recoverable information and emergent conservation laws in fracton stabilizer codes", Physical Review B 97 13, 134426 (2018).
[2] Yi-Chan Lee, Courtney G Brell, and Steven T Flammia, "Topological quantum error correction in the Kitaev honeycomb model", Journal of Statistical Mechanics: Theory and Experiment 2017 8, 083106 (2017).
[3] Fernando Pastawski, Jens Eisert, and Henrik Wilming, "Towards Holography via Quantum Source-Channel Codes", Physical Review Letters 119 2, 020501 (2017).
[4] Kohtaro Kato and Fernando G. S. L. Brandão, "Quantum Approximate Markov Chains are Thermal", Communications in Mathematical Physics (2019).
[5] Yink Loong Len and Hui Khoon Ng, "Open-system quantum error correction", Physical Review A 98 2, 022307 (2018).
[6] Thomas C. Bohdanowicz, Elizabeth Crosson, Chinmay Nirkhe, and Henry Yuen, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019 481 (2019) ISBN:9781450367059.
[7] Yi Ling, Yuxuan Liu, Zhuo-Yu Xian, and Yikang Xiao, "Quantum error correction and entanglement spectrum in tensor networks", Physical Review D 99 2, 026008 (2019).
[8] Weilei Zeng and Leonid P. Pryadko, "Higher-Dimensional Quantum Hypergraph-Product Codes with Finite Rates", Physical Review Letters 122 23, 230501 (2019).
[9] Cédric Bény, Zoltán Zimborás, and Fernando Pastawski, "Approximate recovery with locality and symmetry constraints", arXiv:1806.10324.
[10] Isaac H. Kim and Michael J. Kastoryano, "Entanglement renormalization, quantum error correction, and bulk causality", Journal of High Energy Physics 2017 4, 40 (2017).
[11] Fernando Pastawski and John Preskill, "Code Properties from Holographic Geometries", Physical Review X 7 2, 021022 (2017).
[12] Yi Ling, Yuxuan Liu, Zhuo-Yu Xian, and Yikang Xiao, "Tensor chain and constraints in tensor networks", Journal of High Energy Physics 2019 6, 32 (2019).