Glossary

Bit.

The basic unit of deterministic information. It is a system that can be in one of two possible states, $\mathfrak{0}$ and $\mathfrak{1}$.

Bit string.

A sequence of $\mathfrak{0}$'s and $\mathfrak{1}$'s that represents a state of a sequence of bits. Bit strings are words in the binary alphabet.

Classical information.

The type of information based on bits and bit strings and more generally on words formed from finite alphabets. This is the information used for communication between people. Classical information can refer to deterministic or probabilistic information, depending on the context.

Code.

A set of states that can be used to represent information. The set of states needs to have the properties of the type of information to be represented. The code is usually a subset of the states of a given system $\mathsf {Q}$. It is then a $\mathsf {Q}$-code or a code on $\mathsf {Q}$. If information is represented by a state in the code, $\mathsf {Q}$ is said to carry the information.

Code word.

A state in a code. The term is primarily used for classical codes defined on bits or systems with non-binary alphabets.

Concatenation.

An iterative procedure in which higher-level logical information units are implemented in terms of lower-level units.

Control error.

An error due to non-ideal control in applying operations or gates.

Communication channel.

A means for transmitting information from one place to another. It can be associated with a physical system in which the information to be transmitted is stored by the sender. The system is subsequently conveyed to the receiver, who can then make use of the information.

Correctable error set.

For a given code, a set of errors such that there exists an implementable procedure $R$ that, after any one of these errors ${\color{red}E}$ acts on a state $x$ in the code, returns the system to the state: $x=R{\color{red}E}x$. What procedures are implementable depends on the type of information represented by the system and, if it is a physical system, its physics.

Decoding.

The process of transferring information from an encoded form to its ``natural'' form. In the context of error correction, decoding is often thought of as consisting of two steps, one which removes the errors' effects (sometimes called the recovery procedure) and one that extracts the information (often also called decoding, in a narrower sense).

Depolarizing errors.

An error model for qubits in which random Pauli operators are applied independently to each qubit.

Detectable error.

For a given code, an error that has no effect on an initial state in the code if an observation determines that the state is still in the code. If the state is no longer in the code, the error is said to have been detected and the state no longer represents valid information.

Deterministic information.

The type of information based on bits and bit strings. This is the same as classical information but explicitly excludes probabilistic information.

Encoding.

The process of transferring information from its ``natural'' form to an encoded form. It requires an identification of the valid states associated with the information and the states of a code. The process acts on an information unit and replaces it with the system whose state space contains the code.

Environment.

In the context of information encoded in a physical system, it refers to other physical systems that may interact with the information-carrying system.

Environmental noise.

Noise due to unwanted interactions with the environment.

Error.

Any unintended effect on the state of a system, particularly in storing or otherwise processing information.

Error basis.

A set of state transformations that can be used to represent any error. For quantum systems, errors can be represented as operators acting on the system's state space, and an error basis is a maximal, linearly independent set of such operators.

Error control.

The term for general procedures that limit the effects of errors on information represented in noisy, physical systems.

Error correction.

The process of removing the effects of errors on encoded information.

Error-correcting code.

A code with additional properties that enable a decoding procedure to remove the effects of the dominant sources of errors on encoded information. Any code is error-correcting for some error-model in this sense. To call a code ``error-correcting'' emphasizes the fact that it was designed for this purpose.

Error model.

An explicit description of how and when errors happen in a given system. Typically, a model is specified as a probability distribution over error operators. More general models may need to be considered, particularly in the context of fault tolerant computation, for which correlations in time are important.

Fault tolerance.

A property of encoded information that is being processed with gates. It means that errors occurring during processing, including control errors and environmental noise, do not seriously affect the information of interest.

Gate.

An operation applied to information for the purpose of information processing.

Hamming distance.

The Hamming distance between two binary words (sequences of $\mathfrak{0}$ and $\mathfrak{1}$) is the number of positions in which the two words disagree.

Hilbert space.

A $n$-dimensional Hilbert space consists of all complex $n$-dimensional vectors. A defining operation in a Hilbert space is the inner product. If the vectors are thought of as column vectors, then the inner product $\langle x,y\rangle$ of $x$ and $y$ is obtained by forming the conjugate transpose $x^\dagger$ of $x$ and calculating $\langle x,y\rangle=x^\dagger y$. The inner product induces the usual norm $\vert x\vert^2 = \langle x,x\rangle$.

Information.

Something that can be recorded, communicated and computed with. Information is fungible, which implies that its meaning can be identified regardless of the particulars of the physical realization. Thus, information in one realization (such as ink on a sheet of paper) can be easily transferred to another (for example, spoken words). Types of information include deterministic, probabilistic and quantum information. Each type is characterized by information units, which are abstract systems whose states represent the simplest information of this type. These define the ``natural'' representation of the information. For deterministic information the unit is the bit, whose states are symbolized by $\mathfrak{0}$ and $\mathfrak{1}$. Information units can be put together to form larger systems and can be processed with basic operations acting on a small number of units at a time.

Length.

For codes on $n$ basic information units, the length of the code is $n$.

Minimum distance.

The smallest number of errors that is not detectable by a code. In this context, the error model consists of a set of error operators without specified probabilities. Typically the concept is used for codes on $n$ information units and the error model consists of operators acting on any one of the units. For a classical binary code, the minimum distance is the smallest Hamming distance between two code words.

Noise.

Any unintended effect on the state of a system, particularly an effect with a stochastic component due to incomplete isolation of the system from its environment.

Operator.

A function transforming the states of a system. Operators may be restricted depending on the system's properties. For example, operators acting on quantum systems are always assumed to be linear.

Pauli operators.

The Hermitian matrices $\sigma_x,\sigma_y$ and $\sigma_z$ (Eq. 9) acting on qubits. It is often convenient to consider the identity operator to be included in the set of Pauli operators.

Physical system.

A system explicitly associated with a physical device or particle. The term is used to distinguish between abstract systems used to define a type of information and specific realizations, which are subject to environmental noise and errors due to other imperfections.

Probabilistic bit.

The basic unit of probabilistic information. It is a system whose state space consists of all probability distributions over the two states of a bit. The states can be thought of as describing the outcome of a biased coin flip before the coin is flipped.

Probabilistic information.

The type of information obtained when the state spaces of deterministic information are extended with arbitrary probability distributions over the deterministic states. This is the main type of classical information to which quantum information is compared.

Quantum information.

The type of information obtained when the state space of deterministic information is extended with arbitrary superpositions of deterministic states. Formally, each deterministic state is identified with one of an orthonormal basis vector in a Hilbert space and superpositions are unit-length vectors that are expressible as complex linear sums of the chosen basis vectors. Ultimately it is convenient to extend this state space again by permitting probability distributions over the quantum states. This is still called quantum information.

Qubit.

The basic unit of quantum information. It is the quantum extension of the deterministic bit; that is, its state space consists of the unit-length vectors in a two dimensional Hilbert space.

Repetition code.

The classical, binary repetition code of length $n$ consists of the two words $\mathfrak{0}\mathfrak{0}\ldots\mathfrak{0}$ and $\mathfrak{1}\mathfrak{1}\ldots\mathfrak{1}$. For quantum variants of this code one applies the superposition principle to obtain the states consisting of all unit-length complex linear combinations of the two classical code words.

Scalability.

A property of physical implementations of information processing that implies that there are no bounds on accurate information processing. That is, arbitrarily many information units can be realized and they can be manipulated for an arbitrarily long amount of time without loss of accuracy. Furthermore, the realization is polynomially efficient in terms of the number of information units and gates used.

States.

The set of states for a system characterizes the system's behavior and possible configurations.

Subspace.

For a Hilbert space, a subspace is a linearly closed subset of the vector space. The term can be used more generally for a system $\mathsf {Q}$ of any information type: A subspace of $\mathsf {Q}$ or, more specifically, of the state space of $\mathsf {Q}$ is a subset of the state space that preserves the properties of the information type represented by $\mathsf {Q}$.

Subsystem.

A typical example of a subsystem is the first (qu)bit in a system consisting of two (qu)bits. In general, to obtain a subsystem of system $\mathsf {Q}$, one first selects a subset $C$ of $\mathsf {Q}$'s state space and then identifies $C$ as the state space of a pair of systems. Each member of the pair is then a subsystem of $\mathsf {Q}$. Restrictions apply depending on the types of information carried by the system and subsystems. For example, if $\mathsf {Q}$ is quantum and so are the subsystems, then $C$ has to be a linear subspace and the identification of the subsystems' state space with $C$ has to be unitary.

Subsystem identification.

The mapping or transformation that identifies the state space of two systems with a subset $C$ of states of a system $\mathsf {Q}$. In saying that $\mathsf {L}$ is a subsystem of $\mathsf {Q}$, we also introduce a second subsystem $\mathsf {S}$ and identify the state space of the combined system $\mathsf {LS}$ with $C$.

Syndrome.

One of the states of a syndrome subsystem. It is often used more narrowly for one of a distinguished set of basis states of a syndrome subsystem.

Syndrome subsystem.

In identifying an information-carrying subsystem in the context of error-correction, the other member of the pair of subsystems required for the subsystem identification is called the syndrome subsystem. The terminology comes from classical error-correction, in which the syndrome is used to determine the most likely error that has happened.

System.

An entity that can be in any of a specified number of states. An example is a desktop computer whose states are determined by the contents of its various memories and disks. Another example is a qubit, which can be thought of as a particle whose state space is identified with complex, two-dimensional, length-one vectors. Here, a system is always associated with a type of information, which in turn determines the properties of the state space. For example, for quantum information the state space is a Hilbert space. For deterministic information, it is a finite set called an alphabet.

Twirling.

A randomization method for ensuring that errors act like a depolarizing error model. For one qubit, it involves applying a random Pauli operator before the errors occur and then undoing the operator by applying its inverse.

Unitary operator.

A linear operator $U$ on a Hilbert space that preserves the inner product. That is, for all $x$ and $y$, $\langle Ux,Uy\rangle=\langle x,y\rangle$. If $U$ is given in matrix form, then this condition is equivalent to $U^\dagger U = {\mathchoice {\rm 1\mskip-4mu l} {\rm 1\mskip-4mu l} {\rm 1\mskip-4.5mu l} {\rm 1\mskip-5mu l}}$.

Weight.

For a binary word, the weight is the number of $\mathfrak{1}$'s in the word. For an error operator acting on $n$ systems by applying an operator to each one of them, the weight is the number of non-identity operators applied.