Complexity and entanglement in non-local computation and holography

Alex May

Stanford University

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


Does gravity constrain computation? We study this question using the AdS/CFT correspondence, where computation in the presence of gravity can be related to non-gravitational physics in the boundary theory. In AdS/CFT, computations which happen locally in the bulk are implemented in a particular non-local form in the boundary, which in general requires distributed entanglement. In more detail, we recall that for a large class of bulk subregions the area of a surface called the ridge is equal to the mutual information available in the boundary to perform the computation non-locally. We then argue the complexity of the local operation controls the amount of entanglement needed to implement it non-locally, and in particular complexity and entanglement cost are related by a polynomial. If this relationship holds, gravity constrains the complexity of operations within these regions to be polynomial in the area of the ridge.

► BibTeX data

► References

[1] Geoffrey Penington. Entanglement wedge reconstruction and the information paradox. Journal of High Energy Physics, 2020 (9): 1–84, 2020. https:/​/​​10.1007/​JHEP09(2020)002.

[2] Ahmed Almheiri, Netta Engelhardt, Donald Marolf, and Henry Maxfield. The entropy of bulk quantum fields and the entanglement wedge of an evaporating black hole. Journal of High Energy Physics, 2019 (12): 1–47, 2019. https:/​/​​10.1007/​JHEP12(2019)063.

[3] Stephen P Jordan, Hari Krovi, Keith SM Lee, and John Preskill. BQP-completeness of scattering in scalar quantum field theory. Quantum, 2: 44, 2018. https:/​/​​10.22331/​q-2018-01-08-44.

[4] Seth Lloyd. Ultimate physical limits to computation. Nature, 406 (6799): 1047–1054, 2000. https:/​/​​10.1038/​35023282.

[5] Stephen P. Jordan. Fast quantum computation at arbitrarily low energy. Phys. Rev. A, 95: 032305, Mar 2017. https:/​/​​10.1103/​PhysRevA.95.032305.

[6] Juan Maldacena. The large-N limit of superconformal field theories and supergravity. International journal of theoretical physics, 38 (4): 1113–1133, 1999. https:/​/​​10.1023/​A:1026654312961.

[7] Edward Witten. Anti de Sitter space and holography. arXiv preprint hep-th/​9802150, 1998. 10.4310/​ATMP.1998.v2.n2.a2.

[8] Daniel Harlow. TASI lectures on the emergence of the bulk in AdS/​CFT. arXiv preprint arXiv:1802.01040, 2018. https:/​/​​10.22323/​1.305.0002.

[9] Alex May. Quantum tasks in holography. Journal of High Energy Physics, 2019 (10): 1–39, 2019. https:/​/​​10.1007/​JHEP10(2019)233.

[10] Idse Heemskerk, Joao Penedones, Joseph Polchinski, and James Sully. Holography from conformal field theory. Journal of High Energy Physics, 2009 (10): 079, 2009. http:/​/​​10.1088/​1126-6708/​2009/​10/​079.

[11] Michael Gary, Steven B Giddings, and Joao Penedones. Local bulk S-matrix elements and conformal field theory singularities. Physical Review D, 80 (8): 085005, 2009. https:/​/​​10.1103/​PhysRevD.80.085005.

[12] Juan Maldacena, David Simmons-Duffin, and Alexander Zhiboedov. Looking for a bulk point. Journal of High Energy Physics, 2017 (1): 1–50, 2017. https:/​/​​10.1007/​JHEP01(2017)013.

[13] Alex May, Geoff Penington, and Jonathan Sorce. Holographic scattering requires a connected entanglement wedge. Journal of High Energy Physics, 2020 (8): 1–34, 2020. https:/​/​​10.1007/​JHEP08(2020)132.

[14] Alex May. Holographic quantum tasks with input and output regions. Journal of High Energy Physics, 2021 (8): 1–24, 2021a. https:/​/​​10.1007/​JHEP08(2021)055.

[15] Adrian P Kent, William J Munro, Timothy P Spiller, and Raymond G Beausoleil. Tagging systems, July 11 2006. US Patent 7,075,438.

[16] Adrian Kent, William J Munro, and Timothy P Spiller. Quantum tagging: Authenticating location via quantum information and relativistic signaling constraints. Physical Review A, 84 (1): 012326, 2011. https:/​/​​10.1103/​PhysRevA.84.012326.

[17] Robert A Malaney. Location-dependent communications using quantum entanglement. Physical Review A, 81 (4): 042319, 2010. https:/​/​​10.1103/​PhysRevA.81.042319.

[18] Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, and Christian Schaffner. Position-based quantum cryptography: Impossibility and constructions. SIAM Journal on Computing, 43 (1): 150–178, 2014. https:/​/​​10.1137/​130913687.

[19] Raphael Bousso. A covariant entropy conjecture. Journal of High Energy Physics, 1999 (07): 004, 1999. 10.1088/​1126-6708/​1999/​07/​004.

[20] Eanna E Flanagan, Donald Marolf, and Robert M Wald. Proof of classical versions of the Bousso entropy bound and of the generalized second law. Physical Review D, 62 (8): 084035, 2000. https:/​/​​10.1103/​PhysRevD.62.084035.

[21] Raphael Bousso, Horacio Casini, Zachary Fisher, and Juan Maldacena. Proof of a quantum Bousso bound. Physical Review D, 90 (4): 044002, 2014. https:/​/​​10.1103/​PhysRevD.90.044002.

[22] Harry Buhrman, Serge Fehr, Christian Schaffner, and Florian Speelman. The garden-hose model. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 145–158, 2013. https:/​/​​10.1145/​2422436.2422455.

[23] Sam Cree and Alex May. Code-routing: a new attack on position-verification. arXiv preprint arXiv:2202.07812, 2022. https:/​/​​10.48550/​arXiv.2202.07812.

[24] Salman Beigi and Robert König. Simplified instantaneous non-local quantum computation with applications to position-based cryptography. New Journal of Physics, 13 (9): 093036, 2011. 10.1088/​1367-2630/​13/​9/​093036.

[25] Kfir Dolev. Constraining the doability of relativistic quantum tasks. arXiv preprint arXiv:1909.05403, 2019. https:/​/​​10.48550/​arXiv.1909.05403.

[26] Shinsei Ryu and Tadashi Takayanagi. Aspects of holographic entanglement entropy. Journal of High Energy Physics, 2006 (08): 045, 2006. 10.1088/​1126-6708/​2006/​08/​045.

[27] Veronika E Hubeny, Mukund Rangamani, and Tadashi Takayanagi. A covariant holographic entanglement entropy proposal. Journal of High Energy Physics, 2007 (07): 062, 2007. 10.1088/​1126-6708/​2007/​07/​062.

[28] Aitor Lewkowycz and Juan Maldacena. Generalized gravitational entropy. Journal of High Energy Physics, 2013 (8): 1–29, 2013. https:/​/​​10.1007/​JHEP08(2013)090.

[29] Thomas Faulkner, Aitor Lewkowycz, and Juan Maldacena. Quantum corrections to holographic entanglement entropy. Journal of High Energy Physics, 2013 (11): 1–18, 2013. https:/​/​​10.1007/​JHEP11(2013)074.

[30] Xi Dong, Aitor Lewkowycz, and Mukund Rangamani. Deriving covariant holographic entanglement. Journal of High Energy Physics, 2016 (11): 1–39, 2016a. https:/​/​​10.1007/​JHEP11(2016)028.

[31] Netta Engelhardt and Aron C Wall. Quantum extremal surfaces: holographic entanglement entropy beyond the classical regime. Journal of High Energy Physics, 2015 (1): 1–27, 2015. https:/​/​​10.1007/​JHEP01(2015)073.

[32] Xi Dong and Aitor Lewkowycz. Entropy, extremality, Euclidean variations, and the equations of motion. Journal of High Energy Physics, 2018 (1): 1–33, 2018. https:/​/​​10.1007/​JHEP01(2018)081.

[33] Chris Akers and Geoff Penington. Leading order corrections to the quantum extremal surface prescription. Journal of High Energy Physics, 2021 (4): 1–73, 2021. https:/​/​​10.1007/​JHEP04(2021)062.

[34] Xi Dong and Huajia Wang. Enhanced corrections near holographic entanglement transitions: a chaotic case study. Journal of High Energy Physics, 2020 (11): 1–32, 2020. https:/​/​​10.1007/​JHEP11(2020)007.

[35] Donald Marolf, Shannon Wang, and Zhencheng Wang. Probing phase transitions of holographic entanglement entropy with fixed area states. Journal of High Energy Physics, 2020 (12): 1–41, 2020. https:/​/​​10.1007/​JHEP12(2020)084.

[36] Aron C Wall. Maximin surfaces, and the strong subadditivity of the covariant holographic entanglement entropy. Classical and Quantum Gravity, 31 (22): 225007, 2014. 10.1088/​0264-9381/​31/​22/​225007.

[37] Chris Akers, Netta Engelhardt, Geoff Penington, and Mykhaylo Usatyuk. Quantum maximin surfaces. Journal of High Energy Physics, 2020 (8): 1–43, 2020. https:/​/​​10.1007/​JHEP08(2020)140.

[38] Bartłomiej Czech, Joanna L Karczmarek, Fernando Nogueira, and Mark Van Raamsdonk. The gravity dual of a density matrix. Classical and Quantum Gravity, 29 (15): 155009, 2012. 10.1088/​0264-9381/​29/​15/​155009.

[39] Matthew Headrick, Veronika E Hubeny, Albion Lawrence, and Mukund Rangamani. Causality & holographic entanglement entropy. Journal of High Energy Physics, 2014 (12): 1–36, 2014. https:/​/​​10.1007/​JHEP12(2014)162.

[40] Daniel L Jafferis, Aitor Lewkowycz, Juan Maldacena, and S Josephine Suh. Relative entropy equals bulk relative entropy. Journal of High Energy Physics, 2016 (6): 1–20, 2016. https:/​/​​10.1007/​JHEP06(2016)004.

[41] Xi Dong, Daniel Harlow, and Aron C Wall. Reconstruction of bulk operators within the entanglement wedge in gauge-gravity duality. Physical review letters, 117 (2): 021601, 2016b. https:/​/​​10.1103/​PhysRevLett.117.021601.

[42] Jordan Cotler, Patrick Hayden, Geoffrey Penington, Grant Salton, Brian Swingle, and Michael Walter. Entanglement wedge reconstruction via universal recovery channels. Physical Review X, 9 (3): 031011, 2019. https:/​/​​10.1103/​PhysRevX.9.031011.

[43] Chris Akers, Adam Levine, and Stefan Leichenauer. Large breakdowns of entanglement wedge reconstruction. Physical Review D, 100 (12): 126006, 2019. https:/​/​​10.1103/​PhysRevD.100.126006.

[44] Kfir Dolev and Sam Cree. Holography as a resource for non-local quantum computation. arXiv preprint arXiv:2210.13500, 2022a. https:/​/​​10.48550/​arXiv.2210.13500.

[45] Marco Tomamichel, Serge Fehr, Jędrzej Kaniewski, and Stephanie Wehner. A monogamy-of-entanglement game with applications to device-independent quantum cryptography. New Journal of Physics, 15 (10): 103002, 2013. 10.1088/​1367-2630/​15/​10/​103002.

[46] Andreas Bluhm, Matthias Christandl, and Florian Speelman. Position-based cryptography: Single-qubit protocol secure against multi-qubit attacks. arXiv preprint arXiv:2104.06301, 2021. https:/​/​​10.48550/​arXiv.2104.06301.

[47] ID Ivonovic. Geometrical description of quantal state determination. Journal of Physics A: Mathematical and General, 14 (12): 3241, 1981. 10.1088/​0305-4470/​14/​12/​019.

[48] William K Wootters and Brian D Fields. Optimal state-determination by mutually unbiased measurements. Annals of Physics, 191 (2): 363–381, 1989. https:/​/​​10.1016/​0003-4916(89)90322-9.

[49] Andreas Klappenecker and Martin Rötteler. Constructions of mutually unbiased bases. In International Conference on Finite Fields and Applications, pages 137–144. Springer, 2003. https:/​/​​10.1007/​978-3-540-24633-6_10.

[50] Marius Junge, Aleksander M Kubicki, Carlos Palazuelos, and David Pérez-García. Geometry of Banach spaces: a new route towards Position Based Cryptography. arXiv preprint arXiv:2103.16357, 2021. https:/​/​​10.1007/​s00220-022-04407-9.

[51] Mauricio Karchmer and Avi Wigderson. On span programs. In [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference, pages 102–111. IEEE, 1993. 10.1109/​SCT.1993.336536.

[52] Norman Margolus and Lev B Levitin. The maximum speed of dynamical evolution. Physica D: Nonlinear Phenomena, 120 (1-2): 188–195, 1998. https:/​/​​10.1016/​S0167-2789(98)00054-2.

[53] Florian Speelman. Instantaneous non-local computation of low T-depth quantum circuits. arXiv preprint arXiv:1511.02839, 2015. https:/​/​​10.4230/​LIPIcs.TQC.2016.9.

[54] Satoshi Ishizaka and Tohya Hiroshima. Quantum teleportation scheme by selecting one of multiple output ports. Physical Review A, 79 (4): 042306, 2009. https:/​/​​10.1103/​PhysRevA.79.042306.

[55] Alex May. Quantum tasks in holography (PhD thesis). https:/​/​​collections/​ubctheses/​24/​items/​1.0401122, 2021b. https:/​/​​10.14288/​1.0401122.

[56] András Gilyén, Seth Lloyd, Iman Marvian, Yihui Quek, and Mark M Wilde. Quantum algorithm for Petz recovery channels and pretty good measurements. arXiv preprint arXiv:2006.16924, 2020. https:/​/​​10.1103/​PhysRevLett.128.220502.

[57] Matthias Christandl, Felix Leditzky, Christian Majenz, Graeme Smith, Florian Speelman, and Michael Walter. Asymptotic performance of port-based teleportation. Communications in Mathematical Physics, 381 (1): 379–451, 2021. https:/​/​​10.1007/​s00220-020-03884-0.

[58] Sean Clark. Valence bond solid formalism for d-level one-way quantum computation. Journal of Physics A: Mathematical and General, 39 (11): 2701, 2006. 10.1088/​0305-4470/​39/​11/​010.

[59] Kaushik Chakraborty and Anthony Leverrier. Practical position-based quantum cryptography. Physical Review A, 92 (5): 052304, 2015. https:/​/​​10.1103/​PhysRevA.92.052304.

[60] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70 (5): 052328, 2004. https:/​/​​10.1103/​PhysRevA.70.052328.

[61] Niel De Beaudrap. A linearized stabilizer formalism for systems of finite dimension. Quantum Information & Computation, 13 (1-2): 73–115, 2013. https:/​/​​10.48550/​arXiv.1102.3354.

[62] Adam D Smith. Quantum secret sharing for general access structures. arXiv preprint quant-ph/​0001087, 2000. https:/​/​​10.48550/​arXiv.quant-ph/​0001087.

[63] Alex May. Bulk private curves require large conditional mutual information. Journal of High Energy Physics, 2021 (9): 1–28, 2021c. https:/​/​​10.1007/​JHEP09(2021)042.

[64] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP*= RE. Communications of the ACM, 64 (11): 131–138, 2021. https:/​/​​10.1145/​3485628.

[65] Jiani Fei, Patrick Hayden, and Rae Timmerman. Efficient algorithms for port-based teleportation. to appear.

[66] Kfir Dolev and Sam Cree. Non-local computation of quantum circuits with small light cones. arXiv preprint arXiv:2203.10106, 2022b. https:/​/​​10.48550/​arXiv.2203.10106.

Cited by

[1] Aleksander M. Kubicki, Alex May, and David Pérez-Garcia, "Constraints on physical computers in holographic spacetimes", SciPost Physics 16 1, 024 (2024).

[2] Felix Leditzky, "Optimality of the pretty good measurement for port-based teleportation", Letters in Mathematical Physics 112 5, 98 (2022).

[3] Ha Eum Kim and Kabgyun Jeong, "Port-based entanglement teleportation via noisy resource states", Physica Scripta 99 3, 035105 (2024).

[4] Alex May and Michelle Xu, "Non-local computation and the black hole interior", Journal of High Energy Physics 2024 2, 79 (2024).

[5] Marek Mozrzymas, Michał Horodecki, and Michał Studziński, "From port-based teleportation to Frobenius reciprocity theorem: partially reduced irreducible representations and their applications", Letters in Mathematical Physics 114 2, 56 (2024).

[6] Matthew Steinberg, Sebastian Feld, and Alexander Jahn, "Holographic codes from hyperinvariant tensor networks", Nature Communications 14 1, 7314 (2023).

[7] Sergii Strelchuk and Michał Studziński, "Minimal port-based teleportation", New Journal of Physics 25 6, 063012 (2023).

[8] Joy Cree and Alex May, "Code-routing: a new attack on position verification", Quantum 7, 1079 (2023).

[9] Alex May, Jonathan Sorce, and Beni Yoshida, "The connected wedge theorem and its consequences", Journal of High Energy Physics 2022 11, 153 (2022).

[10] Felix Leditzky, "Optimality of the pretty good measurement for port-based teleportation", arXiv:2008.11194, (2020).

[11] Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman, and Philip Verduyn Lunel, "Relating non-local quantum computation to information theoretic cryptography", arXiv:2306.16462, (2023).

[12] Kfir Dolev and Sam Cree, "Non-local computation of quantum circuits with small light cones", arXiv:2203.10106, (2022).

[13] Kfir Dolev and Sam Cree, "Holography as a resource for non-local quantum computation", arXiv:2210.13500, (2022).

[14] Vahid Asadi, Eric Culf, and Alex May, "Rank lower bounds on non-local quantum computation", arXiv:2402.18647, (2024).

[15] Vahid Asadi, Richard Cleve, Eric Culf, and Alex May, "Linear gate bounds against natural functions for position-verification", arXiv:2402.18648, (2024).

[16] Jacqueline Caminiti, Batia Friedman-Shaw, Alex May, Robert C. Myers, and Olga Papadoulaki, "Holographic scattering and non-minimal RT surfaces", arXiv:2404.15400, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2024-05-21 14:17:25) and SAO/NASA ADS (last updated successfully 2024-05-21 14:17:25). The list may be incomplete as not all publishers provide suitable and complete citation data.