Tuesday, March 31, 2015

Quantum gravity from quantum error-correcting codes?

Guest blog by Dr Beni Yoshida, quantum information fellow at Caltech

The lessons we learned from the Ryu-Takayanagi formula, the firewall paradox, and the ER=EPR conjecture have convinced us that quantum information theory can become a powerful tool to sharpen our understanding of various problems in high-energy physics. But many of the concepts utilized so far rely on entanglement entropy and its generalizations, quantities developed by Von Neumann more than 60 years ago. We live in the 21st century. Why don’t we use more modern concepts, such as the theory of quantum error-correcting codes?
Off-topic, LHC: CERN sent quite some current to the shorted segment of the circuit, apparently melted and destroyed the offending metallic piece in a diode box, and miraculously cured the LHC! Restart could be within days. LM
In a recent paper with Daniel Harlow, Fernando Pastawski and John Preskill, we have proposed a toy model of the AdS/CFT correspondence based on quantum error-correcting codes. Fernando has already written how this research project started after a fateful visit by Daniel to Caltech and John’s remarkable prediction in 1999. In this post, I hope to write an introduction which may serve as a reader’s guide to our paper, explaining why I’m so fascinated by the beauty of the toy model.

This is certainly a challenging task because I need to make it accessible to everyone while explaining real physics behind the paper. My personal philosophy is that a toy model must be as simple as possible while capturing key properties of the system of interest. In this post, I will try to extract some key features of the AdS/CFT correspondence and construct a toy model which captures these features. This post may be a bit technical compared to other recent posts, but anyway, let me give it a try...

Bulk locality paradox and quantum error-correction

The AdS/CFT correspondence says that there is some kind of correspondence between quantum gravity on \((d+1)\)-dimensional asymptotically-AdS space and \(d\)-dimensional conformal field theory on its boundary. But how are they related?

The AdS-Rindler reconstruction tells us how to “reconstruct” a bulk operator from boundary operators. Consider a bulk operator \(\phi\) and a boundary region A on a hyperbolic space (in other words, a negatively-curved plane). On a fixed time-slice, the causal wedge of A is a bulk region enclosed by the geodesic line of A (a curve with a minimal length). The AdS-Rindler reconstruction says that \(\phi\) can be represented by some integral of local boundary operators supported on A if and only if \(\phi\) is contained inside the causal wedge of A. Of course, there are multiple regions A,B,C,… whose causal wedges contain \(\phi\), and the reconstruction should work for any such region.

The Rindler-wedge reconstruction

That a bulk operator in the causal wedge can be reconstructed by local boundary operators, however, leads to a rather perplexing paradox in the AdS/CFT correspondence. Consider a bulk operator \(\phi\) at the center of a hyperbolic space, and split the boundary into three pieces, A, B, C. Then the geodesic line for the union of BC encloses the bulk operator, that is, \(\phi\) is contained inside the causal wedge of BC. So, \(\phi\) can be represented by local boundary operators supported on BC. But the same argument applies to AB and CA, implying that the bulk operator \(\phi\) corresponds to local boundary operators which are supported inside AB, BC, and CA simultaneously. It would seem then that the bulk operator \(\phi\) must correspond to an identity operator times a complex phase. In fact, similar arguments apply to any bulk operators, and thus, all the bulk operators must correspond to identity operators on the boundary. Then, the AdS/CFT correspondence seems so boring...

The bulk operator at the center is contained inside causal wedges of BC, AB, AC. Does this mean that the bulk operator corresponds to an identity operator on the boundary?

Almheiri, Dong, and Harlow have recently proposed an intriguing way of reconciling this paradox with the AdS/CFT correspondence [see also Polchinski et al., TRF]. They proposed that the AdS/CFT correspondence can be viewed as a quantum error-correcting code. Their idea is as follows. Instead of \(\phi\) corresponding to a single boundary operator, \(\phi\) may correspond to different operators in different regions, say \(O_{AB}\), \(O_{BC}\), \(O_{CA}\) living in AB, BC, CA respectively. Even though \(O_{AB}\), \(O_{BC}\), \(O_{CA}\) are different boundary operators, they may be equivalent inside a certain low energy subspace on the boundary.

This situation resembles the so-called quantum secret-sharing code. The quantum information at the center of the bulk cannot be accessed from any single party A, B or C because \(\phi\) does not have representation on A, B, or C. It can be accessed only if multiple parties cooperate and perform joint measurements. It seems that a quantum secret is shared among three parties, and the AdS/CFT correspondence somehow realizes the three-party quantum secret-sharing code!

Entanglement wedge reconstruction?

Recently, causal wedge reconstruction has been further generalized to the notion of entanglement wedge reconstruction. Imagine we split the boundary into four pieces A,B,C,D such that A,C are larger than B,D. Then the geodesic lines for A and C do not form the geodesic line for the union of A and C because we can draw shorter arcs by connecting endpoints of A and C, which form the global geodesic line. The entanglement wedge of AC is a bulk region enclosed by this global geodesic line of AC. And the entanglement wedge reconstruction predicts that \(\phi\) can be represented as an integral of local boundary operators on AC if and only if \(\phi\) is inside the entanglement wedge of AC [1].

Causal wedge vs entanglement wedge.

Building a minimal toy model; the five-qubit code

Okay, now let’s try to construct a toy model which admits causal and entanglement wedge reconstructions of bulk operators. Because I want a simple toy model, I take a rather bold assumption that the bulk consists of a single qubit while the boundary consists of five qubits, denoted by A, B, C, D, E.

Reconstruction of a bulk operator in the “minimal” model.

What does causal wedge reconstruction teach us in this minimal setup of five and one qubits? First, we split the boundary system into two pieces, ABC and DE and observe that the bulk operator \(\phi\) is contained inside the causal wedge of ABC. From the rotational symmetries, we know that the bulk operator \(\phi\) must have representations on ABC, BCD, CDE, DEA, EAB. Next, we split the boundary system into four pieces, AB, C, D and E, and observe that the bulk operator \(\phi\) is contained inside the entanglement wedge of AB and D. So, the bulk operator \(\phi\) must have representations on ABD, BCE, CDA, DEB, EAC. In summary, we have the following:
The bulk operator must have representations on R if and only if R contains three or more qubits.
This is the property I want my toy model to possess.

What kinds of physical systems have such a property? Luckily, we quantum information theorists know the answer; the five-qubit code. The five-qubit code, proposed here and here, has an ability to encode one logical qubit into five-qubit entangled states and corrects any single qubit error. We can view the five-qubit code as a quantum encoding isometry from one-qubit states to five-qubit states:\[

\alpha | 0 \rangle + \beta | 1 \rangle \rightarrow \alpha | \tilde{0} \rangle + \beta | \tilde{1} \rangle

\] where \(| \tilde{0} \rangle\) and \(| \tilde{1} \rangle\) are the basis for a logical qubit. In quantum coding theory, logical Pauli operators \(\bar{X}\) and \(\bar{Z}\) are Pauli operators which act like Pauli X (bit flip) and Z (phase flip) on a logical qubit spanned by \(| \tilde{0} \rangle\) and \(| \tilde{1} \rangle\). In the five-qubit code, for any set of qubits R with volume 3, some representations of logical Pauli X and Z operators, \(\bar{X}_{R}\) and \(\bar{Z}_{R}\), can be found on R. While \(\bar{X}_{R}\) and \(\bar{X}_{R'}\) are different operators for \(R \not= R'\), they act exactly in the same manner on the codeword subspace spanned by \(| \tilde{0} \rangle\) and \(| \tilde{1} \rangle\). This is exactly the property I was looking for.

Holographic quantum error-correcting codes

We just found possibly the smallest toy model of the AdS/CFT correspondence, the five-qubit code! The remaining task is to construct a larger model. For this goal, we view the encoding isometry of the five-qubit code as a six-leg tensor. The holographic quantum code is a network of such six-leg tensors covering a hyperbolic space where each tensor has one open leg. These open legs on the bulk are interpreted as logical input legs of a quantum error-correcting code while open legs on the boundary are identified as outputs where quantum information is encoded. Then the entire tensor network can be viewed as an encoding isometry.

The six-leg tensor has some nice properties. Imagine we inject some Pauli operator into one of six legs in the tensor. Then, for any given choice of three legs, there always exists a Pauli operator acting on them which counteracts the effect of the injection. An example is shown below:

In other words, if an operator is injected from one tensor leg, one can “push” it into other three tensor legs.

Finally, let’s demonstrate causal wedge reconstruction of bulk logical operators. Pick an arbitrary open tensor leg in the bulk and inject some Pauli operator into it. We can “push” it into three tensor legs, which are then injected into neighboring tensors. By repeatedly pushing operators to the boundary in the network, we eventually have some representation of the operator living on a piece of boundary region A. And the bulk operator is contained inside the causal wedge of A. (Here, the length of the curve can be defined as the number of tensor legs cut by the curve). You can also push operators into the boundary by choosing different tensor legs which lead to different representations of a logical operator. You can even have a rather exotic representation which is supported non-locally over two disjoint pieces of the boundary, realizing entanglement wedge reconstruction.

Causal wedge and entanglement wedge reconstruction.

What’s next?

This post is already pretty long and I need to wrap it up…

Shor’s quantum factoring algorithm is a revolutionary invention which opened a whole new research avenue of quantum information science. It is often forgotten, but the first quantum error-correcting code is another important invention by Peter Shor (and independently by Andrew Steane) which enabled a proof that the quantum computation can be performed fault-tolerantly. The theory of quantum error-correcting codes has found interesting applications in studies of condensed matter physics, such as topological phases of matter. Perhaps then, quantum coding theory will also find applications in high energy physics.

Indeed, many interesting open problems are awaiting us. Is entanglement wedge reconstruction a generic feature of tensor networks? How do we describe black holes by quantum error-correcting codes? Can we build a fast scrambler by tensor networks? Is entanglement a wormhole (or maybe a perfect tensor)? Can we resolve the firewall paradox by holographic quantum codes? Can the physics of quantum gravity be described by tensor networks? Or can the theory of quantum gravity provide us with novel constructions of quantum codes?

I feel that now is the time for quantum information scientists to jump into the research of black holes. We don’t know if we will be burned by a firewall or not..., but it is worth trying.

1. Whether entanglement wedge reconstruction is possible in the AdS/CFT correspondence or not still remains controversial. In the spirit of the Ryu-Takayanagi formula which relates entanglement entropy to the length of a global geodesic line, entanglement wedge reconstruction seems natural. But that a bulk operator can be reconstructed from boundary operators on two separate pieces A and C non-locally sounds rather exotic. In our paper, we constructed a toy model of tensor networks which allows both causal and entanglement wedge reconstruction in many cases. For details, see our paper.


  1. Dear Beni, thank you for this irresistible sketch of your highly intriguing work.

    The toy model seems to be very elegant and you have described some of the questions about going beyond the toy model. They're very important. I would also love to understand some questions about the toy model itself - e.g. whether one may imagine that this simple five-qubit boundary CFT with a one-qubit bulk is a "compactification of string/M-theory" of some sort, whether we may describe it using some more standard descriptions that string theorists know, like some almost empty/topological CFT, or something like that.

    When you write about the boundary CFT formulae being "integrals", I think it's a bit oversimplified. You mean some general "functionals". But I guess that the realistic ones are not strictly speaking "integrals of local quantities". They may be more similar to the Wilson lines, which are path-ordered exponentials of integrals, and so on.

    At any rate, I hope that people in the information puzzle subfield of string theory will think about this elegant construction carefully.

  2. Besides the fact that it is not the philosophy of this guy that a toy model should be simple and capturing important features but it is the meaning of the toy model itself, I am now confuse by one point. The ads/cft correspondence is a very much celebrated result, verified in many contexts. Now there is this paradox mentioned at the beginning which needs to be fixed eg by this quantum information trick. Is this paradox fundamental? Is it really plaguing the validity of the ads/cft conjecture? Do we really need to solve it for keeping the conjecture valid?

  3. Second question: quantum correcting codes. It looks like for having such a code, I have to map 1 qb into 5. Would this mean that a quantum computer with error correction must have five times more qbits than the minimum amount needed for the computation I want to perform? This might push even farer in the future an useful implementation of a quantum computer of some kind (leaving out dwave-like stochastic approaches). Is this right ro not?

  4. I would agree that the "conditions" expected from a "toy model" are uncontroversial to the extent of being tautologically true. ;-)

    The firewall paradox disappears - it becomes impossible to prove the paradoxical conclusion - once one accepts sufficiently general relationships between the degrees of freedom, such as those in this toy model.

    The bulk locality paradox only exists if one is naive about the degrees of freedom, too, and this very construction - toy model - is an explicit example showing that the paradox isn't there and the bulk operators don't have to be equal to the identity operator.

    B.Y. will hopefully correct me if the comments above are incorrect.

  5. For a single-error quantum error correction, 5 physical qubits per 1 logical qubit is indeed the provable lower bound - the older ways used 7 or 9 physical qubits.

    A factor of five in the number of (quantum or otherwise) bits etc. isn't such a radical technological advance.

  6. Dear Lubos, it is off topic, but why dont you comment on passing of US army convoy through Czech republic and on the fact, that more than 95% people were very supportive about this all through the country? And I would like to also hear your comment about fact, that your so unbiased Russian press agencies commented it that there very massive demonstrations AGAINST this convoy (which is clearly a lie, considering there were about ten people against the convoy versus thousands of people that supported it on EVERY occasion where the convoy rode) and that people were trying to stop it (when only ONE person in whole country tried to do that).

  7. "model of the AdS/CFT correspondence" 2-D CFT is chiral, arXiv:1107.2917


    Elevating to spacetime AdS/CFT treatment magically vanishes mirror-asymmetry that observably exists. Rigorous derivation from defective postulates affords elegant, empirically defective models. Science asks reality what it is. Religion tells it. No matter how tall and massive its temples, no matter how many levels of Heaven and Hell it postulates, religion does not empirically work. Look, then model.

  8. You write lucidly well, always a good sign.

  9. I am very surprised
    to observe a resemblance of those wedge based Quantum codes with my 3
    Dimensional series of fermions and photons. See http://vixra.org/pdf/1103.0002v4.pdf
    and below:

  10. http://blogs.formulatv.com/amsdo/watch-fast-and-furious-7-online-2015-free-putlocker/

  11. "We just found possibly the smallest toy model of the AdS/CFT correspondence, the five-qubit code!" Are string theorists doomed to work with toy models and fail to explain dark matter so long as they fail to understand that MOND is empirically valid? Google "witten milgrom" for more information.

  12. A short answer to the question is that the five-to-one code is optimal to correct a single qubit error. This result is a special case of the so-called quantum singleton bound.

    But more generally, we can think of "n-to-k" encoding. And one of ultimate goals in quantum coding theory is to come up with a "practical" scheme with large k/n. By practical, I mean that you can efficiently encode, read and error-correct.

    Our construction of holographic codes can be generalized, and it would be wonderful if we can eventually create some good quantum error-correcting codes by holographic constructions. Certainly an important future question.

  13. Certainly, it will give some insights on interesting open questions. For instance, I imagine that people who support the firewall scenario would disagree with the entanglement wedge reconstruction scenario because the entanglement wedge may possibly extend over the singularity. So, this may be a small step to resolving the firewall paradox? (To be clear, I’m not supporting either side on the firewall debate at this moment). This is just one example, and I think that there will be many other applications.

  14. Dear Dr Yoshida, it's interesting that you say that the firewall supporters dislike the wedge reconstruction.

    At least 3/4 of the authors behind the AMPS firewall paper, namely MPS, with an H co-author, referred to the Hamilton et al. paper [7] about the wedge reconstruction approvingly half a year before they published the firewall paper


    Your observation that it is an inconsistent attitude due to the singularity in the wedge is interesting.

  15. This resonates in me with how renormalization came to the rescue (except way beyond what enabled the standard model).

  16. Hiya, Lattice/Tensor-Network approaches are one of the areas I know the least about in all of this, but I have a, (hopefully appropriate) comment and a (possibly dumb) question anyway.

    If I understand correctly the approach here is somewhat similar to/inspired by the MERA tensor approach to ADS/CFT that for example Malcedena is outlining here?


    I was very intrigued by your remarks that we here also seem to find evidence for a compromise situation under the duality between there being an exact 1-1 correspondence between the physics of the CFT and that of the bulk thoery as Susskind was initially expecting, (so that the bulk is in some sense merely a redundant projection of the CFT), and a fully fledged local bulk theory, (which seemed to be Polchinski's preference, at least a while ago).

    Recently we were discussing the state dependent map in PR where in the thermofield-double eternal black hole case, (and I guess more generally as well), physically distinct bulk microstates can be found that map to states in the CFT(s) that are related by purely by a gauge transformation.

    What they found there is also strong evidence that's points clearly to the half-way house situation you describe between a trivial bulk extension and a fully-fledged local bulk theory isn't it?

    So I'm naively wondering if there might even be a direct analogue of this PR consideration in the tensor-network approach.

    Is it possible that pushing a certain product of Pauli Z-bar phase-flip operations on a suitable collection of uncontracted bounary-tensor legs into the bulk can result in a Pauli X bit-flip on one or more of the uncontracted bulk legs?

    In other words, is it possible to change the "shared secret" (bulk microstate) on one or more bulk legs by boundary phase operations alone?

    Well, the boundary tensor legs in this model don't give a dynamical description of an actual fully-fledged lattice gauge-theory anyway, so boundary phase-flips are of course not properly speaking gauge transformations.

    So perhaps it's nonsensical of me to try to make such a direct an analogy here. Sorry if it's a dumb question!!

    I can follow the outlines in these issues reasonably well, but I certainly don't have graduate-level familiarity with all the detailed mathematical machinery involved etc.

  17. Alternate version #1: Same as the original, except SB is wakened both days. She will be led into a red room to be asked for her credence unless it is Tuesday, after Heads. In that case, she will be led into a blue room. She knows these details.

    While waiting to be led into a room, she writes down these probabilities ("R" and "B" mean the color room she will see): P(R)=3/4, P(B)=1/4, P(H)=P(T)=1/2, P(R|H)=1/2, and P(R|T)=1.

    She also knows Bayes Rule:
    P(H|R) = P(R|H)*P(H)/[P(R|H)*P(H)+P(R|T)*P(T)]

    Substituting in known values:
    P(H|R) = (1/2)*(1/2)/[(1/2)*(1/2)+(1/2)*(1)] = 1/3.

    And obviously (or similarly), P(H|B)=1.

    Alternate version #2: Instead of room colors, SB is told that on Tuesday, after heads, she will be told that it is that case before being asked fro her credence. She can again deduce P(H|Not Told)=1/3 and P(T|Told)=1.

    My question for Lubos is, what is different about her information in the original version, than in either of these two? Lubos seems to be confusing "I know it is not Tuesday, after Heads" with "Tuesday, after Heads did not, and can not, happen." This is incorrect. In the original version, SB does receive new information: that it is not Tuesday, after Heads. This information works the same way in all three problems. The correct answer is 1/3.

    It seems natural to treat "trials" as the time variable in these probabilities; that is, the frequentist definition of Probability=Occurrences/Trials. But the use the amnesia drug makes the correct time variable "Observations."