12.1 Protecting the computational Hilbert space
In Section 3.4, Part I, we alluded to “clever error correcting algorithms encoded in software for certain situations exist.” We provide a glimpse of it now.
At one time it appeared the no-cloning theorem and the general impossibility of measuring the exact state of an unknown qubit would make error correction by algorithmic means impossible. In 1995, Peter Shor showed that for a certain class of errors (that also appear in classical computers) it is possible to restore a quantum state using only partial state information.2 Since then several error-correction codes have been devised. They have some similarities with, and some striking differences from classical error-correcting codes. Indeed, classical ideas have seeded the emergence of quantum error-correction codes. A salient feature of these codes is that the original state is recovered by a skillful measurement followed by a unitary operation determined by the measured outcome.
At the algorithmic (logical) level, a qubit is a two-dimensional subspace of a higher dimensional system. At a physical level, qubits are chosen such that it is possible to detect and correct unwanted changes in their state. Programmed manipulation of the information encoded in the qubits generally requires arbitrary and precise control over the entire computing system. Since individual elements in physical devices will always have residual interactions, these must be accounted for when designing logical operations.3 Our intention here is to provide a glimpse of the central ideas that led to the development of error correction algorithms which eventually strengthened our belief that practical quantum computers can be built without waiting for certain hardware limitations to be resolved by advancing hardware technology.4
Since straightforward replication of qubits in an unknown state |ψ〉 is not possible due to the no-cloning theorem, i.e., we cannot perform such operations as |ψ〉 →|ψ〉 ⊗ |ψ〉 ⊗ |ψ〉,5 entanglement is used to spread the information held by designated qubits over multiple qubits through an encoding. This encoding is such that under evolution by a suitable operator the appropriate qubits will recover their original state. In short, we fight entanglement with entanglement. Entanglement has no classical analog. It encodes information in the correlations among the qubits in a given Hilbert space and this space explodes exponentially with the number of qubits.
Quantum information science explores, not the frontier of short distances as in particle physics, or of long distances as in cosmology, but rather the frontier of highly complex quantum states, the entanglement frontier.6
The simplest error conditions (e.g., bit flip, phase flip and their combination) assume that each qubit interacts with the environment independent of any other. This lets interaction operators to be tensor products of one-qubit interaction operators. Immediately Pauli matrices (or operators) become relevant because they span the space of 2 × 2 matrices, and the n-qubit Pauli group Pn (i.e., the group generated by tensor products of the four Pauli operators) spans the space of 2n × 2n matrices.
3For some recent advances, see Heeres, et al (2017).
4See, e.g., Preskill (2012).
5In classical computing, 0 → 000 and 1 → 111 is no big deal.