Glossary

Algorithm.

A set of instructions to be executed by a computing device. What instructions are available depends on the computing device. Typically, instructions include commands for manipulating the contents of memory and means for repeating blocks of instructions indefinitely or until a desired condition is met.

Amplitude.

A quantum system with a chosen orthonormal basis of ``logical'' states $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{i}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ can be in any superposition $\sum_i\alpha_i\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{i}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ of these states, where $\sum_i\vert\alpha_i\vert^2=1$. In such a superposition, the complex numbers $\alpha_i$ are called the amplitudes. Note that the amplitudes depend on the chosen basis.

Ancillas.

Helper systems used to assist in a computation involving other information systems.

Bell basis.

For two qubits $\mathsf {A}$ and $\mathsf {B}$, the Bell basis consists of the four states ${1\over\sqrt{2}}\left(\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\mat... ...space*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {AB}}}}\right)$ and ${1\over\sqrt{2}}\left(\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\mat... ...space*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {AB}}}}\right)$.

Bell states.

The members of the Bell basis.

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 sequence.

A way of combining bits into a larger system whose constituent bits are in a specific order.

Bit string.

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

Black box.

A computational operation whose implementation is unknown. Typically, a black box implements one of a restricted set of operations, and the goal is to determine which of these operations it implements by using it with different inputs. Each use of the black box is called a ``query''. The smallest number of queries required to determine the operation is called the ``query complexity'' of the restricted set. Determining the query complexity of sets of operations is an important problem area of computational complexity.

Bloch sphere.

The set of pure states of a qubit represented as points on the surface of the unit sphere in three dimensions.

Bra.

A state expression of the form $\mbox{$\langle\hspace*{-4.3pt}\langle\hspace*{-4.3pt}\langle$}{\psi}\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}$, which is considered to be the conjugate transpose of the ket expression $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$.

Bra-ket notation.

A way of denoting states and operators of quantum systems with kets (for example, $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$) and bras (for example, $\mbox{$\langle\hspace*{-4.3pt}\langle\hspace*{-4.3pt}\langle$}{\phi}\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}$).

Circuit.

A combination of gates to be applied to information units in a prescribed order. To draw circuits, one often uses a convention for connecting and depicting gates. See also ``network''.

Circuit complexity.

The circuit complexity of an operation on a fixed number of information units is the smallest number of gates required to implement the operation.

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.

Computation.

The execution of the instructions provided by an algorithm.

Computational states.

See the entry for ``logical states''.

Computer.

A device that processes information.

Density matrix or operator.

A representation of pure and mixed states without redundancy. For a pure state $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$, the corresponding density operator is $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\mbox{$\rangle\hspace... ...ace*{-4.3pt}\langle$}{\psi}\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}$. A general density operator is a probabilistic combination $\sum_i\lambda_i\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi_i}\mbo... ...e*{-4.3pt}\langle$}{\psi_i}\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}$, with $\sum_i\lambda_i=1$.

Deterministic information.

The type of information that is based on bits and bit strings. Deterministic information is classical, but it explicitly excludes probabilistic information.

Distinguishable states.

In quantum mechanics, two states are considered distinguishable if they are orthogonal. In this case, a measurement exists that is guaranteed to determine which of the two states a system is in.

Efficient computation.

A computation is efficient if it requires at most polynomially many resources as a function of input size. For example, if the computation returns the value $f(x)$ on input $x$, where $x$ is a bit string, then it is efficient if there exists a power $k$ such that the number of computational steps used to obtain $f(x)$ is bounded by $\vert x\vert^k$, where $\vert x\vert$ is the length (number of bits) of $x$.

Entanglement.

A non-classical correlation between two quantum systems most strongly exhibited by the maximally entangled states such as the Bell states for two qubits, and considered to be absent in mixtures of product states (which are called ``separable'' states). Often states that are not separable are considered to be entangled. However, nearly separable states do not exhibit all the features of maximally entangled states. As a result, studies of different types of entanglement are an important component of quantum information theory.

Gate.

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

Global phase.

Two quantum states are indistinguishable if they differ only by a global phase. That is, $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ and $e^{i\phi}\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ are in essence the same state. The global phase difference is the factor $e^{i\phi}$. The equivalence of the two states is apparent from the fact that their density matrices are the same.

Hilbert space.

An $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 squared norm $\vert x\vert^2 = \langle x,x\rangle$.

Information.

Something that can be recorded, communicated, and computed with. Information is fungible; that is, 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 each type. The information units define the ``natural'' representation of the information. For deterministic information the information 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 them at a time.

Inner product.

The defining operation of a Hilbert space. In a finite dimensional Hilbert space with a chosen orthonormal basis $\{e_i: 1\leq i\leq n\}$, the inner product of two vectors $x=\sum_i x_i e_i$ and $y=\sum_i y_i e_i$ is given by $\sum_i \overline x_i y_i$. In the standard column representation of the two vectors, this is the number obtained by computing the product of the conjugate transpose of $x$ with $y$. For real vectors, this agrees with the usual ``dot'' product. The inner product of $x$ and $y$ is often written in the form $\langle x, y\rangle$. Pure quantum states are unit vectors in a Hilbert space. If $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\phi}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ and $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ are two quantum states expressed in the ket-bra notation, there inner product is given by $\left(\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\phi}\mbox{$\rangle\... ...3pt}\vert$}{\psi}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$.

Ket.

A state expression of the form $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ representing a quantum state. Usually $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ is thought of as a superposition of members of a logical state basis $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{i}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$. One way to think about the notation is to consider the two symbols `` $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}$'' and `` $\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$'' as delimiters denoting a quantum system and $\psi$ as a symbol representing a state in a standard Hilbert space. The combination $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ is the state of the quantum system associated with $\psi$ in the standard Hilbert space via a fixed isomorphism. In other words, one can think of $\psi\leftrightarrow \mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ as an identification of the quantum system's state space with the standard Hilbert space.

Linear extension of an operator.

The unique linear operator that implements a map defined on a basis. Typically, we define an operator $U$ on a quantum system only on the logical states $U:\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{i}\mbox{$\rangle\hspace*... ...t}\vert$}{\psi_i}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$. The linear extension is defined by $U(\sum_i\alpha_i\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{i}\mbox{$\... ...t}\vert$}{\psi_i}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$.

Logical states.

For quantum systems used in information processing, the logical states are a fixed orthonormal basis of pure states. By convention, the logical basis for qubits consists of $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\mathfrak{0}}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ and $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\mathfrak{1}}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$. For larger dimensional quantum systems, the logical basis is often indexed by the whole numbers, $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{0}\mbox{$\rangle\hspace*{-... ...\vert$}{2}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$},\ldots$. The logical basis is often also called the ``computational'' basis, or sometimes, the ``classical'' basis.

Measurement.

The process used to extract classical information from a quantum system. A general projective measurement is defined by a set of projectors $P_i$ satisfying $\sum_iP_i={\mathchoice {\rm 1\mskip-4mu l} {\rm 1\mskip-4mu l} {\rm 1\mskip-4.5mu l} {\rm 1\mskip-5mu l}}$ and $P_iP_j=\delta_{ij}P_i$. Given the quantum state $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$, the outcome of a measurement with the set $\{P_i\}_i$ is one of the classical indeces $i$ associated with a projector $P_i$. The index $i$ is the measurement outcome. The probability of outcome $i$ is $p_i=\vert P_i\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi_i}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}\vert^2$, and given outcome $i$, the quantum state ``collapses'' to $P_i\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi_i}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}/\sqrt{p_i}$.

Mixture.

A probabilistic combination of pure states of a quantum system. Mixtures can be represented without redundancy with density operators. Thus a mixture is of the form $\sum_i\lambda_i\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi_i}\mbo... ...e*{-4.3pt}\langle$}{\psi_i}\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}$, with $\lambda_i\geq 0$, $\sum_i\lambda_i=1$ being the probabilities of the states $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi_i}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$. This expression for mixtures defines the set of density operators, which can also be characterized as the set of operators $\rho$ satisfying $\mbox{tr}(\rho)=1$ and for all $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$, $\mbox{$\langle\hspace*{-4.3pt}\langle\hspace*{-4.3pt}\langle$}{\psi}\mbox{$\ver... ...ert$}{\psi}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}\geq 0$ (``positive semidefinite operator'').

Network.

In the context of information processing, a network is a sequence of gates applied to specified information units. We visualize networks by drawing horizontal lines to denote the time line of an information unit. The gates are represented by graphical elements that intercept the lines at specific points. A realization of the network requires applying the gates to the information units in the specified order (left to right).

Operator.

A function that transforms the states of a system. Operators may be restricted depending on the system's properties. For example, in talking about operators acting on quantum systems, one always assumes that they are linear.

Oracle.

An information processing operation that can be applied. A use of the oracle is called a ``query''. In the oracle model of computation, a standard model is extended to include the ability to query an oracle. Each oracle query is assumed to take one time unit. Queries can reduce the resources required for solving problems. Usually, the oracle implements a function or solves a problem not efficiently implementable by the model without the oracle. Oracle models are used to compare the power of two models of computation when the oracle can be defined for both models. For example, in 1994, D. Simon showed that quantum computers with a specific oracle ${\cal O}$ could efficiently solve a problem that had no efficient solution on classical computers with access to the classical version of ${\cal O}$. At the time, this result was considered to be the strongest evidence for an exponential gap in power between classical and quantum computers.

Overlap.

The inner product between two quantum states.

Pauli operators.

The Hermitian matrices $\sigma_x,\sigma_y,\sigma_z$ acting on qubits, which are two-level quantum systems. They are defined in Eq. 12. It is often convenient to consider the identity operator to be included in the set of Pauli operators.

Polynomial resources.

To say that an algorithm computing the function $f(x)$, where $x$ is a bit string, uses polynomial resources (in orther words, ``is efficient'') means that the number of steps required to compute $f(x)$ is bounded by $\vert x\vert^k$ for some fixed $k$. Here $\vert x\vert$ denotes the length of the bit string $x$.

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 by extending the state spaces of deterministic information to include arbitrary probability distributions over the deterministic states. This is the main type of classical information to which quantum information is compared.

Probability amplitude.

The squared norm of an amplitude with respect to a chosen orthonormal basis $\{\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{i}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}\}$. Thus, the probability amplitude is the probability with which the state $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{i}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ is measured in a complete measurement that uses this basis.

Product state.

For two quantum systems $\mathsf {A}$ and $\mathsf {B}$, product states are of the form $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\mbox{$\rangle\hspace... ...rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}_{{}_{\!\!{\mathsf {B}}}}$. Most states are not of this form.

Program.

An algorithm expressed in a language that can be understood by a particular type of computer.

Projection operator.

A linear operator $P$ on a Hilbert space that satisfies $P^2=P^\dagger P=P$. The projection onto a subspace $V$ with orthogonal complement $W$ is defined as follows: If $x\in V$ and $y\in W$, then $P(x+y)=x$.

Pseudo-code.

An semi-formal computer language that is intended to be executed by a standard ``random access machine'', which is a machine model with a central processing unit and access to a numerically indexed unbounded memory. This machine model is representative of the typical one-processor computer. Pseudo-code is similar to programming languages such as BASIC, Pascal, or C, but does not have specialized instructions for human interfaces, file management, or other ``external'' devices. Its main use is to describe algorithms and enable machine-independent analysis of the algorithms' resource usage.

Pure state.

A state of a quantum system that corresponds to a unit vector in the Hilbert space used to represent the system's state space. In the ket notation, pure states are written in the form $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{\psi}\mbox{$\rangle\hspace... ...*{-3pt}\vert$}{i}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$, where the $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{i}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ form a logical basis and $\sum_i\vert\alpha_i\vert^2=1$.

Quantum information.

The type of information obtained when the state space of deterministic information is extended by normalized superpositions of deterministic states. Formally, each deterministic state is identified with one of an orthonormal basis vector in a Hilbert space and normalized superpositions are unit-length vectors that are expressible as complex linear sums of the chosen basis vectors. It is convenient to extend this state space further by permitting probability distributions over the quantum states (see the entry for ``mixtures''). This extension is still called quantum information.

Qubit.

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

Read-out.

A method for obtaining human-readable information from the state of a computer. For quantum computers, read-out refers to a measurement process used to obtain classical information about a quantum system.

Reversible gate.

A gate whose action can be undone by a sequence of gates.

Separable state.

A mixture of product states.

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}$.

Superposition principle.

One of the defining postulates of quantum mechanics according to which if states $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{1}\mbox{$\rangle\hspace*{-... ...\vert$}{2}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$},\ldots$ are distinguishable then $\sum_i\alpha_i\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{i}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$ with $\sum_i\vert\alpha_i\vert^2=1$ is a valid quantum state. Such a linear combination is called a normalized superposition of the states $\mbox{$\vert\hspace*{-3pt}\vert\hspace*{-3pt}\vert$}{i}\mbox{$\rangle\hspace*{-4.3pt}\rangle\hspace*{-4.3pt}\rangle$}$.

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 that 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.

Unitary operator.

A linear operator $U$ on a Hilbert space that preserves the inner product. That is, $\langle Ux,Uy\rangle=\langle x,y\rangle$. If $U$ is given in matrix form, then this expression 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}}$.

Universal set of gates.

A set of gates that satisfies the requirement that every allowed operation on information units can be implemented by a network of these gates. For quantum information, it means a set of gates that can be used to implement every unitary operator. More generally, a set of gates is considered universal if for every operator $U$, there are implementable operators $V$ arbitrarily close to $U$.