What is quantum entanglement, and what role does it play in quantum error correction?

Question

I want to understand what quantum entanglement is and what role does it play in quantum error correction.

NOTE: As per the suggestions of @JamesWootton and @NielDeBeaudrap, I have asked a separate question for the classical analogy here.

Answer 1

Classical correlations between variables occur when the variables appear random, but whose values are found to systematically agree (or disagree) in some way. However, there will always be someone (or something) that 'knows' exactly what the variables are doing in any given case.

Entanglement between variables is the same, except for the last part. The randomness is truly random. Random outcomes are completely undecided until the time of measurement. But somehow the variables, though they may be separated by galaxies, still know to agree.

---

So what does this mean for error correction? Let's start by thinking about error correction for a simple bit.

When storing a classical bit, the kinds of errors you need to worry about are things like bit flips and erasures. So something might make your 0 become a 1, or vice-versa. Or your bit might wander off somewhere.

To protect the information, we can ensure that our logical bits (the actual information we want to store) are not just concentrated on single physical bits. Instead, we spread it out. So we could use a simple repetition encoding, for example, where we copy our information across many physical bits. This lets us still get our information out, even if some of the physical bits have failed.

This is the basic job of error correction: we spread our information out, to make it hard for errors to mess it up.

For qubits, there are more kinds of error to worry about. For example, you may know that qubits can be in superposition states, and that measurements change these. Unwanted measurements are therefore another source of noise, caused by the environment interacting with (and so in some sense 'looking at' our qubits). This type of noise is known as decoherence.

So how does this affect things? Suppose we use the repetition encoding with qubits. So we replace the $|0\rangle$ in our desired logical qubit state with $|000...000\rangle$, repeated across many physical qubits, and replace the $|1\rangle$ with $|111...111\rangle$. This again protects against bit flips and erasures, but it makes it even easier for stray measurements. Now the environment measure whether we have $|0\rangle$ or $|1\rangle$ by looking at any of many qubits. This will make the effect of decoherence much stronger, which is not what we wanted at all!

To fix this, we need to make it hard for decoherence to disturb our logical qubit information, just as we made it hard for bit flips and erasures. To to this, we have to make it harder to measure our logical qubit. Not too hard that we can't do it whenever we want to, of course, but too hard for environment to do easily. This means ensuring that measuring a single physical qubit should tell us nothing about the logical qubit. In fact, we must make it so that a whole bunch of qubits need to be measured and their results compared to extract any information about the qubit. In some sense, it is a form of encryption. You need enough pieces of the puzzle to have any idea what the picture is.

We could try to do this classically. Information could be spread out in complex correlations among many bits. By looking at enough of the bits and analyzing the correlations, we can we extract some information about the logical bit.

But this would not be the only way to get this information. As I mentioned before, classically there is always that someone or something that already knows everything. It doesn't matter whether it is a person, or just the patterns in the air caused when the encryption was carried out. Either way, the information exists outside of our encoding, and this is essentially an environment that knows everything. Its very existence means that decoherence has occurred to an irreparable degree.

So that's why we need entanglement. With it, we can hide the information away using correlations in the true and unknowable random outcomes of quantum variables.

Answer 2

For a certain class of codes called pure, the presence of entanglement is a necessary and sufficient requirement for quantum error correction, i.e. to correct all errors affecting up to a certain number of subsystems.

Recall the Knill-Laflamme conditions for a quantum error correcting code to be able to detect a certain set of errors $\{E_\alpha\}$: pick any orthonormal basis $|i_\mathcal{Q}\rangle$ that spans the code-space. Then the error $E_\alpha$ can be detected if and only if

\begin{equation} \langle i_\mathcal{Q} | E_\alpha | j_\mathcal{Q} \rangle = \delta_{ij} C(E_\alpha). \quad\quad\quad (1) \end{equation}

Note that $C(E_\alpha)$ is a constant that only depends on the specific error $E_\alpha$, but not on $i$ and $j$. (This means that the error $E_\alpha$ affects all states in the code subspace in the same way). In the case of $C(E_\alpha) \propto \operatorname{tr}(E_\alpha)$, the code if called pure. Many stabilizer codes considered are of this form, not however Kitaev's toric code.

Let us assume an error-model where we are only interested in on how many subsystems our errors act. If our code can detect all errors $E_\alpha$ that act on at most $(d-1)$ subsystems nontrivially, the code is said to have distance $d$. As a consequence, any combination of errors that affect up to $\lfloor(d-1)/2\rfloor$ subsystems can be corrected.

What follows is that for pure codes of distance $d$, every vector lying in the code subspace must be maximally entangled across any bipartition whose smaller subsystem has at most size $(d-1)$: to see this, note that for every error $E_\alpha \neq \mathbb{1}$ and vector $|v_\mathcal{Q} \rangle$ in the subspace (our ONB was chosen arbitrary), one has that

\begin{equation} \langle E \rangle = \operatorname{tr}(E |v_\mathcal{Q} \rangle\langle v_\mathcal{Q}|) = \langle v_\mathcal{Q} |E_\alpha|v_\mathcal{Q} \rangle = \operatorname{tr}(E) = 0. \end{equation}

Thus all observables on at most $(d-1)$ parties are vanishing, and all reduced density matrices on $(d-1)$ parties must be maximally mixed. This implies that $|v_\mathcal{Q}\rangle$ is maximally entangled for any choice of $(d-1)$ parties vs. the rest.

Addendum (for the sufficiency): As an equivalent definition to Eq. (1): All errors $E_\alpha$ acting on less than $d$ places can be detected, if and only if for all $|v\rangle, |w\rangle$ in the code subspace following condition holds,

\begin{equation} \langle v| E_\alpha | v\rangle = \langle w | E_\alpha| w\rangle. \end{equation}

In the case of pure codes, above expression vanishes. It follows that if one has a subspace where every state is maximally entangled for all bipartitions of (d-1) parties vs. the rest, then it is a pure code of distance $d$.

tl;dr: For a large distance $d$, a pure code consists of highly entangled states. It is a necessary and sufficient requirement for the existence of the code.

Addendum: we looked into this question further, details can be found in the paper Quantum Codes of Maximal Distance and Highly Entangled Subspaces. There is a trade-off: the more errors a quantum code can correct, the more entangled must every vector in the code space be. This makes sense, because if the information where not distributed amongst many particles, the environment - by reading a few qubits - could recover the message in the code space. This would then necessarily destroy the coded message, due to the no-cloning theorem. Thus a high distance needs high entanglement.

Answer 3

Entanglement is a natural part of quantum information and quantum computation. If it isn't present --- if you try to do things in such a way that entanglement does not arise --- then you get no benefit from quantum computation. And if a quantum computer is doing something interesting, it will produce a lot of entanglement, at least as a side-effect.

However, this does not mean that entanglement is "what makes quantum computers go". Entanglement is like the spinning gears of a machine: nothing happens if they aren't turning, but that doesn't mean that having those gears spin quickly is enough to make the machine do what you want. (Entanglement is a primitive resource in this way for communication, but not for computation as far as anyone has seen.)

This is as true for quantum error correction as it is for computation. Like all forms of error correction, quantum error correction works by distributing information around a larger system, in particular in the correlations of certain measurable pieces of information. Entanglement is just the usual way in which quantum systems become correlated, so it should come as no surprise that a good quantum error correction code then involves a lot of entanglement. But that doesn't mean that trying to "pump your system full of entanglement", like some sort of helium balloon, is something which is useful or meaningful to do to protect quantum information.

While quantum error correction is sometimes described vaguely in terms of entanglement, more important is how it involves parity checks using different 'observables'. The most important tool for describing this is the stabiliser formalism. The stabiliser formalism can be used to describe some states with large amounts of entanglement, but more importantly it allows you to reason about multi-qubit properties ("observables") fairly easily. From that perspective, one can come to understand that quantum error correction is much more closely related to low-energy many-body physics of spin-Hamiltonians, than just entanglement in general.

Answer 4

There is no classical equivalent to entanglement. Entanglement is perhaps best understood using Dirac (bra-ket) notation.

Each qubit can be in the (ket) state $\left|0\right>$ or in the state $\left|1\right>$ or in a superposition $\alpha\left|0\right> + \beta \left|1\right>$ where $\alpha$ and $\beta$ are complex numbers that fulfill $|\alpha|^2 + |\beta|^2 = 1$. If you have two qubits, the basis states of the 2-qubit system are $\left|0\right> \otimes \left|0\right>$, $\left|0\right> \otimes \left|1\right>$, $\left|1\right> \otimes \left|0\right>$, and $\left|1\right> \otimes \left|1\right>$. To simplify the notation, physicists often write these as $\left|00\right>$, $\left|01\right>$, $\left|10\right>$, and $\left|11\right>$. So being in state $\left|01\right>$ means that the first qubit is in state $\left|0\right>$ and the second qubit is in state $\left|1\right>$.

Now consider a superposition of the kind $\alpha \left|01\right> + \beta \left|10\right>$. This means that the first qubit is in state $\left|0\right>$ with probability $|\alpha|^2$ and in state $\left|1\right>$ otherwise, whilst the second qubit is always in the opposite state that the first one is in: The two particles are entangled.

It is unimportant that in this example, the entangled qubits happen to be in opposite states: They might as well be in the same state and still be entangled. What matters is that their states are not independent from each other. This has caused major headaches for physicists because it means that qubits (or the particles carrying them) cannot simultaneously have strictly local properties and be governed by a concept called realism (reflect their states as intrinsic property). Einstein famously called the resulting paradox (if you still assume locaility and realism) "spooky action at a distance."

Entanglement does not play a special role in quantum error correction: Error correction must work for every state in the computational basis (which does not have entanglement). Then it automatically works also for superpositions of these states (which may be entangled states).

Answer 5

Here is a way to think about the role of entanglement in quantum codes which I think is complementary to Felix Hubers response.

Suppose that we take a maximally entangled state $|\Psi\rangle_{RQ}$ and record the $Q$ system into some quantum error-correcting code. Suppose the code records $Q$ into subsystems $S_1,S_2,S_3$ such that erasure of any one subsystem can be corrected for (I've taken a simple example, but generalizations are possible).

Then, there is an entropic way of thinking about the error correction conditions (as compared to the more algebraic Knill-Laflamme conditions). Specifically, if

$$I(R:S_3) = 0$$

Then it follows that $Q$ can be recovered from $S_1S_2$. See for example arXiv:quant-ph/0112106 for a nice presentation of this fact.

Using this entropic approach to error correction there are fairly direct routes to understanding entanglement in codes. For instance, we can prove that,

$$I(S_1S_2:S_3) \geq 2\log d_R$$

as follows. First we write out this mutual information in terms of its definition,

$$I(S_1S_2:S_3) = S(S_1S_2) + S(S_3) - S(S_1S_2S_3)$$

We'll introduce a purifying system $X$, so that the state on $RS_1S_2S_3X$ is pure. Then using purity we can write

$$I(S_1S_2:S_3) = S(S_3XR) + S(S_3) - S(XR)$$

Note that since we can recover $Q$ from $S_1S_2$, $I(R:S_3X)=I(R:X)=0$. Using this in the above

$$I(S_1S_2:S_3) = S(S_3|X) + S(S_3)$$

Finally, we can bound the right hand side here below by $2 \log d_R$. The intuition behind how we can do this is that $S_3$ is ``significant'' in the sense that there is a set of shares (say $S_1$) which itself reveals no information about $Q$, but together with $S_3$ allows $Q$ to be recovered. Given this, we expect $S_3$ must carry $2\log d_R$ of entropy, since transferring it can be used to establish $2\log d_R$ worth of entanglement. A similar intuition appears in arXiv:quant-ph/0608223. More precisely we consider the quantity $I(R:S_1S_3) - I(R:S_1)$, which some basic manipulations reveal

$$I(R:S_1S_3) - I(R:S_1) = S(S_3|S_1) + S(S_3|XS_2) \leq S(S_3) + S(S_3|X)$$

But then we notice $I(R:S_1S_3) \geq 2\log d_R$ since $S_1S_3$ allows recovery of $Q$, while $I(R:S_1)=0$ by the entropic error correction condition. This lower bounds $S(S_3) + S(S_3|X)$ and so lower bounds $I(S_1S_2:S_3)$.