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

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.

Share

► BibTeX data

► References

[1] B. M. Terhal, Quantum error correction for quantum memories, Rev. Mod. Phys. 87, 307 (2015), arXiv:1302.3428.
https://doi.org/10.1103/RevModPhys.87.307
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.
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).
https://doi.org/10.1103/PhysRevA.56.2567

[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
arXiv:quant-ph/0503139

[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.
https://doi.org/10.1007/s00220-013-1762-6
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.
https://doi.org/10.1103/physrevb.72.045141
arXiv: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.
https://doi.org/10.1063/1.3490195
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.
https://doi.org/10.1103/PhysRevLett.104.050503
arXiv:0909.5200

[11] J. Haah and J. Preskill, Logical operator tradeoff for local quantum codes, Phys. Rev. A 86, 032308 (2012), 1011.3529.
https://doi.org/10.1103/PhysRevA.86.032308
arXiv: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.
https://doi.org/10.1088/1367-2630/13/5/053039
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.
arXiv:1604.04062

[14] I. H. Kim and M. J. Kastoryano, Entanglement renormalization, quantum error correction, and bulk causality, (2017), arXiv:1701.00050.
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.
https://doi.org/10.1088/1367-2630/11/4/043029
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
arXiv:1301.6588

[17] S. Bravyi, Subsystem codes with spatially local generators, Phys. Rev. A 83, 012320 (2011), arXiv:1008.1029.
https://doi.org/10.1103/PhysRevA.83.012320
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
arXiv:1411.3334

[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.
https://doi.org/10.1103/PhysRevA.89.022316
arXiv:1308.4582

[20] Y. Ouyang, Permutation-invariant quantum codes, Phys. Rev. A 90, 062317 (2014), arXiv:1302.3247.
https://doi.org/10.1103/PhysRevA.90.062317
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.
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
arXiv:quant-ph/0112106

[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.
https://doi.org/10.1103/PhysRevLett.104.120501
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.
https://doi.org/10.1103/PhysRevA.81.062342
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.
https://doi.org/10.1103/PhysRevB.94.205123
arXiv:1603.02275

[26] C. T. Chubb and S. T. Flammia, Approximate symmetries of Hamiltonians, (2016), arXiv:1608.02600.
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
arXiv:quant-ph/9712042

[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
arXiv:quant-ph/0605009

[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
arXiv:1003.4994

[32] B. Schumacher and M. A. Nielsen, Quantum data processing and error correction, Phys. Rev. A 54, 2629-2635 (1996), quant-ph/​9604022.
https://doi.org/10.1103/physreva.54.2629
arXiv: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.
https://doi.org/10.1063/1.4838856
arXiv:1306.3142

[35] S. Beigi, Sandwiched Rényi divergence satisfies data processing inequality, J. Math. Phys. 54, 122202 (2013), arXiv:1306.5920.
https://doi.org/10.1063/1.4838855
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.
https://doi.org/10.1103/PhysRevA.81.052302
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).
https://doi.org/10.1016/0370-2693(88)91603-6

[39] C. Chamon, Quantum glassiness, Phys. Rev. Lett. 94, 040402 (2005), cond-mat/​0404182.
https://doi.org/10.1103/PhysRevLett.94.040402
arXiv: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.
https://doi.org/10.1016/j.aop.2010.11.002
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.
https://doi.org/10.1103/PhysRevB.89.075119
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.
https://doi.org/10.1103/PhysRevB.92.235136
arXiv:1505.02576

[43] J. Haah, Commuting Pauli Hamiltonians as maps between free modules, Commun. Math. Phys. 324, 351-399 (2013), arXiv:1204.1063.
https://doi.org/10.1007/s00220-013-1810-2
arXiv:1204.1063

[44] M. B. Hastings, Lieb-Schultz-Mattis in higher dimensions, Physical Review B 69, 104431 (2004), cond-mat/​0305505.
https://doi.org/10.1103/physrevb.69.104431
arXiv: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.
https://doi.org/10.1007/s00220-011-1380-0
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.
https://doi.org/10.1103/PhysRevLett.102.110502
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.
https://doi.org/10.1103/PhysRevLett.110.170503
arXiv:1206.1609

[48] D. Poulin, Stabilizer formalism for operator quantum error correction, Phys. Rev. Lett. 95, 230504 (2005), quant-ph/​0508131.
https://doi.org/10.1103/PhysRevLett.95.230504
arXiv: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
arXiv:0907.4207

[50] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Topological quantum memory, Journal of Mathematical Physics 43, 4452-4505 (2002), quant-ph/​0110143.
https://doi.org/10.1063/1.1499754
arXiv: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.
https://doi.org/10.1142/S1230161210000023
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
arXiv:1411.6643

[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
arXiv:1503.06237

[54] D. Harlow, The Ryu-Takayanagi formula from quantum error correction, (2016), arXiv:1607.03901.
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
arXiv:quant-ph/0610146

[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
arXiv:quant-ph/0312081