How does quantum entanglement enable error correction without violating the no-cloning theorem?

TL;DR: There are many ways of thinking intuitively about classical error correction. We can think of it as a form of data duplication. We can also think of it as the imposition of constraints to curve out a subset of states for the purpose of information encoding. The former is a wrong way of thinking about error correction that, unsurprisingly, leads to the wrong conclusion about the feasibility of quantum error correction. By contrast, the latter provides a natural route to understanding how quantum error correction works.

Wrong way of thinking about classical error correction

On the intuitive level one can think of redundant encoding of classical information realized in classical error correction as exploiting data duplication. This view suggests that quantum error correction should be impossible. However, this turns out to be a weakness of that particular way of looking at error correction.

Better way of thinking about classical error correction

A better way is to regard redundant encoding of classical information as relying on the introduction of constraints, often referred to as checks. A check is a constraint on the set of states of a physical system. States that satisfy all checks are considered valid and are used to represent encoded information. States that fail one or more checks are considered invalid and do not represent any information. Instead, the invalid states are meant to form "buffers" around valid states that absorb errors. The set of violated constraints is the syndrome which, for good codes and sufficiently small error rates, enables one to diagnose errors, i.e. to infer which valid state had been originally encoded.

The constraints inevitably lead to classical correlations in the encoded states.

Examples

Consider a parity bit added to the eight bits of data in an RS-232 link. The extra bit is not really a copy of any of the eight data bits. It is better to think of this situation as involving a constraint that selects an 8-dimensional linear subspace from the 9-dimensional linear space of bit strings.

Consider a credit card number with a check digit appended. The extra digit is not really a copy of any particular digit. Once again, it is better to imagine that we employ a constraint to curve out a subset of valid strings of digits from a large set of all strings of digits of a particular length.

Extension to quantum information

This way of thinking about redundant encoding of information extends naturally to quantum mechanics. Each check is a pair consisting of a quantum observable and an expected eigenvalue. Jointly, all the checks of a quantum error correcting code select a subspace of a quantum processor's Hilbert space. Quantum states within the subspace are considered valid and are used to represent quantum information. Quantum states outside the subspace are considered invalid and don't represent encoded quantum information. Instead, they form a "buffer" that can absorb errors. Measurement outcomes of observables associated with the checks are the syndrome which, for good codes and sufficiently small error rates, enables one to diagnose errors.

Similarly to the classical setting, the constraints inevitably lead to quantum correlations, i.e. entanglement, in the encoded states.