Complexity And Entanglement In Non-local Computation And Holography

Stanford University

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

Abstract

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

@article{May2022complexity, doi = {10.22331/q-2022-11-28-864}, url = {https://doi.org/10.22331/q-2022-11-28-864}, title = {Complexity and entanglement in non-local computation and holography}, author = {May, Alex}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {6}, pages = {864}, month = nov, year = {2022}<br /> }

► References

[1] Geoffrey Penington. Entanglement wedge reconstruction and the information paradox. Journal of High Energy Physics, 2020 (9): 1–84, 2020. https://doi.org/10.1007/JHEP09(2020)002.
https://doi.org/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://doi.org/10.1007/JHEP12(2019)063.
https://doi.org/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://doi.org/10.22331/q-2018-01-08-44.
https://doi.org/10.22331/q-2018-01-08-44

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

[5] Stephen P. Jordan. Fast quantum computation at arbitrarily low energy. Phys. Rev. A, 95: 032305, Mar 2017. https://doi.org/10.1103/PhysRevA.95.032305.
https://doi.org/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://doi.org/10.1023/A:1026654312961.
https://doi.org/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.
https://doi.org/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://doi.org/10.22323/1.305.0002.
https://doi.org/10.22323/1.305.0002
arXiv:1802.01040

[9] Alex May. Quantum tasks in holography. Journal of High Energy Physics, 2019 (10): 1–39, 2019. https://doi.org/10.1007/JHEP10(2019)233.
https://doi.org/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://dx.doi.org/10.1088/1126-6708/2009/10/079.
https://doi.org/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://doi.org/10.1103/PhysRevD.80.085005.
https://doi.org/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://doi.org/10.1007/JHEP01(2017)013.
https://doi.org/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://doi.org/10.1007/JHEP08(2020)132.
https://doi.org/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://doi.org/10.1007/JHEP08(2021)055.
https://doi.org/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://doi.org/10.1103/PhysRevA.84.012326.
https://doi.org/10.1103/PhysRevA.84.012326

[17] Robert A Malaney. Location-dependent communications using quantum entanglement. Physical Review A, 81 (4): 042319, 2010. https://doi.org/10.1103/PhysRevA.81.042319.
https://doi.org/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://doi.org/10.1137/130913687.
https://doi.org/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.
https://doi.org/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://doi.org/10.1103/PhysRevD.62.084035.
https://doi.org/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://doi.org/10.1103/PhysRevD.90.044002.
https://doi.org/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://doi.org/10.1145/2422436.2422455.
https://doi.org/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://doi.org/10.48550/arXiv.2202.07812.
https://doi.org/10.48550/arXiv.2202.07812
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.
https://doi.org/10.1088/1367-2630/13/9/093036

[25] Kfir Dolev. Constraining the doability of relativistic quantum tasks. arXiv preprint arXiv:1909.05403, 2019. https://doi.org/10.48550/arXiv.1909.05403.
https://doi.org/10.48550/arXiv.1909.05403
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.
https://doi.org/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.
https://doi.org/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://doi.org/10.1007/JHEP08(2013)090.
https://doi.org/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://doi.org/10.1007/JHEP11(2013)074.
https://doi.org/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://doi.org/10.1007/JHEP11(2016)028.
https://doi.org/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://doi.org/10.1007/JHEP01(2015)073.
https://doi.org/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://doi.org/10.1007/JHEP01(2018)081.
https://doi.org/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://doi.org/10.1007/JHEP04(2021)062.
https://doi.org/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://doi.org/10.1007/JHEP11(2020)007.
https://doi.org/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://doi.org/10.1007/JHEP12(2020)084.
https://doi.org/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.
https://doi.org/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://doi.org/10.1007/JHEP08(2020)140.
https://doi.org/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.
https://doi.org/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://doi.org/10.1007/JHEP12(2014)162.
https://doi.org/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://doi.org/10.1007/JHEP06(2016)004.
https://doi.org/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://doi.org/10.1103/PhysRevLett.117.021601.
https://doi.org/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://doi.org/10.1103/PhysRevX.9.031011.
https://doi.org/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://doi.org/10.1103/PhysRevD.100.126006.
https://doi.org/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://doi.org/10.48550/arXiv.2210.13500.
https://doi.org/10.48550/arXiv.2210.13500
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.
https://doi.org/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://doi.org/10.48550/arXiv.2104.06301.
https://doi.org/10.48550/arXiv.2104.06301
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.
https://doi.org/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://doi.org/10.1016/0003-4916(89)90322-9.
https://doi.org/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://doi.org/10.1007/978-3-540-24633-6_10.
https://doi.org/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://doi.org/10.1007/s00220-022-04407-9.
https://doi.org/10.1007/s00220-022-04407-9
arXiv:2103.16357

[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.
https://doi.org/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://doi.org/10.1016/S0167-2789(98)00054-2.
https://doi.org/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://doi.org/10.4230/LIPIcs.TQC.2016.9.
https://doi.org/10.4230/LIPIcs.TQC.2016.9
arXiv:1511.02839

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

[55] Alex May. Quantum tasks in holography (PhD thesis). https://open.library.ubc.ca/collections/ubctheses/24/items/1.0401122, 2021b. https://dx.doi.org/10.14288/1.0401122.
https://doi.org/10.14288/1.0401122
https://open.library.ubc.ca/collections/ubctheses/24/items/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://doi.org/10.1103/PhysRevLett.128.220502.
https://doi.org/10.1103/PhysRevLett.128.220502
arXiv:2006.16924

[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://doi.org/10.1007/s00220-020-03884-0.
https://doi.org/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.
https://doi.org/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://doi.org/10.1103/PhysRevA.92.052304.
https://doi.org/10.1103/PhysRevA.92.052304

[60] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70 (5): 052328, 2004. https://doi.org/10.1103/PhysRevA.70.052328.
https://doi.org/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://doi.org/10.48550/arXiv.1102.3354.
https://doi.org/10.48550/arXiv.1102.3354

[62] Adam D Smith. Quantum secret sharing for general access structures. arXiv preprint quant-ph/0001087, 2000. https://doi.org/10.48550/arXiv.quant-ph/0001087.
https://doi.org/10.48550/arXiv.quant-ph/0001087
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://doi.org/10.1007/JHEP09(2021)042.
https://doi.org/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://doi.org/10.1145/3485628.
https://doi.org/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://doi.org/10.48550/arXiv.2203.10106.
https://doi.org/10.48550/arXiv.2203.10106
arXiv:2203.10106

Cited by

[1] Alex May, Jonathan Sorce, and Beni Yoshida, “The connected wedge theorem and its consequences”, arXiv:2210.00018.

[2] Felix Leditzky, “Optimality of the pretty good measurement for port-based teleportation”, arXiv:2008.11194.

[3] Kfir Dolev and Sam Cree, “Non-local computation of quantum circuits with small light cones”, arXiv:2203.10106.

[4] Sam Cree and Alex May, “Code-routing: a new attack on position verification”, arXiv:2202.07812.

[5] Kfir Dolev and Sam Cree, “Holography as a resource for non-local quantum computation”, arXiv:2210.13500.

The above citations are from SAO/NASA ADS (last updated successfully 2022-11-28 18:07:48). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2022-11-28 18:07:46: Could not fetch cited-by data for 10.22331/q-2022-11-28-864 from Crossref. This is normal if the DOI was registered recently.

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.

Generative Data Intelligence

Complexity and entanglement in non-local computation and holography

Abstract

► BibTeX data

► References

Cited by

Are Altcoins done? Trader issues alert amid ‘scary’ behavior in Chainlink (LINK) and others

Decoding The SEC’s Ripple To Ethereum Regulatory Shift – CryptoInfoNet

Latest Intelligence

NYSE considers 24/7 trading to match crypto markets

Fiserv’s Net Profits Increased by Over 30% in Early 2024

First Mover Americas: Venezuela Looks to Tether for Oil Sales as Sanctions Return

Akash Network’s Token Surges 50% on Upbit Listing

Ripple contests SEC’s US$2 bln fine, suggests US$10 mln

VPNs, Firewalls’ Nonexistent Telemetry Lures APTs

Chat with us