Is spacetime a quantum error correcting code? Fun with holography, the AdS/CFT correspondence and black holes

The purpose of this blogpost is to explain a paper that was written by HArlow, Pastawski, Preskilly and Yoshida (HAPPY) titled, “Holographic quantum error-correcting codes: Toy models for the bulk/boundary correspondence.” I admit, I was rather amused when I first came across this paper sometime during the July of this year. I was in something of a superposition between confusion and sheer amazement. But after some degree of thought, which was supplanted by my other readings; I began to wonder about how the ideas of quantum computing could be applied to other problems in Physics. This particular paper, is quite remarkable. It provides a quantum computing take on quantum gravity. It proposes a toy model which resolves some central puzzles with regards to the AdS/CFT correspondence and it paves way for future work along the, "applications of quantum computing ideas to quantum gravity" line.

Introduction 

So before we begin, its probably important to note that this paper deals with the Ads/CFT correspondence. This is a very important idea in modern day high energy physics and was proposed by Maldacena in ‘97. It provides a link between quantum field theory and quantum gravity. So how do I go about explaining it? Well, by showing you a picture. 

Figure 1: A stack of hyperbolic disks, with each one representing the state of the universe at a given time. The hyperbolic disks tiling is referred to as hyperbolic tessellations.

Okay, so there are two parts to these disks: 

1. The edge of the disk which is called the boundary 
2. Everything inside the boundary, which is simply called the bulk (not sure who picked that name)

The AdS/CFT correspondence states that a Conformal Field Theory(a kind of quantum field theory) living on a d-dimensional boundary is equal to a d+1-dimensional bulk based quantum gravity in Ads(anti-de sitter) space. So what does that mean? Alright so AdS space is a kind of space which is bounded. We actually live in a universe which consists of a De-sitter space but its easier to do physics in an AdS space. We’ll have to adapt eventually though… for the time being, Physicists stick to figuring things out in AdS space. 

You may have picked up something, the Ads/CFT link something in d-dimensions to something in d+1 dimensions. That’s called the holographic principle. The Ads/CFT is actually the first realisation of it. What that basically means is that we might be holograms, we look and appear as if we’re higher dimensional creatures, but we may actually belong to a lower dimensional space… it's quite fun to think about this kinda stuff, no? What’s really fascinating however, is how quantum information scientists might be able to offer help with regards to the quantum gravity issue. HAPPY's paper is hard to explain, it’ll take quite a lot to simplify it but I’ll try my best. I’m not gonna make it a popular rendition. I'll talk about the main details of the paper accompanied with some proofs.  I would recommend reading a popular article on it by Preskill himself as well:

https://quantumfrontiers.com/2015/03/27/quantum-gravity-from-quantum-error-correcting-codes/

And if you’re really up for it, try reading HAPPY’s paper yourself. I’m not gonna lie, it can be a pretty tough read but if you’re interested, its definitely worth a shot! The hardest paper I ever read however was actually by Howard J. Carmichael but that's a story for another time... Anyhow, perhaps what I do might simplify the actual paper a bit for you. 

LETS GET CRACKING! 

Well took us long enough to start! So, we begin with two definitions:

• Definition 1: Isometry 
• Definition 2: Perfect Tensor 

Figure 2: Definitions of isometry and perfect tensors

So an isometry is something which maps from one Hilbert space to another while preserving the inner produce. A perfect tensor, is one whose indices can be split into two sets of indices(one set being larger than the other) with the condition that the tensor is an isometry from the smaller set of indices to the larger set. 

Constructing holographic quantum states and codes

Do you remember the Ads/CFT picture I showed you earlier? Remember how the tiles appeared bigger in the bulk but got smaller and smaller as it approached the boundary? Well, thats the property of a field of a discipline called differential geometry. The “disc” is basically a two dimensional hyperbolic space. Now HAPPY constructed a quantum code for this sort of Geometry. It's called the Pentagon code and I've attached it below. 

Figure 3: A quantum error correcting code called the Pentagon code. It belongs to a new class of codes called holographic codes and is constructed using tensor networks.

So there’s one pentagon in the centre of the bulk and it has 5 legs going out of it and connecting it to other pentagons which split further. The connected legs are really contracted tensors (invoke thy knowledge of General Relativity... tbh I never took a course in GR, I binge watched 9 Susskind lectures on the topic. Don't blame me! You don't need it for quantum computing!! - you will need quantum information for quantum gravity in the future though [hopefully]). The un-contracted legs on the boundary are associated with physical spins while the tensor network inside corresponds to a pure state of the spins, and is called a holographic state. The Pentagon tiling is basically an isometric tensor from the bulk to the boundary. This isometry corresponds to an encoding transformation of a quantum error correcting code called the holographic code. 

So, what does all that mean? Well you'll see in a bit, but do you remember the part under the isometry definition which talked about pushing an operator through a tensor? Well okay basically, you can push operators from a point in the bulk to the boundary. That's what isometry from bulk to boundary means. 

So a couple more definitions 

• Definition 3: Holographic state: If a tensor network composed of perfect tensors covers some geometric manifold with a boundary, and all the interior tensor legs are contracted, then a holographic state is a state interpretation of such tensor network where the physical degrees of freedom, are associated with the uncontracted legs at the boundary of the manifold. 
• Definition 4: Holographic code: A tensor network composed of perfect tensors which cover some geometric manifold with boundaries is a holographic code if it gives rise to an isometric map from uncontracted bulk legs to uncontracted boundary legs. 

(apparently uncontracted isn't a word, but I shall perform a naming baptism right now and display my complete lack of care for the english dictionary)

Entanglement Structure of Holographic States

Holographic states reproduce many properties of the Ads/CFT. I will discuss some of these properties here. The first of these is called the Ryu-Takayanagi formula and the second is the negativity of tripartite information. I have depicted the proofs for these as demonstrated in the original paper. The Ryu-Takayanagi formula basically allows us to calculate the entropy of some sub-region we'll call A. So how do we get it? Well let's see...

Figure 4: A demonstration of how the Ryu-Takayanagi formula is recreated using holographic states.

I should mention that the major contribution here is from the cut. Small order corrections are required for that final term. Now, the second interesting property of holographic states is that the tripartite information is negative. The tripartite information is basically another name for the topological entropy, it characterises the entanglement in states of many body systems which have a topological order. Here's a proof for why its negative.

Figure 4: A proof for why the tripartite information is negative.

Alright, so what have we done so far? We've shown key aspects of Ads/CFT are satisfied with holographic states. So we get back the Ryu-Takayanagi formula and we show how the tripartite information is negative. Its time to talk about error correction in holographic codes. 

Quantum error correction in holographic codes

There are many interesting properties associated with Holographic codes. That is to say, they solve a lot of stuff super nicely. I’ll tell you all the things which need solving first, or what the AdS/CFT correspondence demands and then how holographic codes meet those demands. 

Things which need to be satisfied:

1) AdS- Rindler reconstruction 

So what is reconstructed? Alright so basically a bulk operator can be reconstructed from a boundary operator. Still confused? Alright I’ll slow down. 

Figure 5: A hyperbolic disc shown with its causal wedge and an operator Q(x) in the causal wedge. Since Q(x) lies within the causal wedge of A, it can be reconstructed on the boundary of A.

You see that? Okay so in the hyperbolic disc, there are a few things of importance: 

• A region on the boundary dubbed “A”
• A geodesic line (shortest path between two points in curved space) connecting the two extreme points in A 
• The space between the above two which is called the causal wedge 

According to the AdS-Rindler reconstruction, if you have a bulk operator lying in the casual wedge of A, then it can be reconstructed as a boundary operator on the boundary of A. (Kinda makes sense if you think about AdS/CFT right?) okay so the deal is that if the operator Q(x) is deeper in the bulk, then there are multiple regions which contain Q(x) in their causal wedges. So the reconstruction should work for all of those regions. BAZINGA that leads to an interesting problem called the causal wedge problem. 

2) Causal wedge puzzle

Figure 6: A depiction of the causal wedge problem. The blue dot represents an operator and the disc is divided into three different regions titled A, B and C. Since the operator is deep within the bulk, it can be reconstructed onto multiple boundaries which is a problem...

So if you divide the disc in these different ways, meaning that your bulk operator lies in different causal wedges, what you end up with is kind of an issue… see, in the first case, if it lies in BC’s causal wedge, it can be reconstructed on the BC boundary and it commutes with any operator comfortably living on A. But a similar argument follows for the other regions where it can be reconstructed on AC and AB and the operator commutes with operators in the regions B and C respectively. So according to this, if the operator lies in a region of the bulk where it can exist in multiple causal wedges, then the operator can be reconstructed on any part of the disc and it commutes with all local operators on the boundary. 

So there are two ways to solve this problem, one is to use gauge invariance of the boundary theory and the second is to use error correcting codes. 

The first way… no I’m joking, I still have to finish my quantum field theory book. I was supposed to finish it in Christmas but then I got caught up with this and Netflix. Anyhow, the second way basically says that the bulk operator doesn’t correspond to a single boundary operator. Instead, the boundary operators corresponding to the different regions may be equivalent in a low energy subspace of the boundary. 

3) Entanglement wedge

 

Figure 7: A depiction of causal and entanglement wedges which correspond to local and global geodesics respectively. 

Alright so in the first diagram in Figure 7, suppose we have these two regions which represent the causal wedges of A and C. But suppose we want the causal region that represents the union of A and C. Now what do we do? Well basically, you draw geodesics connecting the extreme points of the local geodesics of A and C. This entire geodesic is called the global geodesic (physicists have the coolest names for things, no?) the entire region contained within the global geodesic is called the entanglement wedge of AC (Also makes sense if you think about it)

How to satisfy them: 

So the pentagon code is an isometry from the bulk to the boundary. Now lets get cooking with what that means. That basically means that if an operator is inputted at some tensor in the bulk, then that operator is pushed through the tensor until it covers some arc of the disc at the boundary. How? Well alright lets get to business with this tensor stuff. 

Figure 8: A depiction of 'pushing an operator' through a tensor

So now we know that if we input in an operator, then it'll pass through three legs. AHA!!!!! So not only does this solve the causal wedge problem (why? because it shows how an operator at a single point in the bulk corresponds to an arc of the boundary) it also allows us to reconstruct an entanglement wedge. How? Well let's see. (I used every ounce of my artistic mastery to create this in keynote by the way)

Figure 9: A depiction of how 'pushing an operator' through a tensor allows us to recreate the causal and entanglement wedges talked about in Figure 7. An additional property that is depicted is the resolution of the causal wedge puzzle since an operator that lies deeper within the bulk creates a larger edge in the boundary where it can reconstruct itself. 

Basically, the deeper an operator is within the bulk, the greater the region that it can cover on the boundary. Pretty neat right? Here’s a nice exercise that you could try if you’re interested, take the pentagon code, select a random pentagon in which you wish to input a tensor in. After that, push it through 3 of the 5 legs of the pentagon tensor and sketch out the boundary region. Its actually quite fun! I was at first puzzled about how I was getting the kind of global geodesic you see right now. Until I realised a very interesting property of this code (which should've been obvious but it didn't hit me right away), its made keeping in mind that there are 5 qubits on the boundary with one being in the centre of the bulk. So the global geodesic is actually between 3 of the 5 points on the boundary. 

Figure 10: The entanglement wedge of three points on a disc whose boundary is divided into five regions.

See? Pretty neat huh? I was actually a bit silly here, but the pentagon code actually corresponds to the 5 quit code. Remember my quantum error correction notes? Remember concatenation? Alright basically that one single code in the bulk is concatanated into 5 qubits which exist on the boundary. 

So how do holographic codes and more specifically the pentagon code solve our problem? Well, the pentagon code allows us to reconstruct bulk operators on the boundary, so it shows bulk boundary correspondence and it allows us to construct entanglement wedges, which are determined the depth of the operator within the bulk.

Alright so as a final treat, I shall show you how blackholes come into the mix as well! 

Figure 11: The depiction of a black hole in the tensor network

So what's the deal here? Well basically, operators are only reconstructed on a subspace of the boundary Hilbert space. This sounds like its at odds with the holographic correspondence right? Right so the resolution is that not every bulk operator is reproducible. Why? well, because it lies inside a black hole. So remember how initially the tensor legs of the central pentagon were contracted? Ah now they're not because the main pentagon's inside the black hole! So now we have an isometry that maps the five indices and the bulk legs of the remaining pentagons to the boundary. So how do you make a bigger black hole? Well, you eat up more layers in the tensor network... until eventually the black hole eats up the entire tensor network... On the bright side, the pentagon code really realises the bulk to boundary interpretation! So most boundary states correspond to a black hole in the bulk. 

Conclusions 

Ah so we’re at the end, I’d like to add the lyrics of an epic rock song by The Everlove first, 

“Well I don’t know where we are, 

and I don’t know how… how we got this far. 

But right now, there’s nothing in our way, 

been a long time coming now we’re headed for a better place, 

because tonight we’re alive, so we’ll leave it all behind 

so tonight, we’re alive and we’re running out of time, we’re running on our own way 

Hayom mayo hayem mayai, hayom mayo, said we’re on our way hayom mayo hayem mayai, hayom mayo said we’re on our way.”

I hope I've managed to show you how interesting this paper is. It recreates so many things and it demonstrates how the ideas of quantum computing can be applied to other problems in Physics. The pentagon code, which belongs to the larger family of holographic quantum codes, manages to capture extremely important features of the AdS/CFT. It allows us to recreate the Ryu-Takayanagi formula, it demonstrates that tripartite information is always negative, resolves the causal wedge puzzle and demonstrates how operators deep in the entanglement wedge can be reconstructed and even gives space for black holes. There are issues however, current models are not dynamical and they do not talk about bulk locality at sub-AdS distances. And as Preskill himself said, "Its a toy model and needs to be flushed out eventually." Unfortunately, we live in De-sitter space, this model doesn't particularly help with understanding quantum gravity in that space. There are some other issues which you can read about directly in the paper. I won't go into them because this has already become a pretty long post... 

So in the end, is space-time a quantum error correcting code? Well, we don’t know. It's an open research problem BUT, there seems to be an immense amount of hope with regards to the future. If quantum entanglements are the basis for spacetime geometry, then the quantum computing community will have a couple of things to say about the matter. Perhaps we can jump right into the heart of a blackhole with our years of experience on quantum error correction codes, computational complexity and knowledge about quantum information and resolve natures mysteries! Regardless, I'm just thrilled at a new class of error correcting codes. For me the most interesting question is this: For what other geometries can we construct quantum error correcting codes. Well, only time will tell! 

Before I end, I should say that if you're interested along the lines of applying quantum computing ideas to quantum gravity, there are a few people you should probably follow. (This is an incomplete list since I don't know this area that well except for a few names) Besides the authors of this paper, there's another paper by A.Almheri, X.Dong and D.Harlow(same author as the one for this paper) called "bulk locality and quantum error correction in ads/cft" which you should check out if you're interested in this area. Some other individuals who come to mind are Leonard Susskind (he's actually applying computational complexity to black holes) and Patrick Hayden. If you read the papers, you'll probably find other papers which carry on. This particular application is still pretty young since not many people are fluent in both quantum gravity and quantum information. I've heard that's changing slowly though. Which is great! It would be amazing to see quantum computing ideas being applied to a wide range of situations. 

Hope this was fun! 

P.S. I've realised that the proofs uploaded as images may not always be clear because of the lighting, so for future posts, I'll try to write them down on my iPad with some drawing app. 

Proving the halting problem and Godel's two incompleteness theorems on one page

So I thought I'd share a proof that I first read about in Quantum Computing Since Democritus by Scott Aaronson. However, the proof can be a bit tough to follow because it's only words.  I hope this intuitive approach using diagrams will allow a greater number of individuals to understand Godel's incompleteness theorems. The proofs are short, all you really need is the concept of a computer. Two things before I begin however:

(1) I know that some of my friends who're mathematicians will be slightly grumpy about the lack of rigour. But in my opinion, rigour is the price that one has to pay for simplicity and elegance. I actually remember a quote by Nietzsche, "I wish to say within the space of ten sentences what others say in one book." Feel free to disagree though, everyones free to follow their own approach. I admit, I actually favoured more tedious and rigorous mechanisms for proving things in the past. Christopher eventually managed to convert me with his far simpler and more intuitive approaches towards problem solving. Any leanings of mine towards an elegant proof is due to an aesthetic sense that he helped develop. 

(2) Anyhow, I hope no one minds my more modern approach towards latin, quod erad demonstrandum is a bit of a mouthful, #QED should do nicely. Christopher's also the person who taught me this fine product of 21st century pop culture and I have never failed to adapt myself to the modern era since! The naming baptism of the two theorems as FIT and SIT (first incompleteness theorem and second incompleteness theorem) is simply a demonstration of my devotion towards more pop based phrases. 

(On a sidenote, just click on the pictures and zoom in to see things a bit more clearly) 

So before proving the incompleteness theorems, we must first prove the halting problem. We do that with the oldest tool in the mathematicians arsenal, contradiction. 

Fig 1: An intuitive block diagram proof for the halting problem

Alright so now that we've proved that, we shall start with Godel's first incompleteness theorem. And how do we prove that? 

Well, the answer is contradiction 

Fig 2: A proof for the first incompleteness theorem

Right, so that one requires a small bit of insight; the insight is that a statement about halting is a statement about integers. Skies are still looking blue, so we can adopt the above strategy to prove the second incompleteness theorem. Does anyone wanna guess how we'll do that? 

10 points to the person who said: "contradiction" 

Fig 3: A proof for Godel's second incompleteness theorem 

And there you have it! Personally speaking, I quite like the proof for the second incompleteness theorem. These proofs are quite elegant and they allow us to skip over the slightly gruesome way the two incompleteness theorems are taught in regular math classes (the long way). Don't worry if you don't get it right away though, spend some time thinking about it. Its not the result thats important but the manner of thinking used to achieve that result. You might have a slightly different approach to doing it but the important thing is to manifest your thoughts in some way. Reading proofs like texts won't get you very far. It's important to be able to visualise what's happening. 

I hope everyone enjoyed this!